3.3　进程调度

本节概览：先建立「进程调度」的框架，再依次展开下列小节。

1. 进程调度的任务、机制和方式
2. 轮转调度算法
3. 优先级调度算法
4. 多队列调度算法
5. 多级反馈队列(multileved feedback queue)调度算法
6. 基于公平原则的调度算法

进程调度机制由排队器和分派器等组成。每当一个进程转为就绪状态，排队器就把它插入相应就绪队列；分派器则依据调度程序选定的进程，将其从就绪队列取出，并在分派器与新进程之间进行上下文切换。

通过这两个部件的配合，完成从就绪队列到处理机的调度流程。

非抢占方式（Nonpreemptive Mode）：一旦把处理机分配给某进程，就一直让它运行下去，不会因时钟中断或任何其它原因抢占，直至该进程完成或因某事件被阻塞，才把处理机分配给其它进程。

抢占方式（Preemptive Mode）：允许调度程序根据某种原则暂停正在执行的进程，把处理机重新分配给另一进程。抢占方式较复杂，系统开销也较大。

非抢占方式：分配后不抢占，直至完成或阻塞

抢占方式：按原则可暂停当前进程，开销较大

进程调度的任务包括三步：保存当前进程的处理机现场信息（程序计数器、通用寄存器等）；按某种算法从就绪队列中选取一个进程并将其状态改为运行；由分派程序把处理器分配给该进程，将其 PCB 中现场信息装入处理器寄存器，把控制权交给它从断点恢复运行。

轮转（RR）法：所有就绪进程按 FCFS 排成队列，系统每隔一定时间产生中断，把 CPU 分给队首进程执行一个时间片。时间片用完换下一个队首进程。

这样保证就绪队列中所有进程在确定时间内都能获得一个时间片的处理机时间。

RR 调度中进程切换的两种情况：① 时间片未用完进程就完成了，立即激活调度程序；② 时间片用完时计时器中断被激活，进程尚未完成则送往就绪队列尾部。

时间片大小对系统性能影响很大。时间片太小导致频繁切换开销大；太大则退化为 FCFS。

结合图 3-3（q=1 和 q=4 时进程的周转时间）理解时间片大小对性能的影响。

优先级调度算法把处理机分给就绪队列中优先级最高的进程，分为两种。

1. 非抢占式优先级调度：分配后一直执行到完成或放弃处理机
2. 抢占式优先级调度：执行中出现更高优先级进程就抢占

静态优先级在创建进程时确定，运行期间不变，用整数（优先数）表示。确定依据有三个。

1. 进程类型
2. 进程对资源的需求
3. 用户要求

多队列调度算法将系统中的就绪队列从一个拆分为若干个，把不同类型或性质的进程固定分配到不同就绪队列。不同就绪队列可采用不同调度算法，一个队列中的进程可设置不同优先级，不同队列本身也可设置不同优先级。

由于设置多个就绪队列，每个队列可实施不同调度算法，系统针对不同用户需求很容易提供多种调度策略。

优点：可为不同类型进程提供多种调度策略

多级反馈队列调度算法的机制。

1. 设置多个就绪队列，优先级从高到低
2. 每个队列采用 FCFS 算法
3. 按队列优先级调度

如果第一个队列的时间片略大于多数人机交互所需处理时间，便能较好满足各类用户。

1. 终端型用户
2. 短批处理作业用户
3. 长批处理作业用户

实施公平调度算法时系统必须具备的功能。

1. 跟踪计算每个进程已执行的处理时间
2. 计算每个进程应获得的处理机时间（自创建以来时间除以 n）
3. 计算进程获得处理机时间的比率

公平调度的执行方法。

1. 比较各进程获得处理机时间的比率，选择比率最小的进程运行
2. 该进程运行直到超过最接近它的进程比率为止