第5章 CPU调度
5.1 基本概念
5.1.1 CPU-I/O区间周期
CPU burst -> I/O burst -> CPU burst -> I/O burst -> …
5.1.2 CPU调度程序（CPU Scheduler）
进程在就绪队列（有多种队列）中等待执行，短期调度程序或CPU调度程序选一个能运行的进程分配CPU
CPU调度决策可能在进程的以下情况中发生：
- 从运行到等待状态
- 从运行到就绪状态
- 从等待到就绪状态
- 终止
1、4： 非抢占式的（nonpreemptive）
2、3：抢占式的（preemptive）
5.1.3 抢占调度（Preemptive Scheduling）
采用非抢占调度，一旦CPU分配给一个进程，那么进程会一直使用CPU直到进程终止或切换到等待状态
抢占的代价：被抢后数据可能不一致
5.1.4 分派程序（Dispatcher）
分派程序模块通过短期调度程序把CPU的控制权交给选中的进程，这包括：
- 切换上下文
- 切换到用户模式
- 跳转到用户程序的合适位置，以重新启动程序
要点：尽可能快（因为每次切换都要用）
分派延迟（dispatcher latency）：停止一个进程并且启动另一个进程所花的时间（切换进程时花的时间）
5.2 调度准则（Scheduling Criteria）
- CPU使用率（CPU Utilization）
- 吞吐量（Throughput）：单位时间内完成进程的数量
- 周转时间（Turnaround Time）：从进程提交到完成的时间
- 等待时间（Waiting Time）：在就绪队列中等待所花费时间之和
- 等待时间 = 周转时间 - 执行该线程的时间
- 响应时间（Response Time）：从提交请求到第一次响应的时间
5.3 调度算法
5.3.1 先到先服务调度（FCFS: First-Come, First-Served）
进程到达的先后顺序对结果影响很大；可能让短进程等很久
FCFS是非抢占的
护送效应（convoy effect）：在长进程后到来的短进程得陪着它运行完
5.3.2 最短作业优先调度（SJF: Shortest-Job-First）
是最优调度算法（optimal）
但困难在于不知道下一个CPU区间的长度，所以经常用于长期调度
下一个CPU区间常预测为以前CPU区间的测量长度的指数平均： \(\tau_{n+1} = \alpha t_n + (1-\alpha) \tau_n, 0\leq \alpha \leq 1\) 其中$t_n$是第$n$个CPU区间的长度，$\tau_{n+1}$是下一个CPU区间的预测值，参数$\alpha$控制了最近和过去历史在预测中的相对加权（常取$\alpha=0.5$）。
进一步理解“指数”平均： \(\tau_{n+1}=\alpha t_n+(1-\alpha)\alpha t_{n-1}+...+(1-\alpha)^j \alpha t_{n-j}+...+(1-\alpha)^{n+1} \tau_0\) SJF可抢占可非抢占
抢占SJF调度有时称为最短剩余时间优先调度
5.3.3 优先级调度（Priority Scheduling Algorithm）
SJF是优先级调度的特例（优先级：下一个CPU区间的倒数）
优先级调度可抢占可非抢占
缺点：无穷阻塞/饥饿（starvation），即优先级低的进程无穷等待CPU
解决方法：老化（aging），即逐渐增加等了很久的进程的优先级
5.3.4 轮转法调度（RR: Round-Robin）
常用于分时系统
进程在时间片结束前结束，自动释放CPU；否则到时间就next one
时间片太小 -> 处理器共享
时间片太大 -> FCFS
5.3.5 多级队列调度（Multilevel Queue Scheduling Algorithm）
进程被永久分配到某个队列
可以规定队列之间有绝对的优先级（前一个空了才能动后一个），也可以为每个队列划分时间片。
5.3.6 多级反馈队列调度（Multilevel Feedback Queue Scheduling Algorithm）
与多级队列调度不同，多级反馈队列调度允许进程在队列之间移动。
等太久的进程可以转到高优先级的队列（防止老化aging）
用太多CPU时间的进程可以转到低优先级的队列
通常，多级反馈队列调度程序可由下列参数来定义：
- 队列数量
- 每个队列的调度算法
- 升级的方法
- 降级的方法
- 一开始先进哪个队列的方法
多级反馈队列调度是现在最通用的CPU调度算法，也是最复杂的算法
5.4 多处理器调度
5.4.1 多处理器调度的方法
- 非对称多处理（简单）：用一个处理器来调度，减轻了数据共享的需要
- 对称多处理SMP（复杂）：每个处理器自我调度
以下讨论主要都是关于SMP的
5.4.2 处理器亲和性（Processor Affinity）
处理器亲和性：SMP系统试图避免进程从一个处理器移到另一个处理器（否则前一个的缓存全都失效了）
软亲和性（soft affinity）：尽量，但不能保证一定
硬亲和性（hard affinity）：绝对不可以
5.4.3 负载平衡
设法将工作负载平均地分配到SMP系统上的所有处理器
注意：在具有共同队列的系统中，通常不需要负载平衡（因为一旦处理器空闲它就会立刻从队列中取走一个可执行进程）
负载平衡的方法：
-
Push Migration
周期性检查每个处理器上的负载，若不平衡，则把进程从超载的处理器移到空闲的处理器
-
Pull Migration
空闲处理器从忙处理器收到等待任务
pull和push不能相互排斥，且常被并行执行
负载平衡和亲和性有点矛盾
5.4.4 对称多线程
对称多线程SMT（Intel叫超线程技术）：在同一个物理处理器上生成多个逻辑处理器，每个逻辑处理器都有自己的架构状态（包括通用目的和机器状态寄存器）
SMT是硬件而不是软件提供的！！！但是如果OS能意识到SMT，对性能可以有提升
5.5 线程调度
区别用户级和内核级线程
在大多数现代OS中，OS调度的是内核级线程而不是进程。
用户线程必须映射到内核线程，这可能通过LWP来实现（轻量级进程Light-Weighted Process）。
5.5.1 竞争范围（Contention Scope）
- 进程竞争范围（PCS: Process-Contension Scope）方法：在多对一/多对多模型中，线程库调度用户级线程到一个有效的LWP上（CPU竞争发生在属于相同进程的线程之间）
- 典型地，PCS根据优先级完成
- 系统竞争范围（SCS: System-Contension Scope）方法：为了调度哪个内核线程到CPU（CPU竞争发生在系统的所有线程中）；在一对一模型的系统中，调度仅使用SCS
5.5.2 Pthread调度
Pthread库提供PCS和SCS支持
5.6 实时CPU调度：
- 软实时系统（soft real-time systems）：关键实时任务具有最高优先级，但不能保证何时安排任务
- 硬实时系统（hard real-time systems）：必须在截止日期之前完成任务
5.6.1 最小化延迟
事件延迟（event latency）：从事件发生到事件被服务之间的时间
两种延迟会影响性能：
- 中断延迟（interrupt latency）：从中断到达到开始执行中断程序的时间
- 分派延迟（dispatch latency）：调度器从CPU里把现在的进程撤下并换上另一个的时间
5.6.2 基于优先级的调度
对于实时调度来说，调度器必须支持抢占式的、基于优先级的调度。（但只保证软实时）
对于硬实时必须还要提供赶ddl的能力
进程有新的特性：周期性进程需要在固定区间内占用CPU
5.6.3 单调速率调度（RMS, Rate-Monotonic Scheduling）
分配的优先级和周期的倒数有关：
短周期 = 高优先级，长周期 = 低优先级
图中$P_1$优先级高于$P_2$：
5.6.4 最早截止时间优先调度（EDF, Earliest-Deadline-First Scheduling）
优先级根据ddl分配：
ddl越早，优先级越高
5.6.5 按比例共享调度（PSS, Proportional Share Scheduling）
T的份额被分配给系统中所有的进程。
某个应用分到N份（$N<T$），则它获得$N/T$的处理器时间。
5.6.6 POSIX 实时调度
5.7 OS实例
5.8 算法评估
5.8.1 确定模型
常用分析评估法（Analytic Evaluation），说人话就是用公式和数字表示
确定模型法（Deterministic Modeling）是一种分析评估法，就是预先确定负荷算性能（再说人话就是代数字进去算呗）
5.8.2 排队模型
Little公式： \(n = \lambda \times W\) 其中$n$是平均队列长度（不包括正在服务的进程），$W$是队列的平均等待时间，$\lambda$是新进程到达队列的平均到达率
（推导：系统处于稳定状态时，离开队列的进程数量=到达队列的进程数量）
5.8.3 模拟
驱动模拟的数据可根据概率分布、CPU区间时间、到达时间、离开时间等随机生成。
跟踪磁带可通过监视真实的系统记录下事件发生的顺序
用跟踪磁带的顺序结合驱动模拟可以使模拟更精确
然而模拟费时，跟踪磁带费存储空间，总体来说就是很贵
5.8.4 实现
就是实战，放在真实OS里进行评估
困难：贵、算法所使用的环境会变
