拓荒者号飞行器在1997年7月4日登陆火星,并开始收集星球上的数据,并将数据传送回地球。但是在任务开始几天后,飞行器就开始经历重置整个系统的bug。这导致了大量珍贵的采集数据的丢失。在经历了制作团队(Jet Propulsion Laboratory)巨大的努力排查之后,发现问题的根源在于系统调度中的优先级翻转问题。
对于任何一个设置优先级的操作系统,系统都会先执行优先级最高的任务。优先级翻转是指当系统由于某些原因不得不等待低优先级的任务完成,才让高优先级任务执行的情况。这种看似不合理的情况是非常容易发生的。比如说,为了保证系统运行结果的正确性,公共变量不得不在被使用时先“锁”起来。当程序A在执行过程中,如果占用了某个公共变量X,任何其他的程序,比如B都不可以访问这个变量X。B能做的只有等待A在使用完这个变量,并且释放了对这个变量的控制权之后,才可以去访问这个公共变量X。通常实现这个的方法是设置semaphore。当B的优先级比A高的时候,优先级翻转的问题就随之产生了。
优先级翻转还会带来一个问题,就是在高优先级任务等待低优先级任务完成的时候,可能这个高优先级任务本身就会错过完成的截止日期,这反过来又会影响到其他的程序,翻来覆去就会对整个系统就会造成致命的影响。
回到拓荒者飞行器的故事上,简单来说它的操作系统总共设置了3个任务,优先级依次下降:
T1:周期性的检测飞行器系统和软件是否工作正常
T2:处理图像数据 T3:随机对某些设备的状态进行检测
当任务T1完成后,系统中的看门狗时钟就会被重置到最大值。如果看门狗的数值降低到负值,也就是说当T1没有按时完成时,系统就会认为整个操作系统一定是在某个地方出现了比较严重的问题,安全起见,操作系统就会重置所有的软件以及硬件。这个操作会花费大量的时间。同时系统设定,T1和T3共同拥有一个公共数据结构(即变量)。
下图描述了优先级翻转发生的过程:
t1时刻:T3开始执行
t2时刻:T3锁住了semaphore,也就是s,导致其他程序无法访问公共变量s t3时刻:T1由于拥有更高的优先级,替代了T3,并让自己开始执行 t4时刻:T1想要访问公共变量s,但是由于T3已经锁住了公共变量s,所以T1无法访问公共变量s,只好暂停程序 t5时刻:T2由于拥有比T3更高的优先级,于是开始执行 t6时刻:T2由于一些其他的因素暂停执行,这些因素于T1和T_无关,所以T2可能执行了很长时间 t7时刻:T3终于获得机会执行,在使用完公共变量s并将其释放后,T1立刻抢占了资源,开始执行
由上述过程可以发现,T1必须等待T2和T3都执行完之后才可以执行完自己的程序。这么做的后果是很有可能T1无法按时完成,导致系统重启。
一个比较好的解决方案就是,引入优先级继承的机制,即,在T3锁住公共变量后,它遍继承了和它共享这个公共变量的T1的优先级,如下图所示,这样就可以很大程度上避免上述问题。具体的步骤如下所示:
t1时刻:T3开始执行
t2时刻:T3锁住了semaphore,也就是s,导致其他程序无法访问公共变量s t3时刻:T1由于拥有更高的优先级,替代了T3,并让自己开始执行 t4时刻:T1想要访问公共变量s,但是由于T3已经锁住了公共变量s,所以T1无法访问公共变量s,只好暂停程序,但同时,T1将自己的优先级赋予了T3 t5时刻:T2想要执行,但是此时其优先级小于T3,所以暂不执行 t6时刻:T3执行完对于公共区域内的一系列程序,向T1返还优先级。这时T1抢占了T3的资源开始执行 t7时刻:T1执行完毕,换T2执行