2.处理机调度

调度的概念

调度的层次

1. 高级调度（作业调度），内存和辅存之间的调度，从外存上处于后备队列的作业中挑选一个（或多个），给它（们）分配内存、输入输出设备等必要的资源，并建立相应的进程，多道批处理系统大多配置了作业调度，其他的不需要
2. 中级调度（内存调度），为了提高内存利用率和系统吞吐量，将暂时不能运行的程序调到外存等待（挂起状态）
3. 低级调度（进程调度）

调度的目标

1. 周转周期，作业提交到作业完成所经历的时间，是作业等待、在就绪队列中排队、在处理机上运行及输入/输出操作所花费时间的总和。

$$\begin{align*} \text{周转周期}=\text{作业完成时间}-\text{作业提交时间} \\ \text{带权周转时间}=\frac{\text{周转时间}}{\text{作业实际运行时间}} \end{align*}$$

2. 等待时间，处于等待处理机的时间之和。
3. 响应时间，指从用户提交请求到系统首次产生响应所用的时间。

调度的实现

调度的时机、切换与过程

不能调度和切换

1. 在处理中断过程
2. 进程在操作系统内核临界区中
3. 其他需要完全屏蔽中断的原子操作过程中

进程的调度

非抢占式调度方式

提示

也称非剥夺方式，非抢占调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统，但它不能用于分时系统和大多数的实时系统。

抢占式调度方式

典型的调度算法

先来先服务（FCFS）

提示

算法简单，但效率低；对长作业比较有利，但对短作业不利（相对SJF和高响应比)；有利于CPU繁忙型作业，而不利于I/O繁忙型作业。

短作业优先（SJF）

长作业长期不被调度，出现”饥饿“现象

优先级调度算法

划分

1. 是否可抢占：非抢占式优先级调度算法，抢占式优先级调度算法
2. 进程创建后优先级是否可以改变：静态优先级，动态优先级

进程优先级

1. 系统进程 > 用户进程
2. 交互型进程 > 非交互型进程（前台进程 > 后台进程）
3. I/O型进程 > 计算型进程

高响应比优先调度算法

$$\text{响应比}R_{\mathrm{p}}=\frac{\text{等待时间}+\text{要求服务时间}}{\text{要求服务时间}}$$

时间片轮转调度算法

多级队列调度算法

该算法在系统中设置多个就绪队列，将不同类型或性质的进程固定分配到不同的就绪队列。每个队列可实施不同的调度算法，因此，系统针对不同用户进程的需求，很容易提供多种调度策略。同一队列中的进程可以设置不同的优先级，不同的队列本身也可以设置不同的优先级。在多处理机系统中，可以很方便为每个处理机设置一个单独的就绪队列，每个处理机可实施各自不同的调度策略，这样就能根据用户需求将多个线程分配到一个或多个处理机上运行。

多级反馈队列调度算法

多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合与发展

image.png

设置多级就绪队列，各级队列优先级从高到低，时间片从小到大，新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片。若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经在最下级的队列，则重新放回最下级队列队尾。

只有第k级队列为空时，才会为k+1层进程分配时间片
被抢占处理机的进程重新放回原队列队尾

image.png

进程切换

切换CPU到另一个进程需要保存当前进程状态并恢复另一个进程的状态，这个任务称为上下文切换。

上下文切换流程

1. 挂起一个进程，保存CPU上下文，包括程序计数器和其他寄存器。
2. 更新PCB信息。
3. 把进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列。
4. 选择另一个进程执行，并更新其PCB。
5. 跳转到新进程PCB中的程序计数器所指向的位置执行。
6. 恢复处理机上下文。

模式切换

模式切换与上下文切换是不同的，模式切换时，CPU逻辑上可能还在执行同一进程，用户进
程最开始都运行在用户态，若进程因中断或异常进入核心态运行，执行完后又回到用户态刚被中
断的进程运行。用户态和内核态之间的切换称为模式切换，而不是上下文切换，因为没有改变当
前的进程。上下文切换只能发生在内核态，它是多任务操作系统中的一个必需的特性。