流沙团
模拟实现一个多线程环境
2017-12-26 流沙团


引言



初学者或者一些有经验的开发人员，并不总是对于系统底层有清楚的了解。比如，进程（或线程）调度是如何实现的？往往只停留于模糊的认识。了解这些问题的最好途径是亲自实践。然而开发一个真实系统的门槛很高，而通过学习一个已有系统来了解也非易事，因为错综复杂的代码和关系有时把人搞糊涂了。于是学习者往往写一些模拟程序来努力表达系统是怎样运作的。不过，这些程序往往过于简单。于是“看看能否写一个模拟进程调度的软件”，从这个想法出发我尝试写一个接近真实的调度程序，因为进程或线程调度是现代操作系统的核心部分。经过一段时间的摸索一个调度程序写成了，同时写了一个简单的内存管理。接下来实现了一个模拟文件系统，差不多是按着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. }  




发表评论：
昵称

邮件地址 (选填)

个人主页 (选填)

内容