精华内容
参与话题
问答
  • 什么是优先级反转(翻转)

    千次阅读 2019-06-05 09:13:01
    优先级反转,是指在使用信号量时,可能会出现的这样一种不合理的现象,即: 高优先级任务被低优先级任务阻塞,导致高优先级任务迟迟得不到调度。但其他中等优先级的任务却能抢到CPU资源。-- 从现象上来看,好像是...

     

    优先级反转,是指在使用信号量时,可能会出现的这样一种不合理的现象,即:

    高优先级任务被低优先级任务阻塞,导致高优先级任务迟迟得不到调度。但其他中等优先级的任务却能抢到CPU资源。-- 从现象上来看,好像是中优先级的任务比高优先级任务具有更高的优先权。

    具体来说:当高优先级任务正等待信号量(此信号量被一个低优先级任务拥有着)的时候,一个介于两个任务优先之间的中等优先级任务开始执行——这就会导致一个高优先级任务在等待一个低优先级任务,而低优先级任务却无法执行类似死锁的情形发生。

    一个具体的例子:
    假定一个进程中有三个线程Thread1(高)、Thread2(中)和Thread3(低),考虑下图的执行情况。

    • T0时刻,Thread3运行,并获得同步资源SYNCH1;
    • T1时刻,Thread2开始运行,由于优先级高于Thread3,Thread3被抢占(未释放同步资源SYNCH1),Thread2被调度执行;
    • T2时刻,Thread1抢占Thread2;
    • T3时刻,Thread1需要同步资源SYNCH1,但SYNCH1被更低优先级的Thread3所拥有,Thread1被挂起等待该资源
    • 而此时线程Thread2和Thread3都处于可运行状态,Thread2的优先级大于Thread3的优先级,Thread2被调度执行。最终的结果是高优先级的Thread1迟迟无法得到调度,而中优先级的Thread2却能抢到CPU资源。

    上述现象中,优先级最高的Thread1要得到调度,不仅需要等Thread3释放同步资源(这个很正常),而且还需要等待另外一个毫不相关的中优先级线程Thread2执行完成(这个就不合理了),会导致调度的实时性就很差了。

    什么是优先级继承

    优先级继承就是为了解决优先级反转问题而提出的一种优化机制。其大致原理是让低优先级线程在获得同步资源的时候(如果有高优先级的线程也需要使用该同步资源时),临时提升其优先级。以前其能更快的执行并释放同步资源。释放同步资源后再恢复其原来的优先级。

    带有优先级继承调度过程

     

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

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

    通过优先级继承机制,可以有效解决优先级反转问题,使优先级最高的Thread1获得执行的时机提前。


    转自链接:https://www.jianshu.com/p/c1f7aa944dda
     

    展开全文
  • 优先级反转和解决方法

    万次阅读 多人点赞 2013-10-15 11:26:09
    优先级反转的描述: 假设任务1,任务2,任务3;他们的优先级顺序分别为1 > 2 > 3。有一个稀缺资源S,S由一个信号量控制为互斥访问。 任务3正在执行,并申请到了资源S;任务1抢占了任务3的执行,任务3挂起,任务1...

    优先级反转的描述:

    假设任务1,任务2,任务3;他们的优先级顺序分别为1 > 2 > 3。有一个稀缺资源S,S由一个信号量控制为互斥访问。

    1. 任务3正在执行,并申请到了资源S;
    2. 任务1抢占了任务3的执行,任务3挂起,任务1执行;
    3. 任务1申请资源S,发现被占用,所以挂起,任务3恢复执行;
    4. 任务2抢占了任务3的执行,任务3挂起,任务2执行;
    5. 任务2执行完毕,任务3恢复;
    6. 任务3释放资源S,任务1抢占资源S,任务1执行,任务3挂起;
    7. 任务1执行完毕,任务3执行。

    以上可以看出,任务2虽然比任务1优先级低,但是比任务1优先执行。也就是说任务1的优先级被降低到了任务3的级别。


    分析

    由于稀缺资源S的独占性,任务3在申请到资源后,任务1必然会在任务3释放资源后才能执行完成。而任务2肯定会抢占任务3的执行。这个时候,要想任务1比任务2之前执行,有两种方法:任务3释放资源,任务2不能抢占任务3。

    • 任务3释放资源。这条路走不通,因为独占资源没有操作完成就释放,要么回滚,要么出错。(X)
    • 任务2不能抢占任务3。提升任务3的优先级高于任务2就可以了。(V)提高到多少?假如任务1和任务5共抢资源S,那么任务2、3、4都有可能抢去任务5的执行权,所以任务提升一定要和资源S被申请的最高优先级平等或者大于。对于有相同优先级的内核来说,任务5提升到任务1的优先级即可,对于优先级单一的内核,如ucos,就要提升到高一点。

    解决方法

    1. 优先级天花板。当任务3使用资源S时,就把任务3的优先级提升到能访问资源S的最高优先级,执行完成释放资源之后,把优先级再改回来;这样的方法,简单易行,解决了多个高优先级任务抢占资源S的问题。但是带来了一些缺点,就是不一定每次都有高优先级任务抢占资源S,每次都提升优先级是对CPU资源的一种浪费。
    2. 优先级继承。当任务3使用资源S时,任务1抢占执行权,申请资源S,比较资源1和资源3的优先级,假如任务1优先级高,才提升任务3,提升到和任务1相同的优先级,当任务3释放资源后,将优先级再调整回来。相对于优先级天花板方法,相当于延后执行,克服了任务1的缺点,自己本身的特点是,逻辑复杂,需要操作系统支持相同优先级。在ucos中不容易实现。
    3. 两者结合的方案:当任务3使用资源S时,任务1抢占执行权,申请资源S,比较资源1和资源3的优先级,假如任务1优先级高,才提升任务3,提升到能访问资源S的最高优先级,当任务3释放资源后,将优先级再调整回来。




    展开全文
  • 优先级反转

    千次阅读 2009-07-19 20:14:00
    这些为数众多的RTOS绝大多数都是多任务实时微内核的结构,采用的是基于优先级的可抢占式调度策略。系统为每一个任务分配一个优先权,调度程序保证当前运行的进程是优先权最高的进程。但是,有时候会出现一种比较奇怪...

    1 问题的提出

      目前,市场上占有率比较高的商业RTOS有VxWorks/PSOS、QNX、 LynxOS、VRTX,、Windows CE等。这些为数众多的RTOS绝大多数都是多任务实时微内核的结构,采用的是基于优先级的可抢占式调度策略。系统为每一个任务分配一个优先权,调度程序 保证当前运行的进程是优先权最高的进程。但是,有时候会出现一种比较奇怪的现象:由于多进程共享资源,具有最高优先权的进程被低优先级进程阻塞,反而使具 有中优先级的进程先于高优先级的进程执行,导致系统的崩溃。这就是所谓的优先级反转(Priority Inversion)。

     

    2 优先级反转

       RTOS普遍具有2个特点:实时性和多任务。实时是指系统的响应时间必须在规定的时间内,超出这个时间限制将会使系统出现致命的错误;同时,实时性还要 求对时间要求非常急迫的任务要先于对时间不是很紧急的任务执行。正是由于这2个原因,RTOS的进程调度普遍采用的是基于优先级的可抢占式PBP (Priority Based Preemptive)的调度策略。多任务是嵌入式系统的内在要求。如今的嵌入式系统普遍要求具有多任务并发执行的能力,因此RTOS中也必须提供多任务 并发执行的支持。由于多任务并发,必然会导致多个任务共享资源。如有2个任务task1和task2并发执行,都需要向打印机输出结果。由于只有1台打印 机,所以在某个时间段内只能有1个任务,如task1占有打印机并向打印机输出,而这时另一个任务task2处于等待状态。当task1输出完毕后, task2由等待转为就绪,当RTOS再次调度它时,方可占有打印机向打印机输出。试想如果不采取这种方式,不对打印机这种共享资源加以控制,而让 task1和task2同时向打印机输出,这时候打印机打印的结果谁也看不懂,是一堆乱七八糟的东西。因此,大多数的RTOS采用了一种称作信号量 (semaphore)的机制来实现对共享资源的管理。任何一个想使用临界资源(如打印机等共享资源)的进程在进入临界区(如task1或task2中访 问临界资源的代码)之前必须拥有使用临界资源的信号量,否则不可以执行临界区代码。假设系统中有3个任务,分别为task1、task2和task3。 task1的优先权高于task2,而task2的优先权高于task3。恰在此时task1和task2 因某种原因被阻塞,这时候系统调度task3执行。task3执行一段时间后,task1被唤醒。由于采取的是PBP的调度策略,因此task1抢占 task3的CPU, task1执行。task1执行一段时间后要进入临界区,但此时task3占有此临界资源的信号量。因此task1被阻塞,处于等待状态,等待task3 释放此信号量。经过这么一段时间后,task2此时此刻处于就绪状态。因此系统调度task2执行。如果task3在task2的执行期间一直没有能够被 调度执行的话,那task1和task3将一直等到task2执行完后才能执行,task1更要等到task3释放它所把持的信号量才能执行;而这段时间 完全有可能超出task1的Deadline,使得task1崩溃。当系统看到有高优先级的任务崩溃时候,系统认为此时有重大事故发生,为了挽救系统,看 门狗电路起作用,系统可能被自动复位。从上面的分析可以看到,导致系统崩溃的原因是由于优先级高的任务task1要获取被低优先级任务task2占有的临 界资源而被task2阻塞,而具有中优先级的任务task2抢占task3的CPU,从而导致task2先于task1执行。这时候系统便出现了优先级反 转的情况,如图1所示。
    优先级反转示意图

     

     

    3 优先级反转的解决方法

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

       在优先级继承方案中,当高优先级任务在等待低优先级的任务占有的信号量时,让低优先级任务继承高优先级任务的优先级,即把低优先级任务的优先权提高到高 优先级任务的优先级;当低优先级任务释放高优先级任务等待的信号量时,立即把其优先权降低到原来的优先权。采用这种方法可以有效地解决上面所述的优先权反 转的问题。当高优先级任务task1想要进入临界区时,由于低优先级任务task3占有这个临界资源的信号量,导致task1被阻塞。这时候,系统把 task3的优先权升到task1的优先权,此时优先权处于task1和task3之间的任务task2,即使处于就绪状态也不可以被调度执行,因为此时 task3的优先权已经高于task2,所以task3此时被调度执行。当task3释放task1需要的信号量时,系统立即把task3的优先权降到原 来的高度,来保证task1和task2正常有序执行。整个情况如图2所示。目前,有许多RTOS是采用这种方法来防止优先级反转的,如大家比较熟悉的业 界有名的WindRiver公司的VXWORKS。

    采用优先级继承消除优先级反转

    在 优先权极限方案中,系统把每一个临界资源与1个极限优先权相联系。这个极限优先权等于系统此时最高优先权加1。当1个任务进入临界区时,系统便把这个极限 优先权传递给这个任务,使得这个任务的优先权最高;当这个任务退出临界区后,系统立即把它的优先权恢复正常,从而保证系统不会出现优先权反转的情况。如上 例中,当task3进入临界区时,立即把它的优先权升高到极限优先权,保证task3此时能尽快退出临界区,进而释放其占有的信号量。当高优先级任务 task1执行的时候就不会出现其等待低优先级任务task3释放信号量而被阻塞的情况,从而保证不会出现上面所说的优先级反转。采用这种方案的另一个有 利之处,是仅仅通过改变某个临界资源的优先级就可以使多个任务共享这个临界资源,如下所示。

    void TaskA(void){

    ...

    SetTaskPriority(RES_X_PRIO);

    // 访问共享资源 X.

    SetTaskPriority(TASK_A_PRIO);

    ...

    }

      以上就RTOS中优先级反转问题出现的原因以及解决方法进行了详细的说明。21世纪将是嵌入式系统的时代。从事嵌入式系统设计的人员深入了解RTOS的原理和内部潜在的问题,如优先级反转等,将有助于开发出更加可靠的产品。

    作者:刘辉 孟凡荣 席景科

    展开全文
  • 多线程的那点儿事(之优先级反转

    万次阅读 多人点赞 2011-12-11 18:45:39
     优先级反转对于编写应用层的人员来说不大会发生,但是对于操作系统的设计者来说确是一个逃不过去的问题。要知道怎么样处理优先级反转?那么先看看它是怎么发生的。  (1)调度队列和线程优先级  在操作系统...
    【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】

        优先级反转对于编写应用层的人员来说不大会发生,但是对于操作系统的设计者来说确是一个逃不过去的问题。要知道怎么样处理优先级反转?那么先看看它是怎么发生的。

        (1)调度队列和线程优先级

        在操作系统中,线程的状态有很多种。比如说,线程的状态可能是suspend、block、ready、die几种类型。我们把所有的ready线程放在一个队列里面,这就构成了一个基本的调度队列。

        我们还知道,为了对所有的线程进行有差别的时间调度,我们对所有的线程分配了优先级。打个比方,调度队列有32个线程,每个线程的优先级也是1到32。这些优先级对于线程来说有什么意义呢?那就是,高优先级可以获得较多的时间片运行机会。进一步极端一点说,优先级为32可以32个基本时间片,那么优先级为1的线程只能获得一个时间片的运行机会。

        (2)锁和线程

        在队列调度过程当中,高优先级的线程获得较多的运行机会,而与此对应的低优先级线程运行的机会较少。举个例子来说,现在有32个线程,线程的优先级分布在1~32之间。那么这些程序怎么运行呢,


        线程0x20  优先级32   时间片 32个

        线程0x1F  优先级31   时间片 31个

        线程0x1E  优先级30   时间片 30个

        /* 其他线程 */

        线程0x01  优先级01   时间片 01个

        

        所以如果总的时间片为(1 + 32) * (32 / 2) = 528, 所以一段时间内每个线程都有运行的机会。只不过,各个线程运行的机会不一样而已。但是这一切都因为锁的存在发生了改变。假设现在线程0x20和0x1都在争取一个锁,而这个锁此时正处在线程0x01的运行时间片内,所以线程0x01获得了锁。那么线程0x20此时只好退出运行队列,静静等待线程0x1退出锁了。

        糟糕的还不止这一点,前面我们说过低优先级的线程运行机会较少。所以,线程0x01获得运行的机会只是1/528,即使线程0x20退出了队列,那只有1/496,其中 496 = (1 + 31) / 2 * 31。如果线程0x01运行的时间还比较长,那就比较悲催了。线程0x20还要等待多长时间才能获得线程0x01的锁,那就只有天知道了。此时,原来的优先级也失去了意义,这才是优先级发生反转的真实原因。


        (3)解决方法
        原来制定优先级的目的就是为了让有的程序运行时间长一点,有的程序运行时间短一点。然而,这一切在锁面前从优点变成了缺点。那么解决的办法是什么呢?其实也不难,那就是提高线程0x01的优先级,尽快让线程0x01尽快退出锁。线程0x01和线程0x20交换一下优先级的方法就不错。


    总结:

        (1)优先级反转提醒我们使用锁的代码段应尽量短;

        (2)注意用小锁代替大锁,减少冲突的机会;

        (3)如果锁保护的代码段很短,直接使用原子锁忙等也是不错的一个方法。


    展开全文
  • 优先级反转+解决方案

    万次阅读 2007-09-18 01:33:00
    1. 优先级反转(Priority Inversion) 由于多进程共享资源,具有最高优先权的进程被低优先级进程阻塞,反而使具有中优先级的进程先于高优先级的进程执行,导致系统的崩溃。这就是所谓的优先级反转(Priority Inversion...
  • 什么是优先级反转

    2019-09-29 18:03:27
    最近在看到非公平锁的时候,提到非公平锁可能会导致优先级反转的问题,关于优先级反转这个概念有点空白,只是从字面上理解,应该是优先级高的比优先级低的先执行了。 后面自己下去查了查资料,大概了解了优先级反转...
  • 优先级反转及其解决方法

    千次阅读 2016-03-24 15:32:20
    优先级反转的描述: 假设任务1,任务2,任务3;他们的优先级顺序分别为1 > 2 > 3。有一个稀缺资源S,S由一个信号量控制为互斥访问。 任务3正在执行,并申请到了资源S;任务1抢占了任务3的执行,任务3挂起,...
  • 优先级反转及解决方法探讨

    千次阅读 2017-06-30 17:41:18
    1. 什么是优先级反转(Priority Inversion)  由于多进程共享资源,具有最高优先权的进程被低优先级进程阻塞,反而使具有中优先级的进程先于高优先级的进程执行,导致系统的崩溃。这就是所谓的优先级反转(Priority ...
  • 优先级反转问题及解决方法

    千次阅读 2015-08-28 17:48:53
    (1)什么是优先级反转 简单从字面上来说,就是低优先级的任务先于高优先级的任务执行了,优先级搞反了。那在什么情况下会生这种情况呢? 假设三个任务准备执行,A,B,C,优先级依次是A>B>C; 首先...
  • 优先级反转,又叫优先级翻转、优先级倒置,是操作系统在基于优先级抢占方式进行进程(任务)调度的时候可能出现的一种现象。在原本的调度算法设计中,高优先级进程可以抢占低优先级的CPU资源,先执行高优先级任务。 ...
  • 实时操作系统和优先级反转

    千次阅读 2017-05-22 21:24:30
    实时操作系统(Real-time operating system, RTOS)是说,任务切换和中断响应的时间必须保证在多少时间内(如5us内)完成。  分为硬实时和软实操作系统:  硬实时是说必须在多少时间内完成切换(如VxWorks, 我们...
  • 经过研发人员的分析,最后得出结论,就是因为系统里发生了优先级反转的问题。 其中有如下两个任务需要互斥访问共享资源“信息总线”: T1:总线管理任务,具有最高优先级(这里用T1表示),运行频繁
  • 优先级反转问题的和解决方法

    千次阅读 2015-10-26 16:48:49
    我们都知道,在操作系统的调度算法中有一种算法叫优先级调度算法。这种调度算法可能产生优先级反转的问题,下面我们就简单聊聊优先级反转和解决方法。
  • 优先级反转问题,解决方法:优先级继承 转载:  http://blog.chinaunix.net/uid-20788636-id-1841343.html
  • 优先级倒置

    2013-04-11 15:55:00
    2019独角兽企业重金招聘Python工程师标准>>> ...
  • 优先级翻转发生的条件:  1、首先发生翻转需要有三个任务,它们的优先级分别是高、中、低。  2、低优先级和高优先级都需要take同一个信号量。   优先级翻转的过程:  1、低优先级先take到信号量。  2、...
  • 1. 优先级反转(Priority Inversion)  由于多进程共享资源,具有最高优先权的进程被低优先级进程阻塞,反而使具有中优先级的进程先于高优先级的进程执行,导致系统的崩溃。这就是所谓的优先级反转(Priority ...
  • SMP系统在使用互斥锁时应该注意哪些问题?跟随一个真实的案例来一起分析一下吧~
  • 优先级倒置(Priority inversion)

    千次阅读 2017-04-07 17:48:34
    在嵌入式多任务实时操作系统(real time multitask operating system)...实时操作系统中常见的调度算法是优先级调度,给每个任务(线程)分配一个优先级优先级按任务需要执行的紧急状况来划分,一般优先级数值越低越
  • 说说优先级倒置(Priority inversion)

    万次阅读 2012-03-11 22:24:00
    在嵌入式多任务实时操作系统(real time multitask operating system)...实时操作系统中常见的调度算法是优先级调度,给每个任务(线程)分配一个优先级优先级按任务需要执行的紧急状况来划分,一般优先级数值越低越
  • 关于优先级反转

    2014-10-17 16:27:46
    在多进程、多线程并发的环境里,从概念上看,有多个进程或者多个线程在同时执行,具体到单个CPU级别,实际上任何时刻只能有一个进程或者线程处于执行状态;因此OS需要决定哪个进程执行,哪些进程等待,也就是进程的...
  • 死锁 & 优先级反转

    2018-09-19 12:19:49
    文章侵删。   死锁 在多道程序系统中,多个进程序并发执行,共享系统资源,从而提高了资源利用率和系统吞吐量,但可能发生一种危险----死锁。所谓死锁,是指多个进程因竞争资源而形成的一种僵局,若无外力作用,...
  • 讲解了Linux Pthread中的一些基本概念,包括,死锁,活锁,饿死,优先级反转,为后面研究锁机制和无锁编程打下基础
  • 优先级反转与死锁

    千次阅读 2016-01-05 15:43:42
    1.优先级反转指资源被锁时低优先级任务抢占高优先级任务。 举例:任务A、B、C,优先级从低到高依次为1、2、3,所有任务都是完全抢占式,任务A和C共享资源R。 1.任务A运行,并对资源R加锁; 2.任务C被激活抢占任务...
  • iOS的锁中有一个自选锁OSSpinLock , 这个api被标记为不推荐 , 理由就是会产生优先级反转的问题, 当时并不是特别理解这个优先级反转 . 后来在看一本书 <算法之美> 里在讲进程调度,优先级调度算法时也提到优先级...
  • UCOSIII优先级反转

    2017-12-27 15:04:37
    反转原因:H和L等待同一个信号量,H的任务优先级被降至和L相同优先级,此时M已经成为最高优先级实验举例void start_task(void *p_arg) { OS_CRITICAL_ENTER(); //进入临界区 //创建一个信号量 OS
  • 一、优先级倒置 1.1 形成原因 当前 OS 广泛采用优先级调度算法和抢占方式。高优先级的进程(或线程)被低优先级的进程(或线程)延迟或阻塞。产生的根源是互斥操作的存在。 假如有三个完全独立的进程P1、P2和P3,...
  • 实验三 优先级反转

    2019-01-17 12:08:28
    实验三 优先级反转 一、实验目的 掌握在基于优先级的可抢占嵌入式实时操作系统的应用中,出现优先级反转现象的原理。 二、实验原理 优先级反转原理: 在本实验中,要体现嵌入式实时内核的优先级抢占调度的策略...
  • 背景 很早之前,学习操作系统...优先级倒置 优先级逆转 优先级翻转 先要明白背景知识: 1.操作系统的任务调度 操作系统有多个任务 任务之间谁可以得到执行,是通过任务调度来完成的 2.任务调度有多种方法(..
  • 进程优先级反转

    2012-11-14 22:11:49
    面试的时候碰到了这个问题,没有回答出来,太囧了,...(1)什么是优先级反转(Priority Inversion)  简单从字面上来说,就是低优先级的任务先于高优先级的任务执行了,优先级搞反了。那在什么情况下会生这种情

空空如也

1 2 3 4 5 ... 20
收藏数 23,685
精华内容 9,474
关键字:

优先级反转