CPU调度
基本概念
CPU调度在讨论普通调度概念时使用进程调度，特别指定为线程概念时使用线程调度
CPU-I/O区间
CPU的成功调度依赖于进程的如下属性：进程执行由CPU执行和I/O等待周期组成。进程在这两个状态之间切换。进程执行从CPU区间开始，在这之后是I/O区间，接着是另一个CPU区间，然后是另一个I/O区间，如此进行下去。最终，最后的CPU区间通过系统请求终止执行。
CPU调度程序
每当CPU空闲时，操作系统就必须从就绪队列中选择一个进程来执行。进程的选择由短期调度程序或者叫CPU调度程序执行。调度程序从内存中选择一个能够执行的进程，并为之分配CPU。
就绪队列不必是先进先出（FIFO）队列。正如研究各种调度算法时将看到的，就绪队列可实现为FIFO队列，优先队列，树或简单无序链表。队列中的记录通常为进程控制块（PCB）。
抢占调度
CPU调度决策可在如下四种环境下发生：
- 当一个进程从运行状态切换到等待状态
- 当一个进程从运行状态切换到就绪状态
- 当一个进程从等待状态切换到就绪状态
- 当一个进程终止时。
对于第1和第4两种情况，没有选择而只有调度。一个新进程（如果就绪队列中已有一个进程存在）必须被选择执行。不过，对于第2和第3两种情况，可以进行选择。
当调度只能发生在第1和第4两种情况下时，称调度方案是非抢占的或协作的；否则，称调度方案是抢占的。采用非抢占调度，一旦CPU分配给一个进程，那么该进程会一直使用CPU，直到进程终止或切换到等待状态。
分派程序
分派程序是一个模块，用来将CPU的控制权交给由短期调度程序选择的进程。其功能包括：
- 切换上下文
- 切换到用户模式
- 跳转到用户程序的合适位置，以重新启动程序
调度准则
为了比较CPU调度算法，分析员提出了许多准则，用于比较的特征对确定最佳算法有很大影响。这些准则如下:
- CPU利用率：需要使CPU尽可能忙
- 吞吐量：它指一个时间单元内所完成进程的数量。
- 周转时间：从进程提交到进程完成的时间段称为周转时间。
- 等待时间：等待时间为在就绪队列中等待所花时间之和。
- 响应时间：从提交请求到产生第一响应的时间
需要使CPU使用率和吞吐量最大化，而使周转时间，等待时间和响应时间最小化。
调度算法
CPU调度处理是从就绪队列中选择进程并为之分配CPU时间的问题。有多种不同的CPU调度算法：
先到先服务调度
显然，最简单的CPU调度算法时先到先服务调度算法。采用这种方案，先请求CPU的进程先分配到CPU。
用FIFO队列可以很容易实现FCFS策略。
不过，采用FCFS策略的平均等待时间通常较长。
FCFS调度算法是非抢占的。一旦CPU被分配给了一个进程，该进程就会保持CPU直到释放CPU为止。
最短作业优先调度
另一个CPU调度算法是最短作业优先调度算法（SJF）。这一算法将每个进程与其下一个CPU区间段相关联。
当CPU空闲时，它会赋给具有最短CPU区间的进程。如果两个进程具有同样长度，那么可以使用FCFS调度来处理。
注意，一个更为恰当的表示是下一个最短CPU区间的算法，这是因为调度程序检查进程的下一个CPU区间的长度，而不是其总长度。
SJF调度算法可证明为最优算法，这是因为对于给定的一组进程，SJF算法的平均等待时间最短。
虽然SJF算法最优，但是它不能再短期CPU调度层次上加以实现，因为没有办法知道下一个CPU区间的长度。
一种方法是近似SJF调度，虽然不知道下一个CPU区间的长度，但是可以预测它的值。认为下一个CPU区间的长度与以前的相似。
下一个CPU区间通常可以预测为以前CPU区间的测量长度的指数平均。
SJF算法可能是抢占的或非抢占的。当一个新进程到达就绪队列而以前进程正在执行时，就需要选择。新进程可能有一个更短的CPU区间，抢占SJF算法可抢占当前运行的进程，而非抢占SJF算法会允许当前运行的进程先完成其CPU区间。抢占SJF调度有时称为最短剩余时间优先调度。
优先级调度
SJF算法可作为通用优先级调度算法的一个特例。每个进程都有一个优先级与其关联，具有最高优先级的进程会分配到CPU。具有相同优先级的进程按FCFS顺序调度。
优先调度可以是抢占的或者非抢占的。
优先级调度算法的一个主要问题是无穷阻塞，或饥饿。可以运行但缺乏CPU的进程可以认为是阻塞的。优先级调度算法会使某个低优先级进程无穷等待CPU。
低优先级进程无穷等待问题的解决之一是老化。老化是一种技术，以逐渐增加在系统中等待很长时间的进程的优先级。
轮转调度
轮转调度算法时专门为分时系统设计的。它类似于FCFS调度，但是增加了抢占以切换进程。定义一个较小的时间单元，称为时间片。调度程序为每个进程分配不超过一个时间片的CPU。
为了实现轮转调度，将就绪队列保存为进出的FIFO队列。新进程增加到就绪队列的尾部。CPU调度程序从就绪队列中选择第一个进程，设置定时器在一个时间片之后中断，再分派该进程。
接下来将可能发生两种情况之一：进程可能只需要小于时间片的CPU区间。对于这种情况，进程本身会自动释放CPU。调度程序接着处理就绪队列的下一个进程。否则，如果当前运行进程的CPU区间比时间片要长，定时器会中断并产生操作系统中断，然后进行上下午切换，将进程加入到就绪队列的尾部。接着CPU调度程序会选择就绪队列中的下一个进程。
不过，采用轮转调度策略的平均等待时间通常较长。
轮转调度算法是可抢占的。
多级队列调度
在进程可以容易地分成不同组的情况下，可以建立另一类调度算法。例如，一个常用的划分方法是前台（交互）进程和后台（批处理）进程。
多级队列调度算法将就绪队列分成多个独立队列。根据进程的属性，如内存大小，进程优先级，进程类型，一个进程被永久地分配到一个队列。每个队列都有自己的调度算法。例如：前台进程队列可能采用轮转算法调度，而后台队列可能采用FCFS算法调度。
另外，队列之间必须有调度，通常采用固定优先级抢占调度。例如，前台队列可以比后台队列具有绝对的优先级。
每个队列与较低层队列相比有绝对的优先级。
多级反馈队列调度
通常在使用多级队列调度算法时，进程进入系统时被永久地分配到一个队列。例如：如果前台进程和后台进程分别有独立队列，进程并不从一个队列转移到另一个队列。这种设置的优点是调度开销较低，缺点是不够灵活。
与之相反，多级反馈队列调度算法允许进程在队列之间移动。如果进程使用过多CPU时间，那么它会被转移到更低优先级队列。此外，在较低优先级队列中等待时间过长的进程会被转移到更高优先级队列。这种形式的老化阻止饥饿的发生。
如上图，它有三个队列：0~2。调度程序首先执行队列0内的所有进程。只有当队列0为空时，它才能执行队列1内的进程。类似的，只有队列0和1都为空时，队列2的进程才能执行。到达队列1的进程会抢占队列2的进程。同意，到达队列0的进程会抢占队列1的进程。
进入就绪队列的进程被放入队列0中。队列0中的每个进程都有8ms的时间片。如果一个进程不能在这一时间内完成，那么它就会被转移到队列1的尾部。如果队列0为空，队列1头部的进程会得到一个16ms的时间片。如果它不能完成，那么将被抢占，并被放入队列2中。只有当队列0和1为空时，队列2中的进程才可根据FCFS来执行。
通常，多级反馈队列调度程序可以由下列参数来定义：
- 队列数量
- 每个队列的调度算法
- 用以确定何时升级到更高优先级队列的方法。
- 用以确定何时降级到更低优先级队列的方法
- 用以确定进程在需要服务时应进入哪个队列的方法。
多级队列调度程序的定义使它成为最通用的CPU调度算法。它可以被配置以适应特定系统设计。然而，它也是最复杂的算法。
线程调度
用户级线程与内核级线程的区别之一在于它们被调度的方法。
在执行多对一和多对多模型的系统上，线程库调度用户级线程到一个有效的LWP上运行。这种方法被称为进程竞争范围（PCS），因为CPU竞争发生在属于相同进程的线程之间。
当提及线程库调度用户线程到有效的LWP时，并不意味着线程实际上就在CPU上运行，这需要操作系统将内核线程调度到物理CPU上。
为了决定调度哪个内核线程到CPU，内核采用系统竞争范围（SCS）方法来进行。采用SCS调度方法，竞争CPU发生在系统的所有线程中，采用一对一的模型的系统，调度仅使用SCS方法。
