进程执行不断在两个状态：CPU执行、I/O等待之间进行交替，进程调度的目的是最大化CPU使用率。
基本概念
CPU执行时间分布
程序执行通常具有大量短CPU执行和少量长CPU执行。I/O密集型程序通常具有大量短CPU执行，CPU密集型程序可能只有少量长CPU执行。
调度的抢占
考虑四种发生CPU调度的情况：
- 一个进程从running切换到waiting（如I/O请求）
- 一个进程从running切换到ready（如中断）
- 一个进程从waiting切换到ready（如I/O完成）
- 一个进程终止
抢占的调度：调度可以发生在任一种情况下。可能导致数据竞争。
非抢占的调度：调度只发生在1和4情况下。一个进程一旦被分配了CPU，就会一直使用直到终止或者waiting。
调度准则
评判调度算法的好坏依据以下准则：
- CPU使用率
- 吞吐量：单位时间内完成的进程数量
- 周转时间：进程提交到进程完成的时间。(TT=finish-arrival)
- 等待时间：在就绪队列中所等时间。(WT=start-arrival=TT-burstTime)
- 响应时间：提交请求到产生第一响应的时间，更适合交互系统
下列是有关公式：
- 平均周转时间ATT：(sum (finishTime-arrivalTime)/N)
- 平均等待时间AWT：(sum(startTime-arrivalTime)/N)
- 平均响应时间ART：通常可以认为响应时间等于周转时间。响应时间多一个不长的提交时间。
调度算法
FCFS - 先到先服务
非抢占。先请求CPU的进程首先分配到CPU。
缺点：
- 平均等待时间往往很长
- 护航效应：可能出现所有其他进程都等待一个大进程释放CPU
- 不适合分时系统（每个用户需要定时得到一定CPU时间）
SJF - 最短作业优先
抢占或非抢占的。调度取决于进程的下次CPU执行的长度（而不是一成不变的初始长度）。
下图是非抢占的SJF的甘特图：
缺点：
- 难以预计下次CPU执行的长度，故只能预测逼近理想的SJF
- 通常用于长期调度
抢占的SJF
最短剩余时间优先，即先到先服务，后到比剩余。考虑不同的到达时间：
进行抢占式SJF的分析，关键是抓住Arrival Time作为关键时间节点。
优先级调度
抢占或非抢占的。为每个进程赋一个优先级，假设以低数字代表高优先级。
问题：
-
无穷阻塞（饥饿）：某个低优先级进程可能无穷等待CPU
解决：老化。逐渐增加等待很长时间进程的优先级
RR - 轮转调度
抢占的。定义时间片概念。每次，循环整个就绪队列，对每个进程分配不超过一个时间片的CPU。如果进程耗时少于一片，提前释放，提前进行下次分配；如果进程耗时达到一片，就强制中断执行。
特点：
- 平均等待时间较长
- 性能与时间片大小有关，时间片应远大于上下文切换时间
- 时间片也不能太大，否则可能退化为FCFS
多级队列调度
按照进程的类型与特点各自分配到多种不同的队列，每个队列有自己的调度算法，队列之间也有调度（通常采用固定优先级抢占调度）。
多级反馈队列调度
多级队列调度中某个进程会被永久地分配到某个队列，不够灵活。多级反馈队列允许进程在队列间转移。
例如上图，先进行8时间RR调度，未完成的进入16时间RR调度，再未完成的进入FCFS调度。只有上面的队列为空时，下面的队列才能得到执行。
需要确认下列参数：
- 队列数量
- 每个队列的调度算法
- 确定何时升级任务
- 确定何时降级任务
- 进程需要服务时先进入哪个队列
线程调度
某些操作系统支持更细粒度的线程调度而不仅是进程调度。
两种竞争范围
- 进程竞争范围PCS：线程库将用户线程调度到可用LWP，通常采用优先级调度
- 系统竞争范围SCS：决定哪个内核级线程调度到一个处理器上
多处理器调度
调度方法
- 非对称多处理：让一个处理器处理所有调度决定、IO以及其他系统活动，其他处理器只执行用户代码
- 对称多处理SMP：每个处理器自我调度
处理器的亲和性
大多数SMP系统试图避免将进程从一个处理器移到另一个处理器（保持进程运行在同一处理器），这种情况称为软亲和性。
有的操作系统提供硬亲和性，允许某个进程运行在某个处理器子集上。
亲和性与负载均衡通常是矛盾的。
多处理器多线程
操作系统决定哪个软件线程到哪个硬件线程（逻辑处理器）上运行，并指定每个核如何决定运行哪个硬件线程
实时CPU调度
实时操作系统的CPU调度。当一个实时进程需要CPU时，立即响应。
最小化延迟
两种延迟影响性能：
- 中断延迟：CPU收到中断到中断处理程序开始的时间
- 调度延迟：停止一个进程到启动另一个进程所需的时间
被调度进程的性质
讨论各种调度程序之前，首先说明：
- 这些进程是周期性的，也就是它们定期需要CPU
- 这些进程有三个属性：处理时间t、截止期d、周期p，满足0≤t≤d≤p
- 操作系统需要在截止期前处理完该进程，否则应拒绝服务
调度方法
优先级调度
根据进程的重要性分配优先级，并且可以支持抢占。重要性可以用进程的三个属性来衡量。
单调速率调度
抢占式，静态优先级。
- 每个任务被分配一个优先级，与周期成反比
- 如果一组进程不能由该算法调度，则也不能由其他静态优先级算法调度
最早截止期限优先调度（EDF）
抢占式。截止期限越早，优先级越高。
进程优先级是变化的，不要求进程周期性，也不要求CPU执行时间固定，但需要进程宣布它的截止期。
更适合实际应用的实时调度。
比例分享调度
在所有程序之间分配T股，一个应用分到N股，则确保有N/T的处理器时间。
操作系统实例
-
Linux：完全公平调度程序CFS
每个任务分配的CPU时间根据友好值计算，友好值越高，分配时间越少。
-
Windows：基于优先级、抢占式
-
Solaris：基于优先级，线程有6类，每个类型有不同优先级和调度算法
算法评估
-
确定性模型：特定的预先确定的载荷下进行分析
-
排队模型：根据进程到达系统的时间分布计算数学期望
Little公式：n=λW
- 如果系统处于稳定状态，那么离开队列的进程数等于到达进程数
- n：平均队列长度；λ：进程平均到达率；W：进程等待时间
-
仿真
-
实现