石效存，张鑫诚

(西北工业大学计算机学院，陕西 西安 710072)

0 引言

自动控制、国防工业仿真等领域越来越多地需要操作系统具有实时性，所以实时操作系统越来越受到关注。除了Linux系统实时化，人们越来越多地开始关注Windows操作系统的实时化。这是因为Windows平台具有更低的价格优势、更丰富的应用和更为广大的用户群体。除了实时化，操作系统经常需要一些扩展活动。本文设计了一种Windows驱动加载的自定义临界区。在现代的操作系统和应用程序中，线程或线程之间的通信往往是不可避免的，有些是因为功能本身的需要，有些则是因为资源有限而不得不共享。在操作系统扩展中不可避免地要涉及线程同步问题，而要完全满足自定义要求就需要定制同步机制［1-2］。

1 临界区机制

常见的临界区是一种较为轻量级的机制，在某一时间内只允许一个线程执行某个给定代码段。通常在修改全局数据(如集合类)时会使用临界区。事件、互斥锁和信号量也用于多线程同步，但临界区与它们不同，它并不总是执行向内核模式的控制转换，这一转换成本昂贵。要获得一个未占用临界区，事实上只需要对内存做出很少的修改，速度较快。只有在尝试获得已占用临界区时，它才会跳至内核模式。这一轻量级特性的缺点在于临界区只能用于对同一进程内的线程进行同步。另外在有限次等待后进入内核态，一直到资源可用为止，这会使得性能急剧降低［3］。

临界区主要是利用有限次的自旋来进行线程同步的。如果一定时间内不能进入临界区，那么系统会使得该线程陷入内核，进行相关调度，进行任务切换。在切换时，调度会首先挂起当前线程，利用线程结构中的相关链表指针，插入到等待链表中，利用调度算法选出下一个能够运行的线程，使其运行。临界区在线程同步时涉及系统调度，而由于Windows系统本身的调度策略以及时间片问题，如果在一直得不到临界区的情况下，效率会变得非常糟糕［4］。Windows临界区(CRITICAL_SECTION)结构如下。

DebugInfo字段包含一个指针，指向系统分配的伴随结构，该结构的类型为RTL_CRITICAL_SECTION_DEBUG，主要记录着等待临界区的相关线程信息。LockCount被初始化为数值-1;此数值等于或大于0时，表示此临界区被占用。OwningThread字段包含了拥有此临界区的线程ID，与(RecursionCount-1)数值之间的差值表示有多少个其他线程在等待获得该临界区。RecursionCount字段包含所有者线程已经获得该临界区的次数。如果该数值为0，下一个尝试获取该临界区的线程将会成功。LockSemaphore字段实际上是一个自复位事件，而不是一个信号。它是一个内核对象句柄，用于通知操作系统:该临界区现在空闲。SpinCount仅用于多处理器系统。MSDN文档对此字段进行如下说明:“在多处理器系统中，如果该临界区不可用，调用线程将在对与该临界区相关的信号执行等待操作之前，旋转dwSpinCount次。如果该临界区在旋转操作期间变为可用，该调用线程就避免了等待操作。”旋转计数可以在多处理器计算机上提供更佳性能，其原因在于在一个循环中旋转通常要快于进入内核模式等待状态［5］。

2 临界区设计实现

2.1 临界区与调度

临界区作为线程同步的一种方式，不可避免地需要调度配合。临界区的争夺，总会导致线程间的切换。为了提高性能，调度周期要尽可能地稳定，调度策略应尽可能简洁。但是多线程的情况下，同步机制的出现必然会影响调度工作。

利用Windows现有的调度将出现严重的优先级反转问题，优先级反转是指这样的问题:在线程调度时，一个低优先级的线程占有一个共享资源，从而导致高优先级的线程虽然其它运行条件都满足，但因为得不到该资源而无法运行。在采用抢占式调度算法的操作系统中，当低优先级的线程占有了资源时，它有可能被中等优先级的其它线程抢占。低优先级线程由于被挂起使得该资源得不到及时的释放，从而导致有等待该资源的高优先级线程在更长时间内无法运行。实际的效果就是，相当于把高优先级的线程降到低优先级。实时操作系统显然需要解决优先级反转这一问题［6］。解决优先级反转问题的方法有2种:(1)短暂地提高占有临界区资源线程的优先级，使得其尽快得到CPU资源运行从而释放临界区;(2)为临界区资源本身设定优先级，进入临界区的线程应当以临界区优先级为调度优先级。离开临界区时，应该再次回复本身优先级。

多线程的同步操作会使得线程挂起和恢复操作变得频繁。这将加重调度任务量，影响整体性能。因此需要同步机制尽可能少地影响调度队列，尽可能让同步完成在用户态，不至于进行调度链表操作而影响调度操作。

2.2 临界区结构设计

基于上述论述，首先考虑的是依据Windows本身临界区来设计实时扩展模块的临界区结构。以Windows原有结构为基础，所设计的临界区要与调度器配合解决优先级反转问题。选择临界区不设置优先级，在出现优先级反转时直接提高占有资源的线程优先级。这样做的好处是临界区本身简单化了，用户区不用维护临界区本身的优先级，同时节省了内存。调度器会在有优先级反转时暂时提高占有临界区线程的优先级到最高，保证临界资源能快速得到释放。同时为了保证调度周期的稳定性，尽可能地提高临界区执行效率，操作应该尽可能地在用户态执行。而Windows本身临界区是会进入内核态触发事件对象进行同步。从用户态切换入内核态是非常消耗时间的，所以要尽可能地避免这种切换。Windows临界区中记录等待线程信息主要依靠链表进行，而维护则需要进入内核态。为了提高效率，对于等待线程记录的操作需要在用户态完成，所以舍弃DebugInfo字段，直接定义一个合适的线程ID数组，设计临界区结构如下:

2.3 临界区存储

为了进一步提高效率，可以事先在初始化时就申请足够数量的临界区。由于设置时用于操作的变量没有指针，所以很方便将其映射到用户态。用户态操作LockCount字段时需要用到原子操作Interlocked系列Windows提供的API。以上临界区设置，可以避免大部分的操作进入内核态，但是在初始化临界区时依然需要进入内核，将申请的临界区挂入内核控制链表中。

Windows操作系统对内存管理时，用户地址和内核地址都是虚拟地址［7］，虽然2片地址范围不存在交集，但是对它们的访问最终都映射成访问实际的物理内存地址。可以通过MDL把用户空间和内核空间的一片内存区域跟一片物理内存相关联，如图1所示。

图1 映射示意图

将临界区结构提前申请并映射到用户态后，临界区操作基本可以在用户态完成。这可以大大地减少进入内核的次数，从而提高其实时性能。

2.4 临界区操作

临界区操作主要包括:初始化、进入、退出、删除。临界区操作应该都是原子性的。所以临界区内部操作均需InterLocked系列函数支持。该系列函数式Windows针对无符号整数提供了一系列原子操作。临界区基本接口设计如下:

首先初始化应该在进程一开始就进行。初始化时，需要进入内核态，从预先申请的临界区上取下一个节点，以head_list字段挂接在内核中临界区管理链表上。设置LockCount字段为-1，表示可用。进入和退出时需要配合调度器进行线程状态的维护，以便准确调度。进入时，若临界区可用，则以InterLocked-Increment函数使 LockCount加 1，改变 OwingThread字段为当前线程。若不可用，依然使得LockCount加1，然后将线程id加入WaitingThread字段，同时置线程状态为WAIT。退出操作中需要在释放临界区时，查看WaitingThread字段，找出其中优先级最高者。更改最高优先级线程状态为READY，使其可以参加下一轮调度。删除操作一般在进程结束时进行，进入内核态，从临界区管理链表上取下此节点即可。

以上是临界区本身操作。在进入和退出临界区时，主要的操作是将临界区和相关线程关联起来，同时根据临界区状态设置等待线程的状态为WAIT或者READY。在下一个时钟中断时，进入调度。调度器会根据链表中线程控制表(TCB)的状态进行链表调整［8］，将WAIT状态的节点全部挂入等待队列。若有获取临界区状态为READY的线程，则从WAIT链表转移进入READY链表。最后从READY链表中选择优先级最高的线程运行，设置状态RUN。其基本流程如图2所示。

图2 临界区及调度执行流程

3 试验结果及分析

在完成上述临界区设计的基础上，编码实现了自定义临界区原型。设计实验对其进行功能性测试。实验设计如下:创建3个线程，分别对共享资源(全局变量A)进行加法运算1000次，每次加法之后让线程放弃CPU，最后输出结果。在不使用临界区时，最终结果会出现不确定性，不一定等于3000。使用临界区时，结果总是准确的。2种情况测试各100次，结果如表1所示。

表1 测试结果

测试结果表明，在线程进行全局变量加法时，如果有释放CPU的行为很容易导致结果错误，而使用临界区可以有效地解决全局变量不一致问题。以上测试结果说明自定义的临界区是有效的，它能够保护共享资源，完成多线程的同步问题。

4 结束语

Windows操作系统有着广泛的应用，在很多情况下需要扩展，这时同步机制自定义实现或改进将是必不可少的。本文通过分析提出了一种自定义临界区的设计。应用内存映射，使得进入和退出临界区操作均在用户态进行。相比于需要进入内核态操作，这将使得临界区的操作更为快速。临界区只是同步机制中最简单的一种，而其它同步机制也是很有必要的。另外，实时化过程中同步机制与扩展模块的调度本身的配合很重要。这是一个很值得考虑的问题。Windows本身扩展改造是一个复杂而系统的问题，所以在设计时需要根据相应场景进行全面考量。

［1］杜旭东，蒋泽军，王丽芳，等.基于资源重分配的Windows实时性改造［J］.微电子学与计算机，2012，29(5):95-98，103.

［2］蒋善峰，王丽芳，蒋泽军.Windows时钟机制的实时扩展研究［J］.微电子学与计算机，2013，30(8):116-119，123.

［3］吕浩勇，余启港，董元和.Windows多线程同步技术研究［J］.计算机与现代化，2006(10):86-89.

［4］［美］Jeffrey Richter，［法］Christophe Nasarre.Windows核心编程［M］.北京:清华大学出版社，2010.

［5］钟剑，蒋泽军，王丽芳，等.实时信号量机制的研究［J］.现代电子技术，2012，35(2):40-42，50.

［6］马魁涛，蔡颖，郭宝峰.Win32进程间信息共享的实现方法研究［J］.计算机应用与软件，2007，24(12):119-120，157.

［7］毛德操.Windows内核情景分析［M］.北京:电子工业出版社，2009.

［8］潘汉，莫苏苏.基于Local APIC的Windows 2000实时化改造［J］.电子元器件应用，2009，11(10):79-82.

［9］章秦.Win32多线程同步技术浅析［J］.电子设计工程，2011，19(21):56-58，61.

［10］郭静寰，孟祥迪，熊木地.多线程同步机制在应用程序与驱动程序通信中的应用［J］.微计算机信息，2005，21(18):129-131.

［11］孙建杰，陈佳品.临界区读写锁的实现［J］.计算机与现代化，2011(9):215-219.

［12］周炎涛，李立明.现代操作系统中的多线程技术及其应用［J］.计算机与现代化，2002(7):7-11.

［13］Graunke G，Thakkar S.Synchronization algorithms for sharedmemory multiprocessors［J］.IEEE Computer，1990，23(6):60-69.

［14］王欣明，金蓓弘，张昕.用不对称的P/V操作设计并发算法［J］.计算机工程与应用，2005，41(12):65-69.