优先级反转和死锁的资源管理模式研究与实现

王溪波， 杨丽娜

(沈阳工业大学信息科学与工程学院，辽宁沈阳110870)

0 引 言

嵌入式实时系统是在 IT网络技术发展之后的又一发展新方向。嵌入式系统的产生与许多工程性学科类似，他的产生及发展源于军事航空领域，嵌入式系统已经在各个行业广泛应用，并且逐渐的改变着这些行业。与传统的操作系统相比嵌入式实时操作系统有很多的约束，他要求具有安全性、实时性及高可靠性，每个任务必须在其执行限期内完成，并应符合若干规定，例如有效的调度策略，减少中断处理的时间，优先级反转问题的解决等等。优先级反转现象，即高优先级任务被低优先级任务阻塞而无法正常运行。在多任务并发执行、共享资源时，存在死锁的潜在危险，即指多个任务循环等待它方占有的资源而无限期地僵持下去的局面。需要解决这种现象来消除对系统的不良影响。目前，国内外研究人员提出了大量的设计模式，但 C/OS-Ⅱ并未提供实现方法。本文在分析优先级反转和死锁发生的原因的基础上，修改 C/OS-Ⅱ内核结构并设计相应算法，在 C/OS-Ⅱ中实现了优先级继承协议抑制优先级反转，以排序锁定共享资源管理模式避免死锁的发生，为 C/OS-Ⅱ支持复杂的、高可靠的实时应用奠定了基础。理论分析和结果表明，上述方法在抑制无限优先级反转和避免死锁具有可行性和有效性。

1 研究现状

在嵌入式实时操作系统中，以独占的方式访问共享资源会出现优先级反转的现象，为避免这种现象的发生，现在普遍采用的方法有以下两种：一种是由L.Sha,R.Rajkumar和 J.P.Lehoczky提出的优先级继承协议[1](priorityinheritanceprotocol，PIP)；另一种是由J.B.Goodenough和L.Sha提出的优先级天花板协议[2](priority ceiling protocol，PCP)。

优先级天花板协议的思想是[3]：当任务申请共享资源时，将该任务的优先级提升到可能访问这个资源的所有任务中的最高优先级，当任务退出临界区时，恢复其原有优先级。优先级天花板协议解决了优先级反转同时也可避免死锁的发生，但是 C/OS-Ⅱ目前最大只支持64个优先级[4]，也就是支持的任务最大数为64个，而且还有8个系统任务，所以实际上只有56个优先级可以使用，在实现该协议时，每种共享资源占用一个优先级，随着嵌入式系统设计的日趋复杂，任务的数量受到优先级数量的限制，而且为每一个共享资源分配一个优先级天花板，增加了程序设计的复杂性，使系统的执行效率下降[5]。

优先级继承协议的思想是：当高优先级的任务在等待低优先级的任务占用的信号量时，把低优先级任务的优先级提升到高优先级任务的优先级，当低优先级的任务退出临界区时，立刻恢复到原来的优先级[6]。优先级继承协议的共享资源管理可有内核自动完成，与PCP相比减少了设计者的负担，并提升了管理执行效率[7-8]，但该协议没有考虑死锁问题。优先级继承样例模型如图1所示。

图1 优先级继承样例模型

在此模型中创建了3个任务，Task1、Task2、Task3，优先级分别为10，20，30。Task1在t3时，由于想使用Task3占用的共享资源而阻塞，这时系统提升Task3的优先级至Task1的优先级水平继续执行。Task 3运行结束时，恢复原来的优先级，在t4时 Task 1申请到了共享资源而运行。由于优先级的提升，在t3到t4时间段内，Task 2不会抢占Task 3的运行。这样优先级反转就被限制在一个层次上，不会发生优先级无限反转现象，抑制了优先级反转现象的发生。建立3个任务，Task1、Task2、Task3他们的优先级分别为10、10、20，时间延时分别为6s、4s、2s，C/OS-Ⅱ调度运行结果如图 2 所示。

实验结果证明，由于Task1与Task2的优先级相同，任务Task2得不到CPU的使用权而无法运行，C/OS-Ⅱ不支持相同任务的优先级调度，因此不支持优先级继承协议。相同优先级任务的运行结果如图2所示。

图2 调度运行结果

在 C/OS-Ⅱ中实现优先级继承协议的主要思想：在任务控制块中添加任务标识号TaskID用于标识系统任务以及一个时间片成员TimeSlice。将相同优先级任务链成一个双向循环链表，使优先级索引表指向该循环链表，系统进行任务调度时判断当前任务优先级是否为最高，若是则运行直到时间片TimeSlice结束，下一个相同优先级任务继续执行，反之则查找最高优先级任务。

实验结果表明，经改进后在 C/OS-Ⅱ中支持相同优先级任务的调度，改进内核后调度运行结果如图3所示。

图3 改进内核后调度运行结果

下面介绍优先级继承协议在 C/OS-Ⅱ中的实现。

建立3个任务Task1、Task2、Task3，并且优先级分别设置为10、20、30，Task1优先级最高，建立一个互斥信号量S。其中任务Task1，Task3申请使用信号量S，Task2不申请此信号量。该实验模型的功能是在屏幕上显示一行字符串。其中 Task2先运行，然后Task3获得CPU的使用权并占有共享资源，此时Task1也想申请该信号量，通过该实验验证优先级继承协议在 C/OS-Ⅱ中使用的可行性。

实验结果表明，改进内核后的优先级置顶协议可以在 C/OS-Ⅱ中使用，并且抑制了优先级反转现象。当Task1申请使用Task3占用的信号量时，立刻将Task3的优先级提升到与Task1相同，使Task3尽快的运行，当Task3释放了信号量后，Task1开始运行，可以抑制优先级反转，当执行完后，Task3自动恢复到原来的优先级。改进内核后的优先级继承协议抑制了优先级反转现象如图4和图5所示。

图4 改进内核后的优先级继承协议抑制了优先级反转现象

在 C/OS-Ⅱ中采用基于时间片轮转调度算法优先级继承协议实现能够抑制优先级反转现象，但没考虑死锁问题，不能够避免死锁。

图5 优先级继承协议抑制优先级反转时序

3 死锁产生的原因

死锁也称抱死(deadlock或deadlyembrace)，指两个任务无限期的互相等待对方控制着的资源[10-11]。死锁的产生原因有两个[12]：①有限资源的竞争；②进程的推进顺序。有两个任务Task1和Task2，其共享两个资源R1和R2。Task1的优先级高于Task2的优先级，Task1试图先锁定R2然后再锁定R1，然后再以相反的次序释放R1和R2；Task2试图先锁定R1然后锁定R2，然后也以相反的次序释放它们。在A点Task2获得CPU的使用权开始运行，在B点Task2占用了共享资源R1，在C点，由于Task1的优先级高于Task2的优先级，Task1抢占了Task2获得了CPU的使用权并开始运行，在D点Task1占用了共享资源R2此时系统可以正常运行，但到了E点，Task1又需要占用共享资源R1，而R1已经被Task2占用，所以Task1被阻塞，等待Task2释放R1后继续运行，Task2开始运行，而Task2需要占用共享资源R2，而R2被Task1占用，在这个时候，Task1和Task2都在等待一个不可能到来的条件，因此发生了死锁。死锁产生示意图如图6所示。

图6 死锁的产生

4 避免死锁的主要思想

处理死锁的有3种基本方法：死锁的预防、死锁的避免、死锁的检测与恢复[13]。本文重采用死锁的避免来处理死锁现象。

对优先级继承协议进行改进的主要思想是使其在支持C/OS-Ⅱ实时操作系统的基础上，避免死锁的发生，提高系统的实时性和稳定性。采用排序锁定共享资源的方法，使共享资源按照由低到高的次序被访问，使循环的现象不再发生，从而避免死锁。

共享资源R1和R2，资源号SourceIDR1Task2>Task3，Task3首先获得了cpu的使用权并且开始运行，在t1时刻task1占用了共享资源R1；在t2时刻，Task1申请使用共享资源R2，由于SourceID R1

图7 避免死锁

本文在优先级继承协议的基础上在内核中增加了共享资源控制块 OS_SourceTCB及共享资源控制块链表 OSSource-TCBTbl[]。

4.1 共享资源的数据结构

*OSSourceTCBNext，*OSSourceTCBprev为指向共享资源的指针。共享资源的内容主要包括：指向共享资源堆栈的指针OSSourceTCBStdPtr；共享资源的标识，一个共享对应一个唯一的SourceID，用于指定被访问的顺序；OSTCBPrio任务的优先级，与任务一一对应；当任务占有某个共享资源时，其对应的OSSourceTCBStat被置为1，当共享资源被释放时OSSource-TCBStat置为 0。

4.2 共享资源控制块链表

在资源管理上，增加了两条链表：一条是空的共享资源控制块链表，(其中所有共享资源还没有被任务占用)，令一条是共享资源控制块链表(其中所有共享资源已被任务占用)。具体做法为：系统在调用OSInit()对 C/OS-Ⅱ进行初始化的时候，就先在RAM中建立一个OSSourceTCBTbl[]，然后把各个元素链成一个表，从而形成一个空的共享资源控制块链表。初始化时创建的一个空共享资源控制块链表如图8所示。

4.3 避免死锁的算法描述

在文献[14]的基础上解决死锁问题，对共享资源加锁的基本策略是为每个共享资源分配一个唯一的SourceID每个任务对资源的访问要按照SourceID递增的顺序进行访问，当有任务申请真用某资源时，从OS_SourceTbl[]中查找任务已使用过的资源的最大的SourceID与申请的SourceID’进行比较，如果已经用过的最大的SourceID小于SourceID’则该资源可以被占用。如果任务第一次申请使用资源，则允许使用该资源。如果当任务申请的资源被其他资源占用时，该资源处于阻塞状态，但是死锁不会发生[15]。因为至少有一个任务将不得不阻塞等待一个资源的释放，而该资源的SourceID比占用资源的任务的最大SourceID要小。

用排序锁定共享资源的方法避免死锁发生，代码如下：

5 实验及结果分析

实验的硬件环境为：T6400CPU、512MB内存、250GB硬盘的PC机，软件环境为：移植 C/OS-Ⅱ实时操作系统到PC机上，使用Borland C++4.5和tasm5.0编译器完成程序的测试。

本文根据优先级反转及死锁的基本理论在 C/OS-Ⅱ操作系统上设计了一个抑制优先级反转同时避免死锁的实验模型。在这个实验模型中，C/OS-Ⅱ操作系统创建了3个任务，Task1、Task2和Task3，它们的优先级Task1>Task2>Task3。两个共享资源分别为R1和R2，资源号SourceIDR1Task3，在采用了改进的优先级继承协议的基础上，将Task3的优先级提升到Task1的水平，抑制了先级反转现象，使得低优先级任务Task3继续运行，然后Task3释放了共享资源R1。

从避免死锁现象的运行结果中看到，该模型中的共享资源是按照递增的顺序被访问的，有效避免了死锁的发生。避免死锁现象的运行结果如图9所示。

图9 避免死锁现象的运行结果

6 结束语

图8 空资源控制块链表

本文将优先级继承协议和基于排序锁定共享资源的方法相结合，并通过扩展 C/OS-Ⅱ的内核，使优先级反转和死锁问题的资源管理模式应用到 C/OS-Ⅱ实时操作系统中，不仅可以抑制 C/OS-Ⅱ操作系统的优先级反转同时还可以避免死锁的发生，增强了系统的实时性与稳定性。通过实验验证该方法切实有效。但是，新增的一些数据结构增加了系统的开销，此外还存在资源等待的现象，下一步工作还需解决资源浪费的现象，减少系统开销。

[1]周绪川.一种解决 C/OS中优先级反转问题的方案[J].微计算机信息,2007,23(5-2):58-60.

[2]李光成,褚伟.基于 C/OS-II嵌入式实时系统的优先级倒置分析[J].计算机技术与发展,2007,17(7):98-101.

[3]王涛.实时系统调度若干关键技术的研究[D].哈尔滨:哈尔滨工程大学,2006:59-68.

[4]张军,曹岳辉.改进的优先级继承协议在 C/OS中的实现[J].自动化技术与应用,2009,28(3):126-128.

[5]徐亮,徐中伟.C/OS-II实时系统任务调度优化[J].计算机工程,2007,33(19):57-59.

[6]王继刚,顾国昌.一种改进的优先级继承协议及其算法研究[J].计算机工程,2007,33(8):41-44.

[7]毛德梅,汪明珠.C/OS-II中任务优先级反转问题研究[J].安徽理工大学学报(自然科学版),2007,27(3):39-41.

[8]周本海,王溪波,乔建忠,等.基于多参数的 C/OS-Ⅱ任务优先级和调度方法[J].计算机工程,2007,33(21):28-30.

[9]胡国珍,范生凯.嵌入式RTOS优先级天花板协议研究[J].计算机工程与设计,2009,30(8):1893-1895.

[10]Labrosse J J.MicroC/OS-Ⅱ嵌入式实时操作系统[M].邵贝贝,译.2版.北京:北京航空航天大学出版社,2007:55-56.

[11]千承辉.基于嵌入式实时系统的汽车检测线测控系统研究[D].长春:吉林大学,2008:20-25.

[12]申雪琴.计算机操作系统中死锁问题研究[J].计算机与数字工程,2008,36(7):203-204.

[13]刘林,刘正熙.基于排序的避免死锁的方法[J].微计算机信息,2009,25(5-3):141-142.

[14]周本海.实时系统中实时调度算法及其资源管理的研究[D].沈阳:沈阳工业大学,2007:30-41.

[15]麦中凡,陶伟.实时设计模式[M].北京:北京航空航天大学出版社,2004:282-283.