【操作系统】调度算法

🏫基本概念

非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。

剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

饥饿：某进程/作业长期得不到服务。

等待时间：指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。

周转时间：作业完成时间 - 作业提交时间

带权周转时间：作业周转时间 / 作业实际运行的时间

🏥先来先服务（FCFS, First Come First Serve)

🏩短作业优先（SJF, Shortest Job First)

1. 短作业/进程优先调度算法：每次调度时选择当前已到达且运行时间最短的作业/进程。
2. 严格来说，用于进程调度应该称为短进程优先调度算法(SPF)
3. 抢占式的短作业优先算法又称“最短剩余时间优先算法”(SRTN)：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度。

🍆细节

⛪️高响应比优先（HRRN,Highest Response Ratio Next）

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

以上三种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心“响应时间”，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。因此这三种算法一般适合用于早期的批处理系统，当然，FCFS算法也常结合其他的算法使用，在现在也扮演着很重要的角色。

🌇时间片轮转（RR,Round-Robin)

时间片轮转调度算法：轮流让就绪队列中的进程依次执行一个时间片（每次选择的都是排在就绪队列队头的进程)

🏰时间片大小的影响

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

🗼优先级调度算法

1. 非抢占式的优先级调度算法：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。
2. 抢占式的优先级调度算法：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。另外，当就绪队列发生改变时也需要检查是会发生抢占。

🌄多级反馈队列调度算法

1. 设置多级就绪队列，各级队列优先级从高到低，时间片从**小到大 **
2. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片。若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经在最下级的队列，则重新放回最下级队列队尾
3. 只有第** k 级队列为空时，才会为 k+1 级队头的进程分配时间片 **
4. 被抢占处理机的进程重新放回原队列队尾

🌈实例

1. **进程1在第1级队列执行一个时间片，进程1未结束，进入第2级队列 **
2. **进程2在第1级队列执行一个时间片，进程2未结束，进入第2级队列 **
3. **进程1在第2级队列执行两个时间片，进程1未结束，进入第3级队列 **
4. 进程2在第2级队列执行一个时间片，由于此时进程3进入第1级队列，故执行优先级更高的进程3一个时间片，进程3执行完毕。
5. **第1级队列为空，为第2级队列分配时间片，此时只有进程2，进程2在第2级队列执行两个时间片，进程2执行完毕。 **
6. 进入第3级队列，进程1在第3级队列执行四个时间片，进程1尚未结束，但是进程1已经处于最后一个队列，则重新放回最下级队列队尾，执行最后一个时间片，结束进程1。

比起早期的批处理操作系统来说，由于计算机造价大幅降低，因此之后出现的交互式操作系统（包括分时操作系统、实时操作系统等）更注重系统的响应时间、公平性、平衡性等指标。而后三种算法恰好也能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。

🗽多级队列调度