优先级翻转与优先级继承

优先级翻转与优先级继承

田海立

<chsdate w:st="on" year="2006" month="3" day="7" islunardate="False" isrocdate="False"><strong style=""><span lang="EN-US">2006-3-7</span></strong></chsdate>

摘要

本文描述操作系统中的优先级翻转（Priority Inversion，也有翻译为反转，逆转或倒置的）现象以及如何用优先级继承来解决此类问题的方法，并阐述了 Microsoft Platform Builder for Windows CE 环境下，如何查看此种现象。

目 录

<!--[if supportFields]><b style='mso-bidi-font-weight:normal'><span lang=EN-US><span style='mso-element: field-begin'></span><span style='mso-spacerun:yes'></span>TOC /o &quot;1-3&quot; /h /z /u <span style='mso-element:field-separator'></span></span></b><![endif]-->摘要... <!--[if supportFields]><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'><span style='mso-element:field-begin'></span></span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'> PAGEREF _Toc129492691 /h </span><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-separator'></span></span><![endif]-->1<!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100320039003400390032003600390031000000</w:data> </xml><![endif]--><!--[if supportFields]><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-end'></span></span><![endif]-->
1 优先级翻转（Priority Inversion）... <!--[if supportFields]><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'><span style='mso-element:field-begin'></span></span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'> PAGEREF _Toc129492692 /h </span><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-separator'></span></span><![endif]-->1<!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100320039003400390032003600390032000000</w:data> </xml><![endif]--><!--[if supportFields]><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-end'></span></span><![endif]-->
2 优先级继承（Priority Inheritance）... <!--[if supportFields]><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'><span style='mso-element:field-begin'></span></span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'> PAGEREF _Toc129492693 /h </span><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-separator'></span></span><![endif]-->2<!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100320039003400390032003600390033000000</w:data> </xml><![endif]--><!--[if supportFields]><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-end'></span></span><![endif]-->
2.1 优先级继承... <!--[if supportFields]><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'><span style='mso-element:field-begin'></span></span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'> PAGEREF _Toc129492694 /h </span><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-separator'></span></span><![endif]-->2<!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100320039003400390032003600390034000000</w:data> </xml><![endif]--><!--[if supportFields]><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-end'></span></span><![endif]-->
2.2 WinCE中优先级继承... <!--[if supportFields]><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'><span style='mso-element:field-begin'></span></span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'> PAGEREF _Toc129492695 /h </span><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-separator'></span></span><![endif]-->3<!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100320039003400390032003600390035000000</w:data> </xml><![endif]--><!--[if supportFields]><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-end'></span></span><![endif]-->
2.3 优先级继承的传递性... <!--[if supportFields]><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'><span style='mso-element:field-begin'></span></span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'> PAGEREF _Toc129492696 /h </span><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-separator'></span></span><![endif]-->5<!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100320039003400390032003600390036000000</w:data> </xml><![endif]--><!--[if supportFields]><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-end'></span></span><![endif]-->
3 总结... <!--[if supportFields]><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'><span style='mso-element:field-begin'></span></span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'> PAGEREF _Toc129492697 /h </span><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-separator'></span></span><![endif]-->6<!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100320039003400390032003600390037000000</w:data> </xml><![endif]--><!--[if supportFields]><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-end'></span></span><![endif]-->
参考资料及进一步阅读... <!--[if supportFields]><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'><span style='mso-element:field-begin'></span></span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'> PAGEREF _Toc129492698 /h </span><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-separator'></span></span><![endif]-->6<!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100320039003400390032003600390038000000</w:data> </xml><![endif]--><!--[if supportFields]><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-end'></span></span><![endif]-->
关于作者... <!--[if supportFields]><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'><span style='mso-element:field-begin'></span></span><span style='color:windowtext;display:none;mso-hide:screen;text-decoration:none; text-underline:none'> PAGEREF _Toc129492699 /h </span><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-separator'></span></span><![endif]-->6<!--[if gte mso 9]><xml> <w:data>08D0C9EA79F9BACE118C8200AA004BA90B02000000080000000E0000005F0054006F0063003100320039003400390032003600390039000000</w:data> </xml><![endif]--><!--[if supportFields]><span style='color:windowtext; display:none;mso-hide:screen;text-decoration:none;text-underline:none'><span style='mso-element:field-end'></span></span><![endif]-->

<!--[if supportFields]><b style='mso-bidi-font-weight:normal'><span lang=EN-US><span style='mso-element:field-end'></span></span></b><![endif]-->

1 优先级翻转（Priority Inversion）

优先级翻转（Priority Inversion），是指某同步资源被较低优先级的进程/线程所拥有，较高优先级的进程/线程竞争该同步资源未获得该资源，而使得较高优先级进程/线程反而推迟被调度执行的现象。

优先级翻转现象在普通的分时调度系统中对系统的影响不大，或者本来就对优先级高低的进程/线程被调度的顺序就不太在意的情况下，不用太多关注。但是对于基于优先级调度的实时系统，优先级高的进程/线程被优先调度是调度算法首要考虑的因素，调度程序对于较高优先级被调度单元总是最钟情的，所有其它相应资源分配的考量也是基于优先级做出的。SUN Solaris和Microsoft Windows CE等系统都对优先级翻转现象在操作系统级做了处理。

假定一个进程中有三个线程Thread1、Thread2和Thread3，它们的优先级顺序是Priority(Thread1) > Priority(Thread2) > Priority(Thread3)。考虑图一的执行情况。

图一、优先级翻转现象（无优先级继承）

◇ T0时刻，只有Thread3处于可运行状态，运行过程中，Thread3拥有了一个同步资源SYNCH1；
◇ T1时刻，Thread2就绪进入可运行状态，由于优先级高于正在运行的Thread3，Thread3被抢占（未释放同步资源SYNCH1），Thread2被调度执行；
◇ 同样地T2时刻，Thread1抢占Thread2；
◇ Thread1运行到T3时刻，需要同步资源SYNCH1，但SYNCH1被更低优先级的Thread3所拥有，Thread1被挂起等待该资源，而此时处于可运行状态的线程Thread2和Thread3中，Thread2的优先级大于Thread3的优先级，Thread2被调度执行。

上述现象中，优先级最高的Thread1既要等优先级低的Thread2运行完，还要等优先级更低的Thread3运行完之后才能被调度，如果Thread2和Thread3执行的很费时的操作，显然Thread1的被调度时机就不能保证，整个实时调度的性能就很差了。

2 优先级继承（Priority Inheritance）

2.1 优先级继承

为了解决上述由于优先级翻转引起的问题，Solaris和WinCE引入了优先级继承的解决方法。优先级继承也就是，高优先级进程T_H在等待低优先级的线程T_L继承占用的竞争资源时，为了使T_H能够尽快获得调度运行，由操作系统把T_L的优先级提高到T_H的优先级，从而让T_L以T_H的优先级参与调度，尽快让T_L执行并释放调T_H欲获得的竞争资源，然后T_L的优先级调整到继承前的水平，此时T_H可获得竞争资源而继续执行。

有了优先级继承之后的上述现象的执行情况如图二所示。

图二、优先级继承执行情况

与图一比较，图二中，到了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中，来做一个优先级继承的实验。

<chsdate w:st="on" isrocdate="False" islunardate="False" day="30" month="12" year="1899"><strong style=""><span lang="EN-US" style="font-size: 12pt;">2.2.1</span></strong></chsdate> 程序设计

主线程做了如下工作：
◇ 创建三个子线程，设置它们的优先级顺序：
Priority(Thread1) > Priority(Thread2) > Priority(Thread3)；
◇ 只是启动Thread3。
◇ 创建一个互斥体g_Mutex1，初始状态是未被获得的。

三个子线程的执行体分别如下：

Thread3：
◇ 获得g_Mutex1；
◇ 循环执行一定次数的
打印“Thread3: Executing BEFORE releasing the MUTEX...”
◇ 释放g_Mutex1；
◇ 循环执行：
打印“Thread3: Executing AFTER releasing the MUTEX...”

Thread2：
◇ 打印：“Thread2: Start executing...”
◇ 循环执行：
打印“Thread2: executing...”

Thread1：
◇ 打印：“Thread1: Start executing...”
◇ 打印：“Thread1: Waiting on Mutex1...”
◇ 执行：WaitForSingleObject(g_Mutex1, INFINITE);
◇ 打印：“Thread1: GOT g_Mutex1, and will resume.”
◇ 循环执行：
打印“Thread1: Executing AFTER getting the MUTEX...”

<chsdate w:st="on" isrocdate="False" islunardate="False" day="30" month="12" year="1899"><strong style=""><span lang="EN-US" style="font-size: 12pt;">2.2.2</span></strong></chsdate> Log结果分析

结果输出如下：

TID:a3ecaa1e Thread1: Handler = a<chmetcnv w:st="on" unitname="C" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0">3c</chmetcnv>867b2, ThreadId = a<chmetcnv w:st="on" unitname="C" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0">3c</chmetcnv>867b2
TID:a3ecaa1e Thread2: Handler = <chmetcnv w:st="on" unitname="C" sourcevalue="83" hasspace="False" negative="False" numbertype="1" tcsc="0">83c</chmetcnv><chmetcnv w:st="on" unitname="C" sourcevalue="8" hasspace="False" negative="False" numbertype="1" tcsc="0">8c</chmetcnv>002, ThreadId = <chmetcnv w:st="on" unitname="C" sourcevalue="83" hasspace="False" negative="False" numbertype="1" tcsc="0">83c</chmetcnv><chmetcnv w:st="on" unitname="C" sourcevalue="8" hasspace="False" negative="False" numbertype="1" tcsc="0">8c</chmetcnv>002
TID:a3ecaa1e Thread3: Handler = <chmetcnv w:st="on" unitname="C" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0">3c</chmetcnv><chmetcnv w:st="on" unitname="C" sourcevalue="866" hasspace="False" negative="False" numbertype="1" tcsc="0">866c</chmetcnv>2, ThreadId = <chmetcnv w:st="on" unitname="C" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0">3c</chmetcnv><chmetcnv w:st="on" unitname="C" sourcevalue="866" hasspace="False" negative="False" numbertype="1" tcsc="0">866c</chmetcnv>2
TID:<chmetcnv w:st="on" unitname="C" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0">3c</chmetcnv><chmetcnv w:st="on" unitname="C" sourcevalue="866" hasspace="False" negative="False" numbertype="1" tcsc="0">866c</chmetcnv>2 Thread3 GOT the Mutex g_Mutex1
TID:<chmetcnv w:st="on" unitname="C" sourcevalue="83" hasspace="False" negative="False" numbertype="1" tcsc="0">83c</chmetcnv><chmetcnv w:st="on" unitname="C" sourcevalue="8" hasspace="False" negative="False" numbertype="1" tcsc="0">8c</chmetcnv>002 Thread2: Start executing...
TID:<chmetcnv w:st="on" unitname="C" sourcevalue="83" hasspace="False" negative="False" numbertype="1" tcsc="0">83c</chmetcnv><chmetcnv w:st="on" unitname="C" sourcevalue="8" hasspace="False" negative="False" numbertype="1" tcsc="0">8c</chmetcnv>002 Thread2: executing...
TID:a<chmetcnv w:st="on" unitname="C" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0">3c</chmetcnv>867b2 Thread1: Start executing...
TID:a<chmetcnv w:st="on" unitname="C" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0">3c</chmetcnv>867b2 Thread1: Waiting on Mutex1...
TID:<chmetcnv w:st="on" unitname="C" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0">3c</chmetcnv><chmetcnv w:st="on" unitname="C" sourcevalue="866" hasspace="False" negative="False" numbertype="1" tcsc="0">866c</chmetcnv>2 Thread3: Executing BEFORE releasing the MUTEX...
TID:<chmetcnv w:st="on" unitname="C" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0">3c</chmetcnv><chmetcnv w:st="on" unitname="C" sourcevalue="866" hasspace="False" negative="False" numbertype="1" tcsc="0">866c</chmetcnv>2 Thread3: Executing BEFORE releasing the MUTEX...
......
TID:<chmetcnv w:st="on" unitname="C" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0">3c</chmetcnv><chmetcnv w:st="on" unitname="C" sourcevalue="866" hasspace="False" negative="False" numbertype="1" tcsc="0">866c</chmetcnv>2 Thread3: Executing BEFORE releasing the MUTEX...
TID:<chmetcnv w:st="on" unitname="C" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0">3c</chmetcnv><chmetcnv w:st="on" unitname="C" sourcevalue="866" hasspace="False" negative="False" numbertype="1" tcsc="0">866c</chmetcnv>2 Thread3: Executing BEFORE releasing the MUTEX...
TID:<chmetcnv w:st="on" unitname="C" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0">3c</chmetcnv><chmetcnv w:st="on" unitname="C" sourcevalue="866" hasspace="False" negative="False" numbertype="1" tcsc="0">866c</chmetcnv>2 Thread3: Released the mutex1.
TID:a<chmetcnv w:st="on" unitname="C" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0">3c</chmetcnv>867b2 Thread1: GOT g_Mutex1, and will resume.
TID:a<chmetcnv w:st="on" unitname="C" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0">3c</chmetcnv>867b2 Thread1: Executing AFTER getting the MUTEX...
TID:a<chmetcnv w:st="on" unitname="C" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0">3c</chmetcnv>867b2 Thread1: Executing AFTER getting the MUTEX...
TID:a<chmetcnv w:st="on" unitname="C" sourcevalue="3" hasspace="False" negative="False" numbertype="1" tcsc="0">3c</chmetcnv>867b2 Thread1: Executing AFTER getting the MUTEX...
......

结果中的斜体加粗部分标识了图二的T3－T4时刻的操作。Thread3由于拥有Thread1欲申请的同步资源g_Mutex1而继承了Thread1的优先级，获得了执行。

结果中的粗体加下划线部分标识了图二的T4时刻的操作。Thread3释放同步资源g_Mutex1，Thread3的优先级被恢复到T3之前；Thread1获得了g_Mutex1之后继续执行。

<chsdate w:st="on" year="1899" month="12" day="30" islunardate="False" isrocdate="False"><strong style=""><span lang="EN-US" style="font-size: 12pt;">2.2.3</span></strong></chsdate> 用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.
◇ Uresh Vahalia, UNIX Internals: The New Frontiers, PEARSON EDU / 人民邮电出版社影印, 2003/2003.7

关于作者

田海立，硕士，国家系统分析师，中国系统分析员协会顾问团专业顾问。
您可以通过 HaiLi.Tian(at)csai.cn 或 TianHaiLi(at)nju.org.cn 与他联系，到 http://blog.csdn.net/thl789/ 看他最新的文章。

版权声明：

◇ 本文为作者原创作品，版权归作者所有。
◇ 为了学习和研究，可转载本文，但必须与原文的内容和格式保持一致，并给出原文的链接！

http://blog.csdn.net/thl789/archive/2006/03/07/617629.aspx