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

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

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

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

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

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

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

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

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

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

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

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

是否会导致饥饿: 会

抢占式

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

非抢占式

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

-------------本文结束 感谢阅读-------------