优先级调度算法及其优缺点

SJF 算法是通用优先级调度算法的一个特例。每个进程都有一个优先级与其关联，而具有最高优先级的进程会分配到 CPU。具有相同优先级的进程按 FCFS 顺序调度。SJF 算法是一个简单的优先级算法，其优先级（p）为下次（预测的）CPU 执行的倒数。CPU 执行越长，则优先级越小；反之亦然。

注意，我们按照高优先级和低优先级讨论调度。优先级通常为固定区间的数字，如 0~7 或 0~4095。不过，对于 0 表示最高还是最低的优先级没有定论。有的系统用低数字表示低优先级，其他用低数字表示高优先级。这种差异可以导致混淆。本节用低数字表示高优先级。

举个例子，假设有如下一组进程，它们在时间 0 按顺序 P₁，P₂，…，P₅ 到达，其 CPU 执行时间以 ms 计：

进程	执行时间	优先级
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

采用优先级调度，会按如下 Gantt 图来调度这些进程：

平均等待时间为 8.2ms。

优先级的定义可以分为内部的或外部的：

• 内部定义的优先级采用一些测量数据来计算进程优先级。例如，时限、内存要求、打开文件数量和平均 I/O 执行时间与平均 CPU 执行之比等，都可用于计算优先级。
• 外部定义的优先级采用操作系统之外的准则，如进程重要性、用于支付使用计算机的费用类型和数量、赞助部门、其他因素（通常为政治）等。

优先调度可以是抢占的或非抢占的。当一个进程到达就绪队列时，比较它的优先级与当前运行进程的优先级。如果新到达进程的优先级高于当前运行进程的优先级，那么抢占优先级调度算法就会抢占 CPU。非抢占优先级调度算法只是将新的进程加到就绪队列的头部。

优先级调度算法的一个主要问题是无穷阻塞或饥饿。就绪运行但是等待 CPU 的进程可以认为是阻塞的。优先级调度算法可让某个低优先级进程无穷等待 CPU。对于一个超载的计算机系统，稳定的更高优先级的进程流可以阻止低优先级的进程获得 CPU。一般来说，有两种情况会发生。要么进程最终会运行（在系统最后为轻负荷时），要么系统最终崩溃并失去所有未完成的低优先级进程。（据说，在 1973 年关闭 MIT 的 IBM 7094 时，发现有一个低优先级进程早在 1967 年就已提交，但是一直未能运行。）

低优先级进程的无穷等待问题的解决方案之一是老化。老化逐渐增加在系统中等待很长时间的进程的优先级。例如，如果优先级为从 127（低）到 0（高），那么可以每 15 分钟递减等待进程的优先级的值。最终初始优先级值为 127 的进程会成为系统内最高的优先级，进而能够执行。事实上，不会超过 32 小时，优先级为 127 的进程会老化为优先级为 0 的进程。