调度算法1

在这里插入图片描述

先来先服务

在这里插入图片描述

来看一道习题：

在这里插入图片描述

短作业优先算法

在这里插入图片描述

短作业优先算法同样可以应用于短进程优先算法，对长作业不友好

用一个例子看一下在短作业算法中非抢占算法(SJF)和抢占式子算法(SRTN)

非抢占式算法-SJF

在这里插入图片描述

抢占式算法-SRTN

最短剩余时间优先算法：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度

在这里插入图片描述

在这里插入图片描述

SRTF 算法的平均等待时间，平均周转时间最少

所有进程可以同时运行的情况下，SJF的平均等待时间，平均周转时间最少

抢占式的短作业/进程优先调度算法的平均等待时间按和平均周转时间最少

在这里插入图片描述

高响应比优先算法

在这里插入图片描述

在这里插入图片描述

高响应比优先算法：非抢占式的调度算法，只有当前运行的进程主动放弃CPU时（正常/异常完成，或主动阻塞），才需要进行调度，调度时计算所有就绪进程的响应比，选响应比最高的进程上处理机，避免了饥饿的情况

例题

在这里插入图片描述

总结

调度算法2

总览思维导图

在这里插入图片描述

时间片轮转(RR)

在这里插入图片描述

时间片轮转算法更关注的是进程的响应时间

以时间片为2的情况：

在这里插入图片描述

在这里插入图片描述

以时间片为5的情况

在这里插入图片描述

注意，在15时刻的时候P4的时间片用完，但是就绪队列为空，所以不需要进行调度，P4继续执行即可

时间片为5的情况,每个进程都可以在一个时间片内完成，因此该算法退化为先来先服务算法，会增大进程的时间，因此时间片不能太大

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。
另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境），因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小：

优先级调度算法

在这里插入图片描述

注意，该算法既有抢占式也有非抢占式算法

该算法可能导致饥饿

优先数越大，优先级越高，具体看题目给的要求

非抢占式

优先级相同的情况下，先到达就绪队列的进程的先运行

在这里插入图片描述

抢占式

抢占式的优先级调度算法：每次调度时选择当前己到达且优先级最高的进程。

当前进程主动放弃处理机时发生调度。
另外，当就绪队列发生改变时也需要检查是会发生抢占，

总结

在这里插入图片描述

如过进程在就绪队列中等待了很长时间，可以提升优先级，类似高响应比算法，随着等待时间边长，响应比时间也在变化。

多级反馈队列调度算法

先留个坑…后面有时间再说