调度算法（二）
（1）前言
比起早期的批处理操作系统来说，由于计算机造价大幅降低，因此之后出现的交互式操作系统（包括分时操作系统、实时操作系统等）更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。（比如 UNIX 使用的就是多级反馈队列调度算法）。
（2）RR 时间片轮转 Round-Robin
Ⅰ. 算法思想
公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应。
Ⅱ. 算法规则
按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如 100ms ）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
Ⅲ. 用于作业/进程调度
用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）。
Ⅳ. 是否可抢占
抢占式的算法。若进程未能在时间片内运行完，将被强行剥夺处理机使用权，由时钟装置发出时钟中断来通知 CPU 时间片己到。
Ⅴ. 优缺点
- 优点：公平。响应快，适用于分时操作系统。
- 缺点：由于高频率的进程切换，因此有一定开销。不区分任务的紧急程度。
Ⅵ. 是否会导致饥饿
不会。
Ⅶ. 例子
注：常用于分时操作系统，更注重“响应时间”，因而此处暂不计算周转时间。
1. 时间片为2（模拟较小时间片）
2. 时间片为5（模拟较大时间片）
Ⅷ. 补充
时间片的大小应合理设计，不能过大或过小
（3）优先级调度
Ⅰ. 算法思想
随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序。
Ⅱ. 算法规则
每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程。
Ⅲ. 用于作业/进程调度
即可用于作业调度，也可用于进程调度，还可用于 I/O 调度。
Ⅳ. 是否可抢占
抢占式和非抢占式都有。
Ⅴ. 优缺点
- 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
- 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿。
Ⅵ. 是否会导致饥饿
会。
Ⅶ. 例子
1. 非抢占式（当某个作业/进程主动放弃处理机后发生调度）
2. 抢占式（当前进程主动放弃处理机时发生调度。另外，当就绪队列发生改变时也需要检查是会发生抢占）
Ⅷ. 补充
-
就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置。
-
根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。
- 静态优先级： 创建进程时确定，之后一直不变。
- 动态优先级： 创建进程时有一个初始值，之后会根据情况动态地调整优先级。
-
通常：
- 系统进程优先级高于用户进程
- 前台进程优先级高于后台进程
- 操作系统更偏好 I/O 型进程（I/O 繁忙型进程）（注：与 I/O 型进程相对的是计算型进程（CPU 繁忙型进程）
-
可以从追求公平、提升资源利用率等角度考虑（动态优先级）：
- 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级（某种角度上高响应比优先算法 HRRN 可看作动态调整优先级的优先级调度算法）
- 如果某进程占用处理机运行了很长时间，则可适当降低其优先级
- 如果发现一个进程频繁地进行 I/O 操作，则可适当提升其优先级
（4）多级反馈队列调度
Ⅰ. 算法思想
对其他调度算法的折中权衡。
Ⅱ. 算法规则
- 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
- 新进程到达时先进入第 1 级队列，按 FCFS 原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时己经是在最下级的队列，则重新放回该队列队尾
- 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片
Ⅲ. 用于作业/进程调度
用于进程调度。
Ⅳ. 是否可抢占
抢占式的算法。在 k 级队列的进程运行过程中，若更上级的队列（ 1~k-1 级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回 k 级队列队尾。
实际也可能有非抢占式的版本。
Ⅴ. 优缺点
- 对各类型进程相对公平（先来先服务 FCFS 的优点）
- 每个新到达的进程都可以很快就得到响应（时间片轮转 RR 的优点）
- 短进程只用较少的时间就可完成（短进程优先 SPF 的优点）
- 不必实现估计进程的运行时间（避免用户作假）
- 可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程（拓展：可以将因 I/O 而阻塞的进程重新放回原队列，这样 I/O 型进程就可以保持较高优先级）
Ⅵ. 是否会导致饥饿
会（源源不断有新进程进入高优先级队列）。
Ⅶ. 例子
标签：优先级,队列,调度,算法,进程,抢占 From： https://www.cnblogs.com/Wind730/p/18534400/schedule-algorithm-2-73jds