CPU调度是多道程序操作系统的基础。通过在进程之间切换CPU，操作系统可以提高计算机的吞吐率。
Basic Concepts
Maximum CPU utilization obtained with multiprogramming:
对于单处理器系统，每次只允许一个进程运行；任何其他进程必须等待，直到CPU空闲能被调度位置。多道程序的目标是在任何时候都有某些进程在运行（通过利用等待某些I/O请求的时间），使CPU使用率最大化。
CPU-I/O区间周期：
进程执行由CPU执行和I/O等待周期组成。进程在这两个状态之间切换。进程执行从CPU区间（CPU burst)开始，在这之后是I/O区间（I/O burst），接着是另一个CPU区间，然后是另一个I/O区间，如此进行下去。最终，最后的CPU区间通过系统请求终止执行。
CPU区间时间曲线：
该曲线通常为指数或超指数形式，具有大量短CPU区间和少量长CPU区间。
CPU Scheduler（CPU 调度器）
每当CPU空闲时，操作系统就必须从就绪队列中选择一个进程来执行。进程选择由短期调度程序执行。
CPU调度决策发生的时间：
- 进程从运行到等待的切换
- 进程从运行到就绪的切换
- 进程从等待到就绪的切换
- 进程终止
对于第一种和第四种情况，没有选择只有调度。一个新进程(如果存在)必须被执行，此时是从就绪队列中调度出来执行。不过，对于第二种和第三种情况，可以进行选择。
所谓的选择就是选择一个就绪队列中的进程来执行。当调度只能发生在第一和第四种情况下时，称调度方案是非抢占的(nonpreemptive)的或协作的(cooperative)；否则，称调度方案是抢占的(preemptive)。
非抢占式调度，一旦CPU分配给一个进程，那么该进程会一致使用CPU直到进程终止或切换到等待状态。抢占调度对于访问共享数据是有代价的。需要同步机制来解决；对于操作系统内核的设计也有影响。
Dispatch(分派器)
分派器将CPU的控制权交给短期调度程序选中的进程;包括：
- 上下文切换
- 用户模式切换
- 跳转到用户程序的适当的位置重启程序（中断重新启动）
分派器停止一个进程而启动另一个所要花的时间称为分派延迟(dispatch latency)
Scheduling Criteria(调度准则)
- CPU utilization - keep the CPU as busy as possible
- Throughput(吞吐量) - of processes that complete their execution per time unit.
- Turnaround time(轮转时间) - Turnaround time is the sum of the periods spent waiting to get into memory, waiting in the ready queue, executing on the CPU, and doing I/O.
- Waiting time - amount of time a process has been waiting in the ready queue.
- Response time - amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment).
Scheduling Algorithms(调度算法)
- First-Come,First-Served(FCFS)Scheduling:先请求CPU的进程先分配到CPU。可以使用FIFO队列来实现。不过进程等待时间通常较长。可能会出现护航效果(convoy effect)，导致CPU和设备的使用率变得很低
- Shortest-Job-First(SJF)Scheduling:将每个进程与其下一个CPU区间段相关联。当CPU空闲时，会将CPU分配给具有最短CPU区间的进程。SJF是理想的情况，因为无法测定每个进程运行所需的CPU时间，但可以作为上限。
- Shortest-Remaining-Time-First(SRTF):抢占式的，将CPU分配给当前执行剩余时间最少的进程。
- Determining Length of Next CPU Burst:认为下一个CPU区间的长度与之前的相似，通过计算下一个CPU区间长度的近似值，能选择具有最短预测CPU区间的进程来运行。通常可预测为以前CPU区间的测量长度的指数平均。
- Priority Scheduling:每个进程都有一个优先级与其关联，具有最高优先级的进程会分配到CPU。具有相同优先级的进程按FCFS顺序调度。优先级算法的一个主要问题是无穷阻塞(indefinite blocking)或饥饿(starvation)。解决方法之一是老化(aging)，即逐渐增加在系统中等待很长时间的进程的优先级。
- Round Robin(RR):定义一个较小时间单元(时间片),当时间片走完之后，进程会被抢占同时被加入到就绪队列的末端。如果时间片很大，RR与FCFS类似，如果时间片很小，那么大部分时间浪费在上下文切换。根据经验，80%的CPU区间应该小于时间片，即大部分的进程在一个时间片内可以完成。通常，RR的平均轮转时间高于SJF，但响应时间低于SJF。
- Multilevel Queue:将就绪队列分成多个独立队列。根据进程的属性，如内存大小、进程优先级、进程类型，一个进程被永久地分配到一个队列。每个队列有自己的调度算法。进程进入系统后永久地被分配到一个队列。优点是低调度开销，缺点是不够灵活。
- Multilevel Feedback Queue:允许进程在队列之间移动。根据不同CPU区间的特点区分进程。如果进程使用过多CPU时间，就被转移到更低优先级队列。在较低优先级队列等待时间过长的进程会被转移到更高优先级队列。这种老化可以阻止饥饿发生。
Multiple-Processor Scheduling(多处理器调度)(非重点)
