模拟实现一个多线程环境

A- A+
流沙团 • • C/C++ • 4662View 0

引言

初学者或者一些有经验的开发人员，并不总是对于系统底层有清楚的了解。比如，进程（或线程）调度是如何实现的？往往只停留于模糊的认识。了解这些问题的最好途径是亲自实践。然而开发一个真实系统的门槛很高，而通过学习一个已有系统来了解也非易事，因为错综复杂的代码和关系有时把人搞糊涂了。于是学习者往往写一些模拟程序来努力表达系统是怎样运作的。不过，这些程序往往过于简单。于是“看看能否写一个模拟进程调度的软件”，从这个想法出发我尝试写一个接近真实的调度程序，因为进程或线程调度是现代操作系统的核心部分。经过一段时间的摸索一个调度程序写成了，同时写了一个简单的内存管理。接下来实现了一个模拟文件系统，差不多是按着0.11版的Linux文件系统实现的。我把这个模拟系统看作是学习和实践的一个场所，因此我主要用C++语言而不是C语言来编写，因为面向对象的方法（接口和类）更容易表达要被理解的东西。毕竟这是一个模拟程序，首要目标是帮助人学习和亲自实践，而不是以追求实现效率为先。目前这个模拟系统是在Windows平台上实现的，但它也可能在其它平台上实现。因为这个系统中只有少量与平台或硬件有关的代码，在不同平台上这部分的实现将有差异。

多线程/进程的模拟实现

线程及线程切换的概念

我们先来回顾下线程及其切换的概念。计算机通常按顺序一条一条地执行程序指令。多数处理器（CPU）通常内部借助一些寄存器来完成指令的执行，例如程序计数器（PC），指向下一条要执行的指令，其它是一些数据或状态寄存器等。另外，许多计算机支持使用堆栈（stack）来传递函数参数，存放局部变量等，因为寄存器的数量毕竟有限。通常用一个堆栈寄存器（SP）来指向当前所用的堆栈。当一段程序代码被执行的时候，处理器就处在一个状态中，这个状态可以用当前的程序计数器，堆栈指针，以及其它一些寄存器的集合来定义。如果我们把这个状态保存下来，转去执行其它代码，一段时间后再回过来，把先前保存的状态恢复，使各个寄存器恢复到以前保存的那个状态，继续执行下去，那么这一段程序的执行就好像没有被打断一样。这样一段程序的执行，就像一个独立的执行流或路径，这就是一个线程（thread）的含义了。系统中可以有许多线程，只要对每个线程都按照保存、恢复，恢复、保存来处理，就看起来像是同时各自独立运行。至于线程切换，就是把当前线程的执行状态保存起来，然后把另一个线程的已保存状态恢复过来，成为当前，这就完成切换了。

线程切换的实现

虽然我们大概明白线程及其切换的原理，但编写代码实现出来是最重要的。在寻求实现的过程中，我曾担心一件事：线程切换的实现，是否离不开特殊硬件指令的支持？恐怕是特权指令。我看到一篇网友的文章，他在用户程序中给出了从一个函数切换到另一个函数的例子，他的函数相当于线程函数。因此我参照他的代码在Windows平台上实现了。我用的开发工具为vs2008，为了完成线程切换，需要嵌入Intel汇编指令。

线程切换实现代码

[cpp] view plain copy
  1. void threadSwitch(int *pCurrentESP, int *pCurrentEIP, int nextESP, int nextEIP)  
  2. {  
  3.     __asm  
  4.     {  
  5.         push eax  
  6.         push ebx  
  7.         push ecx  
  8.         push edx  
  9.         push esi  
  10.         push edi  
  11.         push ebp  
  12.         //save ESP  
  13.         mov ebx,esp  
  14.         mov eax,[pCurrentESP]  
  15.         mov [eax],ebx  
  16.         //restore ESP  
  17.         mov eax,nextESP  
  18.         mov esp,eax  
  19.         //Save EIP  
  20.         lea ebx, _RECOVER_  
  21.         mov eax, [pCurrentEIP]  
  22.         mov [eax],ebx  
  23.         //Restore EIP  
  24.         mov eax, nextEIP  
  25.         push eax  
  26.         ret  
  27. _RECOVER_:  
  28.         pop ebp  
  29.         pop edi  
  30.         pop esi  
  31.         pop edx  
  32.         pop ecx  
  33.         pop ebx  
  34.         pop eax  
  35.     }  
  36. }  


我们来分析这段代码如何完成切换的。pCurrentESP指向一个地址，用来存放当前线程的堆栈指针。pCurrentEIP也指向一个地址，用来存放当前线程的下一条指令地址。nextESP和nextEIP分别是将要切换过去的线程（简称下一个线程）的堆栈指针和下一条指令地址。切换的目标是把当前执行环境保存起来，并把下一个线程环境恢复成为当前。首先从push eax到push ebp是把一些通用寄存器保存到当前堆栈中 - 这个堆栈通常就属于这个线程。接下来保存当前线程的ESP，即堆栈指针，保存到pCurrentESP指向的地方 - 通常位于线程的内部数据结构中。后面又把当前线程的下一条指令地址保存起来，通常也是保存到线程内部数据结构中。请注意，下一条指令指向哪里？指向的是_RECOVER_标号处。这样，当以后再切回这个线程时，将执行_RECOVER_标号处代码，这部分代码所作的正是从堆栈中弹出和恢复那些通用寄存器的内容，这样就恢复到这个线程切换前的状态了。现在来看对下一个线程执行环境的恢复。首先是恢复堆栈指针，即把nextESP的内容赋给ESP寄存器，接下来恢复指令计数器EIP。由于EIP不能直接修改，这里利用堆栈并ret指令达到间接改变EIP的目的。这样就跳到下一个线程执行去了（如果此线程也调用这里的切换代码或者类似代码，可能马上就从堆栈中恢复那些通用寄存器，如前面所分析的），下一个线程成为新的当前线程。

我很高兴在上述线程切换的实现中，并未依赖于特殊硬件指令。这部分代码在所在平台下经过测试，证明可以工作。于是，我们在用户程序空间里实现了线程切换，因为模拟程序通常作为宿主机系统上的一个用户进程来运行。当前的实现，是Windows上的一个用户进程。

一个细节：上述切换代码，我定义成一个函数供调用，而不是使用宏（如linux的switch_to宏）。这个函数形式也是可行的。几个参数pCurrentESP，pCurrentEIP，nextESP，nextEIP是该函数的局部变量。C汇编代码对局部变量的访问是通过EBP寄存器。注意切换过程中虽然堆栈指针ESP被改变，但EBP并未改变，因此对这几个局部变量的访问总是有效的。

线程/进程管理类（接口）

线程切换实现之后，其它如线程的内部数据结构，线程调度等相对来说比较容易了。我打算把线程和进程的有关功能放到一个类中。为了清晰，先定义一个线程/进程的管理接口。我也决定在这个模拟系统中，以线程为基本调度单元。一个进程可以有一个或多个线程，其中有一个线程为主线程（主线程若结束，这个进程就要销毁了）。下面是线程/进程管理类接口，其中的接口函数都定义为纯虚函数。

线程/进程管理接口

[cpp] view plain copy
  1. typedef int (*THREAD_PROC)(void *parameter);  
  2.   
  3. class ProcessManager  
  4. {  
  5. public:  
  6. //创建一个进程和其主线程。成功返回该进程的id（进程范围内唯一，大于0），失败返回0。  
  7. //主线程和其它线程的区别是，主线程运行结束，进程就终止，属于该进程的所有线程都释放。  
  8. virtual int createProcess(THREAD_PROC mainThreadProc, void *parameter,   
  9.                 int stackSizeInKB=1024, bool readyToRun=true) = 0;  
  10.   
  11. //创建一个线程。成功返回该线程的id（线程范围内唯一，大于0），失败返回0。  
  12. //为了简化编程，约定线程id从1开始顺序编号（0为系统空闲线程所用）。  
  13. virtual int createThread(THREAD_PROC threadProc, void *parameter,   
  14.                 int stackSizeInKB=1024, bool readyToRun=true) = 0;  
  15. //进程/线程调度。  
  16. //对于合作式的线程调度，需要每个线程主动调用调度函数，让其它线程有机会执行。  
  17. virtual void schedule() = 0;  
  18. //获取当前进程的id。  
  19. virtual int getCurrentProcessId() = 0;  
  20. //获取当前线程的id。  
  21. virtual int getCurrentThreadId() = 0;  
  22. //获取进程的当前工作路径  
  23. virtual const char *getCurrentDir() = 0;  
  24. //设置进程的当前工作目录  
  25. virtual void setCurrentDir(const char *pathname) = 0;  
  26. //使当前线程睡眠指定的毫秒数  
  27. virtual void sleep(int msecs) = 0;  
  28. //获取锁，成功将拥有这个锁（如果之前已获取这个锁，将增加引用计数）。  
  29. //如果锁已经被其它线程拥有，调用线程将阻塞。  
  30. //一个锁可以被同一线程多次获取，但释放也要匹配相同的次数，否则其它线程不能获取它  
  31. virtual void lock(long lock) = 0;  
  32. //尝试获取锁，成功将拥有这个锁。如果锁已经被其它线程拥有，立即返回false  
  33. virtual bool trylock(long lock) = 0;  
  34. //释放锁  
  35. virtual void unlock(long lock) = 0;  
  36. };  


这个线程/进程管理接口最主要的就是支持线程的创建，进程的创建，以及调度。在这里调度的基本含义是指线程调度，因为线程已作为基本调度单位。

对这个接口类需要作些说明。THREAD_PROC是线程函数的原型定义。schedule()是调度函数。为何要把调度函数公开出来呢？因为这个模拟系统目前只支持共享方式的调度。也就是说，这个系统中的每个线程需要主动放弃控制权，好让其它线程有机会运行。假如有个线程不释放控制权，从来不调用schedule()，它就一直独占系统，以致其它线程没有机会执行。此种情况类似一些早期的系统，例如早期Windows系统。如果要实现抢先式调度，就要接管中断和中断处理，因为中断能打断当前程序（线程）的执行，在中断处理函数中可以实现调度。模拟程序目前没有寻到一个方法来支持抢先式调度。createProcess是支持创建进程的接口函数，目前它是简单原始的。我们还未实现从磁盘可执行文件加载和创建进程。至于sleep和线程锁，放在这里主要是展示对于线程调度技术的运用。

线程/进程管理类的实现

我通常会先选择一种简单的实现。如果时间允许，或者有了想法，再去改进或写各种变化的实现。这样的做法是常见的。这个模拟系统，适合作为一个学习和练习的场所。

所用到的一些结构

[cpp] view plain copy
  1. //存放进程相关信息的结构  
  2. class ProcessInternalInfo  
  3. {  
  4. public:  
  5.     int processId;  
  6.     char currentDir[300];  
  7.     ProcessInternalInfo();  
  8. };  
  9.   
  10. //存放线程相关信息的结构  
  11. class ThreadInternalInfo  
  12. {  
  13. public:  
  14.     //线程id及线程所属的进程id  
  15.     int processId;  
  16.     int threadId;  
  17.     //线程切换时对现场的保存和恢复，主要是栈顶指针(esp)和指令计数器(eip)  
  18.     int esp;  
  19.     int eip;  
  20.     //线程所使用的用户栈及其大小  
  21.     char *stackBase;  
  22.     int stackSize;    //字节  
  23.     //线程函数及其参数  
  24.     THREAD_PROC threadProc;  
  25.     void *parameter;  
  26.     //是否进程的主线程  
  27.     bool isMainThread;  
  28.     //错误代码  
  29.     int error;  
  30.     ThreadInternalInfo();  
  31. };  
  32.   
  33. //内部堆栈，内部堆栈应该很小，因为只有thread wrapper function才用到  
  34. struct InternalStack  
  35. {  
  36.     char stack[4*1024];  
  37. };  
  38.   
  39. //锁的实现结构  
  40. class Thread_Lock  
  41. {  
  42. public:  
  43.     long lock;  
  44.     int threadIndex;  
  45.     int refCount;  
  46.     Thread_Lock()  
  47.     {  
  48.         lock = 0;  
  49.         threadIndex = -1;  
  50.         refCount = 0;  
  51.     }  
  52. };  
  53.   
  54. class Thread_Wait  
  55. {  
  56. public:  
  57.     int threadIndex;  
  58.     long lock;  
  59.     Thread_Wait()  
  60.     {  
  61.         threadIndex = -1;  
  62.         lock = 0;  
  63.     }  
  64. };  


管理实现类的定义

[cpp] view plain copy
  1. class ProcessManagerImpl : public ProcessManager  
  2. {  
  3. public:  
  4. ProcessManagerImpl();  
  5. virtual ~ProcessManagerImpl();  
  6. //初始化  
  7. bool initManageData();  
  8.   
  9. virtual int createProcess(THREAD_PROC mainThreadProc, void *parameter,   
  10.             int stackSizeInKB=1024, bool readyToRun=true);  
  11. virtual int createThread(THREAD_PROC threadProc, void *parameter,   
  12.             int stackSizeInKB=1024, bool readyToRun=true);  
  13. virtual void schedule();  
  14. virtual int getCurrentProcessId();  
  15. virtual int getCurrentThreadId();  
  16. virtual const char *getCurrentDir();  
  17. virtual void setCurrentDir(const char *pathname);  
  18. virtual void sleep(int msecs);  
  19. virtual void lock(long lock);  
  20. virtual bool trylock(long lock);  
  21. virtual void unlock(long lock);  
  22.   
  23. //运行第一个进程，进程id为0。使用程序当前的堆栈。  
  24. int runProcess0(THREAD_PROC threadProc, void *parameter);  
  25. void setError(int error);  
  26. int getError();  
  27.   
  28. protected:  
  29. //这里采用数组和索引管理所有进程/线程  
  30. ProcessInternalInfo *_pProcessInfo;  
  31. ThreadInternalInfo *_pThreadInfo;  
  32. //指向就绪线程队列  
  33. int *_pThreadReady;  
  34. //指向阻塞线程队列  
  35. int *_pThreadBlock;  
  36. //为每个线程分配一个内部栈。因为用户线程函数结束后，用户栈将被删除，  
  37. //thread wrapper function不能依靠用户栈工作  
  38. InternalStack *_pInternalStack;  
  39.   
  40. protected:  
  41. //释放相关资源  
  42. void freeManageData();  
  43. //查找未用的进程槽，返回索引。未找到返回-1。  
  44. int find_free_process();  
  45. //查找未用的线程槽，返回索引。未找到返回-1。  
  46. int find_free_thread();  
  47. //加入到就绪线程队列  
  48. void addThreadReady(int threadIndex);  
  49. //加入到阻塞线程队列  
  50. void addThreadBlock(int threadIndex);  
  51. //创建线程  
  52. int create_thread(int processId, bool isMainThread, THREAD_PROC threadProc,   
  53.                  void *parameter, int stackSizeInKB, bool readyToRun);  
  54. //thread wrapper function  
  55. //用户线程结束时要释放堆栈，并从调度队列中删除，所以需要一个对用户线程函数的包装  
  56. static void thread_wrapper_func(ProcessManagerImpl *pImpl, int threadIndex);  
  57. //从就绪线程队列中删除  
  58. void removeReadyThread(int threadIndex);  
  59. //从阻塞线程队列中删除  
  60. void removeBlockThread(int threadIndex);  
  61. //删除一个线程（重置对应的线程槽）  
  62. void removeThread(int threadIndex);  
  63. //删除一个进程（重置对应的进程槽）  
  64. void removeProcess(int processIndex);  
  65. //线程切换  
  66. void threadSwitch(int *pCurrentESP, int *pCurrentEIP, int nextESP, int nextEIP);  
  67. //系统死机 - 通常由于内部错误导致无法处理的情况，就进入这里  
  68. void system_dead();  
  69. //使当前线程睡眠，放入阻塞队列，然后切换到下一个线程  
  70. void block();  
  71. //唤醒一个线程，即从阻塞队列移除，放到就绪队列  
  72. void wakeUp(int threadIndex);  
  73.   
  74. protected:  
  75. //对sleep的支持  
  76. //所有由于调用sleep函数导致睡眠的，超时时间记录在这里，单位毫秒。  
  77. int *_pThreadSleepTimeout;  
  78. //检查看是否有线程的睡眠时间到了，把所有这样的线程唤醒  
  79. void checkSleepTimeout();  
  80.   
  81. //对锁的支持  
  82. Thread_Lock *_pThreadLock;    //存放锁的数组  
  83. int _threadLockCount;  
  84. Thread_Wait *_pThreadWait;    //等待锁的线程  
  85. int _threadWaitCount;  
  86. //查找锁，若找到返回在数组中的索引，未找到返回-1。  
  87. int findLock(long lock);  
  88. void removeLockByIndex(int lockIndex);  
  89. void addWait(int threadIndex, long lock);  
  90. //查找等待给定锁的线程，若找到，从等待中删除并返回线程号；若未找到返回-1。  
  91. int removeWait(long lock);  
  92.   
  93. //对阻塞式文件读写的支持  
  94. //线程由于等待事件而睡眠的，等待的事件存放在下面的数组中  
  95. HANDLE *_pThreadEvent;  
  96. //线程等待事件，可能进入睡眠，直到事件变为信号状态而被唤醒  
  97. void waitEvent(HANDLE hEvent);  
  98. //检查所有的等待事件，把这样的线程唤醒  
  99. void checkThreadEvent();  
  100. void removeThreadEvent(int threadIndex);  
  101. friend class BlockedFileDisk;  
  102. };  


在这个实现中，我使用了一个数组来存放所有的进程对象（_pProcessInfo所指）。一个数组来存放所有的线程对象（pThreadInfo所指）。线程会阻塞或者就绪，_pThreadReady指向就绪队列，pThreadBlock指向阻塞队列。这两个队列的元素存的是线程对象索引。使用这个线程/进程管理类之前，先要把这些数据初始化，这通过调用initManageData()来达到。

构造和初始化

[cpp] view plain copy
  1. #define MAX_PROCESS_NUM    1024  
  2. #define MAX_THREAD_NUM    2048  
  3. #define MAX_LOCK_NUM    200  
  4.   
  5. ProcessInternalInfo::ProcessInternalInfo()  
  6. {  
  7.     processId = -1;    //有效的进程id从0开始  
  8.     memset(currentDir, 0 ,sizeof(currentDir));  
  9.     strcpy(currentDir, "/");  
  10. }  
  11.   
  12. ThreadInternalInfo::ThreadInternalInfo()  
  13. {  
  14.     processId = -1;  
  15.     threadId = -1;    //有效的线程id从0开始  
  16.     esp = 0;  
  17.     eip = 0;  
  18.     stackBase = NULL;  
  19.     stackSize = 0;  
  20.     threadProc = NULL;  
  21.     parameter = NULL;  
  22. isMainThread = false;  
  23.     error = 0;  
  24. }  
  25.   
  26. ProcessManagerImpl::ProcessManagerImpl()  
  27. {  
  28.     //改为明确调用  
  29.     //initManageData();  
  30. }  
  31.   
  32. ProcessManagerImpl::~ProcessManagerImpl()  
  33. {  
  34.     freeManageData();  
  35. }  
  36.   
  37. bool ProcessManagerImpl::initManageData()  
  38. {  
  39.     _pProcessInfo = new ProcessInternalInfo [MAX_PROCESS_NUM];  
  40.     if (!_pProcessInfo) return false;  
  41.     _pThreadInfo = new ThreadInternalInfo [MAX_THREAD_NUM];  
  42.     if (!_pThreadInfo) return false;  
  43.     _pThreadReady = new int [MAX_THREAD_NUM];  
  44.     if (!_pThreadReady) return false;  
  45.     for (int i = 0; i < MAX_THREAD_NUM; i++) _pThreadReady[i] = -1;  
  46.     _pThreadBlock = new int [MAX_THREAD_NUM];  
  47.     if (!_pThreadBlock) return false;  
  48.     for (int i = 0; i < MAX_THREAD_NUM; i++) _pThreadBlock[i] = -1;  
  49.     _pInternalStack = new InternalStack [MAX_THREAD_NUM];  
  50.     if (!_pInternalStack) return false;  
  51.     _pThreadSleepTimeout = new int [MAX_THREAD_NUM];  
  52.     if (!_pThreadSleepTimeout) return false;  
  53.     for (int i = 0; i < MAX_THREAD_NUM; i++) _pThreadSleepTimeout[i] = -1;  
  54.     _pThreadLock = new Thread_Lock [MAX_LOCK_NUM];  
  55.     if (!_pThreadLock) return false;  
  56.     _threadLockCount = 0;  
  57.     _pThreadWait = new Thread_Wait [MAX_THREAD_NUM];  
  58.     if (!_pThreadWait) return false;  
  59. _threadWaitCount = 0;  
  60.     _pThreadEvent = new HANDLE [MAX_THREAD_NUM];  
  61.     if (!_pThreadEvent) return false;  
  62.     for (int i = 0; i < MAX_THREAD_NUM; i++) _pThreadEvent[i] = INVALID_HANDLE_VALUE;  
  63.     return true;  
  64. }  
  65.   
  66. void ProcessManagerImpl::freeManageData()  
  67. {  
  68.     delete [] _pThreadEvent;  
  69.     delete [] _pThreadWait;  
  70.     delete [] _pThreadLock;  
  71.     delete [] _pThreadSleepTimeout;  
  72.     delete [] _pInternalStack;  
  73.     delete [] _pThreadBlock;  
  74.     delete [] _pThreadReady;  
  75.     delete [] _pThreadInfo;  
  76.     delete [] _pProcessInfo;  
  77. }  


l 创建进程（createProcess）

进程创建实现

[cpp] view plain copy
  1. int ProcessManagerImpl::createProcess(THREAD_PROC mainThreadProc, void *parameter,   
  2.                         int stackSizeInKB, bool readyToRun)  
  3. {  
  4.     int freeProcessIndex = find_free_process();  
  5.     if (freeProcessIndex == -1)  
  6.         return 0;  
  7.     ProcessInternalInfo processInfo;  
  8.     processInfo.processId = freeProcessIndex;  
  9.     int threadIndex = create_thread(freeProcessIndex, true, mainThreadProc,   
  10.                         parameter, stackSizeInKB, readyToRun);  
  11.     if (threadIndex == 0)  
  12.         return 0;  
  13.     _pProcessInfo[freeProcessIndex] = processInfo;  
  14.     return freeProcessIndex;  
  15. }  


目前对进程的支持比较简单。这不是一个完整的进程创建过程，因为它假定进程的程序代码已经在内存中了。首先find_free_process查找进程数组，找到一个空闲槽，接着创建这个进程的主线程，成功地话就占用那个进程槽。这样一个进程就算建立了。如果此进程打算使用多个线程，它可以调用createThread创建其它线程。

l 创建线程（createThread）

线程创建实现

[cpp] view plain copy
  1. int ProcessManagerImpl::createThread(THREAD_PROC threadProc, void *parameter,   
  2.                     int stackSizeInKB, bool readyToRun)  
  3. {  
  4.     int processId = getCurrentProcessId();  
  5.     return create_thread(processId, false, threadProc,   
  6. parameter, stackSizeInKB, readyToRun);  
  7. }  
  8.   
  9. int ProcessManagerImpl::create_thread(int processId, bool isMainThread,   
  10. THREAD_PROC threadProc, void *parameter, int stackSizeInKB, bool readyToRun)  
  11. {  
  12.     if (stackSizeInKB < 0)  
  13.         return 0;  
  14.     if (stackSizeInKB == 0)  
  15.         stackSizeInKB = 1024;  
  16.     int freeThreadIndex = find_free_thread();  
  17.     if (freeThreadIndex == -1)  
  18.         return 0;  
  19.     //申请用户栈空间  
  20.     int stackSizeInByte = stackSizeInKB * 1024;  
  21.     char *pStack = new char [stackSizeInByte];  
  22.     //char *pStack = (char *)GetMemoryManager()->alloc(stackSizeInByte);  
  23.     if (pStack == NULL)  
  24.         return 0;  
  25.     ThreadInternalInfo threadInfo;  
  26.     threadInfo.processId = processId;  
  27.     threadInfo.threadId = freeThreadIndex;  
  28.     threadInfo.stackBase = pStack;  
  29.     threadInfo.stackSize = stackSizeInByte;  
  30.     threadInfo.threadProc = threadProc;  
  31.     threadInfo.parameter = parameter;  
  32.     threadInfo.isMainThread = isMainThread;  
  33.     //准备线程初始的esp和eip，eip指向线程wrapper函数的入口地址, esp指向内部栈  
  34.     //由于线程wrapper函数需要两个参数，按照C调用约定，从右到左把这两个参数压入栈，  
  35.     //另外函数返回地址也要占去4个字节，故esp为栈顶减去12个字节。  
  36.     void (*thread_wrapper_func_ptr)(ProcessManagerImpl *, int);  
  37.     thread_wrapper_func_ptr = &thread_wrapper_func;  
  38.     threadInfo.eip = (int)thread_wrapper_func_ptr;  
  39.     threadInfo.esp = (int)(_pInternalStack[freeThreadIndex].stack   
  40.                 + sizeof(_pInternalStack[freeThreadIndex].stack) - 12);  
  41.     ProcessManagerImpl **ppImpl = (ProcessManagerImpl **)(threadInfo.esp + 4);  
  42.     *ppImpl = this;  
  43.     int *pInt = (int *)(threadInfo.esp + 8);  
  44.     *pInt = freeThreadIndex;  
  45.   
  46.     _pThreadInfo[freeThreadIndex] = threadInfo;  
  47.     //新线程加入就绪队列  
  48.     if (readyToRun)  
  49.         addThreadReady(freeThreadIndex);  
  50.     else  
  51.         addThreadBlock(freeThreadIndex);  
  52.     return freeThreadIndex;  
  53. }  


创建线程的主要工作在create_thread()中完成。基本过程是：找到一个空闲线程槽，创建用户堆栈，初始化线程数据结构。线程数据结构中特别需要说明的是eip和esp的初始赋值：eip指向线程的入口代码，esp指向线程的堆栈。当调度运行这个线程时，就将跳到eip所指向的地址，同时将堆栈寄存器设置为esp的值。那么eip和esp的初始值分别是什么呢？一个自然的想法是：eip指向用户线程函数threadProc，esp指向用户堆栈。但这样的话，线程运行结束后，线程所用的资源（例如用户堆栈）在哪里释放呢？它既然运行结束，就应该把控制权转移给其它线程，在哪里把控制权转移呢？思考这些问题的结果是：需要一个线程包装函数，在用户线程函数的前后做这些工作。当线程运行结束后，用户堆栈将被释放，因此我使用线程的一个内部堆栈，在内部堆栈上做这些收尾工作。内部堆栈通常1K到4K就够了。如此看来，eip应该指向用户线程函数的包装函数，esp指向线程内部栈。

线程包装函数

[cpp] view plain copy
  1. //thread wrapper function  
  2. //用户线程结束时要释放堆栈，并从调度队列中删除，所以需要一个对用户线程函数的包装  
  3. //注意：由于内部堆栈很小，要小心，建议不要调用什么C库函数，例如printf  
  4. void ProcessManagerImpl::thread_wrapper_func(ProcessManagerImpl *pImpl,   
  5.                                              int threadIndex)  
  6. {  
  7.     ThreadInternalInfo threadInfo = pImpl->_pThreadInfo[threadIndex];  
  8.     THREAD_PROC threadProc = threadInfo.threadProc;  
  9.     void *parameter = threadInfo.parameter;  
  10.     int userESP = (int)(threadInfo.stackBase + threadInfo.stackSize);  
  11.     int oldESP;  
  12.     //接下来切换到用户堆栈  
  13.     __asm  
  14.     {  
  15.         mov eax,esp  
  16.         mov oldESP,eax  
  17.         mov eax,userESP  
  18.         mov esp,eax  
  19.     }  
  20.     //执行用户线程函数  
  21.     threadProc(parameter);  
  22.     //函数调用完成之后，通常ebp是不会改变，对局部变量的访问仍然有效  
  23.     //恢复到内部堆栈  
  24.     _asm  
  25.     {  
  26.         mov eax,oldESP  
  27.         mov esp,eax  
  28.     }  
  29.   
  30.     //线程函数执行完毕，从就绪队列中移去，从线程队列中也移去  
  31.     pImpl->removeReadyThread(threadIndex);  
  32.     pImpl->removeThread(threadIndex);  
  33.     //如果是主线程，则释放该进程的一切资源，包括属于该进程的所有线程  
  34.     if (threadInfo.isMainThread)  
  35.     {  
  36.         int processId = threadInfo.processId;  
  37.         for (int i = 0; i < MAX_THREAD_NUM; i++)  
  38.         {  
  39.             if (pImpl->_pThreadInfo[i].processId == processId)  
  40.             {  
  41.                 //将该线程从阻塞或是就绪就列中删除  
  42.                 pImpl->removeReadyThread(i);  
  43.                 pImpl->removeBlockThread(i);  
  44.                 pImpl->removeThreadEvent(i);  
  45.                 pImpl->removeThread(i);  
  46.             }  
  47.         }  
  48.         pImpl->removeProcess(processId);  
  49.     }  
  50.     //找到下一个就绪线程，成为当前并切过去  
  51.     //如果有线程由于调用sleep进入休眠的，检查和唤醒之  
  52. pImpl->checkSleepTimeout();      
  53.     pImpl->checkThreadEvent();  
  54.     int currentThreadIndex = pImpl->_pThreadReady[0];  
  55.     if (currentThreadIndex != -1)  
  56.     {  
  57.         int currentESP = pImpl->_pThreadInfo[currentThreadIndex].esp;  
  58.         int currentEIP = pImpl->_pThreadInfo[currentThreadIndex].eip;  
  59.         //切过去  
  60.         __asm  
  61.         {  
  62.             //restore ESP  
  63.             mov eax,currentESP  
  64.             mov esp,eax  
  65.             //Restore EIP  
  66.             mov eax,currentEIP  
  67.             push eax  
  68.             ret  
  69.         }  
  70.     } else  
  71.     {    //就绪队列为空，这应该不会发生，因为Process0总会存在  
  72.         pImpl->system_dead();  
  73.     }  
  74. }  


在这个线程包装函数中，需要注意的一点，就是执行用户线程函数threadProc前后堆栈的改变。执行threadProc前堆栈改为用户堆栈，执行threadProc后堆栈恢复为内部堆栈。接下来对这个线程资源的释放都在内部堆栈上进行。

l 调度函数（schedule）

调度函数实现

[cpp] view plain copy
  1. void ProcessManagerImpl::schedule()  
  2. {  
  3.     //由于线程需要主动让出CPU，让其它线程有机会执行，故在调度上按均等机会处理  
  4.     //做法是：查找下一个就绪线程，把它提为当前线程，原来的线程移到就绪队列末尾  
  5.     //如果没有下一个就绪线程，则立即返回，继续执行当前线程  
  6.   
  7.     //如果有线程由于调用sleep进入休眠的，检查和唤醒之  
  8.     checkSleepTimeout();  
  9.     checkThreadEvent();  
  10.     int currentThreadIndex = _pThreadReady[0];  
  11.     int nextThreadIndex = _pThreadReady[1];  
  12.     if (nextThreadIndex == -1)  
  13.         return;  
  14.   
  15.     //下一个就绪线程提为当前  
  16.     int i;  
  17.     for (i = 1; i < MAX_THREAD_NUM; i++)  
  18.     {  
  19.         if (_pThreadReady[i] != -1)   
  20.             _pThreadReady[i-1] = _pThreadReady[i];  
  21.         else  
  22.             break;  
  23.     }  
  24.     _pThreadReady[i-1] = currentThreadIndex;  
  25.       
  26.     //准备切换，切换时主要保存EBP（栈帧指针）、ESP（当前栈指针）和EIP（指令计数器），  
  27.     //并要修改ESP和EIP，对ESP的修改，不影响对于局部变量的访问（因为是通过EBP进行的）  
  28.     int *pCurrentESP = &(_pThreadInfo[currentThreadIndex].esp);  
  29.     int *pCurrentEIP = &(_pThreadInfo[currentThreadIndex].eip);  
  30.     int nextESP = _pThreadInfo[nextThreadIndex].esp;  
  31.     int nextEIP = _pThreadInfo[nextThreadIndex].eip;  
  32.     threadSwitch(pCurrentESP,pCurrentEIP,nextESP,nextEIP);  
  33. }  


就绪线程队列的首个元素（下标为0），就指向当前线程。由于这个模拟系统是共享式调度，所以简单地采用顺序调度的方式切到下一个线程，原先的线程就移到就绪队列的末尾。完成切换的代码就是前面我们介绍过的threadSwitch函数。也可以实现其它调度算法，例如如果线程有优先级，可以实现基于优先级的调度算法。

l 其它函数

下面列出了线程/进程管理类的一些其它函数，其中多数是辅助实现函数。

一些其它函数

[cpp] view plain copy
  1. //获取当前进程的id。  
  2. int ProcessManagerImpl::getCurrentProcessId()  
  3. {  
  4.     int currentThreadIndex = _pThreadReady[0];  
  5.     return _pThreadInfo[currentThreadIndex].processId;  
  6. }  
  7. //获取当前线程的id。  
  8. int ProcessManagerImpl::getCurrentThreadId()  
  9. {  
  10.     int currentThreadIndex = _pThreadReady[0];  
  11.     return currentThreadIndex;  
  12. }  
  13. //获取进程的当前工作路径  
  14. const char *ProcessManagerImpl::getCurrentDir()  
  15. {  
  16.     int processIndex = getCurrentProcessId();  
  17.     return _pProcessInfo[processIndex].currentDir;  
  18. }  
  19. //设置进程的当前工作目录  
  20. void ProcessManagerImpl::setCurrentDir(const char *pathname)  
  21. {  
  22.     int processIndex = getCurrentProcessId();  
  23.     ProcessInternalInfo *process = _pProcessInfo + processIndex;  
  24.     strncpy(process->currentDir, pathname, sizeof(process->currentDir)-1);  
  25. }  
  26. //查找未用的进程槽，返回索引。未找到返回-1。  
  27. int ProcessManagerImpl::find_free_process()  
  28. {  
  29.     for (int i = 0; i < MAX_PROCESS_NUM; i++)  
  30.     {  
  31.         ProcessInternalInfo processInfo = _pProcessInfo[i];  
  32.         if (processInfo.processId == -1)   
  33.             return i;  
  34.     }  
  35.     return -1;  
  36. }  
  37. //查找未用的线程槽，返回索引。未找到返回-1。  
  38. int ProcessManagerImpl::find_free_thread()  
  39. {  
  40.     for (int i = 0; i < MAX_THREAD_NUM; i++)  
  41.     {  
  42.         ThreadInternalInfo threadInfo = _pThreadInfo[i];  
  43.         if (threadInfo.threadId == -1)   
  44.             return i;  
  45.     }  
  46.     return -1;  
  47. }  
  48. //加入到就绪线程队列  
  49. void ProcessManagerImpl::addThreadReady(int threadIndex)  
  50. {  
  51.     for (int i = 0; i < MAX_THREAD_NUM; i++)  
  52.     {  
  53.         if (_pThreadReady[i] == -1)   
  54.         {  
  55.             _pThreadReady[i] = threadIndex;  
  56.             return;  
  57.         }  
  58.     }  
  59. }  
  60. //加入到阻塞线程队列  
  61. void ProcessManagerImpl::addThreadBlock(int threadIndex)  
  62. {  
  63.     for (int i = 0; i < MAX_THREAD_NUM; i++)  
  64.     {  
  65.         if (_pThreadBlock[i] == -1)   
  66.         {  
  67.             _pThreadBlock[i] = threadIndex;  
  68.             return;  
  69.         }  
  70.     }  
  71. }  
  72. //从就绪线程队列中删除  
  73. void ProcessManagerImpl::removeReadyThread(int threadIndex)  
  74. {  
  75.     for (int i = 0; i < MAX_THREAD_NUM; i++)  
  76.     {  
  77.         if (_pThreadReady[i] == threadIndex)  
  78.         {  
  79.             int k;  
  80.             for (k = i; k < MAX_THREAD_NUM-1; k++)  
  81.             {  
  82.                 _pThreadReady[k] = _pThreadReady[k+1];  
  83.             }  
  84.             _pThreadReady[k]=-1;  
  85.             break;  
  86.         }  
  87.     }  
  88. }  
  89. //从阻塞线程队列中删除  
  90. void ProcessManagerImpl::removeBlockThread(int threadIndex)  
  91. {  
  92.     for (int i = 0; i < MAX_THREAD_NUM; i++)  
  93.     {  
  94.         if (_pThreadBlock[i] == threadIndex)  
  95.         {  
  96.             int k;  
  97.             for (k = i; k < MAX_THREAD_NUM-1; k++)  
  98.             {  
  99.                 _pThreadBlock[k] = _pThreadBlock[k+1];  
  100.             }  
  101.             _pThreadBlock[k]=-1;  
  102.             break;  
  103.         }  
  104.     }  
  105. }  
  106. //删除一个线程（重置对应的线程槽）  
  107. void ProcessManagerImpl::removeThread(int threadIndex)  
  108. {  
  109.     //释放线程的堆栈  
  110.     char *pStack = _pThreadInfo[threadIndex].stackBase;  
  111.     delete [] pStack;  
  112.     //GetMemoryManager()->free(pStack);  
  113.     //线程槽数据复位，相当于删除了这个线程  
  114.     ThreadInternalInfo threadInfo;  
  115.     _pThreadInfo[threadIndex] = threadInfo;  
  116. }  
  117. //删除一个进程（重置对应的进程槽）  
  118. void ProcessManagerImpl::removeProcess(int processIndex)  
  119. {  
  120.     ProcessInternalInfo processInfo;  
  121.     _pProcessInfo[processIndex] = processInfo;  
  122. }  
  123. //系统死机 - 通常由于内部错误导致无法处理的情况，就进入这里  
  124. void ProcessManagerImpl::system_dead()  
  125. {  
  126.     //这里的打印有待改进，因为可能在内部栈上调用，内部栈不够printf使用...  
  127.     printf("\nSorry, system is dead");  
  128.     for (;;) ;  
  129. }  
  130. //线程等待事件，可能进入睡眠，直到事件变为信号状态而被唤醒  
  131. void ProcessManagerImpl::waitEvent(HANDLE hEvent)  
  132. {  
  133.     int teststate = WaitForSingleObject(hEvent, 0);  
  134.     if (teststate == WAIT_FAILED)   //出错，可能句柄无效  
  135.         return;  
  136.     if (teststate == WAIT_OBJECT_0) //已经是有信号状态  
  137.         return;  
  138.     int currentThreadIndex = _pThreadReady[0];  
  139.     _pThreadEvent[currentThreadIndex] = hEvent;  
  140.     block();  
  141. }  
  142. //检查所有的等待事件，把这样的线程唤醒  
  143. void ProcessManagerImpl::checkThreadEvent()  
  144. {  
  145.     for (int i = 0; i < MAX_THREAD_NUM; i++)  
  146.     {  
  147.         HANDLE hEvent = _pThreadEvent[i];  
  148.         if (hEvent != INVALID_HANDLE_VALUE)  
  149.         {  
  150.             int teststate = WaitForSingleObject(hEvent,0);  
  151.             if (teststate == WAIT_OBJECT_0)  
  152.             {  
  153.                 wakeUp(i);  
  154.                 _pThreadEvent[i] = INVALID_HANDLE_VALUE;    //清除事件  
  155.             }  
  156.         }  
  157.     }  
  158. }  
  159. void ProcessManagerImpl::removeThreadEvent(int threadIndex)  
  160. {  
  161.     _pThreadEvent[threadIndex] = INVALID_HANDLE_VALUE;  
  162. }  
  163. //使当前线程睡眠，放入阻塞队列，然后切换到下一个线程  
  164. void ProcessManagerImpl::block()  
  165. {  
  166.     int currentThreadIndex = _pThreadReady[0];  
  167.     int nextThreadIndex = _pThreadReady[1];  
  168.     if (nextThreadIndex != -1)  
  169.     {  
  170.         removeReadyThread(currentThreadIndex);  
  171.         addThreadBlock(currentThreadIndex);  
  172.         //切换到下一个线程（成为当前）  
  173.         int *pCurrentESP = &(_pThreadInfo[currentThreadIndex].esp);  
  174.         int *pCurrentEIP = &(_pThreadInfo[currentThreadIndex].eip);  
  175.         int nextESP = _pThreadInfo[nextThreadIndex].esp;  
  176.         int nextEIP = _pThreadInfo[nextThreadIndex].eip;  
  177.         threadSwitch(pCurrentESP,pCurrentEIP,nextESP,nextEIP);  
  178.     }  
  179.     else  
  180.     {  
  181.         //没有下一个可调度的线程，这种情况应该不会发生，  
  182.         //因为process0总是存在，而且process0也不能调用导致阻塞的函数  
  183.         system_dead();  
  184.     }  
  185. }  
  186. //唤醒一个线程，即从阻塞队列移除，放到就绪队列  
  187. void ProcessManagerImpl::wakeUp(int threadIndex)  
  188. {  
  189.     removeBlockThread(threadIndex);  
  190.     addThreadReady(threadIndex);  
  191. }  
  192. //如果模拟系统还没有起来，就设置/获取错误代码，错误代码放在这里  
  193. static int _error;  
  194.   
  195. //设置错误代码（最近一次系统调用）  
  196. //一些系统调用（如文件系统调用）出错时需要设置错误代码，使用户得知具体错误原因。  
  197. void ProcessManagerImpl::setError(int error)  
  198. {  
  199.     int currentThreadIndex = _pThreadReady[0];  
  200.     if (currentThreadIndex != -1)  
  201.         _pThreadInfo[currentThreadIndex].error = error;  
  202.     else  
  203.         _error = error;  
  204. }  
  205. //取得错误代码  
  206. int ProcessManagerImpl::getError()  
  207. {  
  208.     int currentThreadIndex = _pThreadReady[0];  
  209.     int error;  
  210.     if (currentThreadIndex != -1)  
  211.         error = _pThreadInfo[currentThreadIndex].error;  
  212.     else  
  213.         error = _error;  
  214.     return error;  
  215. }  


l sleep的实现

sleep是一个常见的系统调用。在多任务系统中，其基本的含义就是挂起当前的进程/线程，把控制权交还系统。过了指定的一段时间后，由系统唤醒这个进程/线程。现在我们在模拟系统中实现sleep调用。由于模拟系统的共享式调度特点，决定了sleep的实现虽然尽力，却不能保证睡眠时间的精确性。在共享方式调度下，有几个机会控制权会交还给系统。一个是线程主动调用schedule()的时候，一个是线程运行结束的时候。模拟系统只有在这不多的机会里检查系统时间，以确定是否唤醒那些调用sleep进入阻塞的线程。检查时间的函数是checkSleepTimeout()，这个函数在shcedule()和thread_wrapper_func()里都被调用了。sleep的实现：计算和设置超时时间，然后调用block()挂起当前线程，即把此线程从就绪队列移到阻塞队列，然后切换到下一个就绪线程。checkSleepTimeout()的实现：检查线程的sleep超时时间值，若已到达，调用wakeUp()将此线程唤醒，即从阻塞队列移到就绪队列。

sleep的实现

[cpp] view plain copy
  1. //使当前线程睡眠指定的毫秒数  
  2. void ProcessManagerImpl::sleep(int msecs)  
  3. {  
  4.     if (msecs <= 0)  
  5.         return;  
  6.     int sleepExpiredTickCount = GetTickCount() + msecs;  
  7.     if (sleepExpiredTickCount <= 0)  
  8.         return;  
  9.   
  10.     //把当前线程移到阻塞队列中，同时设置超时时间  
  11.     int currentThreadIndex = _pThreadReady[0];  
  12.     _pThreadSleepTimeout[currentThreadIndex] = sleepExpiredTickCount;  
  13.     block();  
  14. }  
  15.   
  16. //检查看是否有线程的睡眠时间到了，把所有这样的线程唤醒  
  17. void ProcessManagerImpl::checkSleepTimeout()  
  18. {  
  19.     DWORD dwCurrentTickCount = GetTickCount();  
  20.     for (int i = 0; i < MAX_THREAD_NUM; i++)  
  21.     {  
  22.         int sleepExpiredTickCount = _pThreadSleepTimeout[i];  
  23.         if (sleepExpiredTickCount != -1  
  24.             && dwCurrentTickCount >= sleepExpiredTickCount)  
  25.         {  
  26.             //唤醒这个线程，具体就是将此线程从阻塞队列移到就绪队列  
  27.             wakeUp(i);  
  28.             _pThreadSleepTimeout[i] = -1;    //超时值复位  
  29.         }  
  30.     }  
  31. }  


l 锁的实现

在多任务系统中，互斥锁也是常见的。作为示例，这里实现了一种可重入的互斥锁。可重入是指如果获得一个锁的线程再次获取这个锁，也将成功，只是增加引用计数。在这个实现中，简单地用一个整数来代表一个锁，并简单地用两个数组来分别管理所有的锁和等待队列，请参考线程/进程实现类中的定义。lock()的实现：若这个锁被其它线程占用，就阻塞，否则获得它或者增加引用计数（如果之前已获得）。trylock()与lock相似，只是若发现锁被其它线程占用，就立即返回，否则占用这个锁。trylock()是一个不会阻塞的调用。unlock()的实现：锁的引用计数减一，如果已到0，就唤醒一个等待的线程（如果有），此线程将是该锁的新的拥有者。

锁的实现

[cpp] view plain copy
  1. void ProcessManagerImpl::lock(long lock)  
  2. {  
  3.     int currentThreadIndex = _pThreadReady[0];  
  4.     int lockIndex = findLock(lock);  
  5.     if (lockIndex != -1)  
  6.     {  
  7.         Thread_Lock theLock = _pThreadLock[lockIndex];  
  8.         if (currentThreadIndex != theLock.threadIndex)  
  9.         {  
  10.             //其它线程拥有这个锁，当前线程只能阻塞  
  11.             addWait(currentThreadIndex, lock);  
  12.             block();  
  13.             //从阻塞中恢复，已经拥有这个锁了  
  14.         }  
  15.         else  
  16.         {  
  17.             //之前已获取过这个锁，引用数加1  
  18.             theLock.refCount++;  
  19.             _pThreadLock[lockIndex] = theLock;  
  20.         }  
  21.     }  
  22.     else  
  23.     {  
  24.         //获得这个锁，继续运行  
  25.         if (_threadLockCount < MAX_LOCK_NUM)  
  26.         {  
  27.             Thread_Lock theLock;  
  28.             theLock.lock = lock;  
  29.             theLock.threadIndex = currentThreadIndex;  
  30.             theLock.refCount = 1;  
  31.             _pThreadLock[_threadLockCount] = theLock;  
  32.             _threadLockCount++;  
  33.         }  
  34.     }  
  35. }  
  36.   
  37. //查找锁，若找到返回在数组中的索引，未找到返回-1。  
  38. int ProcessManagerImpl::findLock(long lock)  
  39. {  
  40.     for (int i = 0; i < _threadLockCount; i++)  
  41.     {  
  42.         Thread_Lock theLock = _pThreadLock[i];  
  43.         if (theLock.lock == lock)  
  44.             return i;  
  45.     }  
  46.     return -1;  
  47. }  
  48.   
  49. void ProcessManagerImpl::removeLockByIndex(int lockIndex)  
  50. {  
  51.     for (int i = lockIndex; i < _threadLockCount-1; i++)  
  52.     {  
  53.         _pThreadLock[i] = _pThreadLock[i+1];  
  54.     }  
  55.     _threadLockCount--;  
  56. }  
  57.   
  58. void ProcessManagerImpl::addWait(int threadIndex, long lock)  
  59. {  
  60.     Thread_Wait wait;  
  61.     wait.threadIndex = threadIndex;  
  62.     wait.lock = lock;  
  63.     _pThreadWait[_threadWaitCount] = wait;  
  64.     _threadWaitCount++;  
  65. }  
  66.   
  67. bool ProcessManagerImpl::trylock(long lock)  
  68. {  
  69.     int currentThreadIndex = _pThreadReady[0];  
  70.     int lockIndex = findLock(lock);  
  71.   
  72.     if (lockIndex != -1)  
  73.     {  
  74.         Thread_Lock theLock = _pThreadLock[lockIndex];  
  75.         if (currentThreadIndex != theLock.threadIndex)  
  76.         {  
  77.             //其它线程拥有这个锁  
  78.             return false;  
  79.         }  
  80.         else  
  81.         {  
  82.             //之前已获取过这个锁，引用数加1  
  83.             theLock.refCount++;  
  84.             _pThreadLock[lockIndex] = theLock;  
  85.             return true;  
  86.         }  
  87.     }  
  88.     else  
  89.     {  
  90.         //获得这个锁，继续运行  
  91.         if (_threadLockCount < MAX_LOCK_NUM)  
  92.         {  
  93.             Thread_Lock theLock;  
  94.             theLock.lock = lock;  
  95.             theLock.threadIndex = currentThreadIndex;  
  96.             theLock.refCount = 1;  
  97.             _pThreadLock[_threadLockCount] = theLock;  
  98.             _threadLockCount++;  
  99.             return true;  
  100.         }  
  101.     }  
  102.     return false;  
  103. }  
  104.   
  105. void ProcessManagerImpl::unlock(long lock)  
  106. {  
  107.     int currentThreadIndex = _pThreadReady[0];  
  108.     int lockIndex = findLock(lock);  
  109.   
  110.     if (lockIndex != -1)  
  111.     {  
  112.         Thread_Lock theLock = _pThreadLock[lockIndex];  
  113.         if (currentThreadIndex == theLock.threadIndex)  
  114.         {  
  115.             theLock.refCount--;  
  116.             if (theLock.refCount <= 0)  
  117.             {  
  118.                 int waitThreadIndex = removeWait(lock);  
  119.                 if (waitThreadIndex != -1)  
  120.                 {  
  121.                     //唤醒这个等待的线程  
  122.                     theLock.threadIndex = waitThreadIndex;  
  123.                     theLock.refCount = 1;  
  124.                     _pThreadLock[lockIndex] = theLock;  
  125.                     wakeUp(waitThreadIndex);  
  126.                 }  
  127.                 else  
  128.                 {  
  129.                     //没有其它线程等待这个锁，删除它  
  130.                     removeLockByIndex(lockIndex);  
  131.                 }  
  132.             }  
  133.             else  
  134.             {  
  135.                 _pThreadLock[lockIndex] = theLock;  
  136.             }  
  137.         }  
  138.         else  
  139.         {  
  140.             //当前线程不拥有这个锁  
  141.             return;  
  142.         }  
  143.     }  
  144.     else  
  145.     {  
  146.         //锁不存在  
  147.         return;  
  148.     }  
  149. }  
  150.   
  151. //查找等待给定锁的线程，若找到，从等待中删除并返回线程号；若未找到返回-1。  
  152. int ProcessManagerImpl::removeWait(long lock)  
  153. {  
  154.     int i;  
  155.     for (i = 0; i < _threadWaitCount; i++)  
  156.     {  
  157.         if (_pThreadWait[i].lock == lock)  
  158.         {  
  159.             int threadIndex = _pThreadWait[i].threadIndex;  
  160.             //删除这个元素（后续前移）  
  161.             for (int k = i; k < _threadWaitCount-1; k++)  
  162.             {  
  163.                 _pThreadWait[k] = _pThreadWait[k+1];  
  164.             }  
  165.             _threadWaitCount--;  
  166.             return threadIndex;  
  167.         }  
  168.     }  
  169.     return -1;  
  170. }  


多线程/进程测试运行

l 进入模拟多线程环境

我们的模拟程序通常作为宿主机上的一个进程来运行。当模拟系统启动时，从main函数开始运行。 main函数使用宿主系统提供的堆栈。我们就在main函数中创建模拟系统的第一个进程，这个进程的id为0。为此，线程/进程管理实现类提供了一个runProcess0函数，这个函数创建模拟系统中的第一个可调度进程，并立刻运行它。

runProcess0函数

[cpp] view plain copy
  1. //运行第一个进程，进程id为0。使用程序当前的堆栈。  
  2. int ProcessManagerImpl::runProcess0(THREAD_PROC threadProc, void *parameter)  
  3. {  
  4.     //第一个进程/线程，进程/线程号应该为0  
  5.     int freeProcessIndex = find_free_process();  
  6.     if (freeProcessIndex != 0)  
  7.         return -1;  
  8.     int freeThreadIndex = find_free_thread();  
  9.     if (freeThreadIndex != 0)  
  10.         return -1;  
  11.   
  12.     ProcessInternalInfo processInfo;  
  13.     processInfo.processId = freeProcessIndex;  
  14.   
  15.     ThreadInternalInfo threadInfo;  
  16.     threadInfo.processId = freeProcessIndex;  
  17.     threadInfo.threadId = freeThreadIndex;  
  18.     //我们把stackBase设为NULL，表示使用程序当前的栈  
  19.     threadInfo.stackBase = NULL;  
  20.     threadInfo.stackSize = 0;  
  21.     threadInfo.threadProc = threadProc;  
  22.     threadInfo.parameter = parameter;  
  23.     //不必准备线程初始的esp和eip，因为下面即刻转去执行  
  24.   
  25.     _pProcessInfo[freeProcessIndex] = processInfo;  
  26.     _pThreadInfo[freeThreadIndex] = threadInfo;  
  27.     //新线程加入就绪队列  
  28.     addThreadReady(freeThreadIndex);  
  29.     int ret = threadProc(parameter);  
  30.     return ret;  
  31. }  


这个函数与createProcess相似，所不同的是它不必为第一个进程/线程创建堆栈，而是直接用模拟程序的堆栈。另外不必初始化线程数据结构中的esp和eip，因为第一个线程是马上运行的。runProcess0()的效果是将模拟系统的（宿主机）主线程平滑地变成模拟系统中的一个进程/线程，而且是第一个。现在我们可以写出main函数的一个简单框架。

main函数的框架

[cpp] view plain copy
  1. ProcessManagerImpl *_process_manager;  
  2.   
  3. //进程0的主线程函数  
  4. int thread0_proc(void *parameter)  
  5. {  
  6.     return 0;  
  7. }  
  8.   
  9. int main(int argc, char *argv[])  
  10. {  
  11.     if (!init())  
  12.         return -1;  
  13.     //运行进程0  
  14.     int ret = _process_manager->runProcess0(thread0_proc, NULL);  
  15.     unInit();  
  16.     return ret;  
  17. }  


main函数的框架一目了然，在init中做一些初始化工作之后，就运行第一个进程。第一个进程负责产生其它的进程。第一个进程退出时，模拟系统就退出了，unInit完成清理工作。这里第一个线程函数thread0_proc还没有做任何事，似乎没有用处，但在示例代码中将给出一些测试例子。

l 使用自己的内存管理

内存管理通常都是系统的一个基本任务。这个模拟系统也实现了简单内存管理，参见后面的内存管理部分。模拟系统可以使用宿主系统提供的内存管理，也可以使用自己的内存管理。为了使用自己的内存管理，我们重载C++的new和delete运算符，使得对内存的分配和释放操作都是在一块我们管理的内存上进行。

重载new和delete

[cpp] view plain copy
  1. extern MemoryManager *_memory_manager;  
  2.   
  3. void *operator new(size_t size)  
  4. {  
  5.     return _memory_manager->alloc(size);  
  6. }  
  7.   
  8. void operator delete(void *p)  
  9. {  
  10.     _memory_manager->free(p);  
  11. }  


l 示例代码

示例代码1

[cpp] view plain copy
  1. static MemoryManagerImpl _memory_manager_impl;  
  2. MemoryManager *_memory_manager;  
  3. ProcessManagerImpl *_process_manager;  
  4.   
  5. bool init()  
  6. {  
  7.     int managed_memory_size = 30 * 1024 * 1024;  
  8.     _memory_manager_impl.setManagedMemory(managed_memory_size);  
  9.     _memory_manager = &_memory_manager_impl;  
  10.     _process_manager = new ProcessManagerImpl;  
  11.     return _process_manager->initManageData();  
  12. }  
  13.   
  14. void unInit()  
  15. {  
  16.     delete _process_manager;  
  17. }  
  18.   
  19. //进程1的主线程函数  
  20. int process1_thread1(void *parameter)  
  21. {  
  22.     while (1)  
  23.     {  
  24.         int processId = _process_manager->getCurrentProcessId();  
  25.         int threadId =_process_manager->getCurrentThreadId();  
  26.         printf("in process %d, thread %d\n", processId, threadId);  
  27.         //Sleep(500);  
  28.         _process_manager->schedule();  
  29.     }  
  30.     return 0;  
  31. }  
  32.   
  33. //进程0的主线程函数  
  34. int thread0_proc(void *parameter)  
  35. {  
  36.     printf("\npress any key to start\n");  
  37.     getch();  
  38.     int processId = _process_manager->createProcess(process1_thread1, NULL);  
  39.     while (1)  
  40.     {  
  41.         printf("in process0\n");  
  42.         _process_manager->schedule();  
  43.     }  
  44.     return 0;  
  45. }  


这个例子中使用了自己的内存管理，由于new和delete被重载了，内存管理对象自身（_memory_manager_impl）不能通过new创建，所以使用了一个静态对象。在init函数中初始化了内存管理类，此后所有涉及的内存申请和释放操作，都将在这块被管理的内存上进行。然后初始化了线程/进程管理类。

这个例子演示了线程之间的切换。我们来看进程0的主线程函数。进程0只有这一个线程。它调用createProcess创建了进程1，然后进入一个循环。这里是一个无限循环，但你可以改为一个有条件的循环，比如循环一定次数，以测试模拟系统是否正常退出。在这个循环里，它调用了schedule，以便把控制权交给其它线程。再来看进程1的主线程函数，它里面也是一个循环，同样你可以修改循环条件，以观察或调试线程的退出。它也是调用schedule交出控制权。运行这里的示例，结果如下：

in process0

in process 1, thread 1

in process0

in process 1, thread 1

in process0

in process 1, thread 1

....

如此我们看到线程之间不停地切换。因为屏幕刷新太快，可以加个延时操作，请把thread1中被注释的本地延时函数Sleep恢复（Sleep是Win32的一个调用），就可以看到延迟的效果。我们可以稍微修改上面的代码，让一个进程有多个线程，并测试sleep和锁。

示例代码2

[cpp] view plain copy
  1. int process1_thread2(void *parameter)  
  2. {  
  3.     while (1)  
  4.     {  
  5.         printf("in process1_thread2\n");  
  6.         _process_manager->sleep(30);  
  7.     }  
  8.     return 0;  
  9. }  
  10.   
  11. int process1_thread1(void *parameter)  
  12. {  
  13.     int threadId = _process_manager->createThread(process1_thread2, NULL);  
  14.     while (1)  
  15.     {  
  16.         int processId = _process_manager->getCurrentProcessId();  
  17.         int threadId =_process_manager->getCurrentThreadId();  
  18.         printf("in process %d, thread %d\n", processId, threadId);  
  19.         _process_manager->sleep(50);  
  20.     }  
  21.     return 0;  
  22. }  


这个例子中，进程1的主线程中，通过createThread创建了另一个线程。这样进程1就有两个线程了。这两个线程不再调用shcedule()，而是调用sleep()函数。运行这个例子，就会看到系统中有三个线程都在运行。有一点请注意，不要在thread0中调用sleep或其它导致阻塞的函数，免得模拟系统遇到没有线程可以调度的情况。至于线程锁，可以类似写些测试代码，包括测试线程之间的死锁，这里不再多说了。

内存管理

内存管理向来是操作系统的一个基本任务。我们的模拟系统当前只实现了简单的内存管理。它的目标是管理向宿主机系统申请的一块内存，把它看作是模拟系统的可分配内存空间，满足在这个内存空间上的申请和释放操作。

内存管理接口

内存管理接口定义

[cpp] view plain copy
  1. class MemoryManager  
  2. {  
  3. public:  
  4.   
  5. //申请一块内存，size为申请的字节数  
  6. virtual void *alloc(int size) = 0;  
  7.   
  8. //释放先前申请的内存  
  9. virtual void free(void *memblock) = 0;  
  10. };  

 

一个简单的实现

下面是内存管理的一个简单实现。其基本思路是用一些控制块来管理内存的分配。每一块已分配的内存，都有一个控制块（Mem_Ctrl_Block），指出这块已分配内存的大小。为了简单，控制块与已分配内存块紧挨在一起，且在已分配内存块的前面。控制块中有个指针，指向下一个已分配内存的控制块。这样，所有已分配内存的控制块，由低地址往高地址形成了一个单向链表。分配内存的时候，先找链表的两头，看看有无够用空闲内存。若没有就顺着链表，依次看两个控制块之间，有无足够空闲内存用来分配。若找到就建立一个控制块，或插入到链表中，或放到链表的头或尾。释放一块已分配内存的时候，就寻找相应的控制块，找到就从链表中删除。

内存管理实现类的定义

[cpp] view plain copy
  1. class MemoryManagerImpl : public MemoryManager  
  2. {  
  3. public:  
  4. MemoryManagerImpl();  
  5. virtual ~MemoryManagerImpl();  
  6. //设置被管理的内存大小，这块内存可以从外面传入。  
  7. //如果memory为NULL，这块内存将内部申请。  
  8. void setManagedMemory(int size, void *memory = NULL);  
  9. int getManagedSize() const;  
  10. //申请一块内存，size为申请的字节数  
  11. virtual void *alloc(int size);  
  12. //释放先前申请的内存  
  13. virtual void free(void *memblock);  
  14.   
  15. protected:  
  16. struct Mem_Ctrl_Block  
  17. {  
  18.     int reserved;  
  19.     int size;  
  20.     void *next;    //按地址顺序指向下一个Mem_Ctrl_Block  
  21. };  
  22. void *memory_to_manage;  
  23. int size_to_manage;  
  24. bool memory_need_free;  
  25. //指向第一块已分配的内存  
  26. Mem_Ctrl_Block *first_mem_block;  
  27. //指向最后一块已分配的内存  
  28. Mem_Ctrl_Block *last_mem_block;  
  29. }  

 

内存管理类的实现

[cpp] view plain copy
  1. MemoryManagerImpl::MemoryManagerImpl()  
  2. {  
  3.     memory_to_manage = NULL;  
  4.     size_to_manage = 0;  
  5.     first_mem_block = NULL;  
  6.     last_mem_block = NULL;  
  7.     memory_need_free = false;  
  8. }  
  9.   
  10. MemoryManagerImpl::~MemoryManagerImpl()  
  11. {  
  12.     if (memory_need_free)  
  13.         ::free(memory_to_manage);  
  14. }  
  15.   
  16. void MemoryManagerImpl::setManagedMemory(int size, void *memory)  
  17. {  
  18.     if (memory == NULL)  
  19.     {  
  20.         memory_to_manage = ::malloc(size);  
  21.         memory_need_free = true;  
  22.     }  
  23.     else  
  24.     {  
  25.         memory_to_manage = memory;  
  26.         memory_need_free = false;  
  27.     }  
  28.     size_to_manage = size;  
  29. }  
  30.   
  31. int MemoryManagerImpl::getManagedSize() const  
  32. {  
  33.     return size_to_manage;  
  34. }  
  35.   
  36. //申请一块内存，size为申请的字节数  
  37. void *MemoryManagerImpl::alloc(int size)  
  38. {  
  39.     //在下面的分配实现中，控制节点与返回给用户的内存挨在一起  
  40.     //（在用户内存的前面就是控制节点）  
  41.     //检查大小是否合理。这个检查也为了防止计算溢出错误  
  42.     if (size < 0 || size > size_to_manage)  
  43.         return NULL;  
  44.     int need_size = sizeof(Mem_Ctrl_Block) +size;  
  45.     if (need_size < 0)  
  46.         return NULL;  
  47.     if (first_mem_block == NULL)  
  48.     {  
  49.         if (need_size <= size_to_manage)  
  50.         {  
  51.             first_mem_block = (Mem_Ctrl_Block *)memory_to_manage;  
  52.             first_mem_block->size = size;  
  53.             first_mem_block->next = NULL;  
  54.             last_mem_block = first_mem_block;  
  55.             return (char *)first_mem_block + sizeof(Mem_Ctrl_Block);  
  56.         }  
  57.         else  
  58.             return NULL;  
  59.     }  
  60.     //检查第一个已分配的内存块之前有无足够空闲空间，若有，直接分配  
  61.     if (first_mem_block != memory_to_manage  
  62.         && (need_size <= (char *)first_mem_block - (char *)memory_to_manage))  
  63.     {  
  64.         Mem_Ctrl_Block *new_first = (Mem_Ctrl_Block *)memory_to_manage;  
  65.         new_first->size = size;  
  66.         new_first->next = first_mem_block;  
  67.         first_mem_block = new_first;  
  68.         return (char *)first_mem_block + sizeof(Mem_Ctrl_Block);  
  69.     }  
  70.     //检查最后一个已分配的内存块之后有无足够空闲空间，若有，直接分配  
  71.     Mem_Ctrl_Block *after_last = (Mem_Ctrl_Block *)((char *)last_mem_block+ sizeof(Mem_Ctrl_Block) + last_mem_block->size);  
  72.     if ( need_size <= ((char *)memory_to_manage + size_to_manage - (char *)after_last))  
  73.     {  
  74.         //Ok，有足够空闲内存  
  75.         after_last->size = size;  
  76.         after_last->next = NULL;  
  77.         last_mem_block->next = after_last;  
  78.         last_mem_block = after_last;  
  79.         return (char *)last_mem_block + sizeof(Mem_Ctrl_Block);  
  80.     }  
  81.     //沿着已分配的内存块链表搜索下去，查找两个块中间有足够大的空闲可以分配  
  82.     Mem_Ctrl_Block *current = first_mem_block;  
  83.     while (current != last_mem_block)  
  84.     {  
  85.         Mem_Ctrl_Block *next_block = (Mem_Ctrl_Block *)current->next;  
  86.         Mem_Ctrl_Block *after_current = (Mem_Ctrl_Block *)((char *)current+ sizeof(Mem_Ctrl_Block) + current->size);  
  87.         if (need_size <= (char *)next_block - (char *)after_current)  
  88.         {  
  89.             //Ok, 两个已分配块之间有足够的空闲内存，可以分配  
  90.             after_current->next = next_block;  
  91.             after_current->size = size;  
  92.             current->next = after_current;  
  93.             return (char *)after_current + sizeof(Mem_Ctrl_Block);  
  94.         }  
  95.         else  
  96.             current = next_block;  
  97.     }  
  98.     return NULL;  
  99. }  
  100.   
  101. //释放先前申请的内存  
  102. void MemoryManagerImpl::free(void *memblock)  
  103. {  
  104.     if (first_mem_block == NULL)  
  105.         return;  
  106.     if ((char *)first_mem_block + sizeof(Mem_Ctrl_Block) == memblock)  
  107.     {  
  108.         //释放第一个块  
  109.         Mem_Ctrl_Block *old_first = first_mem_block;  
  110.         first_mem_block = (Mem_Ctrl_Block *)first_mem_block->next;  
  111.         old_first->next = NULL;    //这一句为冗余  
  112.         if (last_mem_block == old_first) last_mem_block = NULL;  
  113.         return;  
  114.     }  
  115.     //沿着已分配的内存块链表搜索下去，直到找到给定的内存块  
  116.     Mem_Ctrl_Block *current = first_mem_block;  
  117.     while (current->next)  
  118.     {  
  119.         Mem_Ctrl_Block *next = (Mem_Ctrl_Block *)current->next;  
  120.         if ((char *)next + sizeof(Mem_Ctrl_Block) == memblock)  
  121.         {  
  122.             //将内存块节点从链表中删除，完成释放  
  123.             current->next = next->next;  
  124.             next->next = NULL;//这一句为冗余  
  125.             if (last_mem_block == next) last_mem_block = current;  
  126.             return;  
  127.         }  
  128.         current = next;  
  129.     }  
  130. }  

原文链接： 模拟实现一个多线程环境 版权所有，转载时请注明出处，违者必究。
注明出处格式：流沙团 ( https://gyarmy.com/post-345.html )

发表评论

0则评论给“模拟实现一个多线程环境”