嵌入式实时操作系统中优先级翻转问题的分析与解决方案

明亮 posted @ 2011年3月27日 19:45 in 【科学综合】 , 2245 阅读
本文发表于:http://fml927.is-programmer.com

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

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

所谓优先级翻转问题(priority inversion)即当一个高优先级任务通过信号量机制访问共享资源时,该信号量已被一低优先级任务占有, 而这个低优先级任务在访问共享资源时可能又被其它一些中等优先级的任务抢先, 因此造成高优先级任务被许多具有较低优先级的任务阻塞, 实时性难以得到保证。

2 解决优先级翻转问题有优先级天花板(priority ceiling)和优先级继承(priority inheritance)两种办法。

2.1 优先级天花板是当任务申请某资源时, 把该任务的优先级提升到可访问这个资源的所有任务中的最高优先级, 这个优先级称为该资源的优先级天花板。这种方法简单易行, 不必进行复杂的判断, 不管任务是否阻塞了高优先级任务的运行, 只要任务访问共享资源都会提升任务的优先级。

2.2 优先级继承是当任务A 申请共享资源S 时, 如果S正在被任务C 使用,通过比较任务C 与自身的优先级,如发现任务C 的优先级小于自身的优先级, 则将任务C的优先级提升到自身的优先级, 任务C 释放资源S 后,再恢复任务C 的原优先级。这种方法只在占有资源的低优先级任务阻塞了高优先级任务时才动态的改变任务的优先级,如果过程较复杂, 则需要进行判断。

2.3 优先级继承的传递性
优先级继承的传递性,是指图二的优先级继承发生时,在Thread3的优先级已经提升到Thread1执行的T3-T4时间段里,如果Thread3竞争比Thread3的初始优先级还要低的线程Thread4拥有的同步资源,操作系统同样会把Thread4的优先级提升到Thread1的优先级。SUN的Solaris系统实现了优先级继承和继承的传递,Microsoft的Windows CE虽然实现了优先级继承,但是它只实现了一级,即,没有实现优先级继承的传递性。

3 总结
优先级翻转是多线程环境中应该尽力避免的现象,尤其是依赖线程优先级来调度的系统中。在设计多线程程序时候,避免优先级翻转的最简单方法,就是不要让不同优先级的线程去竞争同一个同步资源。

优先级继承可以减缓优先级翻转带来的问题,但是也不能保证优先级最高的线程绝对地被最先调度执行,还是有一定的延缓时间。如果有优先级继承的传递性,传递的级别很深时,对系统性能的影响还是很大的。


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

       ◇ 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的被调度时机就不能保证,整个实时调度的性能就很差了。


1. 优先级反转(Priority Inversion)
    由于多进程共享资源,具有最高优先权的进程被低优先级进程阻塞,反而使具有中优先级的进程先于高优先级的进程执行,导致系统的崩溃。这就是所谓的优先级反转(Priority Inversion)。

2. 产生原因
      其实,优先级反转是在高优级(假设为A)的任务要访问一个被低优先级任务(假设为C)占有的资源时,被阻塞.而此时又有优先级高于占有资源的任务(C)而低于被阻塞的任务(A)的优先级的任务(假设为B)时,于是,占有资源的任务就被挂起(占有的资源仍为它占有),因为占有资源的任务优先级很低,所以,它可能一直被另外的任务挂起.而它占有的资源也就一直不能释放,这样,引起任务A一直没办法执行.而比它优先低的任务却可以执行. 

      所以,一个解决办法就是提高占有资源任务的优先级,让它正常执行,然后释放资源,以让任务A能正常获取资源而得以执行.

3. 解决方案 ( 优先级继承 / 优先级天花板 )

   目前解决优先级反转有许多种方法。其中普遍使用的有2种方法:一种被称作优先级继承(priority inheritance);另一种被称作优先级极限(priority ceilings)。

  A. 优先级继承(priority inheritance)
      优先级继承是指将低优先级任务的优先级提升到等待它所占有的资源的最高优先级任务的优先级.当高优先级任务由于等待资源而被阻塞时,此时资源的拥有者的优先级将会自动被提升.  
  B. 优先级天花板(priority ceilings)
      优先级天花板是指将申请某资源的任务的优先级提升到可能访问该资源的所有任务中最高优先级任务的优先级.(这个优先级称为该资源的优先级天花板)  
  A 和B的区别: 
优先级继承,只有当占有资源的低优先级的任务被阻塞时,才会提高占有资源任务的优先级,而优先级天花板,不论是否发生阻塞,都提升.

  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter