集团新闻

    进程调度算法

    FCFS

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

    SJF

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

    HRRN

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

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

    RR

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

    Linux进程调度的目标

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

    O(1)调度算法

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

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

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

    普通进程的动态优先级的范围是100139,实时进程的动态优先级的范围是099

    时间片的计算

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

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

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

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

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

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

    进程调度

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

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

    CFS调度算法

    CFS的核心思想

    全公平调度器(CFS)的设计思想是:在一个真实的硬件上模型化一个理想的、精确的多任务CPU。该理想CPU模型运行在100%的负荷、在精确 平等速度下并行运行每个任务,每个任务运行在1/n速度下,即理想CPUn个任务运行,每个任务的速度为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)指的是插入时间,可是红黑树的统计性能是不错的,没有多大概率真的用得了那么多时间,因为红节点和黑节点的特殊排列方式既保证了树的一定程度的平衡,又不至于花太多的时间来维持这种平衡,插入操作大多数情况下都可以很快的完成,特别是对于组织得相当好的数据。