最新消息:20190717 VPS服务器:Vultr新加坡,WordPress主题:大前端D8,统一介绍入口:关于

【整理】什么是优先级反转+有何危害+如何避免和解决

Thread crifan 2597浏览 0评论

背景

很早之前,学习操作系统原理时,在进程调度时,就听说过:

优先级反转

后来在了解ucOS/II时,又遇到过。

之前,也大概了解过,但是基本上是半懂不懂的。

最后又看到这个优先级反转。

所以打算去整理一下

 

什么是优先级反转

优先级反转,英文是priority inversion,也有其他叫法:

  • 优先级倒置
  • 优先级逆转
  • 优先级翻转

 

先要明白背景知识:

1.操作系统的任务调度

操作系统有多个任务

任务之间谁可以得到执行,是通过任务调度来完成的

2.任务调度有多种方法(算法)

常见的有:

  • 罗宾环调度算法:Round-robin scheduling algorithm
  • 基于优先级的调度算法:Priority-controlled scheduling algorithm

3.任务调度的一种常见调度算法就是

根据优先级高低去调度,优先让高优先级的任务去执行的

核心逻辑可以总结为:

任务调度器,总是去激活某个,在所有任务中优先级是最高的,且处于就绪状态的,任务,即让其去执行

4.任务有多种状态:就绪,挂起,等等

当然,任何任务,都可能由于,需要某种资源,而该资源被别人(别的任务)占用,而无法继续运行下去

此时就变成:挂起 –> 等待其所需要的资源被释放

然后才可以继续变成,就绪,等待下次调度时,就可以继续执行了。

5.任务一般被称为:进程,或更小粒度的线程

 

此处,均以进程为例来说明

先直接上图:

priority inversion graphic explanation

然后再解释:

前面已知:

任务调度器,总是去激活某个,在所有任务中优先级是最高的,且处于就绪状态的,任务,即让其去执行

但是,当某个最高优先级的任务A,由于其所需要的某个资源被某个低优先级的任务C占用了(还没使用完,还没释放),所以高优先级任务A就被阻塞了。

按照调度规则:

此高优先级的任务A,必须等到低优先级任务C,把其所占用的资源释放掉后,才能继续运行。

但是要等到低优先级任务C释放其所占用的资源的话,则很明显,必须要先让低优先级的任务C去执行,等低优先级任务C执行完毕后,才能去释放,高优先级任务A所希望得到的那个资源。

所以,任务调度去,就去调度,让低优先级任务C去执行了。

但是,此时,的问题就来了:

在高优先级任务A执行的这段时间内,某个中优先级的任务B,已经处于就绪状态了。

所以使得:

当高优先级的任务A,由于所需资源被占用而挂起,然后中优先级的任务B,由于比(本来打算去调度执行的)低优先级任务C的优先级高,所以被调度执行,然后B去一直执行,直到结束。

此种情况就是:

一个具有中等优先级的任务(B),却比一个更高优先级的任务(A)先执行

就叫做:

优先级反转

即:

本来应该是优先级最高的任务A先执行的,结果却变成了,比优先级最高的任务A,的优先级低一些,中等优先级任务B,先执行了。

好像是:高优先级任务A和中优先级任务B,两者之间的优先级调换了,反转了一样。

所以叫做:优先级反转

 

优先级反转有何危害?

说实话,很久之前,对于:

计算机的概念,都完全只是概念到时候

完全不懂相关技术和概念背后的逻辑的时候

像对于此处的优先级反转,也无法完全理解的时候,自然也不会去考虑此概念背后的含义。

而实际上,不对一个问题背后的现象,原因,去搞清楚的话,自然也是无法理解相关的概念的

此处就是:

(对于,对现实世界中的应用情况不了解,对于概念也理解的不深的话,很可能就会问)

(不就是个优先级反转嘛)即使,发生了优先级反转了,又如何?(地球还不是照转?!)

但是,实际上是:

优先级的反转,有很大危害。

但是,在具体解释优先级反转的危害之前,需要知道相关背景知识:

1.优先级反转,这个概念,往往都是在嵌入式领域内,尤其是嵌入式实时系统方面,才会提及

关于嵌入式实时操作系统,不熟悉的,可以参考:

【整理】嵌入式实时操作系统

2.嵌入式实时操作系统,最最重要的指标就是:确保任务执行时间是可预测的,即涉及到最后期限deadline

比如:

要确保,任何时刻,执行某个任务,都不能超过某个时间,比如1ms(我随便举例的)

 

然后再来解释,优先级反转的危害:

  • 由于优先级反转,造成任务调度时,时间的不确定性。
    • 时间不确定,破坏了实时系统的实时性
      • 严重时可能导致系统崩溃
  • 由于本身基于优先级设计的任务,每个优先级不同的任务,往往对应着实际的现实中的执行的任务
    • 其优先级反转,导致低优先级比高优先级先执行了
      • 直接就导致任务错乱,逻辑错乱了
        • 程序也就异常了?(待确定此部分的理解是否有误)

现实举例:

1.当年火星探路者号(Mars Pathfinder),就由于,此处所说的,优先级反转,而导致了内部执行逻辑出错的bug:

在1997年7月4号发射后,在开始搜集气象数据之后没几天,系统(无故)重启了。

后来,当然,被相关技术人员找到问题根源,就是,这个优先级反转所导致的,然后修复了此bug。

 

注:

当年火星探路者号用的软硬件是:

  • 硬件:
    • CPU:RS6000
    • 总线:VME Bus
    • 各种接口卡/外设:
      • 音频
      • 摄像头
      • 1553总线接口
  • 软件:
    • OS:(Wind River的)VxWorks

详见:

What really happened on Mars ?

What really happened on Mars?

 

如何解决或避免优先级反转?

既然,相对来说,优先级反转,这样的问题,对于,尤其是嵌入式实时系统中,危害这么大,

那么肯定N年前,就有人找到解决办法了:

优先级反转的解决办法:

禁止所有中断(以保护临近区)

当使用,禁止所有中断,来避免优先级反转时,需要满足下面的条件:

只存在两种优先级:

  • 可被抢占的
  • 中断已禁止的

由于没有别的第三种的优先级了,所以,也就不可能发生反转了。

(暂时没有完全理解此种的含义。。。。)

 

priority inheritance 优先级继承:

对于,占了高优先级任务A的某种所需资源的,低优先任务级C,

付给和A相同的优先级,

则:

当A被阻塞,要去调度,即使存在另一个中优先级任务B,则也可以实现:

由于此时低优先级任务C已有和A同样的优先级了,

则调度器自然会去执行:

比中优先级任务B的优先级高的C了。

然后,等C执行完毕后,就可以继续执行A了。

然后再执行B。

如图:

priority inheritence to avoid priority inversion

 

优先级继承的实际例子

还是以之前的

What really happened on Mars ?

中为例来来说明如何应用此,优先级继承:

参见:

HOW WAS THE PROBLEM CORRECTED?

中的解释:

VxWorks中的mutex对象,添加一个布尔值的参数,表示:

mutex是否使用优先级继承

当mutex初始化时,该参数是关闭的;

当此参数被打开时,低优先级的任务,就从高优先级的任务中继承了相同的优先级,

当然,背后是对应的检测机制:

可以判定出,当然被阻塞的高优先级的任务,所需要的资源,被当前自己这个低优先级任务所占用了

由此,解决了优先级反转的问题,避免了系统再次发生无故重启。

 

Priority Celling(最高优先级/优先级天花板)

给临界区,即上述的mutex等公用资源的部分

赋予最高优先级

由此,

凡是想要用到,临界区的资源的任务,

要进入临界区之前,都将临界区的优先级赋值给该任务,

使得该任务有了最高的优先级,可以不被打断,而始终继续运行,直到用到资源

然后退出临界区

这样,就避免了,被高优先级A发现某资源被低优先级的C占用之类的问题了

 

参考资料

embOS Real-Time Operating System

嵌入式系统优先级反转问题分析(作者:郭海训)

Real-time computing

Priority inversion

转载请注明:在路上 » 【整理】什么是优先级反转+有何危害+如何避免和解决

与本文相关的文章

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
58 queries in 0.106 seconds, using 18.64MB memory