SJF 算法是通用优先级调度算法的一个特例。每个进程都有一个优先级与其关联,而具有最高优先级的进程会分配到 CPU。具有相同优先级的进程按 FCFS 顺序调度。SJF 算法是一个简单的优先级算法,其优先级(p)为下次(预测的)CPU 执行的倒数。CPU 执行越长,则优先级越小;反之亦然。
注意,我们按照高优先级和低优先级讨论调度。优先级通常为固定区间的数字,如 0~7 或 0~4095。不过,对于 0 表示最高还是最低的优先级没有定论。有的系统用低数字表示低优先级,其他用低数字表示高优先级。这种差异可以导致混淆。本节用低数字表示高优先级。
举个例子,假设有如下一组进程,它们在时间 0 按顺序 P1,P2,…,P5 到达,其 CPU 执行时间以 ms 计:
进程 | 执行时间 | 优先级 |
---|---|---|
P1 | 10 | 3 |
P2 | 1 | 1 |
P3 | 2 | 4 |
P4 | 1 | 5 |
P5 | 5 | 2 |
采用优先级调度,会按如下 Gantt 图来调度这些进程: