首页 > 编程笔记 > 操作系统笔记

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

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 图来调度这些进程:


 
平均等待时间为 8.2ms。

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

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

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

所有教程

优秀文章