优先级翻转与优先级继承

ゝ一世哀愁。 2022-08-01 14:51 130阅读 0赞

**优先级翻转与优先级继承**

**[田海立][Link 1]**

**2006-3-7**

** **

摘要

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

** **

## 目  录 ##

[摘要][Link 2]  
[1 优先级翻转（Priority Inversion）][1_Priority Inversion]  
[2 优先级继承（Priority Inheritance）][2_Priority Inheritance]  
[       ][Link 3][2.1 优先级继承][Link 3]  
[       ][Link 4][2.2 WinCE中优先级继承][Link 4]  
[       ][Link 5][2.3 优先级继承的传递性][Link 5]  
[3 总结][3]  
[参考资料及进一步阅读][Link 6]  
[关于作者][Link 7]

** **

## 1 优先级翻转（Priority Inversion） ##

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

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

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

![PriorInversion1.jpg][]

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

**◇ ***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引入了优先级继承的解决方法。**优先级继承**也就是，高优先级进程TH在等待低优先级的线程TL继承占用的竞争资源时，为了使TH能够尽快获得调度运行，由操作系统把TL的优先级提高到TH的优先级，从而让TL以TH的优先级参与调度，尽快让TL执行并释放调TH欲获得的竞争资源，然后TL的优先级调整到继承前的水平，此时TH可获得竞争资源而继续执行。

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

![PriorInversion2.jpg][]

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

与图一比较，**图二中**，到了*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 程序设计**

**主线程**做了如下工作：  
       **◇ **创建三个子线程，设置它们的优先级顺序：  
              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...”

**2.2.2 Log结果分析**

结果输出如下：

TID:a3ecaa1e **Thread1**: Handler = a3c867b2, ThreadId = a3c867b2  
       TID:a3ecaa1e **Thread2**: Handler = 83c8c002, ThreadId = 83c8c002  
       TID:a3ecaa1e **Thread3**: Handler = 3c866c2, ThreadId = 3c866c2  
       TID:3c866c2 **Thread3** GOT the Mutex g\_Mutex1  
       TID:83c8c002 **Thread2**: Start executing...   
       TID:83c8c002 **Thread2**: executing...   
       TID:a3c867b2 **Thread1**: Start executing...   
       TID:a3c867b2 **Thread1**: Waiting on Mutex1...   
       ***TID:3c866c2 Thread3: Executing BEFORE releasing the MUTEX...   
       TID:3c866c2 Thread3: Executing BEFORE releasing the MUTEX...   
       ......   
       TID:3c866c2 Thread3: Executing BEFORE releasing the MUTEX...   
       TID:3c866c2 Thread3: Executing BEFORE releasing the MUTEX...*   
       TID:3c866c2 Thread3: Released the mutex1.   
       TID:a3c867b2 Thread1: GOT g\_Mutex1, and will resume.   
       TID:a3c867b2 Thread1: Executing AFTER getting the MUTEX...**   
       TID:a3c867b2 **Thread1**: Executing AFTER getting the MUTEX...   
       TID:a3c867b2 **Thread1**: Executing AFTER getting the MUTEX...   
       **......**

结果中的***斜体加粗部分***标识了图二的*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。

![PriorInversion3.jpg][]

**图三、通过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得到的一个快照。

![PriorInversion4.jpg][]

**图四、通过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] 看他最新的文章。

**版权声明：**

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

[ http://blog.csdn.net/thl789/archive/2006/03/07/617629.aspx][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开始执行。

![实时系统中的优先级翻转问题][0_13259203570fL6.gif]

例子中，由于t1等待t3的资源，而让t2这个家伙抢了先执行，优先级翻转了！

归纳一下：高优先级的任务等待一个被低优先级任务霸占的资源而阻塞，而霸占这个资源的低优先级任务又很容易被其他中等优先级的任务抢占进而阻塞，导致高优先级任务迟迟得不到运行。

*=========*

*解决办法：*

*=========*

**1，优先级继承**

当t1需要访问t3的已经霸占的打印机的时候，会被阻塞，在阻塞t1的时候，顺便把t3的优先级提高到t1的优先级p1，这样任何比t1的优先级低的任务，比如说t2，就甭想抢占t3的cpu来执行。当t3释放打印机的时候，如果之前有过优先级提高，就把t3的优先级打回原形p3。

也就是说，t1 如果“碰”到了t3的资源的，t3的优先级被提高到t1的优先级，t3释放资源的时候，恢复到自己本来的优先级。

![实时系统中的优先级翻转问题][0_1325920729faOZ.gif]

**2,优先级天花板**

在优先权极限方案中，系统把每一个临界资源与一个极限优先权相联系。

这个极限优先权等于系统此时最高优先权加1。

当1个任务进入临界区时，系统便把这个极限优先权传递给这个任务，使得这个任务的优先权最高；

当这个任务退出临界区后，系统立即把它的优先权恢复正常，从而保证系统不会出现优先权反转的情况。

如上例中，当t3进入临界区时，立即(而不是等到t1来“触碰”的时候)把它的优先权升高到极限优先权，

这个时候t3可“安心的”使用资源直到释放，

但是t3此时也应该 "自觉地" 能尽快退出临界区，进而释放其占有的信号量。

当高优先级任务 t1执行的时候就不会出现其等待低优先级任务t3释放信号量而被阻塞的情况，

从而保证不会出现上面所说的优先级反转。

优先级天花板的本质是让占有资源的任务尽快执行完,并释放资源,从而使与其竞争资源的高优先级任务尽快地得到执行,并通过良好定义的调度规则使任务不会交错占有资源而形成环路等待,从而保证死锁不会发生。(http://www.laogu.com/wz\_10162.htm)

[Link 1]: http://blog.csdn.net/thl789/article/details/617629#_关于作者
[Link 2]: http://blog.csdn.net/thl789/article/details/617629#_Toc129492691
[1_Priority Inversion]: http://blog.csdn.net/thl789/article/details/617629#_Toc129492692
[2_Priority Inheritance]: http://blog.csdn.net/thl789/article/details/617629#_Toc129492693
[Link 3]: http://blog.csdn.net/thl789/article/details/617629#_Toc129492694
[Link 4]: http://blog.csdn.net/thl789/article/details/617629#_Toc129492695
[Link 5]: http://blog.csdn.net/thl789/article/details/617629#_Toc129492696
[3]: http://blog.csdn.net/thl789/article/details/617629#_Toc129492697
[Link 6]: http://blog.csdn.net/thl789/article/details/617629#_Toc129492698
[Link 7]: http://blog.csdn.net/thl789/article/details/617629#_Toc129492699
[PriorInversion1.jpg]: /images/20220731/9285507f4b6a43f3b4ea2b4c393fd380.png
[PriorInversion2.jpg]: /images/20220731/6bfefd5c9cca4ff7a5aa0c4f2a19a733.png
[PriorInversion3.jpg]: /images/20220731/f8a0de34c9894cf78b5e79e13a9732af.png
[PriorInversion4.jpg]: /images/20220731/2e5f58c2aac94e47909b30d67b23654d.png
[http_blog.csdn.net_thl789]: http://blog.csdn.net/thl789/
[http_blog.csdn.net_thl789_archive_2006_03_07_617629.aspx]: http://blog.csdn.net/thl789/archive/2006/03/07/617629.aspx
[0_13259203570fL6.gif]: /images/20220731/2717cbfa9aca480a83a6397fbd17775d.png
[0_1325920729faOZ.gif]: /images/20220731/f8167fc94ab44faf8ec9e144f9c454aa.png

发表评论取消回复

表情：

评论列表（有 0 条评论，130人围观）

还没有评论，来说两句吧...

相关阅读

相关 c语言[]优先级大于*优先级

本博文源于笔者正在学习的c语言[]优先级大于*优先级.在定义二维数组时，a+1与[]号结合后，谁的优先级更高，是本博文探讨的话题

待我称王封你为后i/ 2024年04月20日 04:07/ 0 赞/ 12 阅读

相关 css优先级介绍：ID优先级、class与元素选择器

![31e3c653d5c3b1e1cf6c5c987f1476be.jpeg][] 转自：[微点阅读][Link 1] [https://www.weidianyuedu.

╰半夏微凉°/ 2024年03月25日 10:44/ 0 赞/ 21 阅读

相关 Scala操作符与优先级

Scala为它的基本类型提供了丰富的操作符集，包括：算术运算符：加（+），减（-），乘（\），除（/），余数（%）；关系运算符：大于（>），小于（<），等

偏执的太偏执、/ 2022年12月18日 03:56/ 0 赞/ 85 阅读

相关 uC/OS-II学习笔记——优先级反转与优先级继承机制

1. 优先级反转（Priority Inversion）优先级反转，是指某同步资源被较低优先级的进程/线程所拥有，较高优先级的进程/线程竞争该同步资源未获得该资源，而

灰太狼/ 2022年08月02日 15:47/ 0 赞/ 163 阅读

相关优先级翻转与优先级继承

优先级翻转与优先级继承 [田海立][Link 1] 2006-3-7 摘要本文描述操作系统中的优先级翻转（Priority Inversion，

ゝ一世哀愁。/ 2022年08月01日 14:51/ 0 赞/ 131 阅读

相关优先级队列

前面说过普通队列以及循环队列的使用。关于队列还有一种常用的数据结构：优先级队列。先来看一下下面实际背景：在办公的时候，桌面上会有一堆需要处理的文件。但是事有轻重缓急，

心已赠人/ 2022年07月18日 00:26/ 0 赞/ 212 阅读

相关 CSS —— 继承body 确保最高优先级

样式优先级：内联>内部css>外部css. 知道这还不够，有时样式较多时，从某个样式class 中定义某个元素或类的样式，可能没效果，最简单粗暴的方法：直接继承body，如使

Dear 丶/ 2022年06月07日 10:56/ 0 赞/ 149 阅读

相关 FreeRTOS优先级翻转

举例 //高优先级任务的任务函数 void high_task(void pvParameters) { while(1)

男娘i/ 2022年05月30日 00:09/ 0 赞/ 152 阅读

相关 Priority Inversion - 优先级翻转

英文： Priority Inversion 中文：优先级翻转、优先级倒置、优先级逆转介绍：即当一个高优先级任务通过信号量机制访问共享资源时，该信号量已被一低优先

爱被打了一巴掌/ 2022年05月24日 22:56/ 0 赞/ 126 阅读

相关样式的继承+选择器的优先级+伪类的优先级

1.样式的继承 1 <!DOCTYPE html> 2 <html> 3 <head> 4 <meta char

心已赠人/ 2021年11月17日 17:38/ 0 赞/ 283 阅读