任务调度

一、多任务概念

多任务主要分为两类:非抢占式多任务(cooperative multitasking)和抢占式多任务(preemptive multitasking)。

概念:抢占(preemption)、进程的时间片(tineslice)、让步(yielding)、公平调度算法(CFS)

二、I/O消耗型和处理器消耗型进程

I/O消耗型:这种任务应该经常处于可以运行的状态,并且每次都是运行短短的一段时间,因为其等待更多的IO请求的时候,经常会堵塞。

处理器消耗型:这种任务通常在不停的运行,比如说科学计算或者Matlab之类的,从调度的角度来考虑,不应该让他们经常运行,应该是降低调度的频率,延长其运行时间。

有一些任务分类比较模糊,既是I/O消耗型,也是处理器消耗型,比如X Windows服务。

调度的策略是在这两个矛盾中寻找平衡:进程相应迅速(响应时间短)和最大系统的利用率(高吞吐量)。而Unix的调度更倾向于I/O调度,以便于更好的提供程序的响应速度。

三、进程的优先级

调度算法中最基本的一类是基于优先级的调度。通常的(Linux不采用)是优先级高的先运行,低的后运行,相同的优先级的进程按照轮转的方式进行调度,或者是优先级高的程序,其使用的时间片也比较长。调度程序总是选择时间片 没有用尽且优先级最高的进程来运行。

Linux有两种不同的优先级范围:

1)nice值:其范围为-20~19,默认值为0;nice值越大,代表优先级越低(可以理解,越nice,对其他的程序越友好,更容易让路,优先级越低)。在不同的Unix系统中,nice值的含义代表有所不同,在Mac OS X中,nice值代表了分配给进程的时间片的绝对值;Linux中,nice值代表了时间片的比例。使用ps -el看到的进程列表中的NI,就代表了时间片。

happyhls@happy-desktop:~$ ps -el
F S   UID   PID  PPID  C PRI  NI ADDR SZ WCHAN  TTY          TIME CMD
4 S     0     1     0  0  80   0 -  6117 poll_s ?        00:00:00 init
1 S     0     2     0  0  80   0 -     0 kthrea ?        00:00:00 kthreadd
1 S     0     3     2  0  80   0 -     0 run_ks ?        00:00:00 ksoftirqd/0
1 S     0     6     2  0 -40   - -     0 cpu_st ?        00:00:00 migration/0

 2)实时优先级:实时优先级的范围是0~99,与nice相反,实时优先级的数值,数值越大,代表了其进程优先级也就越高。还有一点, 任何实时进程的优先级都要高于普通的进程。实时优先级和nice互不相干。调用 ps -eo state,uid,pid,ppid,rtprio,time,comm

 

happyhls@happy-desktop:~$ ps -eo state,uid,pid,ppid,rtprio,time,comm
S   UID   PID  PPID RTPRIO     TIME COMMAND
S     0     1     0      - 00:00:00 init
S     0     2     0      - 00:00:00 kthreadd
S     0     3     2      - 00:00:00 ksoftirqd/0
S     0     6     2     99 00:00:00 migration/0
S     0     7     2     99 00:00:00 watchdog/0
S     0     8     2     99 00:00:00 migration/1

其中的RTPRIO就代表了实时优先级。如果为-,则代表不是实时优先级。

四、时间片

时间片,表明进程在被抢占之前所能够持续运行的时间。调度策略需要规定一个默认的时间片,其中有一个相对的问题:如果时间片过长,会带来系统对交互响应的滞后,如果时间片过短,会带来更多的进程切换所带来的处理器耗时;同时I/O消耗型和处理器消耗型也有不同的需求,I/O消耗型,希望频繁的调度,但每次只要运行很短的时间,而处理器消耗型则希望每一个调度之后,都能够运行的时间越长越好,比如可以更好的提高高速缓存的命中。

一般的系统中,为了保证交互的流畅,一般都把时间片设置的比较小,而在Linux中,CFS调度是分配的比例给时间片,而非具体的时间。同时时间片还会受到nice值大小的影响。优先级更高的程序会有高的权重,而优先级比较低的程序,其时间片的权重也会比较低。

在大多数系统当中,一个进程是否可以进入运行状态,是其时间片和优先级决定的。而在Linux的CFS当中,抢占的时机取决于新的可运行程序使用了多少的处理器使用比,如果消耗的使用比当前的进程要小,新的进程立刻投入运行,否则则会推迟其运行。

五、调度策略的初步认识CFS

在书的P38页,大体说明一下,有两个任务,一个是文本编辑器,另外一个任务是视频播放,可以明白的是,文本编辑器的任务是I/O消耗型的任务,而视频播放显然是处理器消耗型的任务。假设说这两个任务的优先级相同,nice值相同,那CFS是怎么调度的?

其任务调度如下所示:

首先,两者优先级和nice均相同,因此系统会给这两个分配相同的CPU时间,都是50%,但是每次文本编辑器被唤醒之后,只运行很少的时间,就会放弃CPU,而视频播放则会在其被调度的时候,全力工作。因此运行一段时间后,CFS会发现,给文本处理器的时间是50%,但实际上其使用的时间要远远小于50%,为了保证公平,当文本编辑器被唤醒的时候,CFS会立刻抢占视频编码的进程,让文本处理器运行。简单的理解,给你的这次用不完,下次让你提前用。

六、Linux调度算法

1、调度器类

Linux调度器以模块化的方式提供,模块化结构称为调度器类(scheduler classes),允许多种不同的可动态添加的调度算法并存,调度属于自己的范畴的进程。每一个调度器都有一个优先级,基础调度器(位于kernel/sched.c)会按照优先级遍历调度类,然后进行调度。CFS为针对普通进程的调度类,Linux称为SCHED_NORMAL,CFS算法实现在kernel/sched_fair.c

2、Unix传统进程调度的问题

1)如果要将nice值对应到时间片上去,需要将nice单位值对应到处理器的绝对时间:这就会带来问题,比如是nice=0对应的时间为100ms,而nice=+20的时候,对应的是5ms,那么当两个任务的分别优先级为0和20的时候,两个任务的优先级分配是合理的;但如果此时两个任务都是nice=+20,这时候就会带来问题,这时候满足我们的初衷,就是两个任务都能够获得50%的任务时间,但这个时候的问题是,由于其nice值为+20;因此其5ms就会被调度一次,此时调度非常频繁,开销变大,而其nice很大,本身可能就是后台任务,这个时候这样频繁调度是不合理的。

2)相对nice值的问题。如果两个nice值分别为0和1,那么他们的时间片为100ms和95ms,几乎一样,但如果两个nice值为18和19,那么他们分别获得10ms和5ms的nice值,相差两倍的时间。(因此,一般nice都是使用相对值)

解决的办法就是:将nice值呈几何增加而不是算数增加

3)绝对的时间片是依赖于系统定时器的,而由于平台的不同,其系统定时器可能是10ms,也有可能是5ms,而且相邻的时间片的差值应该是系统定时器的整数倍。

解决的办法是:将nice值到时间片的映射与定时器节拍分离开来。

3、公平调度(CFS)

CFS的出发点为:进程调度的效果应该就像系统具备一个理想中的完美的多任务处理器。

但由于系统调度时的任务抢占必然会有代价,因此CFS首先考虑任务调度系统性能不会受损。CFS的做法是允许每一个进程运行一段时间、循环轮转选择运行最小的进程作为一个运行的进程,而不是再采用分配给每个进程时间片的做法,CFS在所有的可运行进程总数的基础上计算出一个进程应该运行多久,而不是依靠nice的值来计算时间片。nice值在CFS中被作为进程获得的处理器运行比的权重:越高的nice(优先级越低)获得更低的处理器使用权重。相反,更低的nice值的进程获得更高的处理器使用权重。

CFS为了完美多任务中无线小调度周期的近似值设立了一个目标。称作“目标延时”,越小的调度周期有越好的交互性,同时也更加接近完美的多任务。但也要承担更高的切换代价和更差的系统总吞吐能力。(e.g如果目标延迟值为20ms,有两个任务,那么每个任务在抢占之前会运行10ms,如果有10个任务,那么每个任务在抢占之前会运行2ms)

此时又需要考虑一个问题,如果任务接近无线多个,那么每个任务的使用时间将无限接近于0,因此CFS引入了每个进程获得的时间片底线,也称作是最小粒度。默认情况下为1ms。

同时可以看到,nice值对于时间片是几何加权,而不是算数加权。任何nice值对应的是处理器的使用比,而不是绝对值。

About: happyhls


发表评论

电子邮件地址不会被公开。 必填项已用*标注