优先级翻转与优先级继承
2006-3-7
本文描述操作系统中的优先级翻转(Priority Inversion,也有翻译为反转,逆转或倒置的)现象以及如何用优先级继承来解决此类问题的方法,并阐述了 Microsoft Platform Builder for Windows CE 环境下,如何查看此种现象。
目 录摘要
1 优先级翻转(Priority Inversion)优先级翻转(Priority Inversion),是指某同步资源被较低优先级的进程/线程所拥有,较高优先级的进程/线程竞争该同步资源未获得该资源,而使得较高优先级进程/线程反而推迟被调度执行的现象。 优先级翻转现象在普通的分时调度系统中对系统的影响不大,或者本来就对优先级高低的进程/线程被调度的顺序就不太在意的情况下,不用太多关注。但是对于基于优先级调度的实时系统,优先级高的进程/线程被优先调度是调度算法首要考虑的因素,调度程序对于较高优先级被调度单元总是最钟情的,所有其它相应资源分配的考量也是基于优先级做出的。SUN Solaris和Microsoft Windows CE等系统都对优先级翻转现象在操作系统级做了处理。 假定一个进程中有三个线程Thread1、Thread2和Thread3,它们的优先级顺序是Priority(Thread1) > Priority(Thread2) > Priority(Thread3)。考虑图一的执行情况。
图一、优先级翻转现象(无优先级继承) ◇ T0时刻,只有Thread3处于可运行状态,运行过程中,Thread3拥有了一个同步资源SYNCH1; 上述现象中,优先级最高的Thread1既要等优先级低的Thread2运行完,还要等优先级更低的Thread3运行完之后才能被调度,如果Thread2和Thread3执行的很费时的操作,显然Thread1的被调度时机就不能保证,整个实时调度的性能就很差了。 2 优先级继承(Priority Inheritance)2.1 优先级继承为了解决上述由于优先级翻转引起的问题,Solaris和WinCE引入了优先级继承的解决方法。优先级继承也就是,高优先级进程TH在等待低优先级的线程TL继承占用的竞争资源时,为了使TH能够尽快获得调度运行,由操作系统把TL的优先级提高到TH的优先级,从而让TL以TH的优先级参与调度,尽快让TL执行并释放调TH欲获得的竞争资源,然后TL的优先级调整到继承前的水平,此时TH可获得竞争资源而继续执行。 有了优先级继承之后的上述现象的执行情况如图二所示。
图二、优先级继承执行情况 与图一比较,图二中,到了T3时刻,Thread1需要Thread3占用的同步资源SYNCH1,操作系统检测到这种情况后,就把Thread3的优先级提高到Thread1的优先级。此时处于可运行状态的线程Thread2和Thread3中,Thread3的优先级大于Thread2的优先级,Thread3被调度执行。 Thread3执行到T4时刻,释放了同步资源SYNCH1,操作系统此时恢复了Thread3的优先级,Thread1获得了同步资源SYNCH1,重新进入可执行队列。处于可运行状态的线程Thread1和Thread2中,Thread1的优先级大于Thread2的优先级,所以Thread1被调度执行。 上述机制,使优先级最高的Thread1获得执行的时机提前。 2.2 WinCE中优先级继承下面用在Microsoft Platform Builder for Windows CE 5.0环境的Emulator中,来做一个优先级继承的实验。 2.2.1 程序设计 主线程做了如下工作: 三个子线程的执行体分别如下: Thread3: Thread2: Thread1: 2.2.2 Log结果分析 结果输出如下: TID:a3ecaa1e Thread1: Handler = a3c867b2, ThreadId = a3c867b2 结果中的斜体加粗部分标识了图二的T3-T4时刻的操作。Thread3由于拥有Thread1欲申请的同步资源g_Mutex1而继承了Thread1的优先级,获得了执行。 结果中的粗体加下划线部分标识了图二的T4时刻的操作。Thread3释放同步资源g_Mutex1,Thread3的优先级被恢复到T3之前;Thread1获得了g_Mutex1之后继续执行。 2.2.3 用Platform Builder的工具查看 优先级继承时的线程的优先级是无法在程序中通过诸如GetThreadPriority() / CEGetThreadPriority() 之类的函数来查看CurrPrio的,这些函数查看的是显式设置的BasePrio。(WinCE的早期版本里,这些函数返回的是CurrPrio) 我们可以通过Platform Builder的调试工具来查看,不过因为PB提供的Emulator与BP Host之间同步需要时间,所以我们在上面的程序中需要延长Thread3在T3-T4时间段的时间以获得足够的时间查看此时Thread3继承的优先级。仅仅为了查看,这里可以设置一个极限情况,即Thread3在释放g_Mutex1之前无限循环。 下图是做完上述设置之后,通过 Platform Builder 的菜单“View | Debug Windows | Threads”,调出的Process/Thread View。
图三、通过Thread View查看优先级继承 图中,第一行对应Thread3;第二行对应PriorityInversion进程的主线程;第三行对应Thread1;第四行对应Thread2。从Thread3的CurrPrio列可以看出,它的当前的优先级确实提升到了Thread1的优先级。 2.3 优先级继承的传递性优先级继承的传递性,是指图二的优先级继承发生时,在Thread3的优先级已经提升到Thread1执行的T3-T4时间段里,如果Thread3竞争比Thread3的初始优先级还要低的线程Thread4拥有的同步资源,操作系统同样会把Thread4的优先级提升到Thread1的优先级。SUN的Solaris系统实现了优先级继承和继承的传递,Microsoft的Windows CE虽然实现了优先级继承,但是它只实现了一级,即,没有实现优先级继承的传递性。 下图是WinCE中按照上面描述增加了Thread4之后,参看Thread View得到的一个快照。
图四、通过Thread View查看优先级继承的传递性 图中,第一行对应Thread1;第二行对应Thread2;第三行对应PriorityInversion进程的主线程;第四行对应Thread4;第五行对应Thread3。从Thread3和Thread4所在行的CurrPrio列可以看出,Thread3由于等待Thread4拥有的竞争资源而被Blocked,优先级也没有得到提升;Thread4由于拥有Thread3所要竞争的同步资源,其优先级被提升到Thread3的优先级。这种现象不具有优先级继承的传递性。 3 总结优先级翻转是多线程环境中应该尽力避免的现象,尤其是依赖线程优先级来调度的系统中。在设计多线程程序时候,避免优先级翻转的最简单方法,就是不要让不同优先级的线程去竞争同一个同步资源。 优先级继承可以减缓优先级翻转带来的问题,但是也不能保证优先级最高的线程绝对地被最先调度执行,还是有一定的延缓时间。如果有优先级继承的传递性,传递的级别很深时,对系统性能的影响还是很大的。 参考资料及进一步阅读 ◇ Microsoft, MSDN, 2005.
关于作者 田海立,硕士,国家系统分析师,中国系统分析员协会顾问团专业顾问。
版权声明: ◇ 本文为作者原创作品,版权归作者所有。 http://blog.csdn.net/thl789/archive/2006/03/07/617629.aspx 其他的理解:
由于共享访问临界资源的问题,实时系统的优先级会出现翻转,导致低优先级的某个进程会比高优先级的某个进程有限执行。
这是个问题,严重可能导致关键进程迟迟不能执行,系统崩溃。 有2个方法可以解决这个问题,那就是“升级”。 1,优先级继承; 2,优先级天花板.
情景: 任务t1,t2,t3的优先级分别是p1,p2,p3; p1>p2>p3; t3占用打印机正在打印文档,中断到来,任务调度,t1就绪,t1开始运行,t1运行一会,发现自己也需要打印文档,但是打印机被占用了,只好等待(阻塞),os重新开始调度,发现t2就绪,t2比t3的优先级高,t2开始执行,t2执行完毕,或者因为等待另外的资源的,os开始重新调度,执行t3,t3打印完毕,释放了打印机,os重新调度,t1就绪,开始执行,t1打印完毕,结束,os重新调度,t3开始执行。
例子中,由于t1等待t3的资源,而让t2这个家伙抢了先执行,优先级翻转了!
归纳一下:高优先级的任务等待一个被低优先级任务霸占的资源而阻塞,而霸占这个资源的低优先级任务又很容易被其他中等优先级的任务抢占进而阻塞,导致高优先级任务迟迟得不到运行。
========= 解决办法: ========= 1,优先级继承
当t1需要访问t3的已经霸占的打印机的时候,会被阻塞,在阻塞t1的时候,顺便把t3的优先级提高到t1的优先级p1,这样任何比t1的优先级低的任务,比如说t2,就甭想抢占t3的cpu来执行。当t3释放打印机的时候,如果之前有过优先级提高,就把t3的优先级打回原形p3。 也就是说,t1 如果“碰”到了t3的资源的,t3的优先级被提高到t1的优先级,t3释放资源的时候,恢复到自己本来的优先级。
2,优先级天花板 在优先权极限方案中,系统把每一个临界资源与一个极限优先权相联系。 这个极限优先权等于系统此时最高优先权加1。 当1个任务进入临界区时,系统便把这个极限优先权传递给这个任务,使得这个任务的优先权最高; 当这个任务退出临界区后,系统立即把它的优先权恢复正常,从而保证系统不会出现优先权反转的情况。 如上例中,当t3进入临界区时,立即(而不是等到t1来“触碰”的时候)把它的优先权升高到极限优先权, 这个时候t3可“安心的”使用资源直到释放, 但是t3此时也应该 "自觉地" 能尽快退出临界区,进而释放其占有的信号量。 当高优先级任务 t1执行的时候就不会出现其等待低优先级任务t3释放信号量而被阻塞的情况,
从而保证不会出现上面所说的优先级反转。 优先级天花板的本质是让占有资源的任务尽快执行完,并释放资源,从而使与其竞争资源的高优先级任务尽快地得到执行,并通过良好定义的调度规则使任务不会交错占有资源而形成环路等待,从而保证死锁不会发生。(http://www./wz_10162.htm)
|
|