Tips：各种调度算法的学习思路

1、时间片轮转（RR, Round-Robin）

1.1、例子

常用于分时操作系统，更注重 “响应时间”，因而此处不计算周转时间

例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用时间片轮转调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

时间片为 5 的情况

若按照先来先服务调度算法

如果时间片太大，使得每个进程都可以在一个时间片内就完成，

另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境)，

因此如果时间片太小，会导致进程切换过于频繁（不断地频繁切换用户态与内核态），系统会花大量的时间来处理进程切换，

从而导致实际用于进程执行的时间比例减少。
可见时间片也不能太小。

一般来说，设计时间片时要让切换进程的开销占比不超过 $1%1\%$

例题：各进程到达就绪队列的时间、需要的运行时间、进程优先数如下表所示。使用非抢占式的优先级调度算法，分析进程运行情况。（注：优先数越大，优先级越高)

就绪队列未必只有一个，可以按照不同优先级来组织。

根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。

$静态优先级\color{red}静态优先级$ ：

$动态优先级\color{red}动态优先级$ ：

如何合理地设置各类进程地优先级？

通常：

注：与 I/O 型进程相对的是计算型进程（或称 CPU 繁忙型进程）

I/O 设备和 CPU 可以并行工作。如果优先让 I/O 繁忙型进程优先运行的话,

若采用 CPU 繁忙型进程的话，

如果采用的是动态优先级，什么时候应该调整?

可以从追求公平、提升资源利用率等角度考虑

HRRN 高响应比优先调度算法，可以认为是动态地优先级调度算法

FCFS 算法的优点是公平

SJF 算法的优点是能尽快处理完短作业，平均等待/周转时间等参数很优秀

时间片轮转调度算法可以让各个进程得到及时的响应

优先级调度算法可以灵活地调整各种进程被服务的机会

能否对其他算法做个折中权衡? 得到一个综合表现优秀平衡的算法呢?

由于进程源源不断地到来会使得高优先级的队列始终非空，而低优先级的队列需要等待高优先级的队列为空时才能使用，导致低优先级队列中的进程饥饿

算法	可抢占？	优点	缺点	会导致饥饿？	补充
时间片轮转	抢占式	公平；适用于分时系统	频繁切换有开销；不区分优先级	不会	时间片太大或太小导致的影响
优先级调度	有的抢占式的，有的非抢占式的	区分优先级；适用于实时系统	可能导致饥饿	会	动态/静态优先级。各类型型进程如何设置优先级？如何调整优先级
多级反馈队列	抢占式	平衡优秀；6（9 翻了）	一般不说它优缺点；不过可能导致饥饿	会