1. 处理器调度类型

1.1 调度的目的

调度是以满足满足系统目标(响应时间,吞吐率,处理器效率)的方式,把进程分配到一个或多个处理器上执行

1.2 调度类型

类型 解释 理解⭐
长程 决定加入待执行进程池 将批作业/程序加载到系统,最少使用
中程 决定加入部分或全部位于内存中的进程集合 一定涉及到交换(swapping),即挂起态到其他态的转换,稍频繁
短程/分派器 决定处理器执行哪个可运行进程 决定下次执行哪个进程,最频繁,以下事件都属于短程调度:时钟中断、I/O中断、操作系统调用、信号量
I/O 决定可用I/O设备处理哪个挂起的I/O请求 与I/O请求有关

1.3 调度队列&层次

  • 调度队列

本质上,调度属于队列管理,在排队环境中减少延迟优化性
image.png

  • 调度层次

图示反映了不同进程态转换所属的调度
image.png

2. 调度算法

2.1 短程调度规则

根据面向的对象**:系统/用户,是否与性能**相关,系统的调度规则也不同,它们互相依赖可以根据需求切换

对象 性能
用户 相关 周转时间
**(Turnaround

time) | 周转时间=等待时间+执行时间
对批处理作业适用 | | | | 响应时间 | 进程从提交请求到接收响应时间间隔,
对用户需要接收响应的进程更适用 | | | | 最后期限 | 在DDL接近时,规则会降低其余目标 | | | 其他 | 可预测性(predictability) | 无论负载大小,用户不希望出现大范围波动 | | 系统 | 相关 | 吞吐量 (Throughput) | 单位时间完成最大进程数 | | | | 处理器利用率
(Processor efficiency) | 处理器忙状态占比
对共享系统重要,但单用户/实时系统不重要 | | | 其他 | 公平性 | 没有额外限定时,每个进程应该平等对待 | | | | 强制优先级 | 优先执行高优先度的 | | | | 平衡资源** | 当资源都忙,优先调用较少使用紧缺资源的进程 |

2.2 选择调度策略⭐

场景模型: 调度队列

  • 对于cpu进程,执行完成->释放,超时->重新入列
  • 对于I/O进程,执行完成->释放,I/O阻塞->进入阻塞队列(阻塞队列中,I/O设备就需要处理,此时为忙碌,一旦完成I/O,相关设备空闲),非阻塞超时->重新入列

image.png

FCFS (**先来先服务**)

决策模式 非抢占
调度时间 当前进程完毕,执行下一进程
进程选择 设置就绪队列,当前进程结束后,执行队列中存在最久的进程
缺点
- 一个短进程可能会等待很久
- 不利于I/O密集型进程:cpu进程执行时,I/O设备可能空闲,当I/O进程通过就绪队列后阻塞,cpu又空闲
优点
- 适用长进程
- 有利于处理器密集型进程

Round**-Robin(RR轮转)**

决策模式 抢占
调度时间 按基于时钟中断的时间片(time slicing)执行
进程选择 基于FCFS选择下一时间片执行的进程
缺点
- 时间片短虽然利于短作业,但耗费资源,最好让时间片长度略大于典型交互时间,当时间片大于最初进程运行时间后,退化为FCFS
- 在兼具处理器密集进程和I/O密集进程时:I/O进程使用处理器如果阻塞,这段时间占据时间片,实际上处理器没能执行
优点
- 适用通用的分时系统和事务处理系统

virtual** RR(虚拟轮转)**

决策模式 抢占
调度时间 同上RR
进程选择 见👇与RR对比
对比 image.png 区别:

I/O进程阻塞接触后没有回到就绪队列,而是进入辅助队列,直接面向处理器,且辅助队列中进程优先于就绪队列,弥补了I/O阻塞带来的执行缺失
|

SPN**(ext)(最短进程优先**)

决策模式 非抢占
调度时间 当前进程完毕,执行下一进程
进程选择 预期处理时间最短的进程下一个执行
缺点
- 长进程的可预测度降低
- 长进程可能饥饿
优点
- 适用短作业

SRT**(最短剩余时间)**

决策模式 抢占
调度时间 新进程抵达后决定
进程选择 新进程抵达后选取剩余时间最短者
缺点
- 记录过去的服务时间,增加开销
优点
- 不像FCFS偏向长进程,也不像SPN偏向短进程

HRRN**(Higest Response Ration Next最高响应比优先)**

决策模式 非抢占
调度时间 当前进程完毕,执行下一进程
进程选择 计算最大响应比的进程作为下一个
响应比 image.png
- R:响应比
- w:等待时间
- s:预计服务时间

R**最小值为**1.0,只有第一个进入系统的进程才可能达到 | | |

例题：调度策略

给出以下进程调度,比较不同策略下的调度情况:
image.png
此处时间表示某一时刻而非时间段
image.png
FCFS**:**

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
A
B
C
D
E

RR, q=1:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
A
B
C
D
E

规律总结：

image.png
- 规律:阶梯状
- 易错:以5-6-7为例的就绪队列状况,新线程进入先于当前进程重新入队
 image.png

SPN**:**

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
A
B
C
D
E

SPN是非抢占式,一定是一个进程完全执行完后再切换
SRT**:**

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
A
B
C
D
E

SRT=SPN+抢占
HRRN**:**

0 1 2 R 3 4 5 6 7 8 R 9 10 11 12 R 13 14 15 16 17 18 19
A
B 7/6
C 9/4
D 8/5 12/5
E 3/2 7/2

Feedback**,q=1:**

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
A 1 2 3 结束
B 1 2 2 2 3 3 3 3 3 3 4 4 4 5 5 5 6 结束
C 1 2 2 2 3 3 3 3 3 4 4 结束
D 1 2 2 2 3 3 3 3 4 4 4 5 结束
E 1 2 结束

技巧:阶梯+再个方格中标注当前优先级,纵向比较,选择数字小的,当数字一样,选择先处于此优先级的进程(先入队)

本章动画: http://williamstallings.com/OS-Animation/Animations.html