《电子技术应用》
您所在的位置:首页 > 嵌入式技术 > 设计应用 > 实时控制系统中优先级反转问题的解决方法
实时控制系统中优先级反转问题的解决方法
唐宇翔,胡景春
南昌航空大学 信息工程学院,江西 南昌330063
摘要: 以实时操作系统μC/OS-II为例,分析了产生优先级反转的原因,提出了解决该问题的2种方法,即互斥信号量(Mutex)和实现时间片轮番调度法。在保证共享资源互斥访问的前提下,将优先级反转的发生有效地限制在一个层次上,降解了优先级反转现象的发生。
中图分类号: TP316.2
文献标识码: A
Research on reducing priority inversion problem in real-time control systems
TANG Yu Xiang,HU Jing Chun
School of Computer, Nanchang Hangkong University, Nanchang 330063,China
Abstract: Bases on the real-time operating system μC/OS-II, this paper analyses the reason that priority inversion bechanced and then gives exposition how to adjust this problem by mutual exclusive semaphores and time slice. On the precondition, of ensuring mutex visiting of the shared resources, the proposed approach limits the occurrence of priority inversion on one level, and alleviates the priority inversion phenomenon occurrence in μC/OS-II.
Key words : real-time system;priority inversion;priority inheritance

   μC/OS-II是由Jean Labrosse编写的具有高度可移植性且源码公开的嵌入式实时操作系统内核,可用于8 bit、16 bit、32 bit嵌入式微处理器或DSP中。μC/OS-II可以管理64个任务,各任务有自己单独的栈,采用基于优先级的可抢占式PBP(Priority Based Preemptive)调度策略,绝大多数服务的执行时间具有确定性μC/OS-II已被成功地应用于各种系统,在众多领域中,多种基于μC/OS-II设计的产品已经证明了μC/OS-II内核的稳定性,其安全性和稳定性已通过美国FAA认证。
    μC/OS-II操作系统同时也是可剥夺型内核,以保证最重要的进程(通常是优先级最高的进程)能够及时得到运行。但是如果用传统的信号量等机制对共享资源进行互斥操作,在某些时间里会出现高优先级进程被低优先级进程堵塞的现象,这种现象称为优先级反转。本文讨论优先级反转现象的原因,并给出2种抑制优先级反转现象的具体方法。
1 优先级反转现象
    使用实时内核,优先级反转问题是实时系统中出现最多的问题。优先级反转发生在一个高优先级的任务被迫等待一段不确定时间的过程中[1]。优先级反转现象示意图如图1。


    图1中,空白框为任务正常运行过程;阴影框为任务取得信号量后的运行过程。在图中3个任务优先级的高低为T1>T2>T3,T1和T3在运行过程中都需要使用同一资源,T2不需要使用该资源。当T3先占用该资源,T1任务需要等待,直到T3任务释放占用的共享资源。由于T2的优先级比T3高,所以剥夺了T3的CPU使用权,使得T3释放信号量的时间向后拖延,所以T1的运行情况更加恶化,T1取得信号量的时间随之推迟。这样,原本优先级最高的T1任务,在经过以上过程后,优先级反而降到了最低。这时,系统中就发生了优先级反转的现象。
    优先级反转原因可归纳为:高优先级的任务由于要等待被低优先级任务占有的临界资源而被中优先级任务阻塞,而此时具有中优先级的任务抢占了低优先级任务的CPU时间,导致具有中优先级的任务先于高优先级任务而执行。
2 优先级反转的解决方案
    优先级反转问题的解决办法有优先级置顶和优先级继承2种[2]。
    采用优先级置顶的方案,首先在创建互斥信号量时就应同时设置一个相应的置顶优先级,当首先申请到该资源的任务a未释放而又有一个更高优先级的任务b试图申请时,内核会将任务a的优先级提升到置顶优先级,该置顶优先级高于任何可能申请该资源任务的高优先级。优先级置顶的意义在于使占有资源的低优先级任务尽快完成,让高优先级任务的等待不至过长。
    而优先级继承的思想是:在出现上述情况时,提高低优先级任务的优先级使其与高优先级任务的优先级等同。而μC/OS-II却不支持这种方法[3],需要通过修改μC/OS-II内核来实现优先级继承。
2.1 优先级置顶方案
    要在μC/OS-II实现优先级置顶[4],需要用到互斥信号量(Mutex)。
    互斥型信号量的创建是由函数OSMutexCreate( )完成的,它首先检查PCP的优先级数值是否己经被其他任务使用,如果还没有使用就占用这个优先级。然后得到一个新的事件控制块ECB,OSMutexCreate( )置mutex的值为有效,同时将PCP保存起来。
    OSMutexPend( )函数在获取互斥信号量Mutex时,如果Mutex可用,并且占有信号量任务的优先级不是最高,则提升此任务的优先级置PIP,即置顶优先级,使它尽快执行并退出临界区从而释放Mutex。释放信号量函数OSMutexPost( )则是将当前任务的优先级恢复原值,并检查是否有任务仍在申请该资源。
    利用优先级置顶解决前面提到的优先级反转的过程如图2所示。


    以开始系统初始化,直到T1任务开始请求信号量的时刻,系统运行情况和应用普通信号量时的情况是一致的。t2时刻,T1任务开始启动,请求信号量,此时系统得知T1任务所需的信号量正在被T3任务所占据,故提高T3任务的优先级,使之高于请求该信号量的所有任务的优先级;t3时刻,T1任务由于得不到信号量而被挂起,此时由于T3任务的优先级高于T1和T2任务,所以系统让T3任务先完成,从而释放信号量。当T3任务释放信号量的时候,系统得知T3任务的优先级是被暂时提高的,所以恢复T3任务的优先级,此时T1任务可以请求并得到信号量;t4时刻,T1任务由于得到信号量而开始运行;t5时刻,T1任务运行完毕,由系统切换任务,使T2任务开始运行。在一定程度上抑制了优先级反转。在μC/OS-II系统中建立如上所述的3个任务,作用时分别输出格式为“自己的任务名称is running”的字符串。使用了互斥信号量后的实验结果如图3所示。

2.2 优先级继承方案
    在μC/OS-II中,由于不同的任务不能对应同一个优先级,所以不支持上述方法。不过,可以通过修改操作系统的内核,使之成为可能,从而用优先级继承的方案解决优先级反转现象。这里采用类似于时间片轮番调度法的方案,在同一优先级上对不同任务进行调度。
    这种方法给处于同一优先级的不同任务都分配一个时间片,当内核运行到某一任务时,对同优先级且处于就绪态的任务依次进行调度,即当就绪态中先到的任务用完自己的时间片后,CPU控制权转让给就绪态中后一任务。该任务用完自己的时间片后,CPU控制权又转让给后一个就绪态任务。当就绪态的每一个任务都被调度一次之后将重新为它们分配时间片,然后又开始新周期的调度。在调度过程中如果有一个比当前任务优先级更高的任务由其他态变成了就绪态(被创建或获取了一个信号量等等),当前任务的CPU控制权将被剥夺;空闲任务仍然是等到其他任务都退出就绪态才获得CPU使用权。
    这种方法的优点不仅体现在可以让同一优先级对应不同的任务,从而进行优先级继承,还体现在可以增加操作系统调度任务的最大数目,这使应用系统的开发更加灵活。因为在不允许一个优先级对应不同任务的μC/OS-II中,用户能够自己创建的任务数目最多为56个。
    在μC/OS-II中,实现优先级继承方案应该首先在任务控制块(TCB)的结构体中添加构成双向链表的前驱节点指针(变量名为OSMYnext)、后继结点指针(变量名为OSMYprev)和2个用于指示时间的变量(OSMYtime和OSMYtimeremain)。指针的作用是用来查找同一优先级的不同任务,便于添加新任务和删除已经释放了信号量的任务。在没有其他任务和自己处于同一优先级的状态下,链表的前后指针均指向自己。变量OSMYtime的作用表示分给该任务的时间片长度,OSMYtimeremain表示当前时间片剩余时间。
    由于当前任务的时间片使用完时,就会被从就绪表OSRdyGrp以及OSRdyTbl[ ]中清除,这样,正常的调度将被打乱,所以还需增加保存临时OSRdyGrp和OSRdyTbl[ ]的变量OSTempGrp和OSTempTbl[ ]。由于在创建任务时μC/OS-II会比较该任务和已建立的任务的优先级是否相同,所以还需把任务创建函数中相应代码进行屏蔽。
    时钟节拍函数OSTimeTick( )在时间片调度过程中起到了修改时间片计数器的作用,每一次时钟节拍的到来都会引起时间片的减少。在OSTimeTick( )函数中,主要完成以下工作:首先检查同优先级的双向链表指针是否指向自己。如果指向自己,则说明在这一优先级上,只有自己一个任务。如果指向其他的任务,则要通过递减正在运行的任务的时间片来确定分给该任务的时间片是否用完。
    如果时间片没有用完,则执行OS_Sched()函数,让内核进行调度;如果时间片已经用完,则让时间片重新赋值,然后同样进行调度,在没有更高优先级的任务处于就绪态时,系统将运行链表所指示的下一个任务。其主要步骤的流程图如图4所示。

    经过以上步骤,就可以在μC/OS-II系统中基本实现时间片轮番调度,不过要想解决优先级反转的问题,还需要做以下工作。
    当一个任务进入等待互斥信号量OSMutexPend( )函数时,首先判断当前任务的优先级是否高于已经得到并且还没释放该资源的任务优先级。如果当前的任务优先级高,则要将得到该资源的任务优先级提到当前任务的优先级水平,并且把当前任务加到自己的双向链表中,再执行一次内核调度。
    当任务执行OSMutexPost( )释放互斥信号量时,如果在其拥有信号量的过程中被提升过优先级,则将恢复之前的优先级。然后查看是否还有任务在等待该信号量,准备下一次调度。
    用优先级继承的方法测试,同样选取T1、T2、T3 3个任务,进行同优先级置顶方案相同的实验,得到如图5所示的结果。
    从图5可以看出,用时间片解决优先级反转的效果与优先级置顶大致相同,区别仅在于当T3任务取得资源运行时,时间片用完后,T1任务又开始申请该资源,而T3并未放弃,所以出现如图5的结果。如果T3的时间片设置过小,这一过程就将频繁发生,从而降低了效率。所以如果系统当前的任务集合相对简单,则在发生优先级反转时,把低优先级任务的时间片调大一些为好。


    运用时间片轮番调度法,解决了在μC/OS-II系统中实现优先级继承的方案,在一定程度上抑制了优先级反转现象,提高了系统的实时性,还增加了系统同时运行任务的最大数目,提高了系统的运行效率。
    优先级反转是任何一个多任务实时操作系统都无法避免的问题。本文分析了该现象产生的原因,主要讨论了μC/OS-II中运用mutex和时间片轮番调度解决该问题的方法并对其可行性进行了验证。相对优先级继承和优先级置顶策略,在可能出现优先级反转的情况下,动态地改变任务优先级能够保证高优先级任务的执行,有效提高了系统的实时性。
参考文献
[1] 杨宗德,张兵μC/OS-II标准教程[M].北京:人民邮电出版社,2009:153-156.
[2] LABROSSE J.μC/OS-II the real-time kernel[M].Lawrence,R&D Books,2003:47-64.
[3] LABROSSE J J.嵌入式实时操作系统μC/OS-II(第2版) [M].北京:北京航空航天大学出版社,2003:44-46.
[4] 任哲.嵌入式实时操作系统μC/OS-II原理及应用[M].北京:北京航空航天大学出版社,2005:124-130

此内容为AET网站原创,未经授权禁止转载。