跳至正文
杂学书库让好奇心有所归处
简体中文

急事反而排后?优先级反转(Priority Inversion)

一位组长马上要开当天最紧急的会议,正在等会议室的钥匙。可是拿着钥匙的新员工不断被其他前辈叫去跑腿,迟迟腾不出会议室。最重要的事最晚处理,这种奇怪的情况在计算机里也一模一样地发生,这就是“优先级反转(Priority Inversion)”。

简单来说,优先级反转是指“高优先级任务因等待低优先级任务占用的共享资源,实际上被降到更低优先级的现象”。这是多个任务按固定优先级分享处理器的实时系统中早已为人所知的问题;1997年,火星探测器火星探路者号(Mars Pathfinder)在火星上反复重启,使它广为人知。

本文将依次介绍优先级反转如何发生、用三个任务看它的工作原理、在火星上真实发生的探路者号事件,以及防止它的方法与教训。


当高优先级等待低优先级

1. 优先级反转是怎样发生的

红色土壤和石块散布的火星平原上,一辆六轮小型探测车停在像花瓣一样展开面板的着陆器前,留下一道车辙

在优先级调度中,处理器总是先交给就绪任务中优先级最高的那一个。当多个任务共同使用同一资源时,这条简单的规则就开始动摇。

(1)共享资源与锁
多个任务同时修改同一块内存或同一个设备,数据就会混乱。因此操作系统设置互斥锁(Mutex)之类的锁,让同一时间只有一个任务使用该资源。先拿到锁的任务不论优先级高低,在完成工作、释放锁之前都会独占资源。

(2)高优先级任务的等待
低优先级任务持有锁时,如果高优先级任务请求同一资源,高优先级任务必须停下,直到锁被释放。只要低优先级任务完成短短的临界区,锁很快就会释放,因此这种程度的等待属于可以事先计算的“有界反转”。

(3)中优先级任务插队
真正的麻烦出现在这期间有一个与锁无关的中优先级任务被唤醒。中优先级任务比低优先级任务优先级高,于是抢走处理器,低优先级任务只好握着锁停下。结果,高优先级任务要等到比自己优先级低的中优先级任务结束才能运行;如果中优先级任务很多,等待就会无止境地拉长。


2. 用三个任务看工作原理

绿色田野之间狭窄的单车道老石桥上,一辆旧拖拉机缓缓驶过,一辆红色跑车停在桥前的路上等待

优先级反转通常用高、中、低三个任务来说明。只看优先级,高优先级任务应该最先完成,但只要中间夹着一把锁,实际的执行顺序就会颠倒。

优先级反转(Priority Inversion)发生与解决信息图:低优先级任务持有锁、高优先级任务等待、中优先级任务插队,顺序颠倒;优先级继承让低优先级任务暂时提升,高优先级任务立即执行
由于低优先级任务持有的锁,高优先级任务比中优先级任务完成得更晚;采用优先级继承后,低优先级任务暂时提升,能迅速释放锁。
  • 优先级调度(Priority Scheduling):为每个任务设定优先级,在就绪任务中先处理优先级最高者的方式。高优先级任务被唤醒时,会让低优先级任务停下并接管处理器。
  • 互斥锁(Mutex):“互斥(Mutual Exclusion)”的简称,是让同一时间只有一个任务使用共享资源的锁。
  • 临界区(Critical Section):持有锁并操作共享资源的代码段。越短,其他任务等待的时间也越少。
  • 有界反转与无界反转(Bounded and Unbounded Inversion):高优先级任务只等待低优先级任务的临界区那么久,叫有界反转;中优先级任务也插进来、使等待时间无法确定上限,叫无界反转。

在实时系统中,可怕的是无界反转,因为必须在规定时间内完成的任务,将无法知道什么时候才能完成。表面上每个任务都按规则遵守优先级,整体结果却像优先级被颠倒了一样,这正是这个问题难以发现的原因。


3. 在火星上发生的探路者号事件

明亮实验室的金属工作台上,放着装有太阳能板的六轮探测车测试模型、绿色电路板、打开的设备箱和成束的电缆

让优先级反转最广为人知的事件发生在火星上。1997年7月4日登陆火星的美国国家航空航天局(NASA)火星探路者号,在着陆几天后开始出现整个系统突然重启的问题。

(1)反复重启
探路者号的计算机运行的是风河系统公司(Wind River Systems)的实时操作系统VxWorks。问题出现在探测器开始收集气象数据前后。每次重启,当天计划的工作都会推迟到第二天,因此地球上的运营团队必须尽快找出原因。

(2)在地球上重现的原因
喷气推进实验室(JPL)团队在地球上的测试设备上开启记录功能运行同样的情况,不到18小时就成功再次引发重启。原因是教科书式的优先级反转:低优先级的气象数据任务持有锁期间,中优先级任务得以运行,而等待这把锁的高优先级信息总线管理任务没能在规定周期内完成。上层管理任务发现这一点,判断为严重错误,于是触发了重启。

(3)只改一个全局变量的远程修复
出问题的锁是以默认设置创建的,出于性能考虑,优先级继承功能处于关闭状态。团队向火星上的探测器发送了一个修改一个全局变量值、打开该功能的补丁,解决了问题。这件事在同年12月的实时系统学术会议上被介绍后广为人知,飞行软件负责人格伦·里夫斯(Glenn Reeves)也亲自说明了经过。


4. 防止优先级反转的方法

晨光照进来的旧木桌上,放着一把锁梁打开的黄铜挂锁和一把黄铜钥匙

只要使用锁,就很难完全消除优先级反转,但可以防止等待无止境地拉长。代表性的解决办法整理在1990年Lui Sha、Ragunathan Rajkumar、John Lehoczky发表的优先级继承协议(Priority Inheritance Protocols)论文中。

(1)优先级继承
高优先级任务开始等待锁时,把持有锁的低优先级任务的优先级暂时提升到与高优先级任务相同。这样中优先级任务就插不进来,低优先级任务会迅速结束临界区,一释放锁就回到原来的优先级。拯救探路者号的正是这种方法。

(2)优先级天花板协议
这种方式为每把锁预先设定“上限”,即可能使用这把锁的任务中最高的优先级。同一篇论文提出的这一方法,能让最长等待时间事先计算出来,还能防止锁与锁相互咬住而停止的死锁。

(3)设计中的教训
把持有锁的区间做短,并在设计上避免优先级相差很大的任务共用同一资源,也很重要。如今许多实时操作系统和Linux都提供支持优先级继承的锁。探路者号的案例还说明,检查一个默认设置、保留能够重现问题的记录功能有多么重要。

“暂时推一把挡住急事的慢任务,让它先完成”,这个简单的想法,就是理解优先级反转的第一步。

将本文保存为PDF

购买当前文章的所选语言版本。

US$1.00
所选语言: 简体中文

US$1.00 · 一篇文章 · 一种语言

请选择购买方式

以会员身份购买
  • 在任何设备上登录即可再次下载
  • 保存在您的购买记录中
无需账号购买
  • 无需注册,直接付款
  • 可在此浏览器中再次下载
  • 在其他设备上,请使用购买后显示的个人链接
  • 之后在此浏览器中以会员身份登录,购买记录会转入您的账户
  • 如果遗失链接并清除浏览器Cookie,可能无法再次下载

正在查询购买记录……

卖家信息

商号
아카이지
代表人
안호원
营业登记号
530-02-04118
网络销售申报编号
2026-경기군포-0626
申报机关
경기도 군포시
营业地址
경기도 군포시 산본천로 119-9, 1109동 405호 (산본동, 주공아파트)
托管服务提供方
카페24(주)
联系邮箱
sgjjojo@gmail.com
联系电话
010-4194-0821

查看商家登记信息(韩国公平交易委员会)