优先级反转的有趣案例——火星拓荒者

时间:2024-04-05 12:11:06

火星拓荒者(Mars Pathfinder)是一艘在1997年携带探测车登陆火星并建立基地的美国太空船。它包括命名为卡尔萨冈纪念站的登陆者,和一辆重量很轻 (10.6公斤/23磅),命名为旅居者号的轮型机器人火星车。这艘太空船于火星全球探勘者号发射一个月之后的1996年12月4日由德爾它 II发射,并于1997年7月4日于火星上称为欧克西亚沼区的克里斯平原阿瑞斯谷着陆。

火星拓荒者号着陆后﹐开始把数据传送回地球。几天后,信息和图像传送就被一系列的总系统复位所中断。对于软件工程师来说,这个问题是被如何诊断和解决的,仍然是一个引人入胜的故事。


1. 什么是优先级反转?

优先级反转是指一个低优先级的任务持有一个被高优先级任务所需要的共享资源。高优先级任务由于因资源缺乏而处于阻塞状态,一直等到低优先级任务释放资源为止。而低优先级获得的CPU时间少,如果此时有优先级处于两者之间的任务,并且不需要那个共享资源,则该中优先级的任务反而超过这两个任务而获得CPU时间。如果高优先级等待资源时不是阻塞等待,而是忙循环,则可能永远无法获得资源,因为此时低优先级进程无法与高优先级进程争夺CPU时间,从而无法执行,进而无法释放资源,造成的后果就是高优先级任务无法获得资源而继续推进。

简而言之,中优先级的线程一直占据着CPU,导致低优先级线程无法执行,而高优先级线程必须等待低优先级线程执行完释放资源(共享资源)才能执行。

2. 故障发生

故障源自于操作系统中经典的优先级反转问题。

火星探测器有一个信息总线,有一个高优先级的总线管理任务负责总线数据的存取,访问总线都需要通过一个互斥锁;还有一个低优先级的,运行不是很频繁的气象搜集任务,它需要对总线写数据,也就同样需要访问互斥锁;最后还有一个中优先级的通信任务,它的运行时间比较长。

平常,这个系统运行毫无问题,但是有一天,在气象任务获得互斥锁往总线写数据的时候,一个中断发生导致通信任务被调度就绪,通信任务(中优先级)抢占了低优先级的气象任务,而无巧不成书的是,此时高优先级的总线任务正在等待气象任务写完数据归还互斥锁,但是由于通信任务抢占了CPU并且运行时间比较长,导致气象任务得不到CPU时间也无法释放互斥锁,本来是高优先级的总线管理任务也无法执行,总线任务无法及时执行的后果被火星探路者系统认为是一个严重错误,最后就是整个系统被重启。


优先级反转的有趣案例——火星拓荒者

3. 解决方案

解决优先级反转的一个方法就是优先级捐赠。考虑高,中,和低优先级线程H,M和L. 如果H需要等待L(例如,L正在持有锁),并且M在就绪等待列表中,则H 将永远不会获得CPU,所以在L持有锁的同时,H需要将其优先级“捐赠”给L,L获得了高优先级,这使得L能够抢占M。然后一旦L释放(并因此H获得)锁,便撤回捐赠,回到原来的低优先级。

Vxworks允许优先级继承,然而遗憾的工程师们将这个选项关闭了。

工程师们疯狂的工作在实验室复制品上去诊断和解决这个问题,最终发现了优先级反转。为了解决这个问题,工程师们开启了一个布尔参数,来指示是否应该进行互斥锁定的优先级继承。 上述的互斥锁定已经把该参数关闭;如果打开它,优先级反转就能被阻止,故障就这样被修复完成了。

参考来源:https://www.zhihu.com/question/21460912/answer/18299338