精华内容
下载资源
问答
  • 优先级翻转与优先级继承 田海立 2006-3-7   摘要 本文描述操作系统中的优先级翻转(Priority Inversion,也有翻译为反转,逆转或倒置的)现象以及如何用优先级继承来解决此类问题的方法,并阐述了 Microsoft ...

    优先级翻转与优先级继承


    田海立

    2006-3-7

     

    摘要

    本文描述操作系统中的优先级翻转(Priority Inversion,也有翻译为反转,逆转或倒置的)现象以及如何用优先级继承来解决此类问题的方法,并阐述了 Microsoft Platform Builder for Windows CE 环境下,如何查看此种现象。

     

    目  录

    摘要
    1 优先级翻转(Priority Inversion)
    2 优先级继承(Priority Inheritance)
           2.1 优先级继承
           2.2 WinCE中优先级继承
           2.3 优先级继承的传递性
    3 总结
    参考资料及进一步阅读
    关于作者

     

    优先级翻转(Priority Inversion)

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

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

    假定一个进程中有三个线程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的被调度时机就不能保证,整个实时调度的性能就很差了。

    优先级继承(Priority Inheritance)

    2.1 优先级继承

    为了解决上述由于优先级翻转引起的问题,Solaris和WinCE引入了优先级继承的解决方法。优先级继承也就是,高优先级进程TH在等待低优先级的线程TL继承占用的竞争资源时,为了使TH能够尽快获得调度运行,由操作系统把TL的优先级提高到TH的优先级,从而让TL以TH的优先级参与调度,尽快让TL执行并释放调TH欲获得的竞争资源,然后TL的优先级调整到继承前的水平,此时TH可获得竞争资源而继续执行。

    有了优先级继承之后的上述现象的执行情况如图二所示。

     

    图二、优先级继承执行情况

    与图一比较,图二中,到了T3时刻,Thread1需要Thread3占用的同步资源SYNCH1,操作系统检测到这种情况后,就把Thread3的优先级提高到Thread1的优先级。此时处于可运行状态的线程Thread2和Thread3中,Thread3的优先级大于Thread2的优先级,Thread3被调度执行。

    Thread3执行到T4时刻,释放了同步资源SYNCH1,操作系统何时恢复了Thread3的优先级,Thread1获得了同步资源SYNCH1,重新进入可执行队列。处于可运行状态的线程Thread1和Thread2中,Thread1的优先级大于Thread2的优先级,所以Thread1被调度执行。

    上述机制,使优先级最高的Thread1获得执行的时机提前。

    2.2 WinCE中优先级继承

    下面用在Microsoft Platform Builder for Windows CE 5.0环境的Emulator中,来做一个优先级继承的实验。

    2.2.1 程序设计

    主线程做了如下工作:
           ◇ 创建三个子线程,设置它们的优先级顺序:
                  Priority(Thread1) > Priority(Thread2) > Priority(Thread3);
           ◇ 只是启动Thread3。
           ◇ 创建一个互斥体g_Mutex1,初始状态是未被获得的。

    三个子线程的执行体分别如下:

    Thread3
           ◇ 获得g_Mutex1;
           ◇ 循环执行一定次数的
                  打印“Thread3: Executing BEFORE releasing the MUTEX...” 
           ◇ 释放g_Mutex1;
           ◇ 循环执行:
                  打印“Thread3: Executing AFTER releasing the MUTEX...”

    Thread2
           ◇ 打印:“Thread2: Start executing...” 
           ◇ 循环执行:
                  打印“Thread2: executing...”

    Thread1
           ◇ 打印:“Thread1: Start executing...” 
           ◇ 打印:“Thread1: Waiting on Mutex1...” 
           ◇ 执行:WaitForSingleObject(g_Mutex1, INFINITE); 
           ◇ 打印:“Thread1: GOT g_Mutex1, and will resume.” 
           ◇ 循环执行:
                  打印“Thread1: Executing AFTER getting the MUTEX...”

    2.2.2 Log结果分析

    结果输出如下:

           TID:a3ecaa1e Thread1: Handler = a3c867b2, ThreadId = a3c867b2
           TID:a3ecaa1e Thread2: Handler = 83c8c002, ThreadId = 83c8c002
           TID:a3ecaa1e Thread3: Handler = 3c866c2, ThreadId = 3c866c2
           TID:3c866c2 Thread3 GOT the Mutex g_Mutex1
           TID:83c8c002 Thread2: Start executing... 
           TID:83c8c002 Thread2: executing... 
           TID:a3c867b2 Thread1: Start executing... 
           TID:a3c867b2 Thread1: Waiting on Mutex1... 
           TID:3c866c2 Thread3: Executing BEFORE releasing the MUTEX... 
           TID:3c866c2 Thread3: Executing BEFORE releasing the MUTEX... 
           ...... 
           TID:3c866c2 Thread3: Executing BEFORE releasing the MUTEX... 
           TID:3c866c2 Thread3: Executing BEFORE releasing the MUTEX...
     
           TID:3c866c2 Thread3: Released the mutex1. 
           TID:a3c867b2 Thread1: GOT g_Mutex1, and will resume. 
           TID:a3c867b2 Thread1: Executing AFTER getting the MUTEX...
     
           TID:a3c867b2 Thread1: Executing AFTER getting the MUTEX... 
           TID:a3c867b2 Thread1: Executing AFTER getting the MUTEX... 
           ......

    结果中的斜体加粗部分标识了图二的T3-T4时刻的操作。Thread3由于拥有Thread1欲申请的同步资源g_Mutex1而继承了Thread1的优先级,获得了执行。

    结果中的粗体加下划线部分标识了图二的T4时刻的操作。Thread3释放同步资源g_Mutex1,Thread3的优先级被恢复到T3之前;Thread1获得了g_Mutex1之后继续执行。

    2.2.3 用Platform Builder的工具查看

    优先级继承时的线程的优先级是无法在程序中通过诸如GetThreadPriority() / CEGetThreadPriority() 之类的函数来查看CurrPrio的,这些函数查看的是显式设置的BasePrio。(WinCE的早期版本里,这些函数返回的是CurrPrio)

    我们可以通过Platform Builder的调试工具来查看,不过因为PB提供的Emulator与BP Host之间同步需要时间,所以我们在上面的程序中需要延长Thread3在T3-T4时间段的时间以获得足够的时间查看此时Thread3继承的优先级。仅仅为了查看,这里可以设置一个极限情况,即Thread3在释放g_Mutex1之前无限循环。

    下图是做完上述设置之后,通过 Platform Builder 的菜单“View | Debug Windows | Threads”,调出的Process/Thread View。

     

    图三、通过Thread View查看优先级继承

    图中,第一行对应Thread3;第二行对应PriorityInversion进程的主线程;第三行对应Thread1;第四行对应Thread2。从Thread3的CurrPrio列可以看出,它的当前的优先级确实提升到了Thread1的优先级。

    2.3 优先级继承的传递性

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

    下图是WinCE中按照上面描述增加了Thread4之后,参看Thread View得到的一个快照。

     

    图四、通过Thread View查看优先级继承的传递性

    图中,第一行对应Thread1;第二行对应Thread2;第三行对应PriorityInversion进程的主线程;第四行对应Thread4;第五行对应Thread3。从Thread3和Thread4所在行的CurrPrio列可以看出,Thread3由于等待Thread4拥有的竞争资源而被Blocked,优先级也没有得到提升;Thread4由于拥有Thread3所要竞争的同步资源,其优先级被提升到Thread3的优先级。这种现象不具有优先级继承的传递性。

    总结

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

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

    参考资料及进一步阅读

           ◇ Microsoft, MSDN, 2005. 
           ◇ Uresh Vahalia, UNIX Internals: The New Frontiers, PEARSON EDU / 人民邮电出版社影印, 2003/2003.7

    关于作者

           田海立,硕士,国家系统分析师,中国系统分析员协会顾问团专业顾问。
           您可以通过 HaiLi.Tian(at)csai.cn 或 TianHaiLi(at)nju.org.cn 与他联系,到 http://blog.csdn.net/thl789/ 看他最新的文章。

     

    版权声明:

    ◇ 本文为作者原创作品,版权归作者所有。 
    ◇ 为了学习和研究,可转载本文,但必须与原文的内容和格式保持一致,并给出原文的链接!

     http://blog.csdn.net/thl789/archive/2006/03/07/617629.aspx

    展开全文
  • 在项目中,移植了FreeRTOS实时操作系统,因为两个任务中的步进电机动作不能同步运动,使用了互斥信号量,在此记录优先级翻转与优先级继承的作用机制。 先解释共享资源,可以是一段程序、一个功能、一个动作、一段...

        在项目中,移植了FreeRTOS实时操作系统,因为两个任务中的步进电机动作不能同步运动,使用了互斥信号量,在此记录优先级翻转与优先级继承的作用机制。

        先解释共享资源,可以是一段程序、一个功能、一个动作、一段指令或者传输几个字节,也可以是不能同步运行的不相关的多段程序,不同的程序被封装成一个“外壳”,被认为是同一种共享资源S。

        假设有A、B和C三个任务,优先级A>B>C,程序开始,A、B、C处于阻塞状态,任务C捕捉到信号量,开始执行任务C,任务C中使用了共享资源S,接着任务A捕捉到信号量,CPU使用权被任务A抢占,开始执行任务A,任务C被挂起,当运行到共享资源S的地方,发现其被任务C使用,任务A被挂起,任务C开始执行。这时候任务B捕捉到信号量,开始执行任务B,任务B结束以后,才开始执行任务C,任务C释放共享资源后,任务A才能执行。事实上,任务B的优先级低于任务A,但是任务A却要等待任务B,形成了优先级翻转。

        优先级继承,是互斥信号量具有的机制,当一个互斥信号量正在被低优先级的任务使用,有个高优先级任务尝试获取互斥信号量时,会被阻塞。不过这个高优先级的任务会将低优先级任务的提升到与自己相同的优先级,这个过程就是优先级继承。

        优先级继承 ,尽可能的降低了高优先级任务处于阻塞态的时间,并且将已经出现的“优先级翻转”的影响降到最低,但是只能减少影响,不能完全避免。


    展开全文
  • 3.假设系统有一个资源被保护了,此时该资源被L线程在使用,某一时刻H线程需要使用该资源,但L线程还未使用完,H线程申请不到而进入阻塞态,此时已出现优先级翻转现象;没有优先级继承机制的时候:如果L线程执行的...

    三个线程分别是 H线程、M线程、L线程  
    1.三个线程的优先级顺序是:H线程 > M线程 > L线程;
    2.正常运行的时候H线程可以打断M线程与L线程, M线程可以打断L线程;
    3.假设系统有一个资源被保护了,此时该资源被L线程在使用,某一时刻H线程需要使用该资源,但L线程还未使用完,H线程申请不到而进入阻塞态,此时已出现优先级翻转现象;

    没有优先级继承机制的时候:

    如果L线程执行的时候,M线程刚好被唤醒了,由于M线程的优先级比较高,会打断L线程,抢占CPU使用权,直到M线程执行完成;
    M线程将CPU的使用权给L线程,L线程继续执行,L执行完后释放该资源;
    H线程得到该资源,从阻塞态解除;
    这个过程,高优先级的H等待了M线程+L线程的时间,如果有更多线程的时候,那系统就崩溃了,等不起的!

    有优先级继承机制的时候:
    在H贤臣申请资源的时候由于申请不到资源进入阻塞态,系统会把当前使用资源的L线程的优先级临时提高到与H线程的优先级相同
    此时M线程被唤醒也不会打断L线程;
    L线程执行完毕,释放资源,H线程获取资源被继续执行,H线程等待的时间只是L线程的执行时间。

    展开全文
  • 在FreeRTOS操作系统中为了降低优先级翻转问题利用了优先级继承算法。优先级继承算法是指,暂时提高某个占有某种资源的低优先级任务的优先级,使之在所有等待该资源的任务中优先级最高那个任务的优先级相等,而当这...

    在FreeRTOS操作系统中为了降低优先级翻转问题利用了优先级继承算法。优先级继承算法是指,暂时提高某个占有某种资源的低优先级任务的优先级,使之与在所有等待该资源的任务中优先级最高那个任务的优先级相等,而当这个低优先级任务执行完毕释放该资源时,优先级重新回到初始设定值。因此,继承优先级的任务避免了系统资源被任何中间优先级的任务抢占。互斥量与二值信号量最大的不同是:互斥量具有优先级继承机制,而信号量没有。也就是说,某个临界资源受到一个互斥量保护,如果这个资源正在被一个低优先级任务使用,那么此时的互斥量是闭锁状态,也代表了没有任务能申请到这个互斥量,如果此时一个高优先级任务想要对这个资源进行访问,去申请这个互斥量,那么高优先级任务会因为申请不到互斥量而进入阻塞态,那么系统会将现在持有该互斥量的任务的优先级临时提升到与高优先级任务的优先级相同,这个优先级提升的过程叫做优先级继承。这个优先级继承机制确保高优先级任务进入阻塞状态的时间尽可能短,以及将已经出现的“优先级翻转”危害降低到最小。_ _ _ _ _ _ _ _以上内容摘自《野火FreeRTOS 内核实现与应用开发实战指南》

    互斥量实验是基于优先级翻转实验进行修改的,目的是为了测试互斥量的优先级继承机制是否有效。

    创建工程RTOS_Mutex,

    配置HCLK,使用内部晶振,频率为180MHZ(根据板子设置)

    将SYS中时基源(Timebase Source)改为除SysTick之外的任意定时器即可,如:

    配置FreeRTOS,使用CMSIS_V1,先定义一个互斥信号量:

    定义三个任务:

      

      

    Ctrl + S生成代码

    修改代码,

    1,在main.h中添加

    /*Private includes ----------------------------------------------------------*/

    /*USER CODE BEGIN Includes*/#include"stdio.h"

    /*USER CODE END Includes*/

    2,在mian.c中添加

    /*USER CODE BEGIN PFP*/

    int _write(int file , char *ptr,intlen)

    {int i = 0;for(i = 0;i

    ITM_SendChar((*ptr++));returnlen;

    }/*USER CODE END PFP*/...

    ...

    .../*USER CODE BEGIN 2*/printf("starting...\n");/*USER CODE END 2*/

    3,在main.c中修改3个任务入口函数的内容

    /*USER CODE BEGIN Header_StartLowPriorityTask*/

    /**

    * @brief Function implementing the LowPriorityTask thread.

    * @param argument: Not used

    * @retval None*/

    /*USER CODE END Header_StartLowPriorityTask*/

    void StartLowPriorityTask(void const *argument)

    {/*USER CODE BEGIN 5*/

    staticuint32_t i;/*Infinite loop*/

    for(;;)

    {

    printf("LowPriority_Task gets mutex!\n");//获取二值信号量 xSemaphore,没获取到则一直等待

    if(osMutexWait(myMutex01Handle, osWaitForever) ==osOK)

    {

    printf("LowPriority_Task Runing\n\n");

    }for (i=0; i<2000000; i++) { //模拟低优先级任务占用信号量

    osThreadYield();//发起任务调度

    }

    printf("LowPriority_Task Releasing mutex!\r\n");

    osMutexRelease( myMutex01Handle );//给出二值信号量

    osDelay(500);

    }/*USER CODE END 5*/}

    /*USER CODE BEGIN Header_StartMidPriorityTask*/

    /**

    * @brief Function implementing the MidPriorityTask thread.

    * @param argument: Not used

    * @retval None*/

    /*USER CODE END Header_StartMidPriorityTask*/

    void StartMidPriorityTask(void const *argument)

    {/*USER CODE BEGIN StartMidPriorityTask*/

    /*Infinite loop*/

    for(;;)

    {

    printf("MidPriority_Task Runing\n");

    osDelay(500);

    }/*USER CODE END StartMidPriorityTask*/}

    /*USER CODE BEGIN Header_StartHighPriority_Task*/

    /**

    * @brief Function implementing the HighPriority_Ta thread.

    * @param argument: Not used

    * @retval None*/

    /*USER CODE END Header_StartHighPriority_Task*/

    void StartHighPriority_Task(void const *argument)

    {/*USER CODE BEGIN StartHighPriority_Task*/

    /*Infinite loop*/

    for(;;)

    {

    printf("HighPriority_Task gets mutex!\n");//获取二值信号量 xSemaphore,没获取到则一直等待

    if(osMutexWait(myMutex01Handle, osWaitForever) ==osOK)

    {

    printf("HighPriority_Task Runing\n\n");

    }

    printf("HighPriority_Task Releasing mutex!\r\n");

    osMutexRelease( myMutex01Handle );//给出二值信号量

    osDelay(500);

    }/*USER CODE END StartHighPriority_Task*/}

    修改完毕后点击 小锤子 构建工程,然后点击Debug,按如下步骤配置ITM调试

    全速运行之前一定要先点击SWV ITM data Console 页面中的红色圆圈

    现象:

    分析:

    3个任务,LowPriority_Task,的优先级为 osPriorityLow ,任务先获取互斥量,获取成功后先不释放,进行任务调度2000000次,然后释放二值信号量。

    MidPriority_Task的优先级为 osPriorityNormal ,任务每个500ms输出提示信息MidPriority_Task Runing。

    HighPriority_Task的优先级为  osPriorityHigh,任务先获取互斥量,获取成功后输出提示信息,然后立即释放互斥量。

    程序先执行优先级最高的HighPriority_Task的,然后执行优先级第二高的MidPriority_Task,最后执行优先级最低的LowPriority_Task 。在LowPriority_Task中,任务先获取互斥量,获取成功后先不释放,进行任务调度,调度到优先级最高的HighPriority_Task,HighPriority_Task任务获取互斥量,因为此时互斥量被占用,所以会获取失败,进入阻塞态。由于互斥量的优先级继承机制,此时的LowPriority_Task的优先级被暂时提高到与HighPriority_Task一样,所以即使进行任务调度也不会执行MidPriority_Task,直到LowPriority_Task释放信号量(此时,由于优先级继承机制,LowPriority_Task恢复到原来的优先级),程序立即执行HighPriority_Task,当HighPriority_Task执行完毕后,按照优先级执行MidPriority_Task,最后再执行LowPriority_Task。如此循环...

    展开全文
  • 文章目录互斥锁优先级翻转优先级继承互斥锁的数据结构互斥锁控制块互斥锁相关的宏定义创建互斥锁销毁互斥锁获取互斥锁释放互斥锁 互斥锁 互斥锁又称互斥信号量,是一种特殊的二值信号量,它和信号量不同的是,它...
  • RT Thread IPC总结

    2012-11-01 16:18:00
    但是无法实现中断的互斥3、信号量,轻量级的互斥机制,因为初始值不一定为1,所以他没有所有者(拥有者)的概念,且没有解决优先级翻转的问题4、互斥量是管理临界资源的一种有效手段,它使用优先级继承方法解决了...
  • uC/OS-III之资源管理--互斥型信号量

    千次阅读 2017-06-02 17:37:37
    2.互斥型信号量通过安全优先级继承机制(一旦一个具有高优先级的任务H想要访问共享资源,占有该资源的任务的优先级将被提升至任务H一样),来避免无界优先级翻转的问题。3.互斥型信号量是一种被定义为OS_MUTEX数据...
  • 但是互斥信号量可以解决二值信号量出现的优先级翻转问题,解决办法就是优先级继承 普通互斥信号量创建及运行,参阅安富莱电子demo /* 互斥信号量句柄 */ static SemaphoreHandle_t xMutex = NULL; static void ...
  • 1.2.5 各种方式的优先级问题 1.3 体验CSS 1.3.1 从零开始 1.3.2 加入CSS控制 1.3.3 控制图片 1.3.4 CSS的注释 第2章 CSS的基本语法 2.1 CSS选择器 2.1.1 标记选择器 2.1.2 类别选择器 ...
  • 因为没解出来二叉树翻转的白板算法题,惨遭 Google 拒绝,继而引发推特热议。 在 JavaScript 中也有很多树形结构。比如 DOM 树,省市区地址联动,文件目录等; JSON 本身就是树形结构...
  • java自学之道

    2014-01-05 20:17:04
    1.2 线程调度与优先级 1.3 线程的状态与生命周期 1.4 控制一个线程生命周期最常用的方法 2、线程的创建和启动 3、线程的同步与死锁 3.1 同步的概念 3.2 线程同步举例 3.3 线程死锁 六、GUI 1、图形用户界面概述 ...
  • JavaScript详解(第2版)

    2018-04-25 09:58:36
     5.1.2 优先级和结合性   5.2 运算符类型   5.2.1 算术运算符   5.2.2 快捷赋值运算符   5.2.3 递增运算符和递减运算符   5.2.4 拼接运算符   5.2.5 比较运算符   5.2.6 逻辑运算符   ...
  • 2.5.5 运算符的优先级 41 2.5.6 结合性 42 2.5.7 表达式 43 2.6 常用函数 43 2.6.1 数学函数 43 2.6.2 字符处理函数 44 2.6.3 随机数函数 44 2.6.4 转换函数 45 2.6.5 日期函数 45 第3章 流程控制语句 46 ...
  • 已解决BOM报告中指定参数类型优先级的问题。 26496 尝试从单组件编辑器编辑特定组件占用空间时出现已解决的异常错误。 26699 已解决的问题,其中Vault 3.0中的现有部件请求未显示在“资源管理器”面板中。 26967 ...
  • 新版Android开发教程.rar

    千次下载 热门讨论 2010-12-14 15:49:11
    开放手机联盟, Open Handset Alliance :是美国 Google 公司 2007 年 11 月 5 日宣布组建的一个全球性的联 盟组织。这一联盟将会支持 Google 发布的 Android 手机操作系统或者应用软件,共同开发名为 Android 的 ...
  • 二元信号量具有互斥和同步多任务的作用,它互斥量非常相似,当有一个区别是互斥量具有优先权...1.优先级继承 2.优先级翻转 3.死锁 以下内容来自RT-Thread官网: https://www.rt-thread.org/document/site/pr...

空空如也

空空如也

1 2
收藏数 26
精华内容 10
关键字:

优先级翻转与优先级继承