《现代操作系统》—— 调度

前言

现代计算机都是多道程序设计系统。在多道程序设计系统中，通常会有多个进程或线程同时竞争同一个CPU。只要有2个或更多的进程处于就绪状态，那么这种情形就发生了：CPU必须要在多个就绪的进程中选择下一个要运行的程序。在操作系统中，完成这个选择工作的程序叫做调度程序（scheduler）。该程序使用的算法叫做调度算法。 许多适用于进程调度的方法同样也适用于线程调度。内核管理线程的时候，调度是按照线程级别进行的，与线程所属的进程没有关联。本文主要讨论同样适用于进程和线程调度的问题。然后介绍线程调度所独有的问题。本文讨论的问题假设机器是单CPU单核。

调度时机

1. 在创建一个新进程时。需要决定是运行父进程还是子进程。由于父进程和子进程都处于就绪状态，所以调度程序可以根据实际情况决策调度哪个进程。
2. 在一个进程退出时。需要从就绪的进程中选择一个进程。
3. 在一个进程阻塞在I/O、信号量或其他原因导致阻塞时。需要选择一个就绪的进程。
4. 在一个I/O中断发生时。如果中断来自于I/O设备，而设备现在完成了工作，某些被阻塞的等待I/O的进程就成为了可运行的就绪的进程。当然是否让期运行取决于调度程序。

调度算法分类

不同的应用领域有不同的目标，也就需要不同的操作系统。所以，不同的操作系统，需要有不同的调度算法。常见的操作系统分为3类：

• 批处理系统
  • 批处理系统是弱交互的。通常是在后台、批量的、集中式的完成一批任务。不会有用户在终端旁等待一个短请求的及时响应。所以，非抢占式算法适用于批处理系统。
• 交互式系统
  • 在交互式用户环境中，为了避免一个进程长时间霸占CPU、避免一个程序因为错误而排斥其他进程，也为了能够及时响应用户的高优先级的交互，抢占是必须的。所以，抢占式算法适用于交互式系统。
  • 服务器也属于交互式系统，因为他们要经常服务于多个突发的（远程）用户。
• 实时系统
  • 实时系统中，抢占有时是不需要的。因为进程了解他们可能长时间得不到运行，所以会很快的完成个字的工作并阻塞。

调度算法目标

说是调度算法的目标，其实也是衡量调度算法的指标。下面将介绍一些适合于所有系统的通用指标，然后再介绍衡量不同类型系统调度算法的指标。

通用目标

调度算法的好坏取决于目标系统，所以需要对不同类型的应用不同的调度算法。但仍有一些目标适用于所有系统，包括：

• 公平性。给每个进程公平的CPU份额。相似的进程应该得到相似的服务。对一类等价的进程中，某些进程获得的服务多，某些进程获得的服务少，这是不公平的。
• 策略强制执行。保证策略能够被执行，策略要凌驾于进程之上，就像法律凌驾于个人之上。保证策略的执行就像是保证法律的执行。不能有漏网之鱼。
• 平衡性。保持系统的各个部分尽可能忙碌。如果CPU和I/O设备时刻都能运行，那么相对于某些设备空转，前者能完成更多的工作。

批处理系统目标

• 吞吐量。系统每小时完成任务的数量。
• 周转时间。一个批处理作业提交到完成的时间。该时间反映了用户等待时间，时间越小越好。
• CPU利用率。虽然被应用与批处理系统的度量。但不是一个好的度量指标。真正有价值的是系统每小时完成多少作业（吞吐量）以及完成作业所需的时间（周转时间）。

交互式系统目标

• 响应时间。交互式系统对某些用户行为的响应时间是有要求的，这也是采用抢占式算法的原因之一。
• 均衡性。

实时系统目标

• 满足截止时间
• 可预测性

调度算法

批处理系统中的调度

1. 先来先服务
2. 最短作业优先
3. 最短剩余时间优先

交互式系统中的调度

1. 轮转调度
2. 优先级调度
3. 多级队列
4. 最短进程优先
5. 保证调度
6. 彩票调度
7. 公平分享调度

实时系统中的调度

• 实时系统是一种时间起着主导作用的系统。他们的特点是：要求系统在恰当的时间内做出响应。对时间都都敏感的，正确的但是迟到的应答往往比没有响应更糟糕。比如，医院特别护理部门的病人监护装置、飞机中的自动驾驶系统、自动化工厂中的机器人控制系统等。
• 实时系统调度算法分为静态和动态。静态调度算法在系统开始运行之前做出决策。动态调度算法在运行过程中进行调度决策。静态调度算法要求事先掌握所完成的工作和必须满足的截止时间等所有必要信息时，才能工作，动态调度算法没有这个要求。

策略和机制

采用调度机制和调度策略分离的原则。将调度算法以某种形式参数化，参数可以由用户进程填写。

线程调度

线程分为用户级线程和内核级线程。 用户级线程场景下，当进程获得CPU的时间片时，由进程内的线程调度程序决定把时间片分给哪个线程。直到该进程被挂起。用户级场景下，运行时系统使用的调度算法通常是轮转调度和优先级调度。唯一的缺陷是缺乏一个时钟中断运行过长的线程，但由于用户级线程之间是合作关系，这种影响通常也不是问题。 内核级线程的场景下，内核选择一个线程，内核级线程是脱离用户级的，内核不会考虑这个线程属于哪个进程。当然如果有必要，内核也做得到。内核对被选中的线程赋予一个时间片，超过时间片则线程被挂起。

用户级线程和内核级线程的差别在于性能。用户级线程的切换只需要少量的机器指令。而内核级线程需要完整的上下文切换，修改内存映射，使高速缓存失效，这导致了若干数量及的延迟。这也就是说，从进程A的一个线程A1切换到进程B的一个线程B1，其代价高于切换到进程A的线程A2。 用户级线程可以使用专为应用程序定制的线程调度程序，这能比内核更好的满足应用程序的需要。