嵌入式Linux中文站

linux进程调度方法简述


 
在 Linux2.6 中,仍有三种调度策略: SCHED_OTHER、SCHED_FIFO 和 SCHED_RR。
  SCHED_ORHER:普通进程,基于优先级进行调度。
  SCHED_FIFO:实时进程,实现一种简单的先进先出的调度算法。
  SCHED_RR:实时进程,基于时间片的SCHED_FIFO,实时轮流调度算法。
    前者是普通进程调度策略,后两者都是实时进程调度策略。SCHED_FIFO 与 SCHED_RR 的区别是:当进程的调度策略为前者时,当前实时进程将一直占用 CPU 直至自动退出,除非有更紧迫的、优先级更高的实时进程需要运行时,它才会被抢占 CPU;当进程的调度策略为后者时,它与其它实时进程以实时轮流算法去共同使用 CPU,用完时间片放到运行队列尾部。进程提供了两种优先级,一种是普通的进程优先级,第二个是实时优先级。前者适用SCHED_NORMAL调度策略,后者可选SCHED_FIFO或SCHED_RR调度策略。任何时候,实时进程的优先级都高于普通进程,实时进程只会被更高级的实时进程抢占,同级实时进程之间是按照FIFO(一次机会做完)或者RR(多次轮转)规则调度的。

实时进程的调度
    实时进程,只有静态优先级,因为内核不会再根据休眠等因素对其静态优先级做调整,其范围在0~MAX_RT_PRIO-1间。默认MAX_RT_PRIO配置为100,也即,默认的实时优先级范围是0~99。而nice值,影响的是优先级在MAX_RT_PRIO~MAX_RT_PRIO+40范围内的进程。
    不同与普通进程,系统调度时,实时优先级高的进程总是先于优先级低的进程执行。直到实时优先级高的实时进程无法执行。实时进程总是被认为处于活动状态。如果有数个优先级相同的实时进程,那么系统就会按照进程出现在队列上的顺序选择进程。假设当前CPU运行的实时进程A的优先级为a,而此时有个优先级为b的实时进程B进入可运行状态,那么只要b<a,系统将中断A的执行,而优先执行B,直到B无法执行(无论A,B为何种实时进程)。
不同调度策略的实时进程只有在相同优先级时才有可比性:
(1)对于FIFO的进程,意味着只有当前进程执行完毕才会轮到其他进程执行。由此可见相当霸道。
(2)对于RR的进程。一旦时间片消耗完毕,则会将该进程置于队列的末尾,然后运行其他相同优先级的进程,如果没有其他相同优先级的进程,则该进程会继续执行。
    RR进程和FIFO进程都采用实时优先级做为调度的权值标准,RR是FIFO的一个延伸。FIFO时,如果两个进程的优先级一样,则这两个优先级一样的进程具体执行哪一个是由其在队列中的位置决定的,这样导致一些不公正性(优先级是一样的,为什么要让你一直运行?),如果将两个优先级一样的任务的调度策略都设为RR,则保证了这两个任务可以循环执行,保证了公平。使用统一的数据结构管理SCHED_FIFO和SCHED_RR进程,同一优先级选择就绪队列头的的那个进程运行。
注:调用函数sched_setscheduler()可以设置实时进程的优先级。
补充:nice值
    Nice值是类UNIX操作系统中表示静态优先级的数值。每个进程都有自己的静态优先级,优先级高的进程得以优先运行。Nice值的范围是-20~+19,拥有Nice值越大的进程的实际优先级越小(即Nice值为+19的进程优先级最小,为-20的进程优先级最大),默认的Nice值是0。由于Nice值是静态优先级,所以一经设定,就不会再被内核修改,直到被重新设定。Nice值只起干预CPU时间分配的作用,实际中的细节,由动态优先级决定。“Nice值”这个名称来自英文单词nice,意思为友好。Nice值越高,这个进程越“友好”,就会让给其他进程越多的时间。
    nice表示进程可被执行的优先级的修正数值。如前面所说,优先级值(PRI)越小越快被执行,那么加入nice值后,将会使得PRI变为:PRI(new)=PRI(old)+nice。这样,当nice值为负值的时候,那么该程序将会优先级值将变小,即其优先级会变高,则其越快被执行。
    进程在创建时并不是平等的,他们被赋予不同的优先级值,例如有些对计算机本身的操作至关重要的程序必须比其他次要的程序具有更高的优先级(则其有更小的优先级值)。而如前面所说,nice的值是表示进程优先级值可被修正数据值,因此,每个进程都在其计划执行时被赋予一个系统nice值,这样系统就可以根据系统的资源以及具体进程的各类资源消耗情况,主动干预进程的优先级值。这个过程,用户也可手工干预其中,但是要被赋予相应的权限。

普通进程的调度
    Linux对普通的进程,根据动态优先级进行调度。而动态优先级是由静态优先级(static_prio)调整而来。Linux下,静态优先级是用户不可见的,隐藏在内核中。而内核提供给用户一个可以影响静态优先级的接口,那就是nice值,两者关系如下:
  static_prio=MAX_RT_PRIO +nice+ 20
  nice值的范围是-20~19,因而静态优先级范围在100~139之间。nice数值越大就使得static_prio越大,最终进程优先级就越低。ps -el 命令执行结果:NI列显示的每个进程的nice值,PRI是进程的优先级(如果是实时进程就是静态优先级,如果是非实时进程,就是动态优先级)。
而进程的时间片就是完全依赖 static_prio 定制的,见下图,摘自《深入理解linux内核》:

    前面也说了,系统调度时,还会考虑其他因素,因而会计算出一个叫进程动态优先级的东西,根据此来实施调度。因为,不仅要考虑静态优先级,也要考虑进程的属性。例如如果进程属于交互式进程,那么可以适当的调高它的优先级,使得界面反应地更加迅速,从而使用户得到更好的体验。Linux2.6 在这方面有了较大的提高。Linux2.6认为,交互式进程可以从平均睡眠时间这样一个measurement进行判断。进程过去的睡眠时间越多,则越有可能属于交互式进程。则系统调度时,会给该进程更多的奖励(bonus),以便该进程有更多的机会能够执行。奖励(bonus)从0到10不等。
  系统会严格按照动态优先级高低的顺序安排进程执行。动态优先级高的进程进入非运行状态,或者时间片消耗完毕才会轮到动态优先级较低的进程执行。动态优先级的计算主要考虑两个因素:静态优先级,进程的平均睡眠时间也即bonus。计算公式如下,
     dynamic_prio = max (100, min (static_prio - bonus + 5, 139))
  在调度时,Linux2.6 使用了一个小小的trick,就是算法中经典的空间换时间的思想,使得计算最优进程能够在O(1)的时间内完成。
为什么根据睡眠和运行时间确定奖惩分数是合理的?

  睡眠和CPU耗时反应了进程IO密集和CPU密集两大瞬时特点,不同时期,一个进程可能即是CPU密集型也是IO密集型进程。对于表现为IO密集的进程,应该经常运行,但每次时间片不要太长。对于表现为CPU密集的进程,CPU不应该让其经常运行,但每次运行时间片要长。交互进程为例,假如之前其其大部分时间在于等待CPU,这时为了调高相应速度,就需要增加奖励分。另一方面,如果此进程总是耗尽每次分配给它的时间片,为了对其他进程公平,就要增加这个进程的惩罚分数。可以参考CFS的virtutime机制。


本文永久更新链接:http://embeddedlinux.org.cn/emb-linux/process-thread/201709/09-7311.html



分享:

评论