您的位置:新葡亰496net > 电脑系统 > 新葡亰496net:关于优先级反转,进程管理

新葡亰496net:关于优先级反转,进程管理

发布时间:2019-12-29 22:49编辑:电脑系统浏览(102)

    进程的引入

    当计算机在引入多道程序时,出现了临界资源竞争的情况,为了刻画和解决程序间的这种制约关系,提出了进程的概念,用以改善资源的利用率,提高程序的吞吐量。

    (一)

    调度器:

    新葡亰496net 1

    触发调度(轮转):

    新葡亰496net 2

    ① 非抢占式调度:进程自己发起

    ② 抢占式调度:操作系统内核引起。容易引起系统的不一致性,要考虑锁、信号量,但会改善系统的响应能力。

    选择获得处理器的下一个进程 --。 进程切换(保护老进程现场、恢复新进程运行) -->回收处理器资源

    系统获得CPU控制权(CPU再次运行系统内核):

    新葡亰496net 3

    进程切换 --> 处理器现场的切换

    将处理器当前现场保存在前一个进程的PCB中的context中。需要保存的大致是任务状态段TSS。


    转自:

    进程控制块PCB

    • linux系统的所有进程控制块都是通过结构体指针数组形式的数据结构来表示的(每个PCB块大约有1kb):
    /*全局变量nr_task动态记录进程数*/
    struct task_sturct *task[NR_TASK]={&init_task};
    

    运行状态进程的PCB同样用结构体指针数组表示:

    current_set[];
    
    • task_struct结构体定义:
    struct task_struct{
        ...
        unsigned short uid;
        int pid;
        ...
        volatile long state;
        long prority;
        unsigned long rt_protity;
        long counter;
        unsigned long policy;
        ...
        struct task_struct *next_task, *prev_task;
        struct task_struct *next_run, *prev_run;
        struct task struct *p_opptr, *pptr, *p_cptr, *pysptr, *p_ptr;
        ...
    };
    

    数据成员说明:
    uid:用户标识;
    pid:进程标识;
    state:进程状态标识;
    1)可运行状态
    2)可中断阻塞状态
    3)不可中断阻塞状态
    4)僵死状态
    5)暂停状态
    6)交换状态
    protity:进程优先级;
    counter:优先级计数器,用于进程轮转调度算法;
    policy:进程调度策略;
    next_task,prev_task:PCB双向链表指针;
    p_opptr ...:指明进程家族间的关系,分别为祖父进程,父进程,子进程,以及新老进程指针;

    (二)、进程选择算法

    评价标准:公平性;策略强制执行;均衡;响应时间、延迟;满意度(降低等待时间);吞吐量、带宽;周转时间

     

    进程属性

    • 进程ID:PID,进程唯一标志符;
    • 父进程ID:PPID;
    • 启动进程的用户ID:UID;
    • 所归属的组ID:GID;
    • 进程执行的优先级;
    • 进程连接终端

    1、批处理系统调度算法

    (1)先来先服务(FCFS)

    新葡亰496net 4

    (2)短进程优先(SPN)

    新葡亰496net 5

    平均等待时间最短、周转时间最短,但可能饿死长进程。

    (3)最短剩余时间优先(SRTN)

    SPN算法的抢占版本。当有进程就绪时,将他的下一次运行时间与当前进程的剩余时间,如果小,就抢占当前进程。

    新葡亰496net 6


    在多进程、多线程并发的环境里,从概念上看,有多个进程或者多个线程在同时执行,具体到单个CPU级别,实际上任何时刻只能有一个进程或者线程处于执行状态;因此OS需要决定哪个进程执行,哪些进程等待,也就是进程的调度。

    优先级问题

    谦让度:标识进程之间资源竞争能力,高谦让度的进程,资源竞争能力弱。负值或0表示最高优先级,对其他进程不谦让。谦让度的值一般为:-20~19;当前硬件发展速度非常快,一般我们是不设置进程优先级的,除非有进程失控而疯狂的抢占资源;

    在创建进程时,nice可以为进程设置谦让值,但进程优先级的值为父进程shell优先级的值与nice所指定的谦让度相加的结果。即,利用nice指定的值是一个增量,而不是优先级的绝对值。

    运行 a.out 程序,并为它指定谦让度增量为5:

        nice -n 5 a.out &
    

    利用renice来更改谦让度:

        renice 谦让度 PID
    

    2、交互系统调度算法

    (1)轮转法(RR)

    加了时间片限制的先入先出FCFS算法。

    新葡亰496net 7

    新葡亰496net 8

    (2)可变时间片轮转法

    新葡亰496net 9

    新葡亰496net:关于优先级反转,进程管理。(3)优先级

    新葡亰496net 10

    可能饿死优先级低的进程:

    新葡亰496net 11

    (4)多级队列法

    不同种类的进程应有不同的优先级和时间片。根据实际情况将进程分组,提供几个就绪队列,每个队列有自己独立的调度算法,根据进程特性把进程链入某一队列,队列间可采用其他调度算法。

    Linux用了140多个队列,用了一个位图,每位一个队列。

    (5)多级反馈队列法

    新葡亰496net 12

    新葡亰496net 13

    (6)彩票调度法

    优先级算法的变形。

    新葡亰496net 14

    (7)公平分享法

    每个用户拥有的进程数不一样。

    新葡亰496net 15

    新葡亰496net 16


    一、调度的目标
    1、首先要区分程序使用CPU的三种模式:IO密集型、计算密集型和平衡型。对于IO密集型程序来说,响应时间非常重要;对于CPU密集型来说,CPU的周转时间就比较重要;对于平衡型程序来说,响应和周转之间的平衡是最重要的。
    2、CPU的调度就是要达到极小化平均响应时间、极大化系统吞吐率、保持系统各个功能部件均处于繁忙状态和提供某种公平的机制。
    3、对于实时系统来说,调度的目标就是要达到截止时间前完成所应该完成的任务和提供性能的可预测性。

    进程调度算法简介

    程序使用cpu的三种模式:I/O密集型、计算密集型和平衡型。对于I/O密集型程序,响应时间非常重要,响应时间不及时,和可能丢失数据;对于计算密集型程序,cpu的周转时间非常重要;对于平衡型程序,协调响应和cpu周转的工作最重要。

    进程周转时间:等待进入内存的时间,在就绪队列中等待的时间,在 CPU中执行的时间和I/O操作的时间的总和。

    3、实时系统调度算法

    实时系统是一种时间起主导作用的系统。

    实时分为硬实时和软实时。硬实时有死线限制,软实时可容忍偶尔的失误。

    新葡亰496net 17

    新葡亰496net 18


    二、调度算法

    FCFS算法

    FCFS(frist come first serve),也叫FIFO算法,先来先执行。短任务执行可能会非常慢,因为前面的进程可能占用很长时间,造成平均响应时间过长。

    (三)、进程调度-Ucore实现(略写)

    新葡亰496net 19

    1、FCFS调度器

    新葡亰496net 20

    新葡亰496net 21

    新葡亰496net 22

    新葡亰496net 23

    新葡亰496net 24


    1、FCFS(First come first serve),或者称为FIFO算法,先来先处理。这个算法的优点是简单,实现容易,并且似乎公平;缺点在于短的任务有可能变的非常慢,因为其前面的任务占用很长时间,造成了平均响应时间非常慢。

    新葡亰496net:关于优先级反转,进程管理。时间片轮转算法

    目的是改善短程序响应时间长的问题。方法是周期性的对进程进行切换。该算法最关键的时间片的选择,时间片过长和FIFO算法区别不大,时间片过短,进程频繁切换的开销大于执行程序的开销,系统效率降低。

    2、进程切换

    如果选中的下一个进程不是当前进程,则要进行进程切换,由函数proc_run完成。

    新葡亰496net 25

    这个过程:进程创建 --。 设堆栈 --> 设context --》 就绪态 --> 插入队列

    查找时找到他 --> 调度第一次运行

    新葡亰496net 26


    2、时间片轮询算法,这是对FIFO算法的改进,目的是改善短程序(运行时间短)的响应时间,其方法就是周期性地进行进程切换。这个算法的关键点在于时间片的选择,时间片过大,那么轮转就越接近FIFO,如果太小,进程切换的开销大于执行程序的开销,从而降低了系统效率。因此选择合适的时间片就非常重要。选择时间片的两个需要考虑的因素:一次进程切换所使用的系统消耗以及我们能接受的整个系统消耗、系统运行的进程数。
        时间片轮询看上起非常公平,并且响应时间非常好,然而时间片轮转并不能保证系统的响应时间总是比FIFO短,这很大程度上取决于时间片大小的选择,以及这个大小与进程运行时间的相互关系。

    STCF算法

    STCF算法全称:short time to complete frist。核心是每个进程都有优先级,短进程的优先级要高于长进程的优先级。STCF算法分为:非抢占式和抢占式两类。非抢占式就是让已经在cpu上运行的程序执行到结束或者阻塞,然后在就绪队列中选择执行时间最短的程序来执行。而抢占式是,每当有新进程进入就绪队列时,都会去判断当前运行进程和新进程的执行时间长短,选择执行时间短的进程运行,及永远保证cpu运行的是所有进程中执行时间最短的进程。该算法有个非常明显的缺点:长任务进程无法执行。还有该算法的关键点是如何预测进程所需的执行时间。

    3、调度器框架(略,详见ppt)

    (1)调度器类

    进程管理的接口函数:①入队操作;②出队操作;③选出操作;④更新操作

    (2)唤醒 --> 就绪状态,僵死的唤不醒。

    (3)RR调度器

    RR轮转法——加了时间片的FCFS算法

    新葡亰496net 27

    (4)Stride调度算法

    Stride调度算法是对彩票调度算法的改进。

    新葡亰496net 28

    新葡亰496net 29

    新葡亰496net 30

    左偏树:

    新葡亰496net 31

    新葡亰496net 32

    新葡亰496net 33

    3、STCF算法(Short time to complete first),顾名思义就是短任务优先算法。这种算法的核心就是所有的程序都有一个优先级,短任务的优先级比长任务的高,而OS总是安排优先级高的进程运行。
        STCF又分为两类:非抢占式和抢占式。非抢占式STCF就是让已经在CPU上运行的程序执行到结束或者阻塞,然后在所有的就绪进程中选择执行时间最短的来执行;而抢占式STCF就不是这样,在每进来一个新的进程时,就对所有进程(包括正在CPU上执行的进程)进行检查,谁的执行时间短,就运行谁。

    优先级调度算法

    解决了STCF算法中长任务进程饥饿的问题,而暴露出的短任务会饥饿的问题,可以通过动态调整优先级来解决。实际上动态调整优先级(称为权值) 时间片轮转的策略正是Linux系统进程调度的策略之一的分时调度策略,调度过程如下:

    (1) 创建任务指定采用分时调度策略,指定优先级nice的值(-20~19)
    (2) 依据nice的值确定在cpu上的执行时间
    (3) 如果没有等待资源,则将该任务加入就绪队列中
    (4) 调度程序遍历就绪队列,通过对动态优先级的计算,选择计算结果最
    大的去执行。当时间片用完时或进程主动放弃cpu时,该任务就重新放回就
    绪队列队尾或等待队列中。
    (5) 调度程序重新按照(4)的方式调度进程。
    (6) 当调度程序发现所有就绪队列中的进程的权值都不大于0时,重复(2)
    的过程
    

    现代OS通常都会采用混合调度算法。如:将不同的进程分为几个大类,每个大类有不同的优先级,不同大类的进程调度取决于大类的优先级,同一个大类的进程调度采用时间片轮转算法来实现。

        STCF总是能提供最优的响应时间,然而它也有缺点,第一可能造成长任务的程序无法得到CPU时间而饥饿,因为OS总是优先执行短任务;其次,关键问题在于我们怎么知道程序的运行时间,怎么预测某个进程需要的执行时间?通常有两个办法:使用启发式方法估算(例如根据程序大小估算),或者将程序执行一遍后记录其所用的CPU时间,在以后的执行过程中就可以根据这个测量数据来进行STCF调度。

    4、优先级调度,STCF遇到的问题是长任务的程序可能饥饿,那么优先级调度算法可以通过给长任务的进程更高的优先级来解决这个问题;优先级调度遇到的问题可能是短任务的进程饥饿,这个可以通过动态调整优先级来解决。实际上动态调整优先级(称为权值) 时间片轮询的策略正是linux的进程调度策略之一的 SCHED_OTHER分时调度策略,它的调度过程如下:

    (1)创建任务指定采用分时调度策略,并指定优先级nice值(-20~19)。

    (2)将根据每个任务的nice值确定在cpu上的执行时间(counter)。

    (3)如果没有等待资源,则将该任务加入到就绪队列中。

    (4)调度程序遍历就绪队列中的任务,通过对每个任务动态优先级的计算(counter 20-nice)结果,选择计算结果最大的一个去运行,当这个时间片用完后(counter减至0)或者主动放弃cpu时,该任务将被放在就绪队列末尾(时间片用完)或等待队列(因等待资源而放弃cpu)中。

    (5)此时调度程序重复上面计算过程,转到第4步。

    (6)当调度程序发现所有就绪任务计算所得的权值都为不大于0时,重复第2步。

    linux还有两个实时进程的调度策略:FIFO和RR,实时进程会立即抢占非实时进程。

    5、显然,没有什么调度算法是毫无缺点的,因此现代OS通常都会采用混合调度算法。例如将不同的进程分为几个大类,每个大类有不同的优先级,不同大类的进程的调度取决于大类的优先级,同一个大类的进程采用时间片轮询来保证公平性。

    6、其他调度算法,保证调度算法保证每个进程享用的CPU时间完全一样;彩票调度算法是一种概率调度算法,通过给进程“发彩票”的多少,来赋予不同进程不同的调用时间,彩票调度算法的优点是非常灵活,如果你给短任务发更多“彩票”,那么就类似STCF调度,如果给每个进程一样多的“彩票”,那么就类似保证调度;用户公平调度算法,是按照每个用户,而不是按照每个进程来进行公平分配CPU时间,这是为了防止贪婪用户启用了过多进程导致系统效率降低甚至停顿。

    7、实时系统的调度算法,实时系统需要考虑每个具体任务的响应时间必须符合要求,在截止时间前完成。
    (1)EDF调度算法,就是最早截止任务优先(Earliest deadline first)算法,也就是让最早截止的任务先做。当新的任务过来时,如果它的截止时间更靠前,那么就让新任务抢占正在执行的任务。EDF算法其实是贪心算法的一种体现。如果一组任务可以被调度(也就是所有任务的截止时间在理论上都可以得到满足),那么EDF可以满足。如果一批任务不能全部满足(全部在各自的截止时间前完成),那EDF满足的任务数最多,这就是它最优的体现。EDF其实就是抢占式的STCF,只不过将程序的执行时间换成了截止时间。EDF的缺点在于需要对每个任务的截止时间做计算并动态调整优先级,并且抢占任务也需要消耗系统资源。因此它的实际效果比理论效果差一点。

    (2)RMS调度算法,EDF是动态调度算法,而RMS(rate monotonic scheduling)算法是一种静态最优算法;该算法在进行调度前先计算出所有任务的优先级,然后按照计算出来的优先级进行调度,任务执行中间既不接收新任务,也不进行优先级调整或者CPU抢占。因此它的优点是系统消耗小,缺点就是不灵活了。对于RMS算法,关键点在于判断一个任务组是否能被调度,这里有一个定律,如果一个系统的所有任务的CPU利用率都低于ln2,那么这些任务的截止时间均可以得到满足,ln2约等于0.693147,也就是此时系统还剩下有30%的CPU时间。这个证明是Liu和Kayland在1973年给出的。

    三、优先级反转
    1、什么是优先级反转?
        优先级反转是指一个低优先级的任务持有一个被高优先级任务所需要的共享资源。高优先任务由于因资源缺乏而处于受阻状态,一直等到低优先级任务释放资源为止。而低优先级获得的CPU时间少,如果此时有优先级处于两者之间的任务,并且不需要那个共享资源,则该中优先级的任务反而超过这两个任务而获得CPU时间。如果高优先级等待资源时不是阻塞等待,而是忙循环,则可能永远无法获得资源,因为此时低优先级进程无法与高优先级进程争夺CPU时间,从而无法执行,进而无法释放资源,造成的后果就是高优先级任务无法获得资源而继续推进。

    2、解决方案:
    (1)设置优先级上限,给临界区一个高优先级,进入临界区的进程都将获得这个高优先级,如果其他试图进入临界区的进程的优先级都低于这个高优先级,那么优先级反转就不会发生。

    (2)优先级继承,当一个高优先级进程等待一个低优先级进程持有的资源时,低优先级进程将暂时获得高优先级进程的优先级别,在释放共享资源后,低优先级进程回到原来的优先级别。嵌入式系统VxWorks就是采用这种策略。
        这里还有一个八卦,1997年的美国的火星探测器(使用的就是vxworks)就遇到一个优先级反转问题引起的故障。简单说下,火星探测器有一个信息总线,有一个高优先级的总线任务负责总线数据的存取,访问总线都需要通过一个互斥锁(共享资源出现了);还有一个低优先级的,运行不是很频繁的气象搜集任务,它需要对总线写数据,也就同样需要访问互斥锁;最后还有一个中优先级的通信任务,它的运行时间比较长。平常这个系统运行毫无问题,但是有一天,在气象任务获得互斥锁往总线写数据的时候,一个中断发生导致通信任务被调度就绪,通信任务抢占了低优先级的气象任务,而无巧不成书的是,此时高优先级的总线任务正在等待气象任务写完数据归还互斥锁,但是由于通信任务抢占了CPU并且运行时间比较长,导致气象任务得不到CPU时间也无法释放互斥锁,本来是高优先级的总线任务也无法执行,总线任务无法及时执行的后果被探路者认为是一个严重错误,最后就是整个系统被重启。Vxworks允许优先级继承,然而遗憾的工程师们将这个选项关闭了。

    (3)第三种方法就是使用中断禁止,通过禁止中断来保护临界区,采用此种策略的系统只有两种优先级:可抢占优先级和中断禁止优先级。前者为一般进程运行时的优先级,后者为运行于临界区的优先级。火星探路者正是由于在临界区中运行的气象任务被中断发生的通信任务所抢占才导致故障,如果有临界区的禁止中断保护,此一问题也不会发生。

    本文由新葡亰496net发布于电脑系统,转载请注明出处:新葡亰496net:关于优先级反转,进程管理

    关键词:

上一篇:9安装vsftpd并配置多用户的方法

下一篇:没有了