基于新信号量策略的实时提升技术

针对优先级队列过分强调高优先级线程的缺点和先进先出队列过分强调平均的缺点，本文提出基于优先级和先进先出队列结合的排队策略，同时兼顾实时线程的强实时要求和一般线程的公平要求。

NT内核将用户线程以一对一方式映射到内核中，并基于优先级调度内核线程，内核将优先级从低到高分为32级，0～15级为一般线程，16～31级为实时线程。本文将这种线程调度队列的分级方式见之于信号量的等待队列，如图1虚直线上部分所示，把线程等待队列构造成一个长度为17、类型为LIST_ENTRY的哈希（Hash）指针数组，数组1～16根据优先级排列同一级别的实时线程，数组0根据先进先出排列一般线程。线程请求资源后，若信号量计数器小于0，且线程优先级小于16，则将该线程按照先进先出策略排在线程等待队列的队尾；若线程优先级大于等于16，则按照优先级排列该线程。当线程释放资源时，若信号量计数器小于0，内核应先从优先级队列中搜索挂起线程，再从先进先出队列中搜索挂起线程。


4 新信号量策略在NT内核中的实现及结果分析

为了兼容操作系统上层软件，本文仅修改"请求"函数的代码而不改变现有信号量的数据结构，将图1虚直线上部分描述的新信号量策略映射到虚直线下，把优先级队列和先进先出队列融合到一个队列中，队列的前半部分是优先级队列，由指针FLINK指定，后半部分为先进先出队列，由指针BLINK指定，这种复合型队列同时具备优先级和先进先出队列的优点，体现了"一个队列两种策略"。线程请求资源后，若信号量计数器小于0，且线程的优先级小于16，按照先进先出策略将线程排在BLINK指向的先进先出队列队尾；若线程的优先级大于等于16，则将线程按照优先级策略在FLINK指向的优先级队列中搜索相应的位置，找到小于优先级队列中的线程并放在该线程之后。当线程释放资源时，若信号量计数器小于0，由于线程已经根据策略放入恰当的位置，内核只需要从KSEMAPHORE→WaitList→FLINK取出第一个线程送往线程调度队列即可。为了最小化修改范围，用下述代码替换内核\base\ntos\ke\wait.c文件中KeWaitForSingleObject()函数的部分代码以实现新策略：
if (KeQueryPriorityThread(Thread) < 16)
{InsertTailList(&Objectx->Header.WaitListHead,
&WaitBlock->WaitListEntry);}
else {ListHead1 = &Objectx->Header.WaitListHead;
WaitEntry1 = ListHead1->Flink;
while(WaitEntry1 != ListHead1) {
WaitBlock1 = CONTAINING_RECORD(WaitEntry1,
KWAIT_BLOCK, WaitListEntry);
if(KeQueryPriorityThread(Thread) >
KeQueryPriorityThread(WaitBlock1->Thread))
{break;}
WaitEntry1 = WaitEntry1->Flink;}
InsertTailList(WaitEntry1, &WaitBlock->
WaitListEntry);}

根据C规范[4]设计一个应用程序测试内核修改后的性能指标，由于NT内核对于一个特定的进程只能有一个特定的优先级类，进程内的所有线程只能属于该优先级，程序应该第一次进程化为实时类型的主控进程，生成信号量和挂在信号量上的实时线程，第二次进程化为一般类型的客户进程，生成挂在信号量上的一般线程，主线程释放实时线程和一般线程。应用程序中有4个参量：一般线程数NrTh、实时线程数RtTh；信号量Seph及资源争夺时间RunT。实验中,固定Seph=1，RunT=10 000 ms，改变NrTh和RtTh的值，分别在表1所列的内核上运行，结果如表1所示。

从表1可以看出：1～12行的调度结果和前述分析的各种策略的优缺点一致，对于FIFO，无论不同优先级线程的比例是多少，它们被调度的次数几乎完全相同。对于LIFO，从数据可以看出，两个优先级为8、一个优先级为6和优先级为26、25、24的线程处在等待队列的前端，而且几乎每次都是这几个线程被调度。对于Priority，无论是否有实时类线程，只要优先级高，被调度的次数就多。对于新策略（Priority and FIFO），有实时线程就按优先级调度，若只有一般线程就按照FIFO调度，既有FIFO的特性（比较第2行和第11行）也有Priority的特性（比较第1行和第4行），而其他策略则只具有一种特性。应用程序在其他操作系统测试结果见14～22行，比较可以看出，14～22行的数据与10～12行的数据几乎完全一致，由此可以推断Windows 7操作系统的信号量等待队列也是先进先出策略。

研究发现，提升系统实时性应该具备两个条件[5]：(1)不同任务可统一，包括将中断任务和线程任务按不同特征统一映射到一个优先级队列中，内核根据这个优先级队列统一调度任务，中断线程化为上述两种任务的统一提供了可能；(2)所有资源可抢占，计算资源可抢占可行且易实现