为什么需要调度
- 进程包括CPU执行和IO执行
- CPU执行时间与频率之间的关系成指数或超指数分布
- IO密集型程序通常是大量短CPU执行，CPU密集程序可能只有少量长CPU执行
- 调度能提高CPU利用率、系统响应速度
两种思想：
- Multiprogramming：让 CPU 在一个进程等 I/O 时去执行别的进程
- Multitasking：让多个任务轮流获得 CPU，看起来都在同时运行
为什么必须这样做：
- 因为系统里进程很多
- 它们状态不同
- 而 CPU 数量有限
进程调度主要反映的是Ready和Running之间的关系
调度类型
长程调度
- 从磁盘上开始
- 从创建到Ready
- 耗时较长
- 确定哪一个程序进入系统中处理
- 控制系统的并发度
- 创建的进程越多，每个进程执行的时间占比越小
- 会限制系统的并发度
中程调度
- 一般指Suspend到Ready
- 从阻塞到挂起
- 是交换功能swap的一部分
- 换入决定取决于管理系统并发度的需求
短程调度
- 一般指Ready到Running
- 也称为分派程序
- 执行频率：长程<中程<短程
- 精确决定下次执行哪一个进程
- 导致当前进程阻塞或抢占当前运行进程的事件发生时就调用短程调度程序
触发调度的事件
- 新进程来了
- 当前进程结束了
- 当前进程阻塞了
- 阻塞进程恢复了
主要是两类：
第一类：当前运行进程不能再继续占用 CPU
例如：
- 进程终止
- 进程等待 I/O 这时 CPU 空出来了，必须重新选一个进程运行。
第二类：系统中可运行进程集合发生变化
例如：
- 新进程创建
- 某个等待 I/O 的进程恢复为就绪态 这时调度器可能要重新评估“谁更适合现在运行”。
抢占式调度和非抢占式调度
当调度在“从运行状态切换到等待状态（I/O请求或wait（）调用）”和“终止”时发生时，调度方案是非抢占的。
当调度在“从运行状态切换到就绪状态（出现中断）”和“从等待切换到就绪 （ I/O完成）”发生时，调度方案是抢占式的。
在非抢占式调度下，一旦CPU分配给进程，进程将保持CPU，直到终止或切换到等待状态释放CPU为止
只有进程不主动交出CPU，就是非抢占式调度
调度准则
- CPU利用率
- 吞吐量
- 周转时间
- 指任务到达（发起）到完成的整一段时间，包含处理和等待、IO的时间
- 等待时间
- 进程在Ready Queue中等待耗费的时间
- 响应时间
- 从用户或进程提交请求开始，到系统第一次给出响应为止所经过的时间
- 不同准则之间存在相互冲突，比如提高CPU利用率和响应时间，不可能同时使所有指标都增加
调度算法
输入
- 一系列进程
- 每个进程的到达时间，CPU所需资源
- 在线调度
- 进程是实时到来的（实际情况下）
- 离线调度
- 进程相关信息已获取，再来进行调度（主要用于验证）
输出
一个排好序的队列
类型
- FIFO：先来先执行（非抢占式）
- ShortestJobFirst：耗时最短的先执行（抢占or非抢占）（抢占的版本也被称为Shortest Remaining Time）
- RoundRobin：时间片轮转（抢占）
- 优先级调度
- 基于优先级的多队列
不同指标的计算
- Waiting Time：P1=0,P2=23,P3=25（通过开始的时间-到达时间来计算）
- Turnaround Time：P1=24,P2=26,P3=28（通过进程运行结束的时间-到达时间来计算）
FCFS(FIFO)
- 先请求CPU的进程先分配到CPU
- 是非抢占的，进程得到CPU会一直占用CPU直到终止或请求IO
- 对到达的顺序敏感，同样的进程输入，但是顺序不同，会导致指标变化
- 会出现等待时间过长的问题
- 护航效应：一个运行时间很长的进程走在前面，后面一群短进程被迫跟着它慢慢等
- 短作业等待时间变长
- 平均等待时间变大，平均周转时间变差
- 系统响应速度下降
SJF（非抢占）
- 不会在进程执行中被抢占，当有优先级更高的到来时不会影响其运行
- 一个运行完后，在剩下进程中挑CPU需求最小的继续运行
SJF（抢占）
- 每一个新进程到达，都会计算一次优先级
- 根据每个进程的剩余CPU需求来调度
- 增加了上下文切换的成本
- 这一调度算法是最优的，因为其平均等待时间最小
- 在进程开始运行之前，所需的资源是不知道的，通过预测来实现
- 预测使用的算法为
RR
- 为分时系统设计，类似FCFS但是有抢占
- 每个进程给定一个较小的时间单位称为时间片，其用完后，CPU选择另一个进程调度执行
- 循环整个就绪队列， 一个一个执行
- 如果就绪队列中有n个进程，且时间片为q，则每个进程一次最多以 q个时间单位的块获取1/n的CPU时间。没有进程等待超过（n-1）个时间单位。
- 若两个进程同时到达，未调度过的进程往往有更高优先级
- 性能表现来看并不占优，但是由于用户需要及时响应，其仍被需要
- 性能很大程度取决于时间片大小，时间片太大，与FCFS一样
- 时间片太小，产生大量上下文切换，反而使程序性能降低
- 时间片要远大于上下文切换的时间
- 80%的CPU执行时间应小于时间片
优先级调度
- 用根据内部（时限、内存需求）和外部定义（重要性、所有者）确定的优先级编号，与每个进程相关联
- 问题：饥饿——低优先级进程可能永远不会执行
- 解决方案：老化——随着时间推移，进程优先级会增加
多级队列调度（Feedback）
- 本质优先级调度器
- 就绪作业队列分成多个单独队列，每个队列有不同的调度算法
- 分为前台进程（RR）和后台进程（FCFS）
- 不同队列之间的调度
- 固定优先级抢占调度
- 为队列之间划分时间片，每个队列有一定比例的CPU时间
- 短时间的进程优先级最高，长时间的进程自动降低优先级
- 包含以下参数
- 队列数量
- 每个队列的调度算法
- 用于确定何时升级到高优先级队列的方法
- 用于确定何时降级到更低优先级队列的方法
- 用于确定当某个进程需要服务时，该进程将进入哪个队列的方法
线程调度
- 如果支持线程，则调度线程而非进程
- 线程可在两种范围内被调度
- PCS（Process-ContentionScope）：线程在同一个进程内部互相竞争CPU
- SCS（System-ContentionScope）：线程在整个系统范围内竞争CPU
- 在多对一模型中：多个用户线程映射到一个内核线程。这时内核看不到这些用户线程，只能看到进程，所以用户线程之间的选择通常属于 PCS。
- 在一对一模型中：每个用户线程都对应一个内核线程。 这时内核能直接看到每个线程，所以线程在系统范围内竞争，属于 SCS。
调度策略
选择函数
表示调度器按什么标准挑选下一个进程
决策方式
是否允许抢占：
- FCFS：非抢占
一旦开始跑，就不会被打断。 - Round Robin：抢占式（按时间片）
时间片用完就强制切换。 - SPN：非抢占
选中最短作业后就让它跑完。 - SRT：抢占式（有新进程到达时）
如果来了一个剩余时间更短的进程，就可能抢占当前进程。 - HRRN：非抢占
每次选响应比最高的一个让它跑完。 - Feedback：抢占式（按时间片）
通常基于时间片和优先级变化来调度。