操作系统基础23-优先级调度算法

2020-11-29 17:17·重学IT的老猫

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

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

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

平均等待时间为 8.2ms。优先级的定义可以分为内部的或外部的：

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

算法思想：随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序。 算法规则：调度时选择优先级最高的作业/进程 用于作业/进程调度：即可用于作业调度，也可用于进程调度。甚至，还会用于I/O调度中。 是否可抢占？：抢占式、非抢占式都有。非抢占式需要在进程主动放弃处理机式进程调度即可，而抢占式还需在就绪队列变化式，检查是否会发生抢占。

优缺点：优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调至对各个作业/进程的偏好程度。缺点：若源源不断地有高优先级进程到来，则可能导致饥饿

是否会导致饥饿：会