处理机调度与死锁

2024-01-09 22:31:40

进程调度算法

进程调度算法也称为CPU调度算法

当 CPU 空闲时,操作系统就选择内存中的某个「就绪状态」的进程,并给其分配 CPU。

调度算法影响的是等待时间(进程在就绪队列中等待调度的时间总和),而不能影响进程真在使用 CPU 的时间和 I/O 时间。

  • 先来先服务调度算法
  • 最短作业优先调度算法
  • 高响应比优先调度算法
  • 时间片轮转调度算法
  • 最高优先级调度算法
  • 多级反馈队列调度算法

先来先服务调度算法FCFS

每次从就绪队列选择最先进入队列的进程,然后一直运行,直到进程退出或被阻塞,才会继续从队列中选择第一个进程接着运行。

在这里插入图片描述

每次从就绪队列选择最先进入队列的进程,然后一直运行,直到进程退出或被阻塞,才会继续从队列中选择第一个进程接着运行。

在这里插入图片描述

在这里插入图片描述

平均等待时间 = 平均周转时间 - 运行时间

在这里插入图片描述

最短作业优先调度算法SJF

优先选取运行时间最短的作业,如果时间一样则先来先服务。有助于提高系统的吞吐量。

在这里插入图片描述

非抢占式:

在这里插入图片描述

等待时间 = 开始运行时间 - 到达时间

周转时间 = 运行结束时间 - 到达时间

平均等待时间 = 平均周转时间 - 运行时间

抢占式:

在这里插入图片描述

由于P2剩余进程时间是2个时间单位是要小于新来的P4进程4个时间单位的,因此先完成P2再去调度P4,而P1还剩5个时间单位,最后再调度。

先算出周转时间 = 运行结束时间 - 到达时间

再用周转时间 - 区间时间来算等待时间

最高优先级调度算法HPF

从就绪队列中选择最高优先级的进程进行运行

进程的优先级可以分为,静态优先级或动态优先级:

  • 静态优先级:创建进程时候,就已经确定了优先级了,然后整个运行时间优先级都不会变化;
  • 动态优先级:根据进程的动态变化调整优先级,比如如果进程运行时间增加,则降低其优先级,如果进程等待时间(就绪队列的等待时间)增加,则升高其优先级,也就是随着时间的推移增加等待进程的优先级

在这里插入图片描述

先算出周转时间 = 运行结束时间

再用周转时间 - 区间时间来算等待时间

高响应比优先调度算法 HRRN

每次进行进程调度时,先计算「响应比优先级」,然后把「响应比优先级」最高的进程投入运行,「响应比优先级」的计算公式:权衡了短作业和长作业

在这里插入图片描述

时间片轮转调度算法RR

每个进程被分配一个时间段,称为时间片(Quantum),即允许该进程在该时间段中运行。

  • 如果时间片用完,进程还在运行,那么将会把此进程从 CPU 释放出来,并把 CPU 分配另外一个进程;
  • 如果该进程在时间片结束前阻塞或结束,则 CPU 立即进行切换;

通常时间片设为 20ms~50ms 通常是一个比较合理的折中值。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

等待时间 = 周转时间(运行结束时间) - 运行时间

在这里插入图片描述

在这里插入图片描述

多级队列调度算法MFQ

多级反馈队列(Multilevel Feedback Queue)调度算法是「时间片轮转算法」和「最高优先级算法」的综合和发展。

顾名思义:

  • 「多级」表示有多个队列,每个队列优先级从高到低,同时优先级越高时间片越短。
  • 「反馈」表示如果有新的进程加入优先级高的队列时,立刻停止当前正在运行的进程,转而去运行优先级高的队列;

在这里插入图片描述

该算法很好的兼顾了长短作业,同时有较好的响应时间。

文章来源:https://blog.csdn.net/m0_60496161/article/details/135490181
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。