交互式调度算法

交互式系统要让用户的操作尽快得到反应，因此更关心算法的响应时间、公平性和任务紧急程度。

算法	主要依据	抢占性	适合解决的问题
RR	到达就绪队列的顺序、时间片	抢占	让每个进程周期性获得 CPU
优先级调度	优先级	可抢占，也可非抢占	区分任务紧急程度
多级队列调度	进程类型所属队列	取决于队列间策略	按系统进程、交互进程、批处理进程等分类管理
多级反馈队列调度	队列优先级、时间片、运行反馈	抢占	在响应、公平、短进程优先之间折中

算法	是否区分优先级	是否使用时间片	是否允许队列迁移	主要优点	主要风险
RR	否	是	否	公平、响应快	时间片过小会增加切换开销
优先级调度	是	不一定	否	能表达任务紧急程度	低优先级进程可能饥饿
多级队列调度	是，按队列区分	可按队列设置	通常不迁移	不同类型进程分开管理	低优先级队列可能饥饿
多级反馈队列调度	是，按队列动态区分	是	是	综合响应、公平和短进程优先	规则复杂，低级队列仍可能饥饿

RR 时间片轮转

RR，Round-Robin，即时间片轮转调度。

角度	RR
思想	公平地、轮流地为各进程服务，让每个进程在一定时间间隔内得到响应
规则	按进入就绪队列的顺序，每次让队头进程运行一个时间片
使用对象	进程调度
抢占性	抢占式
优点	公平，响应快，适合分时系统
缺点	进程切换频繁，有上下文切换开销；不区分任务紧急程度
饥饿	不会

如果进程在一个时间片内完成，它主动放弃 CPU；如果时间片用完仍未完成，时钟中断触发调度，操作系统剥夺 CPU，把它放回就绪队列队尾。

同一时刻的入队顺序

若某个时刻同时发生新进程到达和当前进程时间片用完，新到达进程先进入就绪队列，当前进程后进入就绪队列。

示例：

时间片为 2 时，运行顺序为：

$$
P1 \to P2 \to P1 \to P3 \to P2 \to P4 \to P1 \to P4 \to P4
$$

对应的 CPU 占用区间为：

时间片大小会直接影响系统表现：

时间片	结果
过大	每个进程可能在一个时间片内就完成，RR 退化为 FCFS，响应时间变长
过小	时钟中断和上下文切换太频繁，CPU 时间被调度开销消耗
合适	让交互进程较快得到响应，同时不让切换开销过大

优先级调度给每个作业或进程设置优先级，调度时选择优先级最高者。

角度	优先级调度
思想	按任务紧急程度或系统偏好分配 CPU
规则	每次调度时，从候选者中选择优先级最高者
使用对象	可用于作业调度、进程调度，也可用于 I/O 调度
抢占性	可抢占，也可非抢占
优点	能表达任务紧急程度，适合实时系统；也便于体现系统策略
缺点	高优先级进程不断到来时，低优先级进程可能长期得不到服务
饥饿	可能

非抢占式优先级调度只在当前进程完成、阻塞或主动放弃 CPU 时重新选择。抢占式优先级调度还要在就绪队列变化时检查：若新到达进程优先级高于当前运行进程，就抢占当前进程。

优先级可以分为两类：

类型	含义	特点
静态优先级	创建进程时确定，之后不变	实现简单，但难以反映运行过程中的变化
动态优先级	创建时有初值，运行过程中可调整	更灵活，可以缓解饥饿，也能体现系统当前偏好

常见设置思路：

多级队列调度把就绪队列拆成多个队列，进程创建后按类型进入固定队列。例如：

队列之间常见两种安排：

队列间策略	含义
固定优先级	高优先级队列不空时，低优先级队列不能运行
时间片划分	给不同队列分配固定 CPU 比例，例如 50%、40%、10%

多级队列调度的关键是分类。一个进程通常固定属于某个队列，队列之间不强调迁移。它能把不同类型进程分开管理，但如果采用固定优先级，低优先级队列可能长期得不到 CPU。

多级反馈队列调度保留多个就绪队列，但进程可以根据运行情况在队列之间迁移。

角度	多级反馈队列
思想	在 FCFS 的公平、RR 的响应、SPF 的短进程优先、优先级调度的灵活性之间折中
规则	新进程先进入最高优先级队列；用完本级时间片仍未完成则下降一级；高优先级队列为空时才调度低优先级队列
使用对象	进程调度
抢占性	抢占式
优点	新进程响应快；短进程容易较早完成；不需要预估运行时间；可通过队列和时间片设置体现系统偏好
缺点	规则较复杂；若高优先级进程持续到来，低优先级进程可能饥饿
饥饿	可能

基本规则如下：

统一例子：

设三层队列：

按抢占规则，运行过程为：

$$
P1(Q1,0\sim1)\to P2(Q1,1\sim2)\to P1(Q2,2\sim4)\to P2(Q2,4\sim5)\to P3(Q1,5\sim6)\to P2(Q2,6\sim8)\to P1(Q3,8\sim12)\to P1(Q3,12\sim13)
$$

这个过程体现了三个机制：