Linux进程调度算法

互联网技术 waitig 643℃ 百度已收录 0评论

进程调度算法

FCFS

先来先服务(FCFS)调度算法是一种最简单的调度算法,当在作业调度中采用该算法时,每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业,将它们调入内存,为它们分配资源、创建进程,然后放入就绪队列。在进程调度中采用FCFS算法时,则每次调度是从就绪队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

SJF

最短作业优先调度中我们根据作业的执行时间长短来调度。相比于FCFS,SJF能大大提高系统的吞吐能力改善进程的周转时间,但SJF对长进程非常不利,可能长时间得不到执行,且未能依据进程的紧迫程度来划分执行的优先级,以及难以准确估计进程的执行时间,从而影响调度性能。

HRRN

最高响应比优先法(HRRN,Highest Response Ratio Next)是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短,而SJF方式只考虑执行时间而未考虑等待时间的长短。因此,这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短,从中选出响应比最高的作业投入执行。这样,即使是长作业,随着它等待时间的增加,W / T也就随着增加,也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于每次调度前要计算响应比,系统开销也要相应增加。

响应比R定义如下: R =(W+T)/T = 1+W/T

RR

时间片轮转算法(RR,Round-Robin)采用剥夺策略。时间片轮转调度是一种最古老,最简单,最公平且使用最广的算法,又称RR调度。每个进程被分配一个时间段,称作它的时间片,即该进程允许运行的时间。在时间片轮转算法中,时间片的大小对系统性能的影响很大,因此时间片的大小应选择恰当怎样确定时间片的大小。

Linux进程调度的目标

  1. 高效性:高效意味着在相同的时间下要完成更多的任务。调度程序会被频繁的执行,所以调度程序要尽可能的高效;
  2. 加强交互性能:在系统相当的负载下,也要保证系统的响应时间;
  3. 保证公平和避免饥渴;
  4. SMP调度:调度程序必须支持多处理系统;
  5. 软实时调度:系统必须有效的调用实时进程,但不保证一定满足其要求;

O(1)调度算法

进程有两个优先级,一个是静态优先级,一个是动态优先级.静态优先级是用来计算进程运行的时间片长度的,动态优先级是在调度器进行调度时用到的,调度器每次都选取动态优先级最高的进程运行。

动态优先级=max(100 , min(静态优先级 – bonus + 5 , 139))

动态优先级的生成是以静态优先级为基础,再加上相应的惩罚或奖励(bonus).这个bonus并不是随机的产生,而是根据进程过去的平均睡眠时间做相应的惩罚或奖励.交互性强的进程会得到调度程序的奖励(bonus为正),而那些一直霸占CPU的进程会得到相应的惩罚(bonus为负).

普通进程的动态优先级的范围是100~139,实时进程的动态优先级的范围是0~99

时间片的计算

Linux2.4版本的内核调度算法理解起来简单:在每次进程切换时,内核依次扫描就绪队列上的每一个进程,计算每个进程的优先级,再选择出优先级最高的进程来运行;尽管这个算法理解简单,但是它花费在选择优先级最高进程上的时间却不容忽视。系统中可运行的进程越多,花费的时间就越大,时间复杂度为O(n)。

2.6内核所采用的O(1)算法则很好的解决了这个问题,该算法可以在恒定的时间内为每个进程重新分配好时间片,而且在恒定的时间内可以选取一个最高优先级的进程,重要的是这两个过程都与系统中可运行的进程数无关,这也正是该算法取名为O(1)的缘故。

数据结构

运行队列:每个cpu都有一个运行队列
优先级数组: 该结构体中有一个用来表示进程动态优先级的数组queue

#define MAX_USER_RT_PRIO        100
#define MAX_RT_PRIO             MAX_USER_RT_PRIO
#define MAX_PRIO                (MAX_RT_PRIO + 40)
typedef struct prio_array prio_array_t;
struct prio_array {
        unsigned int nr_active;
        unsigned long bitmap[BITMAP_SIZE];
        struct list_head queue[MAX_PRIO]; //0~139
};

queue数组中包含140个可运行状态的进程链表,每一条优先级链表上的进程都具有相同的优先级。
prio_array结构中还包括一个优先级位图bitmap.该位图使用一个位(bit)来代表一个优先级. 比如第一个位为1则表示第一条优先级链表上有进程。

O(1)调度算法将系统中的可运行进程分为两类:

  • 活动进程: 那些还没有用完时间片的进程
  • 过期进程: 那些已经用完时间片的进程

调度程序的工作就是在活动进程集合中选取一个最佳优先级的进程,如果该进程时间片恰好用完,就将该进程放入过期进程集合中。

不管是过期进程集合还是活跃进程集合,都将每个优先级的进程组成一个链表,因此每个集合就有140个不同优先级的进程链表.同时,两个集合中还采用优先级位图来标记每个优先级链表中是否存在进程。

进程调度

调度程序每次都是选取优先级最高而且还有剩余时间片的进程来运行。在选取最高优先级的进程时,首先利用优先级位图从高到低找到第一个被设置的位,该位对应着一条进程链表,这个链表中的进程是当前系统所有可运行进程中优先级最高的。在该优先级链表中选取头一个进程,它拥有最高的优先级,即为调度程序马上要执行的进程。

struct task_struct *prev, *next;
struct list_head *queue;
struct prio_array *array;
int idx;

prev = current;
array = rq->active;
idx = sehed_find_first_bit(array->bitmap); //找到位图中第一个不为0的位的序号
queue = array->queue + idx; //得到对应的队列链表头
next = list_entry(queue->next, struct task_struct, run_list); //得到进程描述符
if (prev != next) //如果选出的进程和当前进程不是同一个,则交换上下文
    context_switch();

周期性调度函数schedule_tick():
schedule_tick函数用来更新进程的时间片,它被调用时本地中断被禁止。

  1. 首先通过相应的函数和宏获得当前处理器的编号、当前可运行队列和当前进程描述符.再通过sched_clock函数获得最近一次定时器中断的时间戳。

  2. 如果当前进程是普通进程,则只需递减当前进程的时间片.如果时间片还未用完,则函数返回。

  3. 如果当前进程时间片用完,首先从当前活动进程集合中调用dequeue_task()函数删除该进程,然后通过set_tsk_need_resched函数设置TIF_NEED_RESCHED标志,以便稍后重新进行进程调度。

  4. 接着通过effective_prio()函数更新当前进程的动态优先级,进程的动态优先级是以进程的静态优先级(static_prio)为基数,在通过bonus适当的对其惩罚或奖励。

  5. 如果当前进程的时间片已经用完,则调用task_timeslice函数对当前进程重新分配时间片。

  6. 如果当前进程的时间片已经用完,则需要判断是否把该进程移入过期队列中。

  7. 当活动进程链表都为空时,就把活动进程链表和过期进程链表交换过来,重新调度过期队列中的进程,此时先前的活动进程链表就变成了过期进程链表。

O(1)调度算法最大的问题还是, 当系统中的交互性程序过多时,运行的不太理想, 比如桌面系统。

CFS调度算法

CFS的核心思想

全公平调度器(CFS)的设计思想是:在一个真实的硬件上模型化一个理想的、精确的多任务CPU。该理想CPU模型运行在100%的负荷、在精确 平等速度下并行运行每个任务,每个任务运行在1/n速度下,即理想CPU有n个任务运行,每个任务的速度为CPU整个负荷的1/n。

由于真实硬件上,每次只能运行一个任务,这就得引入”虚拟运行时间”(virtual runtime)的概念,虚拟运行时间为一个任务在理想CPU模型上执行的下一个时间片(timeslice)。实际上,一个任务的虚拟运行时间为考虑到运行任务总数的实际运行时间。

CFS 背后的主要想法是维护为任务提供处理器时间方面的平衡(公平性)。CFS为了体现的公平表现在2个方面:
(1)进程的运行时间相等
CFS 在叫做虚拟运行时的地方维持提供给某个任务的时间量。任务的虚拟运行时越小, 意味着任务被允许访问服务器的时间越短 — 其对处理器的需求越高。
例如,如果具有 4 个可运行的任务,那么 fair_clock将按照实际时间速度的四分之一增加。每个任务将设法跟上这个速度。这是由分时多任务处理的量子化特性决定的。也就是说,在任何一个时间段内只有一个任务可以运行;因此,其他进程在时间上的拖欠将增大(wait_runtime)。因此,一旦某个任务进入调度,它将努力赶上它所欠下的时间(并且要比所欠时间多一点,因为在追赶时间期间,fair_clock 不会停止计时)。

加权任务引入了优先级。假设我们有两个任务:其中一个任务占用 CPU 的时间量是另一个任务的两倍,比例为 2:1。执行数学转换后,对于权重为 0.5 的任务,时间流逝的速度是以前的两倍。

(2)睡眠的进程进行补偿
CFS 还包含睡眠公平概念以便确保那些目前没有运行的任务(例如,等待 I/O)在其最终需要时获得相当份额的处理器。

CFS调度器的运行时间是O(logN),而以前的调度器的运行时间是O(1),这是不是就是说CFS的效率比O(1)的更差呢?
答案并不是那样,我们知道CFS调度器下的运行队列是基于红黑树组织的,找出下一个进程就是截下左下角的节点,固定时间完成,所谓的O(logN)指的是插入时间,可是红黑树的统计性能是不错的,没有多大概率真的用得了那么多时间,因为红节点和黑节点的特殊排列方式既保证了树的一定程度的平衡,又不至于花太多的时间来维持这种平衡,插入操作大多数情况下都可以很快的完成,特别是对于组织得相当好的数据。

调度原理

在cfs中,没有确定时间片的概念,不再像以前那样根据进程的优先值为进程分配一个确定的时 间片,在这个时间片过期后发生无条件进程切换,而未过期时则可以发生抢占。这个时间片的思想从早期的分时unix继承而来,已经不再适应现在抢占,特别是内核抢占无处不在的新世界了,如今的处理器速度大大提高,时钟大大精确了,另外外设越来越智能,为cpu分担的工作越来越多,cpu仍然作为计算机的中心就不能对外设为所欲为了,外设的中断更加频繁和有效,但是如果应用这些外设的运行于cpu的进程如果还是延迟响应的话,事情就会显得有些不和谐。这就要求调度器必须改进,以前的时钟不精确,中断不频繁,外设少,总线带宽低,应用不丰富等原因使得内核非抢占是可以忍受的,后来虽然有了内核抢占但是还是和硬件格格不入,应用程序总是看起来反映迟缓或者不公平,cfs调度器在这种情况下由运而生,cfs的总体思想就是尽量使进程公平的被调度,这种公平不是同等对待所有进程,而是按照进程权值百分之百履行优先级承诺。cfs算法意味着cpu的调度和硬件行为的步调更加的一致,同时也免去了复杂的行为预测算法,这比较符合这个世界的规则。按照以前的时间片方式硬件的时间片和操作系统调度的软件时间片差好几个数量级,而且软件已经不能做的更加精确了,因此必须抛弃这种方式,cfs调度器看上去更像是一部无级变速器,既然跟不上硬件就别用时间片跟,到最后不但还是跟不上,而且还使得时间片调度行为丧失了世界原本的性质,所以才有了那么多复杂的预测算法。cfs回归了世界的本质,就是公平的履行承诺。在2.6.25以后cfs中在每个队列设置了一个字段,就是vruntime,这个字段在系统运行期间单调增长,各个进程自己也有一个vruntime,它们相互追赶向这个vruntime看齐,并且可以最终将自己的vruntime设置为队列的vruntime,处理器总是挑选vruntime小的运行,这其实是一种对掉队者的补偿,这就是公平,每个进程的vruntime相当于它自己的虚拟时钟,如果每个进程的虚拟时钟同步,各个进程就可以说是公平的,相互追赶vruntime并且向cfsq的vruntime看齐就是保持虚拟时钟同步。对于不同权值的进程,它们的虚拟时钟快慢不同,这才是公平的真正含义,比方说权值大的进程的虚拟时钟10秒走一个字,而权值小的进程虚拟时钟1秒就走一个字,虚拟时钟都走一个字就同步了,但是权值大的进程运行了10秒而小权值的进程才运行1秒。

cfs定义了一种新的模型,它给cfs_rq(cfs的run queue)中的每一个进程安排一个虚拟时钟,vruntime。如果一个进程得以执行,随着时间的增长(也就是一个个tick的到来),其vruntime将不断增大。没有得到执行的进程vruntime不变。

而调度器总是选择vruntime跑得最慢的那个进程来执行。这就是所谓的“完全公平”。为了区别不同优先级的进程,优先级高的进程vruntime增长得慢,以至于它可能得到更多的运行机会。

CFS的公平依据就是每个调度实体的权重(weight),这个权重是有优先级来决定的,即优先级越高权重越高,linux内核采用了从nice 到 prio 到 weight的一个转换关系来实现了每个调度实体权重的确定。

组织结构

CFS调度运行队列采用红黑树方式组织,红黑树种的key值以vruntime排序。每次选择下一个进程运行时即是选择最左边的一个进程运行。而对于入队和处队都会更新调度队列、调度实体的相关信息。
cfs.gif-10.5kB

CFS还有一个重要特点,即调度粒度小。CFS之前的调度器中,除了进程调用了某些阻塞函数而主动参与调度之外,每个进程都只有在用完了时间片或者属于自己的时间配额之后才被抢占。而CFS则在每次tick都进行检查,如果当前进程不再处于红黑树的左边,就被抢占。在高负载的服务器上,通过调整调度粒度能够获得更好的调度性能。

CFS实现

在2.6.23内核中,刚刚实现的CFS调度器显得很淳朴,每次的时钟滴答中都会将当前进程先出队,推进其虚拟时钟和系统虚拟时钟后再入队,然后判断红黑 树的左下角的进程是否还是当前进程而抉择是否要调度,这种调度器的key的计算是用当前的虚拟时钟减去待计算进程的等待时间,如果该计算进程在运行,那么其等待时间就是负值,这样,等待越长的进程key越小,从而越容易被选中投入运行;

在2.6.25内核以后实现了一种更为简单的方式,就是设置一个运行队列的虚拟时钟,它单调增长并且跟踪该队列的最小虚拟时钟的进程,key值由进程的vruntime和队列的虚拟时钟的差值计算,这种方式就是真正的追赶, 比2.6.23实现的简单,但是很巧妙,不必在每次时钟滴答中都将当前进程出队,入队,而是根据当前进程实际运行的时间和理想应该运行的时间判断是否应该调度。

参考资料

http://www.cnblogs.com/tianguiyu/articles/6091378.html
http://www.cnblogs.com/brucemengbm/p/6901980.html
http://www.360doc.com/content/15/0922/01/12144668_500602693.shtml


本文由【waitig】发表在等英博客
本文固定链接:Linux进程调度算法
欢迎关注本站官方公众号,每日都有干货分享!
等英博客官方公众号
点赞 (0)分享 (0)