引言
初学者或者一些有经验的开发人员，并不总是对于系统底层有清楚的了解。比如，进程（或线程）调度是如何实现的？往往只停留于模糊的认识。了解这些问题的最好途径是亲自实践。然而开发一个真实系统的门槛很高，而通过学习一个已有系统来了解也非易事，因为错综复杂的代码和关系有时把人搞糊涂了。于是学习者往往写一些模拟程序来努力表达系统是怎样运作的。不过，这些程序往往过于简单。于是“看看能否写一个模拟进程调度的软件”，从这个想法出发我尝试写一个接近真实的调度程序，因为进程或线程调度是现代操作系统的核心部分。经过一段时间的摸索一个调度程序写成了，同时写了一个简单的内存管理。接下来实现了一个模拟文件系统，差不多是按着0.11版的Linux文件系统实现的。我把这个模拟系统看作是学习和实践的一个场所，因此我主要用C++语言而不是C语言来编写，因为面向对象的方法（接口和类）更容易表达要被理解的东西。毕竟这是一个模拟程序，首要目标是帮助人学习和亲自实践，而不是以追求实现效率为先。目前这个模拟系统是在Windows平台上实现的，但它也可能在其它平台上实现。因为这个系统中只有少量与平台或硬件有关的代码，在不同平台上这部分的实现将有差异。
多线程/进程的模拟实现
线程及线程切换的概念
我们先来回顾下线程及其切换的概念。计算机通常按顺序一条一条地执行程序指令。多数处理器（CPU）通常内部借助一些寄存器来完成指令的执行，例如程序计数器（PC），指向下一条要执行的指令，其它是一些数据或状态寄存器等。另外，许多计算机支持使用堆栈（stack）来传递函数参数，存放局部变量等，因为寄存器的数量毕竟有限。通常用一个堆栈寄存器（SP）来指向当前所用的堆栈。当一段程序代码被执行的时候，处理器就处在一个状态中，这个状态可以用当前的程序计数器，堆栈指针，以及其它一些寄存器的集合来定义。如果我们把这个状态保存下来，转去执行其它代码，一段时间后再回过来，把先前保存的状态恢复，使各个寄存器恢复到以前保存的那个状态，继续执行下去，那么这一段程序的执行就好像没有被打断一样。这样一段程序的执行，就像一个独立的执行流或路径，这就是一个线程（thread）的含义了。系统中可以有许多线程，只要对每个线程都按照保存、恢复，恢复、保存来处理，就看起来像是同时各自独立运行。至于线程切换，就是把当前线程的执行状态保存起来，然后把另一个线程的已保存状态恢复过来，成为当前，这就完成切换了。
线程切换的实现
虽然我们大概明白线程及其切换的原理，但编写代码实现出来是最重要的。在寻求实现的过程中，我曾担心一件事：线程切换的实现，是否离不开特殊硬件指令的支持？恐怕是特权指令。我看到一篇网友的文章，他在用户程序中给出了从一个函数切换到另一个函数的例子，他的函数相当于线程函数。因此我参照他的代码在Windows平台上实现了。我用的开发工具为vs2008，为了完成线程切换，需要嵌入Intel汇编指令。
线程切换实现代码
void threadSwitch(int *pCurrentESP, int *pCurrentEIP, int nextESP, int nextEIP)
{
__asm
{
push eax
push ebx
push ecx
push edx
push esi
push edi
push ebp
//save ESP
mov ebx,esp
mov eax,[pCurrentESP]
mov [eax],ebx
//restore ESP
mov eax,nextESP
mov esp,eax
//Save EIP
lea ebx, _RECOVER_
mov eax, [pCurrentEIP]
mov [eax],ebx
//Restore EIP
mov eax, nextEIP
push eax
ret
_RECOVER_:
pop ebp
pop edi
pop esi
pop edx
pop ecx
pop ebx
pop eax
}
}
我们来分析这段代码如何完成切换的。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并未改变，因此对这几个局部变量的访问总是有效的。
线程/进程管理类（接口）
线程切换实现之后，其它如线程的内部数据结构，线程调度等相对来说比较容易了。我打算把线程和进程的有关功能放到一个类中。为了清晰，先定义一个线程/进程的管理接口。我也决定在这个模拟系统中，以线程为基本调度单元。一个进程可以有一个或多个线程，其中有一个线程为主线程（主线程若结束，这个进程就要销毁了）。下面是线程/进程管理类接口，其中的接口函数都定义为纯虚函数。
线程/进程管理接口
typedef int (*THREAD_PROC)(void *parameter);
class ProcessManager
{
public:
//创建一个进程和其主线程。成功返回该进程的id（进程范围内唯一，大于0），失败返回0。
//主线程和其它线程的区别是，主线程运行结束，进程就终止，属于该进程的所有线程都释放。
virtual int createProcess(THREAD_PROC mainThreadProc, void *parameter,
int stackSizeInKB=1024, bool readyToRun=true) = 0;
//创建一个线程。成功返回该线程的id（线程范围内唯一，大于0），失败返回0。
//为了简化编程，约定线程id从1开始顺序编号（0为系统空闲线程所用）。
virtual int createThread(THREAD_PROC threadProc, void *parameter,
int stackSizeInKB=1024, bool readyToRun=true) = 0;
//进程/线程调度。
//对于合作式的线程调度，需要每个线程主动调用调度函数，让其它线程有机会执行。
virtual void schedule() = 0;
//获取当前进程的id。
virtual int getCurrentProcessId() = 0;
//获取当前线程的id。
virtual int getCurrentThreadId() = 0;
//获取进程的当前工作路径
virtual const char *getCurrentDir() = 0;
//设置进程的当前工作目录
virtual void setCurrentDir(const char *pathname) = 0;
//使当前线程睡眠指定的毫秒数
virtual void sleep(int msecs) = 0;
//获取锁，成功将拥有这个锁（如果之前已获取这个锁，将增加引用计数）。
//如果锁已经被其它线程拥有，调用线程将阻塞。
//一个锁可以被同一线程多次获取，但释放也要匹配相同的次数，否则其它线程不能获取它
virtual void lock(long lock) = 0;
//尝试获取锁，成功将拥有这个锁。如果锁已经被其它线程拥有，立即返回false
virtual bool trylock(long lock) = 0;
//释放锁
virtual void unlock(long lock) = 0;
};
这个线程/进程管理接口最主要的就是支持线程的创建，进程的创建，以及调度。在这里调度的基本含义是指线程调度，因为线程已作为基本调度单位。
对这个接口类需要作些说明。THREAD_PROC是线程函数的原型定义。schedule()是调度函数。为何要把调度函数公开出来呢？因为这个模拟系统目前只支持共享方式的调度。也就是说，这个系统中的每个线程需要主动放弃控制权，好让其它线程有机会运行。假如有个线程不释放控制权，从来不调用schedule()，它就一直独占系统，以致其它线程没有机会执行。此种情况类似一些早期的系统，例如早期Windows系统。如果要实现抢先式调度，就要接管中断和中断处理，因为中断能打断当前程序（线程）的执行，在中断处理函数中可以实现调度。模拟程序目前没有寻到一个方法来支持抢先式调度。createProcess是支持创建进程的接口函数，目前它是简单原始的。我们还未实现从磁盘可执行文件加载和创建进程。至于sleep和线程锁，放在这里主要是展示对于线程调度技术的运用。
线程/进程管理类的实现
我通常会先选择一种简单的实现。如果时间允许，或者有了想法，再去改进或写各种变化的实现。这样的做法是常见的。这个模拟系统，适合作为一个学习和练习的场所。
所用到的一些结构
//存放进程相关信息的结构
class ProcessInternalInfo
{
public:
int processId;
char currentDir[300];
ProcessInternalInfo();
};
//存放线程相关信息的结构
class ThreadInternalInfo
{
public:
//线程id及线程所属的进程id
int processId;
int threadId;
//线程切换时对现场的保存和恢复，主要是栈顶指针(esp)和指令计数器(eip)
int esp;
int eip;
//线程所使用的用户栈及其大小
char *stackBase;
int stackSize; //字节
//线程函数及其参数
THREAD_PROC threadProc;
void *parameter;
//是否进程的主线程
bool isMainThread;
//错误代码
int error;
ThreadInternalInfo();
};
//内部堆栈，内部堆栈应该很小，因为只有thread wrapper function才用到
struct InternalStack
{
char stack[4*1024];
};
//锁的实现结构
class Thread_Lock
{
public:
long lock;
int threadIndex;
int refCount;
Thread_Lock()
{
lock = 0;
threadIndex = -1;
refCount = 0;
}
};
class Thread_Wait
{
public:
int threadIndex;
long lock;
Thread_Wait()
{
threadIndex = -1;
lock = 0;
}
};
管理实现类的定义
class ProcessManagerImpl : public ProcessManager
{
public:
ProcessManagerImpl();
virtual ~ProcessManagerImpl();
//初始化
bool initManageData();
virtual int createProcess(THREAD_PROC mainThreadProc, void *parameter,
int stackSizeInKB=1024, bool readyToRun=true);
virtual int createThread(THREAD_PROC threadProc, void *parameter,
int stackSizeInKB=1024, bool readyToRun=true);
virtual void schedule();
virtual int getCurrentProcessId();
virtual int getCurrentThreadId();
virtual const char *getCurrentDir();
virtual void setCurrentDir(const char *pathname);
virtual void sleep(int msecs);
virtual void lock(long lock);
virtual bool trylock(long lock);
virtual void unlock(long lock);
//运行第一个进程，进程id为0。使用程序当前的堆栈。
int runProcess0(THREAD_PROC threadProc, void *parameter);
void setError(int error);
int getError();
protected:
//这里采用数组和索引管理所有进程/线程
ProcessInternalInfo *_pProcessInfo;
ThreadInternalInfo *_pThreadInfo;
//指向就绪线程队列
int *_pThreadReady;
//指向阻塞线程队列
int *_pThreadBlock;
//为每个线程分配一个内部栈。因为用户线程函数结束后，用户栈将被删除，
//thread wrapper function不能依靠用户栈工作
InternalStack *_pInternalStack;
protected:
//释放相关资源
void freeManageData();
//查找未用的进程槽，返回索引。未找到返回-1。
int find_free_process();
//查找未用的线程槽，返回索引。未找到返回-1。
int find_free_thread();
//加入到就绪线程队列
void addThreadReady(int threadIndex);
//加入到阻塞线程队列
void addThreadBlock(int threadIndex);
//创建线程
int create_thread(int processId, bool isMainThread, THREAD_PROC threadProc,
void *parameter, int stackSizeInKB, bool readyToRun);
//thread wrapper function
//用户线程结束时要释放堆栈，并从调度队列中删除，所以需要一个对用户线程函数的包装
static void thread_wrapper_func(ProcessManagerImpl *pImpl, int threadIndex);
//从就绪线程队列中删除
void removeReadyThread(int threadIndex);
//从阻塞线程队列中删除
void removeBlockThread(int threadIndex);
//删除一个线程（重置对应的线程槽）
void removeThread(int threadIndex);
//删除一个进程（重置对应的进程槽）
void removeProcess(int processIndex);
//线程切换
void threadSwitch(int *pCurrentESP, int *pCurrentEIP, int nextESP, int nextEIP);
//系统死机 - 通常由于内部错误导致无法处理的情况，就进入这里
void system_dead();
//使当前线程睡眠，放入阻塞队列，然后切换到下一个线程
void block();
//唤醒一个线程，即从阻塞队列移除，放到就绪队列
void wakeUp(int threadIndex);
protected:
//对sleep的支持
//所有由于调用sleep函数导致睡眠的，超时时间记录在这里，单位毫秒。
int *_pThreadSleepTimeout;
//检查看是否有线程的睡眠时间到了，把所有这样的线程唤醒
void checkSleepTimeout();
//对锁的支持
Thread_Lock *_pThreadLock; //存放锁的数组
int _threadLockCount;
Thread_Wait *_pThreadWait; //等待锁的线程
int _threadWaitCount;
//查找锁，若找到返回在数组中的索引，未找到返回-1。
int findLock(long lock);
void removeLockByIndex(int lockIndex);
void addWait(int threadIndex, long lock);
//查找等待给定锁的线程，若找到，从等待中删除并返回线程号；若未找到返回-1。
int removeWait(long lock);
//对阻塞式文件读写的支持
//线程由于等待事件而睡眠的，等待的事件存放在下面的数组中
HANDLE *_pThreadEvent;
//线程等待事件，可能进入睡眠，直到事件变为信号状态而被唤醒
void waitEvent(HANDLE hEvent);
//检查所有的等待事件，把这样的线程唤醒
void checkThreadEvent();
void removeThreadEvent(int threadIndex);
friend class BlockedFileDisk;
};
在这个实现中，我使用了一个数组来存放所有的进程对象（_pProcessInfo所指）。一个数组来存放所有的线程对象（pThreadInfo所指）。线程会阻塞或者就绪，_pThreadReady指向就绪队列，pThreadBlock指向阻塞队列。这两个队列的元素存的是线程对象索引。使用这个线程/进程管理类之前，先要把这些数据初始化，这通过调用initManageData()来达到。
构造和初始化
#define MAX_PROCESS_NUM 1024
#define MAX_THREAD_NUM 2048
#define MAX_LOCK_NUM 200
ProcessInternalInfo::ProcessInternalInfo()
{
processId = -1; //有效的进程id从0开始
memset(currentDir, 0 ,sizeof(currentDir));
strcpy(currentDir, "/");
}
ThreadInternalInfo::ThreadInternalInfo()
{
processId = -1;
threadId = -1; //有效的线程id从0开始
esp = 0;
eip = 0;
stackBase = NULL;
stackSize = 0;
threadProc = NULL;
parameter = NULL;
isMainThread = false;
error = 0;
}
ProcessManagerImpl::ProcessManagerImpl()
{
//改为明确调用
//initManageData();
}
ProcessManagerImpl::~ProcessManagerImpl()
{
freeManageData();
}
bool ProcessManagerImpl::initManageData()
{
_pProcessInfo = new ProcessInternalInfo [MAX_PROCESS_NUM];
if (!_pProcessInfo) return false;
_pThreadInfo = new ThreadInternalInfo [MAX_THREAD_NUM];
if (!_pThreadInfo) return false;
_pThreadReady = new int [MAX_THREAD_NUM];
if (!_pThreadReady) return false;
for (int i = 0; i < MAX_THREAD_NUM; i++) _pThreadReady[i] = -1;
_pThreadBlock = new int [MAX_THREAD_NUM];
if (!_pThreadBlock) return false;
for (int i = 0; i < MAX_THREAD_NUM; i++) _pThreadBlock[i] = -1;
_pInternalStack = new InternalStack [MAX_THREAD_NUM];
if (!_pInternalStack) return false;
_pThreadSleepTimeout = new int [MAX_THREAD_NUM];
if (!_pThreadSleepTimeout) return false;
for (int i = 0; i < MAX_THREAD_NUM; i++) _pThreadSleepTimeout[i] = -1;
_pThreadLock = new Thread_Lock [MAX_LOCK_NUM];
if (!_pThreadLock) return false;
_threadLockCount = 0;
_pThreadWait = new Thread_Wait [MAX_THREAD_NUM];
if (!_pThreadWait) return false;
_threadWaitCount = 0;
_pThreadEvent = new HANDLE [MAX_THREAD_NUM];
if (!_pThreadEvent) return false;
for (int i = 0; i < MAX_THREAD_NUM; i++) _pThreadEvent[i] = INVALID_HANDLE_VALUE;
return true;
}
void ProcessManagerImpl::freeManageData()
{
delete [] _pThreadEvent;
delete [] _pThreadWait;
delete [] _pThreadLock;
delete [] _pThreadSleepTimeout;
delete [] _pInternalStack;
delete [] _pThreadBlock;
delete [] _pThreadReady;
delete [] _pThreadInfo;
delete [] _pProcessInfo;
}
l 创建进程（createProcess）
进程创建实现
int ProcessManagerImpl::createProcess(THREAD_PROC mainThreadProc, void *parameter,
int stackSizeInKB, bool readyToRun)
{
int freeProcessIndex = find_free_process();
if (freeProcessIndex == -1)
return 0;
ProcessInternalInfo processInfo;
processInfo.processId = freeProcessIndex;
int threadIndex = create_thread(freeProcessIndex, true, mainThreadProc,
parameter, stackSizeInKB, readyToRun);
if (threadIndex == 0)
return 0;
_pProcessInfo[freeProcessIndex] = processInfo;
return freeProcessIndex;
}
目前对进程的支持比较简单。这不是一个完整的进程创建过程，因为它假定进程的程序代码已经在内存中了。首先find_free_process查找进程数组，找到一个空闲槽，接着创建这个进程的主线程，成功地话就占用那个进程槽。这样一个进程就算建立了。如果此进程打算使用多个线程，它可以调用createThread创建其它线程。
l 创建线程（createThread）
线程创建实现
int ProcessManagerImpl::createThread(THREAD_PROC threadProc, void *parameter,
int stackSizeInKB, bool readyToRun)
{
int processId = getCurrentProcessId();
return create_thread(processId, false, threadProc,
parameter, stackSizeInKB, readyToRun);
}
int ProcessManagerImpl::create_thread(int processId, bool isMainThread,
THREAD_PROC threadProc, void *parameter, int stackSizeInKB, bool readyToRun)
{
if (stackSizeInKB < 0)
return 0;
if (stackSizeInKB == 0)
stackSizeInKB = 1024;
int freeThreadIndex = find_free_thread();
if (freeThreadIndex == -1)
return 0;
//申请用户栈空间
int stackSizeInByte = stackSizeInKB * 1024;
char *pStack = new char [stackSizeInByte];
//char *pStack = (char *)GetMemoryManager()->alloc(stackSizeInByte);
if (pStack == NULL)
return 0;
ThreadInternalInfo threadInfo;
threadInfo.processId = processId;
threadInfo.threadId = freeThreadIndex;
threadInfo.stackBase = pStack;
threadInfo.stackSize = stackSizeInByte;
threadInfo.threadProc = threadProc;
threadInfo.parameter = parameter;
threadInfo.isMainThread = isMainThread;
//准备线程初始的esp和eip，eip指向线程wrapper函数的入口地址, esp指向内部栈
//由于线程wrapper函数需要两个参数，按照C调用约定，从右到左把这两个参数压入栈，
//另外函数返回地址也要占去4个字节，故esp为栈顶减去12个字节。
void (*thread_wrapper_func_ptr)(ProcessManagerImpl *, int);
thread_wrapper_func_ptr = &thread_wrapper_func;
threadInfo.eip = (int)thread_wrapper_func_ptr;
threadInfo.esp = (int)(_pInternalStack[freeThreadIndex].stack
+ sizeof(_pInternalStack[freeThreadIndex].stack) - 12);
ProcessManagerImpl **ppImpl = (ProcessManagerImpl **)(threadInfo.esp + 4);
*ppImpl = this;
int *pInt = (int *)(threadInfo.esp + 8);
*pInt = freeThreadIndex;
_pThreadInfo[freeThreadIndex] = threadInfo;
//新线程加入就绪队列
if (readyToRun)
addThreadReady(freeThreadIndex);
else
addThreadBlock(freeThreadIndex);
return freeThreadIndex;
}
创建线程的主要工作在create_thread()中完成。基本过程是：找到一个空闲线程槽，创建用户堆栈，初始化线程数据结构。线程数据结构中特别需要说明的是eip和esp的初始赋值：eip指向线程的入口代码，esp指向线程的堆栈。当调度运行这个线程时，就将跳到eip所指向的地址，同时将堆栈寄存器设置为esp的值。那么eip和esp的初始值分别是什么呢？一个自然的想法是：eip指向用户线程函数threadProc，esp指向用户堆栈。但这样的话，线程运行结束后，线程所用的资源（例如用户堆栈）在哪里释放呢？它既然运行结束，就应该把控制权转移给其它线程，在哪里把控制权转移呢？思考这些问题的结果是：需要一个线程包装函数，在用户线程函数的前后做这些工作。当线程运行结束后，用户堆栈将被释放，因此我使用线程的一个内部堆栈，在内部堆栈上做这些收尾工作。内部堆栈通常1K到4K就够了。如此看来，eip应该指向用户线程函数的包装函数，esp指向线程内部栈。
线程包装函数
//thread wrapper function
//用户线程结束时要释放堆栈，并从调度队列中删除，所以需要一个对用户线程函数的包装
//注意：由于内部堆栈很小，要小心，建议不要调用什么C库函数，例如printf
void ProcessManagerImpl::thread_wrapper_func(ProcessManagerImpl *pImpl,
int threadIndex)
{
ThreadInternalInfo threadInfo = pImpl->_pThreadInfo[threadIndex];
THREAD_PROC threadProc = threadInfo.threadProc;
void *parameter = threadInfo.parameter;
int userESP = (int)(threadInfo.stackBase + threadInfo.stackSize);
int oldESP;
//接下来切换到用户堆栈
__asm
{
mov eax,esp
mov oldESP,eax
mov eax,userESP
mov esp,eax
}
//执行用户线程函数
threadProc(parameter);
//函数调用完成之后，通常ebp是不会改变，对局部变量的访问仍然有效
//恢复到内部堆栈
_asm
{
mov eax,oldESP
mov esp,eax
}
//线程函数执行完毕，从就绪队列中移去，从线程队列中也移去
pImpl->removeReadyThread(threadIndex);
pImpl->removeThread(threadIndex);
//如果是主线程，则释放该进程的一切资源，包括属于该进程的所有线程
if (threadInfo.isMainThread)
{
int processId = threadInfo.processId;
for (int i = 0; i < MAX_THREAD_NUM; i++)
{
if (pImpl->_pThreadInfo[i].processId == processId)
{
//将该线程从阻塞或是就绪就列中删除
pImpl->removeReadyThread(i);
pImpl->removeBlockThread(i);
pImpl->removeThreadEvent(i);
pImpl->removeThread(i);
}
}
pImpl->removeProcess(processId);
}
//找到下一个就绪线程，成为当前并切过去
//如果有线程由于调用sleep进入休眠的，检查和唤醒之
pImpl->checkSleepTimeout();
pImpl->checkThreadEvent();
int currentThreadIndex = pImpl->_pThreadReady[0];
if (currentThreadIndex != -1)
{
int currentESP = pImpl->_pThreadInfo[currentThreadIndex].esp;
int currentEIP = pImpl->_pThreadInfo[currentThreadIndex].eip;
//切过去
__asm
{
//restore ESP
mov eax,currentESP
mov esp,eax
//Restore EIP
mov eax,currentEIP
push eax
ret
}
} else
{ //就绪队列为空，这应该不会发生，因为Process0总会存在
pImpl->system_dead();
}
}
在这个线程包装函数中，需要注意的一点，就是执行用户线程函数threadProc前后堆栈的改变。执行threadProc前堆栈改为用户堆栈，执行threadProc后堆栈恢复为内部堆栈。接下来对这个线程资源的释放都在内部堆栈上进行。
l 调度函数（schedule）
调度函数实现
void ProcessManagerImpl::schedule()
{
//由于线程需要主动让出CPU，让其它线程有机会执行，故在调度上按均等机会处理
//做法是：查找下一个就绪线程，把它提为当前线程，原来的线程移到就绪队列末尾
//如果没有下一个就绪线程，则立即返回，继续执行当前线程
//如果有线程由于调用sleep进入休眠的，检查和唤醒之
checkSleepTimeout();
checkThreadEvent();
int currentThreadIndex = _pThreadReady[0];
int nextThreadIndex = _pThreadReady[1];
if (nextThreadIndex == -1)
return;
//下一个就绪线程提为当前
int i;
for (i = 1; i < MAX_THREAD_NUM; i++)
{
if (_pThreadReady[i] != -1)
_pThreadReady[i-1] = _pThreadReady[i];
else
break;
}
_pThreadReady[i-1] = currentThreadIndex;
//准备切换，切换时主要保存EBP（栈帧指针）、ESP（当前栈指针）和EIP（指令计数器），
//并要修改ESP和EIP，对ESP的修改，不影响对于局部变量的访问（因为是通过EBP进行的）
int *pCurrentESP = &(_pThreadInfo[currentThreadIndex].esp);
int *pCurrentEIP = &(_pThreadInfo[currentThreadIndex].eip);
int nextESP = _pThreadInfo[nextThreadIndex].esp;
int nextEIP = _pThreadInfo[nextThreadIndex].eip;
threadSwitch(pCurrentESP,pCurrentEIP,nextESP,nextEIP);
}
就绪线程队列的首个元素（下标为0），就指向当前线程。由于这个模拟系统是共享式调度，所以简单地采用顺序调度的方式切到下一个线程，原先的线程就移到就绪队列的末尾。完成切换的代码就是前面我们介绍过的threadSwitch函数。也可以实现其它调度算法，例如如果线程有优先级，可以实现基于优先级的调度算法。
l 其它函数
下面列出了线程/进程管理类的一些其它函数，其中多数是辅助实现函数。
一些其它函数
//获取当前进程的id。
int ProcessManagerImpl::getCurrentProcessId()
{
int currentThreadIndex = _pThreadReady[0];
return _pThreadInfo[currentThreadIndex].processId;
}
//获取当前线程的id。
int ProcessManagerImpl::getCurrentThreadId()
{
int currentThreadIndex = _pThreadReady[0];
return currentThreadIndex;
}
//获取进程的当前工作路径
const char *ProcessManagerImpl::getCurrentDir()
{
int processIndex = getCurrentProcessId();
return _pProcessInfo[processIndex].currentDir;
}
//设置进程的当前工作目录
void ProcessManagerImpl::setCurrentDir(const char *pathname)
{
int processIndex = getCurrentProcessId();
ProcessInternalInfo *process = _pProcessInfo + processIndex;
strncpy(process->currentDir, pathname, sizeof(process->currentDir)-1);
}
//查找未用的进程槽，返回索引。未找到返回-1。
int ProcessManagerImpl::find_free_process()
{
for (int i = 0; i < MAX_PROCESS_NUM; i++)
{
ProcessInternalInfo processInfo = _pProcessInfo[i];
if (processInfo.processId == -1)
return i;
}
return -1;
}
//查找未用的线程槽，返回索引。未找到返回-1。
int ProcessManagerImpl::find_free_thread()
{
for (int i = 0; i < MAX_THREAD_NUM; i++)
{
ThreadInternalInfo threadInfo = _pThreadInfo[i];
if (threadInfo.threadId == -1)
return i;
}
return -1;
}
//加入到就绪线程队列
void ProcessManagerImpl::addThreadReady(int threadIndex)
{
for (int i = 0; i < MAX_THREAD_NUM; i++)
{
if (_pThreadReady[i] == -1)
{
_pThreadReady[i] = threadIndex;
return;
}
}
}
//加入到阻塞线程队列
void ProcessManagerImpl::addThreadBlock(int threadIndex)
{
for (int i = 0; i < MAX_THREAD_NUM; i++)
{
if (_pThreadBlock[i] == -1)
{
_pThreadBlock[i] = threadIndex;
return;
}
}
}
//从就绪线程队列中删除
void ProcessManagerImpl::removeReadyThread(int threadIndex)
{
for (int i = 0; i < MAX_THREAD_NUM; i++)
{
if (_pThreadReady[i] == threadIndex)
{
int k;
for (k = i; k < MAX_THREAD_NUM-1; k++)
{
_pThreadReady[k] = _pThreadReady[k+1];
}
_pThreadReady[k]=-1;
break;
}
}
}
//从阻塞线程队列中删除
void ProcessManagerImpl::removeBlockThread(int threadIndex)
{
for (int i = 0; i < MAX_THREAD_NUM; i++)
{
if (_pThreadBlock[i] == threadIndex)
{
int k;
for (k = i; k < MAX_THREAD_NUM-1; k++)
{
_pThreadBlock[k] = _pThreadBlock[k+1];
}
_pThreadBlock[k]=-1;
break;
}
}
}
//删除一个线程（重置对应的线程槽）
void ProcessManagerImpl::removeThread(int threadIndex)
{
//释放线程的堆栈
char *pStack = _pThreadInfo[threadIndex].stackBase;
delete [] pStack;
//GetMemoryManager()->free(pStack);
//线程槽数据复位，相当于删除了这个线程
ThreadInternalInfo threadInfo;
_pThreadInfo[threadIndex] = threadInfo;
}
//删除一个进程（重置对应的进程槽）
void ProcessManagerImpl::removeProcess(int processIndex)
{
ProcessInternalInfo processInfo;
_pProcessInfo[processIndex] = processInfo;
}
//系统死机 - 通常由于内部错误导致无法处理的情况，就进入这里
void ProcessManagerImpl::system_dead()
{
//这里的打印有待改进，因为可能在内部栈上调用，内部栈不够printf使用...
printf("\nSorry, system is dead");
for (;;) ;
}
//线程等待事件，可能进入睡眠，直到事件变为信号状态而被唤醒
void ProcessManagerImpl::waitEvent(HANDLE hEvent)
{
int teststate = WaitForSingleObject(hEvent, 0);
if (teststate == WAIT_FAILED) //出错，可能句柄无效
return;
if (teststate == WAIT_OBJECT_0) //已经是有信号状态
return;
int currentThreadIndex = _pThreadReady[0];
_pThreadEvent[currentThreadIndex] = hEvent;
block();
}
//检查所有的等待事件，把这样的线程唤醒
void ProcessManagerImpl::checkThreadEvent()
{
for (int i = 0; i < MAX_THREAD_NUM; i++)
{
HANDLE hEvent = _pThreadEvent[i];
if (hEvent != INVALID_HANDLE_VALUE)
{
int teststate = WaitForSingleObject(hEvent,0);
if (teststate == WAIT_OBJECT_0)
{
wakeUp(i);
_pThreadEvent[i] = INVALID_HANDLE_VALUE; //清除事件
}
}
}
}
void ProcessManagerImpl::removeThreadEvent(int threadIndex)
{
_pThreadEvent[threadIndex] = INVALID_HANDLE_VALUE;
}
//使当前线程睡眠，放入阻塞队列，然后切换到下一个线程
void ProcessManagerImpl::block()
{
int currentThreadIndex = _pThreadReady[0];
int nextThreadIndex = _pThreadReady[1];
if (nextThreadIndex != -1)
{
removeReadyThread(currentThreadIndex);
addThreadBlock(currentThreadIndex);
//切换到下一个线程（成为当前）
int *pCurrentESP = &(_pThreadInfo[currentThreadIndex].esp);
int *pCurrentEIP = &(_pThreadInfo[currentThreadIndex].eip);
int nextESP = _pThreadInfo[nextThreadIndex].esp;
int nextEIP = _pThreadInfo[nextThreadIndex].eip;
threadSwitch(pCurrentESP,pCurrentEIP,nextESP,nextEIP);
}
else
{
//没有下一个可调度的线程，这种情况应该不会发生，
//因为process0总是存在，而且process0也不能调用导致阻塞的函数
system_dead();
}
}
//唤醒一个线程，即从阻塞队列移除，放到就绪队列
void ProcessManagerImpl::wakeUp(int threadIndex)
{
removeBlockThread(threadIndex);
addThreadReady(threadIndex);
}
//如果模拟系统还没有起来，就设置/获取错误代码，错误代码放在这里
static int _error;
//设置错误代码（最近一次系统调用）
//一些系统调用（如文件系统调用）出错时需要设置错误代码，使用户得知具体错误原因。
void ProcessManagerImpl::setError(int error)
{
int currentThreadIndex = _pThreadReady[0];
if (currentThreadIndex != -1)
_pThreadInfo[currentThreadIndex].error = error;
else
_error = error;
}
//取得错误代码
int ProcessManagerImpl::getError()
{
int currentThreadIndex = _pThreadReady[0];
int error;
if (currentThreadIndex != -1)
error = _pThreadInfo[currentThreadIndex].error;
else
error = _error;
return error;
}
l sleep的实现
sleep是一个常见的系统调用。在多任务系统中，其基本的含义就是挂起当前的进程/线程，把控制权交还系统。过了指定的一段时间后，由系统唤醒这个进程/线程。现在我们在模拟系统中实现sleep调用。由于模拟系统的共享式调度特点，决定了sleep的实现虽然尽力，却不能保证睡眠时间的精确性。在共享方式调度下，有几个机会控制权会交还给系统。一个是线程主动调用schedule()的时候，一个是线程运行结束的时候。模拟系统只有在这不多的机会里检查系统时间，以确定是否唤醒那些调用sleep进入阻塞的线程。检查时间的函数是checkSleepTimeout()，这个函数在shcedule()和thread_wrapper_func()里都被调用了。sleep的实现：计算和设置超时时间，然后调用block()挂起当前线程，即把此线程从就绪队列移到阻塞队列，然后切换到下一个就绪线程。checkSleepTimeout()的实现：检查线程的sleep超时时间值，若已到达，调用wakeUp()将此线程唤醒，即从阻塞队列移到就绪队列。
sleep的实现
//使当前线程睡眠指定的毫秒数
void ProcessManagerImpl::sleep(int msecs)
{
if (msecs <= 0)
return;
int sleepExpiredTickCount = GetTickCount() + msecs;
if (sleepExpiredTickCount <= 0)
return;
//把当前线程移到阻塞队列中，同时设置超时时间
int currentThreadIndex = _pThreadReady[0];
_pThreadSleepTimeout[currentThreadIndex] = sleepExpiredTickCount;
block();
}
//检查看是否有线程的睡眠时间到了，把所有这样的线程唤醒
void ProcessManagerImpl::checkSleepTimeout()
{
DWORD dwCurrentTickCount = GetTickCount();
for (int i = 0; i < MAX_THREAD_NUM; i++)
{
int sleepExpiredTickCount = _pThreadSleepTimeout[i];
if (sleepExpiredTickCount != -1
&& dwCurrentTickCount >= sleepExpiredTickCount)
{
//唤醒这个线程，具体就是将此线程从阻塞队列移到就绪队列
wakeUp(i);
_pThreadSleepTimeout[i] = -1; //超时值复位
}
}
}
l 锁的实现
在多任务系统中，互斥锁也是常见的。作为示例，这里实现了一种可重入的互斥锁。可重入是指如果获得一个锁的线程再次获取这个锁，也将成功，只是增加引用计数。在这个实现中，简单地用一个整数来代表一个锁，并简单地用两个数组来分别管理所有的锁和等待队列，请参考线程/进程实现类中的定义。lock()的实现：若这个锁被其它线程占用，就阻塞，否则获得它或者增加引用计数（如果之前已获得）。trylock()与lock相似，只是若发现锁被其它线程占用，就立即返回，否则占用这个锁。trylock()是一个不会阻塞的调用。unlock()的实现：锁的引用计数减一，如果已到0，就唤醒一个等待的线程（如果有），此线程将是该锁的新的拥有者。
锁的实现
void ProcessManagerImpl::lock(long lock)
{
int currentThreadIndex = _pThreadReady[0];
int lockIndex = findLock(lock);
if (lockIndex != -1)
{
Thread_Lock theLock = _pThreadLock[lockIndex];
if (currentThreadIndex != theLock.threadIndex)
{
//其它线程拥有这个锁，当前线程只能阻塞
addWait(currentThreadIndex, lock);
block();
//从阻塞中恢复，已经拥有这个锁了
}
else
{
//之前已获取过这个锁，引用数加1
theLock.refCount++;
_pThreadLock[lockIndex] = theLock;
}
}
else
{
//获得这个锁，继续运行
if (_threadLockCount < MAX_LOCK_NUM)
{
Thread_Lock theLock;
theLock.lock = lock;
theLock.threadIndex = currentThreadIndex;
theLock.refCount = 1;
_pThreadLock[_threadLockCount] = theLock;
_threadLockCount++;
}
}
}
//查找锁，若找到返回在数组中的索引，未找到返回-1。
int ProcessManagerImpl::findLock(long lock)
{
for (int i = 0; i < _threadLockCount; i++)
{
Thread_Lock theLock = _pThreadLock[i];
if (theLock.lock == lock)
return i;
}
return -1;
}
void ProcessManagerImpl::removeLockByIndex(int lockIndex)
{
for (int i = lockIndex; i < _threadLockCount-1; i++)
{
_pThreadLock[i] = _pThreadLock[i+1];
}
_threadLockCount--;
}
void ProcessManagerImpl::addWait(int threadIndex, long lock)
{
Thread_Wait wait;
wait.threadIndex = threadIndex;
wait.lock = lock;
_pThreadWait[_threadWaitCount] = wait;
_threadWaitCount++;
}
bool ProcessManagerImpl::trylock(long lock)
{
int currentThreadIndex = _pThreadReady[0];
int lockIndex = findLock(lock);
if (lockIndex != -1)
{
Thread_Lock theLock = _pThreadLock[lockIndex];
if (currentThreadIndex != theLock.threadIndex)
{
//其它线程拥有这个锁
return false;
}
else
{
//之前已获取过这个锁，引用数加1
theLock.refCount++;
_pThreadLock[lockIndex] = theLock;
return true;
}
}
else
{
//获得这个锁，继续运行
if (_threadLockCount < MAX_LOCK_NUM)
{
Thread_Lock theLock;
theLock.lock = lock;
theLock.threadIndex = currentThreadIndex;
theLock.refCount = 1;
_pThreadLock[_threadLockCount] = theLock;
_threadLockCount++;
return true;
}
}
return false;
}
void ProcessManagerImpl::unlock(long lock)
{
int currentThreadIndex = _pThreadReady[0];
int lockIndex = findLock(lock);
if (lockIndex != -1)
{
Thread_Lock theLock = _pThreadLock[lockIndex];
if (currentThreadIndex == theLock.threadIndex)
{
theLock.refCount--;
if (theLock.refCount <= 0)
{
int waitThreadIndex = removeWait(lock);
if (waitThreadIndex != -1)
{
//唤醒这个等待的线程
theLock.threadIndex = waitThreadIndex;
theLock.refCount = 1;
_pThreadLock[lockIndex] = theLock;
wakeUp(waitThreadIndex);
}
else
{
//没有其它线程等待这个锁，删除它
removeLockByIndex(lockIndex);
}
}
else
{
_pThreadLock[lockIndex] = theLock;
}
}
else
{
//当前线程不拥有这个锁
return;
}
}
else
{
//锁不存在
return;
}
}
//查找等待给定锁的线程，若找到，从等待中删除并返回线程号；若未找到返回-1。
int ProcessManagerImpl::removeWait(long lock)
{
int i;
for (i = 0; i < _threadWaitCount; i++)
{
if (_pThreadWait[i].lock == lock)
{
int threadIndex = _pThreadWait[i].threadIndex;
//删除这个元素（后续前移）
for (int k = i; k < _threadWaitCount-1; k++)
{
_pThreadWait[k] = _pThreadWait[k+1];
}
_threadWaitCount--;
return threadIndex;
}
}
return -1;
}
多线程/进程测试运行
l 进入模拟多线程环境
我们的模拟程序通常作为宿主机上的一个进程来运行。当模拟系统启动时，从main函数开始运行。 main函数使用宿主系统提供的堆栈。我们就在main函数中创建模拟系统的第一个进程，这个进程的id为0。为此，线程/进程管理实现类提供了一个runProcess0函数，这个函数创建模拟系统中的第一个可调度进程，并立刻运行它。
runProcess0函数
//运行第一个进程，进程id为0。使用程序当前的堆栈。
int ProcessManagerImpl::runProcess0(THREAD_PROC threadProc, void *parameter)
{
//第一个进程/线程，进程/线程号应该为0
int freeProcessIndex = find_free_process();
if (freeProcessIndex != 0)
return -1;
int freeThreadIndex = find_free_thread();
if (freeThreadIndex != 0)
return -1;
ProcessInternalInfo processInfo;
processInfo.processId = freeProcessIndex;
ThreadInternalInfo threadInfo;
threadInfo.processId = freeProcessIndex;
threadInfo.threadId = freeThreadIndex;
//我们把stackBase设为NULL，表示使用程序当前的栈
threadInfo.stackBase = NULL;
threadInfo.stackSize = 0;
threadInfo.threadProc = threadProc;
threadInfo.parameter = parameter;
//不必准备线程初始的esp和eip，因为下面即刻转去执行
_pProcessInfo[freeProcessIndex] = processInfo;
_pThreadInfo[freeThreadIndex] = threadInfo;
//新线程加入就绪队列
addThreadReady(freeThreadIndex);
int ret = threadProc(parameter);
return ret;
}
这个函数与createProcess相似，所不同的是它不必为第一个进程/线程创建堆栈，而是直接用模拟程序的堆栈。另外不必初始化线程数据结构中的esp和eip，因为第一个线程是马上运行的。runProcess0()的效果是将模拟系统的（宿主机）主线程平滑地变成模拟系统中的一个进程/线程，而且是第一个。现在我们可以写出main函数的一个简单框架。
main函数的框架
ProcessManagerImpl *_process_manager;
//进程0的主线程函数
int thread0_proc(void *parameter)
{
return 0;
}
int main(int argc, char *argv[])
{
if (!init())
return -1;
//运行进程0
int ret = _process_manager->runProcess0(thread0_proc, NULL);
unInit();
return ret;
}
main函数的框架一目了然，在init中做一些初始化工作之后，就运行第一个进程。第一个进程负责产生其它的进程。第一个进程退出时，模拟系统就退出了，unInit完成清理工作。这里第一个线程函数thread0_proc还没有做任何事，似乎没有用处，但在示例代码中将给出一些测试例子。
l 使用自己的内存管理
内存管理通常都是系统的一个基本任务。这个模拟系统也实现了简单内存管理，参见后面的内存管理部分。模拟系统可以使用宿主系统提供的内存管理，也可以使用自己的内存管理。为了使用自己的内存管理，我们重载C++的new和delete运算符，使得对内存的分配和释放操作都是在一块我们管理的内存上进行。
重载new和delete
extern MemoryManager *_memory_manager;
void *operator new(size_t size)
{
return _memory_manager->alloc(size);
}
void operator delete(void *p)
{
_memory_manager->free(p);
}
l 示例代码
示例代码1
static MemoryManagerImpl _memory_manager_impl;
MemoryManager *_memory_manager;
ProcessManagerImpl *_process_manager;
bool init()
{
int managed_memory_size = 30 * 1024 * 1024;
_memory_manager_impl.setManagedMemory(managed_memory_size);
_memory_manager = &_memory_manager_impl;
_process_manager = new ProcessManagerImpl;
return _process_manager->initManageData();
}
void unInit()
{
delete _process_manager;
}
//进程1的主线程函数
int process1_thread1(void *parameter)
{
while (1)
{
int processId = _process_manager->getCurrentProcessId();
int threadId =_process_manager->getCurrentThreadId();
printf("in process %d, thread %d\n", processId, threadId);
//Sleep(500);
_process_manager->schedule();
}
return 0;
}
//进程0的主线程函数
int thread0_proc(void *parameter)
{
printf("\npress any key to start\n");
getch();
int processId = _process_manager->createProcess(process1_thread1, NULL);
while (1)
{
printf("in process0\n");
_process_manager->schedule();
}
return 0;
}
这个例子中使用了自己的内存管理，由于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
int process1_thread2(void *parameter)
{
while (1)
{
printf("in process1_thread2\n");
_process_manager->sleep(30);
}
return 0;
}
int process1_thread1(void *parameter)
{
int threadId = _process_manager->createThread(process1_thread2, NULL);
while (1)
{
int processId = _process_manager->getCurrentProcessId();
int threadId =_process_manager->getCurrentThreadId();
printf("in process %d, thread %d\n", processId, threadId);
_process_manager->sleep(50);
}
return 0;
}
这个例子中，进程1的主线程中，通过createThread创建了另一个线程。这样进程1就有两个线程了。这两个线程不再调用shcedule()，而是调用sleep()函数。运行这个例子，就会看到系统中有三个线程都在运行。有一点请注意，不要在thread0中调用sleep或其它导致阻塞的函数，免得模拟系统遇到没有线程可以调度的情况。至于线程锁，可以类似写些测试代码，包括测试线程之间的死锁，这里不再多说了。
内存管理
内存管理向来是操作系统的一个基本任务。我们的模拟系统当前只实现了简单的内存管理。它的目标是管理向宿主机系统申请的一块内存，把它看作是模拟系统的可分配内存空间，满足在这个内存空间上的申请和释放操作。
内存管理接口
内存管理接口定义
class MemoryManager
{
public:
//申请一块内存，size为申请的字节数
virtual void *alloc(int size) = 0;
//释放先前申请的内存
virtual void free(void *memblock) = 0;
};
一个简单的实现
下面是内存管理的一个简单实现。其基本思路是用一些控制块来管理内存的分配。每一块已分配的内存，都有一个控制块（Mem_Ctrl_Block），指出这块已分配内存的大小。为了简单，控制块与已分配内存块紧挨在一起，且在已分配内存块的前面。控制块中有个指针，指向下一个已分配内存的控制块。这样，所有已分配内存的控制块，由低地址往高地址形成了一个单向链表。分配内存的时候，先找链表的两头，看看有无够用空闲内存。若没有就顺着链表，依次看两个控制块之间，有无足够空闲内存用来分配。若找到就建立一个控制块，或插入到链表中，或放到链表的头或尾。释放一块已分配内存的时候，就寻找相应的控制块，找到就从链表中删除。
内存管理实现类的定义
class MemoryManagerImpl : public MemoryManager
{
public:
MemoryManagerImpl();
virtual ~MemoryManagerImpl();
//设置被管理的内存大小，这块内存可以从外面传入。
//如果memory为NULL，这块内存将内部申请。
void setManagedMemory(int size, void *memory = NULL);
int getManagedSize() const;
//申请一块内存，size为申请的字节数
virtual void *alloc(int size);
//释放先前申请的内存
virtual void free(void *memblock);
protected:
struct Mem_Ctrl_Block
{
int reserved;
int size;
void *next; //按地址顺序指向下一个Mem_Ctrl_Block
};
void *memory_to_manage;
int size_to_manage;
bool memory_need_free;
//指向第一块已分配的内存
Mem_Ctrl_Block *first_mem_block;
//指向最后一块已分配的内存
Mem_Ctrl_Block *last_mem_block;
}
内存管理类的实现
MemoryManagerImpl::MemoryManagerImpl()
{
memory_to_manage = NULL;
size_to_manage = 0;
first_mem_block = NULL;
last_mem_block = NULL;
memory_need_free = false;
}MemoryManagerImpl::~MemoryManagerImpl()
{
if (memory_need_free)
::free(memory_to_manage);
}void MemoryManagerImpl::setManagedMemory(int size, void *memory)
{
if (memory == NULL)
{
memory_to_manage = ::malloc(size);
memory_need_free = true;
}
else
{
memory_to_manage = memory;
memory_need_free = false;
}
size_to_manage = size;
}int MemoryManagerImpl::getManagedSize() const
{
return size_to_manage;
}//申请一块内存，size为申请的字节数
void *MemoryManagerImpl::alloc(int size)
{
//在下面的分配实现中，控制节点与返回给用户的内存挨在一起
//（在用户内存的前面就是控制节点）
//检查大小是否合理。这个检查也为了防止计算溢出错误
if (size < 0 || size > size_to_manage)
return NULL;
int need_size = sizeof(Mem_Ctrl_Block) +size;
if (need_size < 0)
return NULL;
if (first_mem_block == NULL)
{
if (need_size <= size_to_manage)
{
first_mem_block = (Mem_Ctrl_Block *)memory_to_manage;
first_mem_block->size = size;
first_mem_block->next = NULL;
last_mem_block = first_mem_block;
return (char *)first_mem_block + sizeof(Mem_Ctrl_Block);
}
else
return NULL;
}
//检查第一个已分配的内存块之前有无足够空闲空间，若有，直接分配
if (first_mem_block != memory_to_manage
&& (need_size <= (char *)first_mem_block - (char *)memory_to_manage))
{
Mem_Ctrl_Block *new_first = (Mem_Ctrl_Block *)memory_to_manage;
new_first->size = size;
new_first->next = first_mem_block;
first_mem_block = new_first;
return (char *)first_mem_block + sizeof(Mem_Ctrl_Block);
}
//检查最后一个已分配的内存块之后有无足够空闲空间，若有，直接分配
Mem_Ctrl_Block *after_last = (Mem_Ctrl_Block *)((char *)last_mem_block+ sizeof(Mem_Ctrl_Block) + last_mem_block->size);
if ( need_size <= ((char *)memory_to_manage + size_to_manage - (char *)after_last))
{
//Ok，有足够空闲内存
after_last->size = size;
after_last->next = NULL;
last_mem_block->next = after_last;
last_mem_block = after_last;
return (char *)last_mem_block + sizeof(Mem_Ctrl_Block);
}
//沿着已分配的内存块链表搜索下去，查找两个块中间有足够大的空闲可以分配
Mem_Ctrl_Block *current = first_mem_block;
while (current != last_mem_block)
{
Mem_Ctrl_Block *next_block = (Mem_Ctrl_Block *)current->next;
Mem_Ctrl_Block *after_current = (Mem_Ctrl_Block *)((char *)current+ sizeof(Mem_Ctrl_Block) + current->size);
if (need_size <= (char *)next_block - (char *)after_current)
{
//Ok, 两个已分配块之间有足够的空闲内存，可以分配
after_current->next = next_block;
after_current->size = size;
current->next = after_current;
return (char *)after_current + sizeof(Mem_Ctrl_Block);
}
else
current = next_block;
}
return NULL;
}//释放先前申请的内存
void MemoryManagerImpl::free(void *memblock)
{
if (first_mem_block == NULL)
return;
if ((char *)first_mem_block + sizeof(Mem_Ctrl_Block) == memblock)
{
//释放第一个块
Mem_Ctrl_Block *old_first = first_mem_block;
first_mem_block = (Mem_Ctrl_Block *)first_mem_block->next;
old_first->next = NULL; /