《现代操作系统》读书笔记之——进程调度（二）

7.交互系统的调度算法

• 时间片轮转调度算法（Round-Robin Scheduling）

    时间片轮换调度算法是最古老、最简单、最公平并且使用最广泛的调度算法之一。每个进程被分配一段时间间隔，叫做时间片（quantum）。进程在这个时间间隔内允许运行，如果时间片用完了，那么CPU将会被抢占并且分给别的进程。如果在时间片结束之前，进程阻塞或者是结束了，那么CPU也会被分配给别的进程。调度器需要做的，就是要维护一个可运行程序的列表。如下图a所示。当一个进程的时间片结束了，那么这个进程会被放到这个列表的尾部，如图b所示。

对于这种调度算法来说，一个比较重要的议题是时间片的长度设置为多少比较合理。从一个进程切换到另外一个进程是需要花费一定的管理时间的，比如保存或者加载寄存器和内存映射，更新一系列的列表，刷新内存缓存等等，假设这部分时间花费1ms，而一个时间片是4ms，那么没进行4ms的时间计算之后还需要花1ms时间来进行进程切换，那么20%的CPU时间被浪费了。很显然，这种代价太高了。

    现在假设时间片是100ms，而同时又50个交互用户在终端前等待计算机的响应。假设他们几乎是同时输好命令，并且按下enter键，这样就形成了50个进程，并且调度器将这50个进程放进在一个就绪进程的列表里，然后第一个运行100ms，花1ms切换，以此类推，那么第50个用户就倒霉了，5m多之后才得到响应。

    另外一个问题是，假设时间片的时间设置得长于CPU突发事件（CPU burst），那么几乎不会出现抢占。而大部分进程在在时间片用完之前就发生阻塞，这样就又导致进程切换。

    总结一下这个问题就是四个字：过犹不及。时间片不能太长也不能太短，一般来说大概30~50ms就好。

• 优先级调度算法（Priority Scheduling）    

    前一种调度算法，默认是认为所有的进程具有相同的优先级。但是对于很多多用户的计算机的管理者并不这么认为。比如大学，社会等级可能是，校长第一，其次教授，再者秘书，再次是门卫，最后是学生。像这种，需要将外部因素考虑进来就导致了优先级调度。这种算法的基本思路是非常直接的：给每个进程赋予一个优先级，优先级最高的就绪进程才被挑选运行。

    即使只有一个用户的PC机，各种进程的优先级也是不同的。比如一个在后台发电子邮件的进程的优先级肯定地狱前台播放视频的播放器进程的优先级要低。

    为了阻止高优先级的进程一直运行下去，调度器需要在每个时钟中断的时候降低当前运行进程的优先级。如果这时候该进程的由优先级已经低于其他进程中优先级最高的进程，那么就会发生进程切换。另一种方法是，每个进程会被设置一个最长运行时间，如果超过这个时间，第二高优先级就会开始运行。

    进程的优先级可以静态设置或者动态的设置。在商业计算中心，高优先级的进程可能收费$100每小时，中等优先级$75每小时，而低优先级的$50每小时。很有趣的是，UNIX系统中有个nice命令，用户使用它来自愿让出自己的CPU时间，以便对他人更加友好，但是没人用这个命令。

    进程优先级有时候也会被动态的赋予来实现某些特定的系统目标。例如，对于I/O倾向的进程，只有它请求CPU就尽量满足他，然后让它开始下一个I/O请求，这样，在它进行I/O操作的时候就可以让其他的进程进行实际的计算。不然的话，I/O倾向的进程总是花时间在请求CPU，并且占着内存。一个简单的给I/O倾向的进程提供优质服务的算法是给它的优先级设置为1/f，其中f指的是这个进程在上一个时间片中实际使用时间与时间片长度的比例。假设时间片是50ms，这个进程上个周期使用了1ms，那么1/f=1/(1/50)=50。如果他使用了25ms，那么优先级1/f=1/(25/50)=2。

    通常来说，将相同优先级的进程组合到一组中，然后组间采用优先级调度算法，而组内采用时间片轮换算法。下图显示了一个四组优先级的系统：

其调度算法如下：只要优先级4中有可运行进程，则给每个进程运行一个时间片，不需担心低优先级组中的进程。如果优先级4这一组已经没进城的话，则开始运行进程组3，以此类推。

• 多级队列调度（Multiple Queues）    

    最早的优先级调度器出现在MIT的CTSS系统，是一个运行在IBM 7094机型上的分时系统。CTSS有个问题是，它的进程切换是很慢的，因为7094只能在内存中存储一个进程。每一次进程切换意味着将内存中的进程交换到硬盘，然后从硬盘中读取一个新的进入内存。于是CTSS系统的设计者很快反应过来，给CPU倾向的进程更长的时间片，这样减小交换。但是给所有进程更大的时间片意味着降低系统的响应时间，他们的解决方案就是设置优先级级别。最高级级别的进程运行一个时间片，次高级级别的进程运行两个时间片，再次高级

级别的进程运行四个时间片。当一个进程用完分配给他的时间片，那么它会被降低一个别中去。

    对于有些进程，开始运行了一段长时间，但是随后需要编程交互式的进程，那么可以采用下面的措施来防止它一直被惩罚：只要终端上有回车键（Enter键）按下，则属于该终端的所有进程就都被移到最高优先级。但是这样又会出现问题：假设一台机器上的某个用户发现了这个规律（只要没几秒敲一下回车，就可以大大提高响应时间），那么他很可能告诉所有的朋友。后果会怎样呢？所以说，理论上合理离实际上可行还有一段很长的距离。

    还有一些其他的算法用来给进程分配一定的优先级类别。比如，伯克利制造的比较有影响力的XDS940系统就有四个优先级类别：终端、I/O、短时间片和长时间片。当一个一直等待终端输入的进程最终被唤醒时，它被转到最高优先级类（终端）。当等待磁盘块数据的一个进程就绪时，将它转到第2类。当进程在时间片用完时仍为就绪时，它一般被放入第3类。但如果一个进程已经多次用完时间片而从未因终端或其他I/O原因阻塞，那么它将被转入最低优先级类。

• 最短进程优先（Shortest Process Next）    

    由于最短作业优先算法能够使平均最短响应时间降到最低，因此，如果这个算法在交互式系统中也能被应用的话也是很不错的。某种程度来说，确实是可以的。交互进程一般都遵守下面的模式：等待命令输入，执行命令，等待命令输入，执行命令......如果我们将每个需要执行的命令看作是一个"作业",那么可以通过优先选取最短的那个命令运行来降低平均响应时间。问题就在于怎么判定哪个进程是最短的呢。

    一种方法是根据以往的经验作出估计，然后挑选最短的那个。假设某个终端上每条命令的估计运行时间为T0。现在假设测量到其下一次运行时间为T1。可以用这两个值的加权和来改进估计时间，即aT0 + (1-a)T1。通过选择a的值，可以决定是尽快忘掉老的运行时间，还是在一段长时间内始终记住它们。当a = 1/2时，可以得到如下序列：

T0，T0/2 + T1/2，T0/4 + T1/4 + T2/2， T0/8 + T1/8 + T2/4 + T3/2。可以看到，在三轮过后，T0在新的估计值中所占的比重下降到1/8。有时把这种通过当前测量值和先前估计值进行加权平均而得到下一个估计值的技术称作老化（aging）。老化技术在很多需要根据以前的值进行预测的情况下都是适用的。当a取1/2时，老化技术非常好实现。这一点很显然。

• 保证性调度（Guaranteed Scheduling）    

    一种完全不同的调度算法是向用户作出明确的性能保证，然后去实现它。一种很实际并很容易实现的保证是：若用户工作时有n个用户登录，则用户将获得CPU处理能力的1/n。类似地，在一个有n个进程运行的单用户系统中，若所有的进程都等价，则每个进程将获得1/n的CPU时间。同样的道理，为了实现所做的保证，系统必须跟踪各个进程自创建以来已使用了多少CPU时间。然后它计算各个进程应获得的CPU时间，即自创建以来的时间除以n。由于各个进程实际获得的CPU时间是已知的，所以很容易计算出真正获得的CPU时间和应获得的CPU时间之比。比率为0.5说明一个进程只获得了应得时间的一半，而比率为2.0则说明它获得了应得时间的2倍。于是该算法随后转向比率最低的进程，直到该进程的比率超过它的最接近竞争者为止。

• 彩票调度（Lotterry Scheduling）    

    给用户一个保证，然后兑现之，这是个好想法，不过很难实现。但是，有一个既可给出类似预测结果而又有非常简单的实现方法的算法，这个算法称为彩票调度（lottery scheduling）。其基本思想是向进程提供各种系统资源（如CPU时间）的彩票。一旦需要做出一项调度决策时，就随机抽出一张彩票，拥有该彩票的进程获得该资源。在应用到CPU调度时，系统可以掌握每秒钟50次的一种彩票，作为奖励每个获奖者可以得到20ms的CPU时间。

    为了说明George Orwell关于“所有进程是平等的，但是某些进程更平等一些”的含义，可以给更重要的进程额外的彩票，以便增加它们获胜的机会。如果出售了100张彩票，而有一个进程持有其中的20张，那么在每一次抽奖中该进程就有20%的取胜机会。在较长的运行中，该进程会得到20%的CPU。相反，对于优先级调度程序，很难说明拥有优先级40究竟是什么意思，而这里的规则很清楚：拥有彩票f份额的进程大约得到系统资源的f 份额。

    彩票调度具有若干有趣的性质。例如，如果有一个新的进程出现并得到一些彩票，那么在下一次的抽奖中，该进程会有同它持有彩票数量成比例的机会赢得奖励。换句话说，彩票调度是反应迅速的。

    写作进程之间可以交换彩票。一个客户进程向服务器进程发送消息后就被阻塞，该客户进程可以把它所有的彩票交给服务器，以便增加该服务器下次运行的机会。在服务器运行完成之后，该服务器再把彩票还给客户机，这样客户机又可以运行了。事实上，如果没有客户机，服务器根本就不需要彩票。

    彩票调度可以用来解决用其他方法很难解决的问题。一个例子是，有一个视频服务器，在该视频服务器上若干进程正在向其客户提供视频流，每个视频流的帧速率都不相同。假设这些进程需要的帧速率分别是10、20和25帧/秒。如果给这些进程分别分配10、20和25张彩票，那么它们会自动地按照大致正确的比例（即10∶20∶25）划分CPU的使用。

• 平等分配调度（Fair-share Scheduling）    

    到现在为止，我们假设被调度的都是各个进程自身，并不关注其所有者是谁。这样做的结果是，如果用户1启动9个进程而用户2启动1个进程，使用轮转或相同优先级调度算法，那么用户1将得到90%的CPU时间，而用户2只得到10%的CPU时间。

    作为一个例子，考虑有两个用户的一个系统，每个用户都保证获得50% CPU时间。用户1有4个进程A、B、C和D，而用户2只有1个进程E。如果采用轮转调度，一个满足所有限制条件的可能序列是：

    A E B E C E D E A E B E C E D E …

    另一方面，如果用户1得到比用户2两倍的CPU时间，我们会有

    A B E C D E A B E C D E …

    当然，大量其他的可能也存在，可以进一步探讨，这取决于如何定义公平的含义。

8.实时系统的调度算法

    实时系统是一种时间起着主导作用的系统。典型地，外部的一种或多种物理设备给了计算机一个刺激，而计算机必须在一个确定的时间范围内恰当地做出反应。实时系统是一种时间起着主导作用的系统。典型地，外部的一种或多种物理设备给了计算机一个刺激，而计算机必须在一个确定的时间范围内恰当地做出反应。对于这种系统来说，正确的但是迟到的应答往往比没有还要糟糕。

    实时系统被分为硬实时系统和软实时系统。这两个概念是从对实时的要求力度。硬实时要求绝对满足截止时间要求，而软实时倒是可以偶尔不满足。两种情况下，实时是通过将问题分摊到很多进程上，并且每个进程的行为时可提前预测到的。这些进程往往存活时间很短，当一个外部事件被检测到时，调度器需要调度这些进程来满足所有的截止期要求。

    实时系统需要响应的事件可以分为周期性的与非周期性的。一个系统可能要响应多个周期性事件流。根据每个事件需要处理时间的长短，系统甚至有可能无法处理完所有的事件。例如，如果有m个周期事件，事件i以周期Pi 发生，并需要Ci秒CPU时间处理一个事件，那么可以处理负载的条件是

     满足这个条件的系统被称作可调度系统。作为一个例子，考虑一个有三个周期性事件的软实时系统，其周期分别是100ms、200ms和500ms。如果这些事件分别需要50ms、30ms和100 ms的CPU时间，那么该系统是可调度的，因为 0.5 + 0.15 + 0.2 < 1。如果有第四个事件加入，其周期为1秒，那么只要这个事件是不超过每事件150ms的CPU时间，那么该系统就仍然是可调度的。在这个计算中隐含了一个假设，即上下文切换的开销很小，可以忽略不计。

    实时系统的调度算法可以是静态或动态的。前者在系统开始运行之前作出调度决策；后者在运行过程中进行调度决策。只有在可以提前掌握所完成的工作以及必须满足的截止时间等全部信息时，静态调度才能工作。而动态调度算法不需要这些限制。