调度 ​

当计算机系统是多道程序设计系统时，通常就会有多个进程或线程同时竞争 CPU。只要有两个或更多的进程处于就绪状态，这种情形就会发生。如果只有一个 CPU 可用，那么就必须选择下一个要运行的进程。在操作系统中，完成选择工作的这一部分称为调度程序，该程序使用的算法称为调度算法。

何时调度 ​

1. 在创建一个新进程之后，需要决定是运行父进程还是运行子进程。

2. 在一个进程退出时必须做出调度决策。

3. 当一个进程阻塞在 I/O 和信号量上或由于其他原因阻塞时，必须选择另一个进程运行。

4. 第四，在一个 I/O 中断发生时，必须做出调度决策。

调度算法分类 ​

1. 批处理。
2. 交互式。
3. 实时。

调度算法的目标 ​

为了设计调度算法，有必要考虑什么是一个好的调度算法。某些目标取决于环境（批处理、交互式或实时），但是还有一些目标是适用于所有情形的。

批处理系统中的调度 ​

（1）先来先服务 ​

在所有调度算法中，最简单的是非抢占式的先来先服务算法。使用该算法，进程按照它们请求 CPU 的顺序使用 CPU 。

优点：

这个算法的主要优点是易于理解并且便于在程序中运用。

缺点：

平均等待时间过长。

（2）最短作业优先 ​

当输入队列中有若干个同等重要的作业被启动时，调度程序应使用最短作业优先算法。

只有在所有的作业都可同时运行的情形下，最短作业优先算法才是最优化的。

（3）最短剩余时间优先 ​

最短作业优先的抢占式版本是最短剩余时间优先算法。使用这个算法，调度程序总是选择剩余运行时间最短的那个进程运行。

交互式系统中的调度 ​

（1）轮转调度

一种最古老、最简单、最公平且使用最广的算法是轮转调度。每个进程被分配一个时间段，称为时间片，即允许该进程在该时间段中运行。如果在时间片结束时该进程还在运行，则将剥夺 CPU 并分配给另一个进程。如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换。

需要注意的是，时间片设得太短会导致过多的进程切换，降低了 CPU 效率；而设得太长又可能引起对短的交互请求的响应时间变长。将时间片设为 20ms ～ 50 ms 通常是一个比较合理的折中。

（2）优先级调度

每个进程被赋予一个优先级，允许优先级最高的可运行进程先运行。为了防止高优先级进程无休止地运行下去，调度程序可以在每个时钟滴答（即每个时钟中断）降低当前进程的优先级。如果这个动作导致该进程的优先级低于次高优先级的进程，则进行进程切换。

（3）多级队列

将一组进程按优先级分成若干类，并且在各类之间采用优先级调度，而在各类进程的内部采用其他调度方式。

（4）最短进程优先

对于批处理系统而言，由于最短作业优先常常伴随着最短响应时间，所以如果能够把它用于交互进程，那将是非常好的。

（5）保证调度

向用户作出明确的性能保证，然后去实现它。

一种很实际并很容易实现的保证是：若用户工作时有 n 个用户登录，则用户将获得 CPU 处理能力的 1/n 。类似地，在一个有 n 个进程运行的单用户系统中，若所有的进程都等价，则每个进程将获得 1/n 的 CPU 时间。看上去足够公平了。

（6）彩票调度

向进程提供各种系统资源（如 CPU 时间）的彩票。一旦需要做出一项调度决策时，就随机抽出一张彩票，拥有该彩票的进程获得该资源。在应用到 CPU 调度时，系统可以掌握每秒钟 50 次的一种彩票，作为奖励每个获奖者可以得到 20 ms 的 CPU 时间。

（7）公平分享调度

到现在为止，我们假设被调度的都是各个进程自身，并不关注其所有者是谁。

为了避免这种情形，某些系统在调度处理之前考虑谁拥有进程这一因素。在这种模式中，每个用户分配到 CPU 时间的一部分，而调度程序以一种强制的方式选择进程。这样，如果两个用户都得到获得 50% CPU 时间的保证，那么无论一个用户有多少进程存在，每个用户都会得到应有的 CPU 份额。

策略和机制 ​

我们讨论的调度算法中没有一个算法从用户进程接收有关的调度决策信息，这就导致了调度程序很少能够做出最优的选择。

解决问题的方法是将调度机制与调度策略分离，也就是将调度算法以某种形式参数化，而参数可以由用户进程填写。

在这里，调度机制位于内核，而调度策略则由用户进程决定。