解决优先级倒置问题的RTOS优先级调度策略

大多数商用实时操作系统(RTOS)均采用基于优先级的抢先调度器,这些系统为每个任务分配唯一的优先等级。调度器可以保证在所有等待运行的任务中,真正运行的总是具有最高优先级的任务。为了满足上述目标,调度器需要在执行中抢先优先级较低的任务。

由于多个任务共享资源,调度器控制范围以外的事件可以在必要的情况下阻止具有最高优先级的准备就绪任务运行。如果出现这种情形,将有可能使任务错过临界期限(critical deadline),从而导致系统崩溃。优先级倒置就是当具有最高优先级的准备就绪任务在应该运行却无法执行时所采用的一项应急措施。

资源共享引发的问题

在采用基于优先级的调度器中,一旦两个任务共享了资源(如存储缓冲器),那么其中之一通常具有较高的优先级。高优先级的任务期望一旦准备就绪就能运行,但当高优先级任务就绪,而低优先级任务正在使用共享资源时,高优先级任务必须等待,直到低优先级任务完成对共享资源的操作。这时,我们称高优先级任务被挂起。如果高优先级任务必须满足临界期限,那么还必须计算所有共享资源在最坏条件下的“锁定时间(lockout time)”,并在设计中加以考虑。如果累积的锁定时间过长,那么资源共享机制就必须重新设计。任务需要共享资源进行通信和数据处理,但这种多线程特性并不适用于实时或嵌入式系统。

优先级倒置技术

当高优先级任务挂起时,中优先级的任务抢先了正在使用共享资源的低优先级任务,因而真正的问题来自运行阶段；如果高优先级任务已准备就绪并等待运行,但中优先级任务此刻正在运行,这时就出现了优先级倒置问题。

低优先级任务L和高优先级任务H共享了资源,在任务L占有资源之后不久,任务H就绪；但这时任务H必须等待任务L完成对共享资源的操作。在任务L完成对共享资源的操作之前,任务M也已就绪并将抢先任务L运行。在任务M(也许还包括其他的中优先级任务)运行时,系统中具有最高优先级的任务H仍然保持挂起状态。

许多优先级倒置都不会给系统带来危害,最多只是延迟了马上应该运行的任务。但偶尔也会出现系统关键优先级的倒置,例如这种情形就出现在1997年7月的火星“拓荒者(Mars Pathfinder)”探测任务中。“拓荒者”是对火星表层进行高分辨率拍照并将照片发回地球的小飞行器。

“拓荒者”遭遇的问题并不出自登陆软件,而来自登陆命令软件。大量的任务通过很大的一块共享内存区进行通信,其中部分是低优先级的天气数据任务,另一些则是具有高优先级的信息总线管理任务。设计该软件的喷气推进实验室(JPL)的工程人员建立了信号量(semaphore)机制对共享内存区数据进行存取控制。

大部分时间里,软件都能无故障地运行；但有时在任务执行中,一个较为严重的问题足以引发整个软件重启。当低优先级的天气任务获得信号量并对共享内存区进行存取时,就产生一连串导致系统崩溃的事件序列。在这段时间中,高优先级的总线管理任务也需要信号量,但不得不等待信号量的释放(因为天气任务正在使用该信号量)。此后不久,触发了一条中断,导致中优先级的通信任务就绪。通信任务无须对共享内存区进行存取,但该任务的优先级高于其他正在运行的任务。因此低优先级的天气任务将被抢先,并开始运行中优先级的通信任务。中优先级任务需要进行大量的处理,因此将占用相当长的时间。这期间,低优先级的天气任务仍然占据信号量,而高优先级的总线管理任务则在等待信号量的释放。由于高优先级的任务相当重要,因此经常会触发一个监控定时器。如果未触发监控定时器,系统将自动重启。

这样的问题并不由RTOS的错误(如对信号量的错误操作)导致,相反,软件展现了信号量和进程间通信的一个显著特征。实际上,“拓荒者”的RTOS支持可选的工作区,而JPL的科学家根本就没有实施这项功能。幸亏科学家们可以远程操作工作区并完成任务。

两种优先级倒置方案

优先级倒置研究获得了两种解决方案。第一种方案称为优先级继承(priority inheritance),该技术强令低优先级的任务继承与之共享资源并被挂起的任意高优先级任务的优先等级。一旦高优先级任务开始挂起,即可实施优先级继承,直到资源释放。这需要得到操作系统的大力支持。

第二种解决方案称为优先级顶置(priority ceiling),该方案为每种资源都分配优先级；调度器将该优先级传送至任何存取资源的任务,而分配给资源的优先级则为最高优先级用户的优先级。一旦任务完成对该资源的操作,其优先级恢复正常。

优先级顶置的一大特色就在于任务可以共享资源,并且只需简单地改变资源的优先级,因此就不再需要信号量。

============================

void TaskA(void)

{

...

SetTaskPriority(RES_X_PRIO);

// Access shared resource X.

SetTaskPriority(TASK_A_PRIO);

...

}

=============================

当任务A的优先级提升时(该任务正对资源X进行存取),任务A将不会为任何其他资源挂起。当低优先级任务完成对共享资源的操作时,高优先级的用户将只能成为最高优先级的等待任务。

尽管我们都不全为火星任务编写过程序,但仍然可以从以往的错误中汲取经验并避免在下一解决方案的实施中重复相同的错误。许多商用的RTOS均支持优先级继承或优先级倒置,并且只需知道自己需要那种解决方案。

参考文献

Jones, Mike. "What Really Happened on Mars Rover Pathfinder," Risks-Forum Digest, December 1997.

Sha L., R. Rajkumar, and J.P. Lehoczky. "Priority Inheritance Protocols: An Approach to Real-Time Synchronization," IEEE Transactions on Computers, September 1990, p. 1175.

作者:David Kalinsky

用户教育总监

OSE Systems公司

Email: david@

Michael Barr

主编

Embedded Systems Programming

Email: mbarr@