第三章处理程序与执行绪的描述和排程
这个章节将详细介绍Windows CE 系统中的处理程序 (process) 和执行绪(thread)，并对Windows CE操作系统所使用的排程策略进行分析。处理程序是资源分配的基本单位，而执行绪是排程的基本单位。这一章的程序代码主要节选于[CEROOT]PRIV ATE\WINCEOS\COREOS\NK\KERNEL\ 目录的 schedule.c、intrapi.c 以及 [CEROOT]PRIV ATE\WINCEOS\COREOS\NK\INC 目录的schedule.c、kernel.h的几个档案，其目的在于了解程序在开发执行时，对系统资源的共享以及程序的排程。
3.1 处理程序的定义和描述
3.1.1 处理程序概述
处理程序是一个具有一定独立功能之程序的动态执行过程。处理程序由正文段 (text)、用户数据段 (user segment) 以及系统数据段 (system segment) 共同组成一个执行环境，负责处理器、内存和外围等资源的分配和回收。处理程序是计算机系统资源的使用主体，是操作系统分配资源的基本单位。
处理程序具有动态性、独立性、并行性和结构化等特征。动态性是指处理程序具有动态的地址空间，地址空间的大小和内容都是动态变化的。地址空间的内容包括程序代码(指令执行和处理器状态的改变)、数据(变量的生成和初始化) 和系统控制信息(PCB (Process Control Block) 的生成和删除)。独立性是指各个处理程序的地址空间相互独立，除非采用处理程序间通信服务，否则不能相互影响。并行性也称为异步性，是指从宏观上来看，各个处理程序是同时独立运行的。结构化是指处理程序对于地址空间的结构划分，如程序代码段、数据段和核心段划分。
我们必须了解处理程序和程序的区别，程序是一个普通档案，是一个程序代码指令和数据的集合，这些指令和程序代码储存在磁盘上成为可执行映像(Executable Image)，是一个静态的实体。我们可以用下面简单的方式了解处理程序和程序的关系：
1.处理程序和程序的关系
程序是处理程序的两个重要组成之一。处理程序的主要目的是执行它所对应的程序。
2.处理程序和程序的区别
主要有以下三种：
z程序是静态的，处理程序是动态的；
z程序可以在储存设备(如：磁盘) 上长期保存，而处理程序则是在建立处理程序后产生，结束处理程序后消失。
z一个程序可以对应多个处理程序，但是一个处理程序只能对应一个程序。例如：打开Word的两个窗口，编辑两个不同的文字文件，就对应
到两个不同的处理程序。
3.1.2 Windows CE处理程序的描述
Windows CE的处理程序不同于Windows 98或Windows NT，最大差别在于 Windows CE最多只可以支持32个处理程序在系统中同时运行，系统启动的时候，将至少自动启动四个处理程序，一个是NK.exe，用来提供操作系统中kernel 的服务，第二个是FILESYS.EXE，它用来提供相关档案系统的服务，第三个是GWES.EXE，它用来提供对GUI系统的支持，第四个是DEVICE.EXE，它用来加载和管理外围的驱动程序。他们占据虚拟地址的前四个slots，一个slot有32MB 空间，详见资料储存部分的介绍，目前执行的处理程序将会对应到第一个slot (slot 0)。大部分的Windows CE系统，也会同时建立EXEPLORER.EXE处理程序﹔如果Windows CE系统正在与个人计算机相连，则会启动REPLLOG.EXE和PAPISRV.EXE，他们用来管理个人计算机和Windows CE系统之间的连接服务。所以使用者可以启动的处理程序最多大概有24个，或稍微多一点，但是对一般的使用来说，这是足够的。
不同于Windows 98或Windows NT系统，Windows CE系统不支持一些功能，例如Windows CE系统不支持许多处理程序和与执行绪相关的函数。Windows CE 系统不支持环境 (environment)，所有与处理环境有关的Win32函数在Windows CE系统中并不存在。
3.1.3 Windows CE处理程序结构分析
在Windows CE中，每一个处理程序由一个程序结构来描述。也就是我们平时说的PCB。它定义于NK/INC/kernel.h。处理程序的所有信息都保存在这个结构中，当系统建立一个处理程序时，将分配一个新的程序结构，处理程序结束时，这个结构将被回收。
与Windows 98或Windows NT的处理程序相比较，Windows CE处理程序包含比较少的状态信息。由于Windows CE不支持驱动程序及工作目录 (Working Directory) 的概念，所以每个处理程序不需要保存这些信息。Windows CE也不需要保存一系列的环境变量，所以PCB中不需要有关于环境变量的部分。Windows CE不支持句柄继承，所以也不需要告诉处理程序这些相关的信息。由于以上种种原因，Windows CE处理程序的结构相对地简单很多。
处理程序是系统资源分配的基本单位，为方便管理，在Windows CE中把处理程序当作对象 (HANDLE hProc)。下面将简单介绍一个程序结构的主要部分：z procnum：BYTE类别，目前处理程序的识别号码 (ID)，用来辨识不同的处理程序。
z pProxList：存放proxy的队列，LPPROXY结构的链接。
z hProc：这是此处理程序的句柄，在呼叫SC_GetProcFromPtr时使用。
z dwVMBase：DWORD类别，记录处理程序在内存所占区域中的基地址。z pTh：一个处理程序可能拥有多个执行绪(详见执行绪介绍部分)， pTh表示当前处理程序中的第一个执行绪。
z BasePtr：LPVOID类别，指向载入.EXE可执行档的基底指标。
z lpszProcName：LPWSTR类别，记录处理程序的名称。
z PfnEH：处理程序例外处理器，PEXCEPTION_ROUTINE类别。
z pMainTh：此处理程序所拥有的主执行绪，当主执行绪结束后，处理程序也随之结束。
z pmodResource：PMODULE类别，MODULE结构在NK/INC/kernel.h中所定义。包含资源的模块指针，其中的资源可以被目前的处理程序用到。
z oe：openexe_t类别。指向可执行档句柄的指标。
为了让读者容易理解，下面列出Windows CE中所定义的程序结构。
程序的结构如下：
程序代码3.1
struct Process {
BYTE procnum; /* 00: ID of this process [ie: it's slot number] */
BYTE DbgActive; /* 01: ID of process currently DebugActiveProcess'ing this process */ BYTE bChainDebug /* 02: Did the creator want to debug child processes? */
BYTE bTrustLevel; /* 03: level of trust of this exe */
#define OFFSET_TRUSTLVL 3 // offset of the bTrustLevel member in Process structure
LPPROXY pProxList; /* 04: list of proxies to threads blocked on this process */
HANDLE hProc; /* 08: handle for this process，needed only for
SC_GetProcFromPtr
*/
DWORD dwVMBase; /* 0C: base of process's memory section，or 0 if not in use */
PTHREAD pTh; /* 10: first thread in this process */
ACCESSKEY aky; /* 14: default address space key for process's threads */
LPVOID BasePtr; /* 18: Base pointer of exe load */
HANDLE hDbgrThrd; /* 1C: handle of thread debugging this process， if any */
LPWSTR lpszProcName; /* 20: name of process */
DWORD tlsLowUsed; /* 24: TLS in use bitmask (first 32 slots) */
DWORD tlsHighUsed; /* 28: TLS in use bitmask (second 32 slots) */
PEXCEPTION_ROUTINE pfnEH; /*2C: process exception handler */
LPDBGPARAM ZonePtr; /* 30: Debug zone pointer */
PTHREAD pMainTh; /* 34 primary thread in this process*/
PMODULE pmodResource; /* 38: module that contains the resources */
LPName pStdNames[3]; /* 3C: Pointer to names for stdio */
LPCWSTR pcmdline; /* 48: Pointer to command line */
DWORD dwDyingThreads; /* 4C: number of pending dying threads */
openexe_t oe; /* 50: Pointer to executable file handle */
e32_lite e32; /* ??: structure containing exe header */
o32_lite *o32_ptr; /* ??: o32 array pointer for exe */
LPVOID pExtPdata; /* ??: extend pdata */
BYTE bPrio; /* ??: highest priority of all threads of the process */
BYTE fNoDebug; /* ??: this process cannot be debugged */
WORD wPad; /* padding */
}; /* Process */
3.1.4 处理程序的同步与互斥
Windows CE在 NK\INC\schedule.h中定义了event (相当于触发器，可以用于通知个别或多个执行绪某个event的出现)、mutex与 semaphore三种同步对象。而在NK\kernel.c中定义了这些同步对象的系统呼叫，可以用于处理程序或者执行绪的同步和互斥。
具体关于semaphore、mutex、event的机制不再介绍，这跟在Windows 2000中的semaphore、mutex、event有一定的相同之处，读者可以参考Windows 2000中的对应结构以获得更一步的了解，这里只介绍相关的API函数。
1.event
event是同步对象之一，用于通知执行绪事件的发生，有signaled和nonsignaled两种状态。建立时可以选择自动从signaled状态恢复到nonsignaled 状态，或者手动恢复。从Windows CE 2.0开始，event可以被命名，因此可以被处理程序用于同步通信的共享。与事件相关的API有：SC_CreateEvent，用于建立一个event并传回相应的句柄﹔SC_OpenEvent，用于打开一个已经存在的event，并传回相应的句柄﹔SC_EventCloseHandle，用于关闭一个event等等。下面以其中的部分函数为例，进行简单的说明。
函数原型：
HANDLE CreateEvent (
LPSECURITY_ATTRIBUTES lpEventAttributes，
BOOL bManualReset，
BOOL bInitialState，
LPTSTR lpName
);
要达到处理程序间的event共享，处理程序必需各自建立一个相同名字的event，而不能只在单一处理程序中建立，再把句柄交给其余处理程序使用。要用它来发号志，可以使用以下函数：
BOOL SetEvent (HANDLE hEvent ); //只释放一个等待的执行绪
BOOL PulseEvent (HANDLE hEvent ) ; //释放所有等待的执行绪
BOOL ResetEvent (HANDLE hEvent ) ; //手动恢复nonsignal状态
与mutex的API有：SC_CreateMutex、SC_ReleaseMutex等等，分别用来建立和释放一个mutex，这里不再详细说明，请读者自己参阅Windows 2000对应函数的说明。
与semaphore有关的API有：SC_CreateSemaphore、SC_ReleaseSemaphore、SC_SemCloseHandle等等，分别用来建立semaphore，释放semaphore，以及关闭一个semaphore的句柄时使用，这里也不详细说明，请读者参阅Windows 2000对应函数的说明。
2.相关的等待函数
DWORD WaitForSingleObject ( HANDLE hHandle，DWORD dwMilliseconds ) ;
作用：执行绪等待一个event，用于停滞 (Block) 执行绪直到等待的event发出信号或者预定的时间到达。其回传值表明了等待结束的原因，回传值可能如下：WAIT_OBJECT_0 //指定的event发出信号
WAIT_TIMEOUT //时间到，但等待的event没有发出信号
WAIT_ABANDONED//被等待的执行绪结束了，但没有释放event
WAIT_FAILED //同步对象的句柄不合法
DWORD WaitForMultipleObjects (DWORD nCount, CONST HANDLE *lpHandles, BOOL bWaitAll,
dwMilliseconds);
DWORD
作用：执行绪等待多个event，Windows CE不允许等待所有event发信号，所以bWaitAll只能为FALSE，当任何一个event发信号时，函数就返回。其回传值与前一函数基本相同，只是如果是event发出信号而返回时，回传值为WAIT_OBJECT_0加上同时发出信号事件的句柄 (handle) 中最小的注标(即
lpHandles发出信号事件中最小的注标)。
3.2 执行绪介绍
3.2.1 执行绪概述
从60年代处理程序的概念提出以来，处理程序就一直是操作系统独立运行的基本单位，在多个处理程序同时执行时，处理程序切换的系统负荷却非常的大，在此同时，处理程序间数据共享的效率亦受到高度重视。80年代中，人们提出了比处理程序更小、且能独立运行的基本单位——执行绪 (thread)，目的是用来减少程序同时执行时所需要的事件和空间使用，提高处理程序的并行性。
1.执行绪的概念：
执行绪是处理程序的一个实体，是CPU排程和分配的基本单位，除了一些在运行中必要的资源(例如：程序计数器，一些缓存器和堆栈)，执行绪基本上不拥有系统资源，但是执行绪可以和同属于同一个处理程序的其它执行绪共享处理程序所拥有的全部资源。一个执行绪可以建立和撤销另一个执行绪，同一个处理程序内的执行绪也可以并行执行。
执行绪具有处理程序所具有的许多特征，所以又被称为轻量级处理程序。通常一个处理程序都有至少有一个以上的执行绪 (Windows CE中是主执行绪)。下面将简单地比较执行绪和处理程序的差别：
z排程方面：传统操作系统中，处理程序是分配资源，独立排程和分派的基本单位。引入执行绪后，执行绪是排程和分派的基本单位，处理程序
仍然是拥有资源的基本单位。将原本处理程序的两个属性分开(为资源
分配与排程的基本单位)，执行绪成为排程的基本单位后，执行绪就可以
轻装执行，这样可以显著提高系统的并行程度，同一处理程序内部执行
绪的切换并不需要处理程序的切换。
z并行性：引入执行绪，不仅在处理程序之间可以并行执行，而且在一个处理程序中的多个执行绪之间也可以并行执行，因此操作系统具有更好
的并行性，并且能更有效的使用系统资源及提高系统的效率。
z资源之拥有：处理程序是一个拥有资源的独立单位，一般来说，执行绪不拥有自己的系统资源，它使用其所属的处理程序的资源。
系统负荷：由于处理程序的建立、结束或切换时，系统都要为处理程序分配、回收或暂存资源，付出的代价比较大，而执行绪的建立、结束及切换所需要和保存的资源(如：缓存器) 较少，所以执行绪之各项系统负荷远远小于处理程序所需。
2.引入执行绪的优点：
z建立一个新执行绪的负担比建立处理程序少得多。建立执行绪不需要额外分配大量资源，所以相对于建立处理程序，建立执行绪的速度要快得非常多，而且系统的负担也非常小。
z两个执行绪之间的切换时间非常的快。
z在同一个处理程序内的执行绪共享处理程序所拥有的资源(包括内存和档案等)，所以执行绪之间的数据共享不需要额外的机制﹔简化的通讯方式，
也使数据交换速度得以加快。
z执行绪能独立执行，所以能充分利用和发挥处理器与外围设备的并行工作能力。
3.2.2 Windows CE执行绪的结构分析
在Windows CE中，每一个执行绪由一个在NK/INC/kernel.h中定义的thread
结构所描述。下面对执行绪的数据结构进行大致的分类：
1.wInfo信息：
它是一个16位的无符号整数 (unsigned integer)，包括下列信息(见表3.1)：
表3.1 wInfo信息
名称说明
TIMEMODE_SHIFT 执行绪所处的时间模式
RUNSTATE_SHIFT 执行绪是否可执行
BURIED_SHIFT 隐藏偏移
SLEEPING_SHIFT 执行绪是否在睡眠
DEBUGBLK_SHIFT 是否启动侦错，暂停了执行绪
DYING_SHIFT 是否被设定为结束
STACKFAULT_SHIFT 堆栈错误信息
DEAD_SHIF 执行绪有关结束的信息
NEEDDBG_SHIFT 执行绪是否要侦错
profiling PROFILE_SHIFT Montecarlo NOPRIOCALC_SHIFT 非优先级计算位
DEBUGWAIT_SHIFT 执行绪侦错等待信息
USERBLOCK_SHIFT 执行绪是否可以自动进入停滞状态NEEDSLEEP_SHIFT 执行绪是否应该放回睡眠队列中
我们可以透过在kernel.h中定义的偏移量来获得以上的信息：
2位 ( bit )
#define RUNSTATE_SHIFT 0 //
1位
#define DYING_SHIFT 2 //
1位
#define DEAD_SHIFT 3 //
1位
#define BURIED_SHIFT 4 //
1位
#define SLEEPING_SHIFT 5 //
1位
#define TIMEMODE_SHIFT 6 //
1位
#define NEEDDBG_SHIFT 7 //
1位
#define STACKFAULT_SHIFT 8 //
1位
#define DEBUGBLK_SHIFT 9 //
1位
#define NOPRIOCALC_SHIFT 10 //
1位
#define DEBUGWAIT_SHIFT 11 //
1位
#define USERBLOCK_SHIFT 12 //
#ifdef DEBUG
1位(仅在侦错时使用)
#define DEBUG_LOOPCNT_SHIFT 13 //
#endif
1位
#define NEEDSLEEP_SHIFT 14 //
1位，必须是15，透过汇编语言来使用#define PROFILE_SHIFT 15 //
2.各种链接信息
一个执行绪属于某个处理程序，一个处理程序中可能同时有多个执行绪，排程以执行绪为基本单位，某个执行绪可能正在执行，可能处于可执行队列，也可能处于睡眠队列，所以需要各种连结信息来联系不同的执行绪，执行绪的一些主要连接信息如表3.2所示：
表 执行绪的一些主要连接信息
名称描述
PnextInProc 指向目前处理程序的下一个执行绪Pproc 指向目前处理程序的指针PprevInProc 目前处理程序的上一个执行绪POwnerProc 指向父处理程序的指针pNextSleepRun 下一个睡眠的执行绪，或者是下一个可
执行的执行绪
pPrevSleepRun 上一个睡眠的或可执行的执行绪pUpRun; 指向上一个执行绪，它执行完后自己才
可以执行
pDownRun 指向等待此执行绪执行完后才可执行
的执行绪
pUpSleep 指向上一个执行绪，它执行完后自己才
被唤醒
pDownSleep 指向等待此执行绪执行完后才唤醒的
执行绪
3.执行绪排程信息
系统透过排程信息来决定让那一个执行绪运行，这主要由执行绪的目前优先级 (bCPrio) 决定，而透过执行绪的时间片段 (dwQuantum) 信息，系统可以决定让执行绪执行多长的时间。由于使用preemptive round-robin排程算法，所以一个正在执行的执行绪被preempted后，它所剩下的时间信息也要保留。
表3.3 执行绪数据结构中的一些排程相关信息
名称含义
bBPrio 基本的优先级
bCPrio 目前优先级
dwQuantum 执行绪所拥有的时间片段dwQuantLeft 执行绪所剩下的时间片段
4.执行绪时间信息
执行绪从建立到结束间有一个生命周期，kernel需要记录并统计执行绪所耗费的CPU时间。这个时间分为user-mode时间和kernel-mode时间，每个时间中断，kernel都要更新先前正在执行的执行绪所耗费的时间信息。除了这些，还有一些其它的相关信息，表3.4中列出了一些比较重要的时间信息：
表3.4 执行绪时间信息
名称描述
ftCreate 执行绪建立的时间
dwKernTime 执行绪在kernel-mode所消耗的时间dwUserTime 执行绪在user-mode所消耗的时间dwPendTime 执行绪等待操作的最长等待时间dwPendWakeup 执行绪等待的最长时间
5.一些有关计数的信息
wCount用于停滞执行绪队列的计数，wCount2用于睡眠队列的计数。
WORD wCount; /* nonce for blocking lists */停滞队列的当前计数
WORD wCount2; /* nonce for SleepList */睡眠队列的当前计数
WORD
wCrabCount;
6.有关Windows CE排程
CE是基于preeemptive的time-sliced round-robin来进行排程，系统 Windows
可能要在同的执行绪之间切换，所以切换时必须保存执行绪的上下文 (context) 信息。
cpu context information */
thread's
CPUCONTEXT ctx; /*
为方便读者理解，下面列出Windows CE中所定义的Thread结构：
程序代码3.2
struct Thread {
WORD wInfo; /* 00: various info about thread，see above */
BYTE bSuspendCnt; /* 02: thread suspend count */
BYTE bWaitState; /* 03: state of waiting loop */
LPPROXY pProxList; /* 04: list of proxies to threads blocked on this thread */ PTHREAD pNextInProc; /* 08: next thread in this process */
PPROCESS pProc; /* 0C: pointer to current process */
PPROCESS pOwnerProc; /* 10: pointer to owner process */
ACCESSKEY aky; /* 14: keys used by thread to access memory & handles */ PCALLSTACK pcstkTop; /* 18: current api call info */
DWORD dwOrigBase; /* 1C: Original stack base */
DWORD dwOrigStkSize; /* 20: Size of the original thread stack */
LPDWORD tlsPtr; /* 24: tls pointer */
DWORD dwWakeupTime; /* 28: sleep count，also pending sleepcnt on waitmult */ LPDWORD tlsSecure; /* 2c: TLS for secure stack */
LPDWORD tlsNonSecure; /* 30: TLS for non-secure stack */
LPPROXY lpProxy; /* 34: first proxy this thread is blocked on */
DWORD dwLastError; /* 38: last error */
HANDLE hTh; /* 3C: Handle to this thread，needed by NextThread */ BYTE bBPrio; /* 40: base priority */
BYTE bCPrio; /* 41: curr priority */
WORD wCount; /* 42: nonce for blocking lists */
PTHREAD pPrevInProc; /* 44: previous thread in this process */
LPTHRDDBG pThrdDbg; /* 48: pointer to thread debug structure，if any */
LPBYTE pSwapStack; /* 4c */
FILETIME ftCreate; /* 50: time thread is created */
CLEANEVENT *lpce; /* 58: cleanevent for unqueueing blocking lists */
DWORD dwStartAddr; /* 5c: thread PC at creation，used to get thread name */ CPUCONTEXT ctx; /* 60: thread's cpu context information */
PTHREAD pNextSleepRun; /* ??: next sleeping thread，if sleeping；
next runnable thread on runq，if runnable */ PTHREAD pPrevSleepRun; /* ??: back pointer if sleeping or runnable */
PTHREAD pUpRun; /* ??: up run pointer (circular) */
PTHREAD pDownRun; /* ??: down run pointer (circular) */
PTHREAD pUpSleep; /* ??: up sleep pointer (null terminated) */
PTHREAD pDownSleep; /* ??: down sleep pointer (null terminated) */
LPCRIT pOwnedList; /* ??: list of crits (critical section) and mutexes for priority
*/
inversion
LPCRIT pOwnedHash[PRIORITY_LEVELS_HASHSIZE];
DWORD dwQuantum; /* ??: thread quantum */
DWORD dwQuantLeft; /* ??: quantum left */
LPPROXY lpCritProxy; /* ??: proxy from last critical section block，in case stolen back
*/
LPPROXY lpPendProxy; /* ??: pending proxies for queueing */
DWORD dwPendReturn; /* ??: return value from pended wait */
DWORD dwPendTime; /* ??: timeout value of wait operation */
PTHREAD pCrabPth;
WORD wCrabCount;
WORD wCrabDir;
DWORD dwPendWakeup; /* ??: pending timeout */
WORD wCount2; /* ??: nonce for SleepList */
BYTE bPendSusp; /* ??: pending suspend count */
BYTE bDbgCnt; /* ??: recursive level in debug message */
HANDLE hLastCrit; /* ??: Last crit taken，cleared by nextthread */
DWORD dwCrabTime;
CALLSTACK IntrStk;
DWORD dwKernTime; /*
elapsed kernel time */
??:
DWORD dwUserTime; /* ??: elapsed user time */
}; /* Thread */
3.3 其它一些重要的数据结构
在schedule.h和schedule.c中还有一些重要的数据结构，这些数据结构在排程过程中有着非常大的影响，下面列出几个主要的结构。
z schedule.h中有关于执行绪时间的数据结构：
typedef struct THREADTIME {
struct THREADTIME *pnext;
HANDLE hTh;
FILETIME CreationTime;
FILETIME ExitTime;
FILETIME KernelTime;
FILETIME UserTime;
} THREADTIME, *LPTHREADTIME; /*建立时间*/
/*结束时间*/
/*kernel-mode时间*/ /*user-mode时间*/
z有关临界区的数据结构：typedef struct CRIT {
LPCRITICAL_SECTION lpcs;
LPPROXY pProxList;
LPPROXY pProxHash[PRIORITY_LEVELS_HASHSIZE]; LPCRIT pPrev;
BYTE bListed;
BYTE bListedPrio;
BYTE iOwnerProc;
BYTE bPad;
struct CRIT * pPrevOwned;
struct CRIT * pNextOwned;
struct CRIT * pUpOwned;
struct CRIT * pDownOwned;
LPCRIT pNext;
} CRIT; /* Pointer to a critical_section structure */
/* previous event in list */
/* Is this on someone's owner list */
/* Index of the owner process */
/* Prev crit/mutex (for prio inversion) */
/* Next crit/mutex section owned (for prio inversion) */ /* Next CRIT in list */
z有关可执行执行绪队列的数据结构：typedef struct {
PTHREAD pRunnable;
PTHREAD pth;
PTHREAD pHashThread[PRIORITY_LEVELS_HASHSIZE]; } RunList_t; /* 可执行执行绪的队列*/ /* 目前正在执行的执行绪*/
pRunnable 是指向可执行队列的指针，这个队列是由双向连结串行(doubly-linked list) 组成的。PRIORITY_LEVELS_HASHSIZE 的值是 256，所以，pHashTable 共有 256 个entry，每一个entry各指向一个优先权等级大小不同的执行绪队列。
z有关执行绪等待队列的数据结构：
typedef struct sleeper_t {
PTHREAD
pth;
WORD
wCount2;
WORD
wDirection;
DWORD
dwWakeupTime; } sleeper_t; /* 指向睡眠队列的指针 */
/* 下一个执行绪最长要被唤醒的时间 */
z结束执行绪（void RemoveThread(RTs *pRTs)函数）相关结构：typedef struct RTs {
PTHREAD pHelper;
DWORD dwBase, dwLen; DWORD dwOrigBase;
PPROCESS pProc;
LPTHRDDBG pThrdDbg; HANDLE hThread;
PTHREAD pThread;
CLEANEVENT *lpce1; CLEANEVENT *lpce2; CLEANEVENT *lpce3; LPDWORD pdwDying; //如果要释放堆栈，将用到此信息
//如果在fiber堆栈中，则需要释放的初始基址信息//如果要释放处理程序，将用到此信息
//如果要释放一个侦错结构，将用到此信息
//如果要释放一个句柄或执行绪时间，将用到此信息//如果要释放一个执行绪结构，将用到此信息
} RTs;
3.4 Windows CE中的排程
3.4.1 Windows CE排程的简介
CE是一个preemptive的多任务操作系统，它采用以优先权顺序为 Windows
主的时间片段循环方法 (time-sliced round-robin)。一般来说执行绪是排程的基本单位，执行绪可执行一个固定的时间片段，在Windows CE系统中有许多队列，分别对应不同目录的处理程序。一个处理程序在同一个时间只能在一个队列中，而目前正在执行的处理程序(如果有的话) 则例外。可执行的执行绪处于一个可执行队列之中(对每一种优先级，都对应一个可执行队列，最多可有256个可执行队列)。其它队列包括等待队列等等，目前执行的执行绪之时间片段用完后，如果这个执行绪不是时间关键 (time-critical) 的话，执行绪排程策略会把它排到相同优先级的执行队列的末尾，然后再让等待队列中优先级最高的执行绪执行，此执行绪的优先级应该和刚刚用完时间片段的执行绪具有相同的优先级。否则，如果等待队列中之执行绪优先级较高，它会抢占前一个执行的执行绪，如果其优先级较低，前一个用完时间片段的执行绪会继续执行。在Windows CE系统中，一般设定的时间片段大小为100ms (当然这个时间片段可以藉由OEM厂商所开发的不同硬件来设置)。也就是说，Windows CE以优先权顺序选择执行绪来执行，拥有最高优先级的执行绪将在低优先级的执行绪前面执行。基本排程情况如图3.1所示。
图3.1 Windows CE的排程机制
3.4.2 执行绪排程的时机
执行绪排程的时机如下：
执行绪状态改变
可执行队列的前面插入了一个执行绪
时间片段用完或被preempted
中断处理完后。
执行绪状态切换方式如下：执行绪执行完后，执行绪从就绪态转入睡眠态，或者执行绪从睡眠态转换到就绪态，分别藉由执行RemoveThread()、RunqDequeue()、NextThread()来呼叫MakeRun()，在这个函数中会呼叫相应的程序代码。当可执行队列前面插入了一个执行绪时，MakeRun()会进行判断，一个执行绪要侵占目前执行的执行绪，也会呼叫类似上述的MakeRun()函数，时间片段的分配与中断相关，所以这也跟中断处理完后的情况相同，在KCNextThread(void)函数中，将判断时间片段使用的情况。
借着Reschedule来判断是否关闭电源，还是执行当前执行绪相关的下一个执行绪，或者是直接执行一个新的执行绪。如果没有执行绪可以执行，那么将呼叫一个OEMIdle函数使CPU闲置。如下面程序代码所示(在NK\KERNEL\x86的fault.c中)：
程序代码3.3
Naked Reschedule()
{
__asm {
test [KData].bPowerOff,
0FFh jz short
rsd10
mov [KData].bPowerOff,
0 call DoPowerOff
rsd10:
sti
cmp word ptr ([KData].bResched), 1 jne short
rsd11
mov word ptr ([KData].bResched), 0 call NextThread
rsd11:
cmp dword ptr ([KData].dwKCRes), 1 jne short
rsd12
mov dword ptr ([KData].dwKCRes), 0 call KCNextThread
cmp dword ptr ([KData].dwKCRes), 1 je short
rsd10
rsd12:
mov eax,
[RunList.pth] // 是否需要关闭电源// 是 – 关闭电源
test eax,
eax
jz short
rsd50
cmp eax,
edi
jne short
rsd20
jmp RunThread
//转换到一个新的处理程序上下文信息
//.转换到一个新的执行绪，更新当前处理程序和地址空间信息，在TSS中编辑ring0堆栈指针，使其//指向新的执行绪的寄存器保存空间
// (eax) = ptr to thread structure
rsd20: mov edi, eax
mov
esi,
(THREAD)[eax].hTh
push
edi
call SetCPUASID
pop ecx
mov hCurThd, esi
mov PtrCurThd, edi
mov ecx,
[edi].tlsPtr
mov [KData].lpvTls,
ecx
cmp edi,
g_CurFPUOwner
jne SetTSBit
clts
jmp MuckWithFSBase
SetTSBit:
mov eax,
CR0
test eax,
TS_MASK
jnz MuckWithFSBase
or eax,
TS_MASK
mov CR0,
eax
MuckWithFSBase:
mov edx, offset g_aGlobalDescriptorTable+KGDT_PCR
sub ecx,
FS_LIMIT+1
mov word ptr [edx+2], cx
shr ecx,
16 // 没有可运行的执行绪
// 再次分发同一个执行绪
// 保存执行绪指标 (Program Counter) // (esi) = 执行绪句柄 (thread handle)
// 设置hCurProc
// 清除堆栈
// 设置当前执行绪句柄
// 设置当前执行绪指标
// (ecx) = thread local storage ptr
// 设置TLS(Thread Local Storage)指标
// (ecx) = ptr to NK_PCR base
// 设置FS基址的低端值
mov byte ptr [edx+4], cl
mov byte ptr [edx+7], ch
lea ecx,
[edi].ctx.TcxSs+4
mov [MainTSS].Esp0,
ecx
jmp RunThread
// 如果没有执行绪可以执行，呼叫OEMldle关闭掉CPU rsd50: cli
cmp word ptr ([KData].bResched), 1
je short
DoReschedule
call OEMIdle
mov byte ptr ([KData].bResched), 1
jmp Reschedule DoReschedule:
sti
jmp Reschedule
}
} // 设置FS基址的三个比特值
// 设置FS基址的高端值
// (ecx) = ptr to end of context save area // 执行edi所指向的执行绪
3.4.3 关于执行绪的优先级
与Windows 98和Windows NT相比，Windows CE为执行绪分配时间的方法有很大的不同。在Windows NT中，一个处理程序建立的时候将同时建立一个与优先级有关的类别 (class)，执行绪将从建立它的父处理程序中的优先级类别(priority class) 中获得自己的优先权，具有优先级类别高的处理程序所建立的执行绪将具有较高优先权。Windows CE系统没有类似Windows NT系统的优先级类别，所以所有的处理程序都是同类的，单个执行绪可以有不同的优先级，而且执行绪所在的处理程序并不影响执行绪的优先级。
Windows CE中的执行绪可以粗略的分为执行态 (RUNSTATE_RUNNING 正在执行)、可执行态，睡眠态(等待态)。其中后面两种状态可以细分如下：
z可执行态：
RUNSTATE_RUNNABLE‐可以执行
RUNSTATE_BLOCKED‐可执行态的停滞态，可能是自行进入停滞态RUNSTATE_NEEDSRUN‐即将进入可执行状态
z停滞态：
WAITSTATE_SIGNALLED‐等待某个信号的唤醒
WAITSTATE_PROCESSING‐重新处理等待态
WAITSTATE_BLOCKED‐等待状态的停滞态
在Windows CE原始程序代码NK\INC\schedule.h中，关于优先级的定义如下：
#define MAX_PRIORITY_LEVELS 256
#define MAX_WIN32_PRIORITY_LEVELS 8
这表明有8种不同的优先级别，最多256个优先级，藉由在NK\inc\schedule.h 中定义的杂凑值 (hash value) 对应到相应的优先级，一个优先级级别的大小是32。
#define PRIORITY_LEVELS_HASHSIZE 32
#define PRIORITY_LEVELS_HASHSCALE
(MAX_PRIORITY_LEVELS/PRIORITY_LEVELS_HASHSIZE)
数值越低，优先级越高。一个执行绪可以有任一优先级。执行绪优先级如表3.5所示：
表3.5 执行绪的优先等级
优先级描述
THREAD_PRIORITY_TIME_CRITICAL 比普通优先级高三个级别，这种优先
级的执行绪不能被preempted THREAD_PRIORITY_HIGHEST 比普通优先级高两个级别THREAD_PRIORITY_ABOVE_NORMAL比普通优先级高一个级别THREAD_PRIORITY_NORMAL 普通优先级，所有的执行绪建立时皆
为这个级别
THREAD_PRIORITY_BELOW_NORMAL比普通优先级低一个级别THREAD_PRIORITY_LOWEST 比普通优先级低两个级别THREAD_PRIORITY_ABOVE_IDLE 比普通优先级低三个级别THREAD_PRIORITY_IDLE 比普通优先级低四个级别
所有的高优先级执行绪在低优先级执行绪之前被执行，也就是说：如果某个优先级的执行绪能够被排程，那么所有具有较高优先级的执行绪必须是在被停滞的状态。被停滞的执行绪是指那些等待某种系统资源或同步对象的执行绪还没有用完自己所拥有的时间片段，但是因为没有这些系统资源或同步对象，所以被停滞的执行绪不能执行。相同优先级的执行绪采用时间片段循环的方法来排程。一旦一个执行绪自动放弃它的时间片段，而进入被停滞状态，或是用完了它的时间片段而换给别的执行绪执行，所有相同优先级的执行绪就可以在这个执行绪继续执行之前执行。如果一个有较高优先级被停滞执行绪清除了停滞状态，而且目前
有一个低优先级的执行绪正在执行，那么这个低优先级的执行绪将被preempted，转而排程这个高优先级的执行绪，也就是说高优先级的执行绪抢占了低优先级执行绪的执行权。上面说的情况有两个例外，如果一个执行绪具THREAD_PRIORITY_TIME_CRITICAL优先级，这个有THREAD_PRIORITY_TIME_CRITICAL优先级的执行绪将使所有的执行绪等待，直到他执行结束。所以这个优先级一般是被保留，用来在设备驱动中断时使用。
还有一种例外情况就是：如果一个低优先级的执行绪拥有执行所需的资源，而高优先级的执行绪正在等待某种资源，则低优先级的执行绪将临时被赋予较高的优先级 (priority inversion)，这样可以使低优先级的执行绪得以执行完并且释放它所占有的资源。一个执行绪刚建立的时候，它的优先级总是THREAD_PRIORITY_NORMAL，我们可以藉由SetThreadPriority (HANDLE hThread, int nPriority) 来设置执行绪的优先级，对于已经存在的执行绪，可以透过int GetThreadPriority (HANDLE hThread) 来得知它的优先级。
3.4.4 跟排程有关的函数简介
在shedule.c中有很多与排程有关的函数，下面介绍其中的一些主要函数：
1.MakeRunIfNeeded(HANDLE hth)
程序代码3.4
Void MakeRunIfNeeded (HANDLE hth)
{
PTHREAD pth;
KCALLPROFON(39);
if (( pth = HandleToThread(hth)) &&
(GET_RUNSTATE(pth) == RUNSTATE_NEEDSRUN)) {
if (GET_SLEEPING(pth))
{
SleepqDequeue(pth);
pth->wCount ++;
}
MakeRun(pth);
}
KCALLPROFOFF(39);
}//开启profiling 机制。
//检查执行绪的状态是否为即将进入可运行状态。//执行绪现正处在睡眠态，将它从睡眠队列中移除。
//呼叫 MakeRun 重新排程。
//关闭profiling 机制。
2.MakeRun(PTHREAD pth)
如果当前没有可以运行的执行绪，或者指定的执行绪pth是优先级最高的执行绪，那么把pth插入到可运行队列的最前面，并判断是否需要重新修改排程策略。否则，就是有比pth优先级更高的执行绪，把pth插入到合适的地方插入。
程序代码3.5
VOID MakeRun(PTHREAD pth )
{
DWORD prio， prio2;
PTHREAD pth2， pth3;
if (!pth->bSuspendCnt)
{
SET_RUNSTATE(pth，RUNSTATE_RUNNABLE);
prio = GET_CPRIO(pth);
prio2 = prio/PRIORITY_LEVELS_HASHSCALE;
if (!(pth2 = RunList.pRunnable) || (prio < GET_CPRIO(pth2)))
{
pth->pPrevSleepRun = 0;
if (pth->pNextSleepRun = pth2)
{
pth2->pPrevSleepRun = pth;
}
pth->pUpRun = pth->pDownRun = RunList.pHashThread[prio2] = pth; RunList.pRunnable = pth;
if (!RunList.pth || (prio < GET_CPRIO(RunList.pth)))
SetReschedule();
} else {
if (!(pth2 = RunList.pHashThread[prio2]))
{
RunList.pHashThread[prio2] = pth;
while (!(pth2 = RunList.pHashThread[-- prio2]))
;
} //没有可执行的执行绪或者pth自己就是最高优先权的执行绪。
//将 pth 插入runnable 队列最前面，并更新hash table。
//检查是否需要重新排程
//没有其它正在执行的执行绪或者目前的执行绪 pth 优先权是最高的。
//设定重新排程。
//若有其它优先权高于 pth 的执行绪，找出队列中正确的位置将 pth 插入。//与 pth 相同优先权的执行队列为空。//找到前面非0的hash table entry。