3.3交互进程的调度

交互进程通过从键盘或指示装置接收命令或数据&＃xff0c;并且通过生成用户的终端或其它输出设备上的输出响应与在对话框的形式与用户通信。

调度交互进程的主要目标是对每个输入做出迅速响应。因此&＃xff0c;交互式进程必须使用抢占式调度来分时共享 CPU&＃xff0c;以便让每个进程都有机会及时取得进展。

RR调度算法

时间量子&＃xff0c;Q&＃xff0c;是在进程内被允许使用的CPU时间的一个很短的时间单位&＃xff08;通常为10到100毫秒&＃xff09;。

RR(round-robin)算法使用单一的进程队列。优先级仅由进程在队列中的位置决定。队列头部的进程具有最高优先级&＃xff0c;允许运行 Q 个时间单位。当 Q 结束时&＃xff0c;进程被移动到队列的尾部&＃xff0c;下一个位于队列头部的进程又被允许运行 Q 个时间单位。

ML 调度算法

RR调度平等对待所有的进程。外部优先级可以根据重要性划分成多个组。ML(MultiLevel) 调度在每个优先级维护一个单独的进程队列。在每个级别内&＃xff0c;进程使用 RR 进行调度。

例&＃xff1a;

1. ML 在队列中维护 N 个不同优先级的进程。
2. 选择最高优先级队列 § 头部的进程执行。
3. 当该级别允许的最长时间到期时&＃xff0c;正在运行的进程 § 移动到同一队列的尾部&＃xff0c;下一个进程 (q) 开始使用 CPU。
4. 优先级为 N-2 的新进程 (v) 进入相应队列的尾部。
5. 优先级高于当前运行进程 (q) 的新进程 (x) 抢占正在运行的进程。只有当更高级别的所有队列都为空时&＃xff0c;给定级别的进程才能运行。例如&＃xff1a;s 将仅在级别 N 和 N-1 的进程终止后运行。

MLF 调度算法

多级反馈(Multilevel feedback)调度类似于 ML&＃xff0c;但通过以下方式解决饥饿和公平问题&＃xff1a;

• 在每个优先级使用不同的时间量
• 动态改变每个进程的优先级

在多级反馈 (MLF) 算法下&＃xff0c;新到达的进程进入最高优先级队列 N&＃xff0c;并允许运行 Q 个时间单位。当超过 Q 时&＃xff0c;进程将移至下一个优先级较低的队列 N-1&＃xff0c;并允许运行 2Q 时间单位。优先级每降低一倍&＃xff0c;量程大小就会加倍。因此&＃xff0c;在优先级 L&＃xff0c;允许的最大时间是 2^(NL) Q 个时间单位。

MLF 会自动偏向运行时间较短的进程&＃xff0c;而运行时间较长的进程会逐渐迁移到较低优先级。

1. MLF 维护 N 个优先级。从级别 N 的量子 Q 开始&＃xff0c;每个级别允许的最长时间随着每低一个级别增加一倍。
2. 新进程总是以最高优先级 N 进入。
3. 队列头部的进程 § 最多可以运行 Q 个时间单位。
4. 当 p 超过 Q 时&＃xff0c;p 从 CPU 中移除并移至下一个较低队列 N-1 的尾部。下一个过程&＃xff08;q&＃xff09;继续。
5. 如果 q 也超过 Q&＃xff0c;则 q 移动到级别 N-1&＃xff0c;并且允许进程 p 运行 2Q 时间单位。
6. 一个新进程 ® 在级别 N 进入并中断 p&＃xff0c;它在 q 后面的相同级别 N-1 处进入。允许进程 r 运行 Q 个时间单位。
7. 如果 r 在一个 Q 内终止并离开&＃xff0c;则 q 重新进入以完成第 N-1 级的 2Q 时间单位。
8. 如果 q 在耗尽 2Q 之前终止并离开&＃xff0c;则允许 p 在级别 N-1 完成 2Q 时间单位。如果没有新进程到达&＃xff0c;p 继续运行。如果 p 没有终止&＃xff0c;则 p 会继续降低优先级直到级别 1。
9. 在最低优先级&＃xff0c;时间是无限的&＃xff0c;所以 p 最终在这个级别终止。

交互式调度算法的性能

进程的**响应时间(response time)**是从提交请求&＃xff08;按 Enter 键或单击鼠标按钮&＃xff09;到响应开始到达所经过的时间。保证足够的响应时间是调度交互式进程的主要目标。

对于单独运行的进程&＃xff0c;响应时间取决于请求的类型。例如&＃xff1a;按下一个键和看到字符出现在屏幕上之间的时间应该是人眼无法察觉的。对文档进行拼写检查或呈现视频剪辑的请求可能需要几秒钟的时间。

当多个进程分时共享 CPU 时&＃xff0c;响应时间随着进程数、时间片长度以及执行上下文切换所需的时间而增加。

-> 3.4实时进程调度

此博客仅用于自我学习的记录&＃xff0c;如有不当请指正。09/03/2021