操作系统笔记【处理机调度知识】

CPU 在计算机系统中是非常重要的，但是早期的时候非常简单，是因为它像其他资源一样被一个作业所独占，不存在什么处理及分配或者调度的问题，但是随着各种多道程序的设计以及不同类型的操作系统的出现，不同的CPU的管理方法将会为用户提供不同性能的操作系统

而衡量调度策略的指标也有很多：

• CPU利用率：使CPU尽可能忙，实现高效
• 吞吐量：单位时间中完成的进程（即一定时间的总工作量）
• 周转时间：运行该进程所花费的时间
• 等待时间：在就绪队列中等待所花费的时间
• 响应时间：从提交请求到产生第一个响应的时间

小结：

CPU调度：进程调度程序按照一定的策略，动态的将CPU分配给某个进程，并使之执行

目的：使CPU资源利用率最高

(二) 分级调度

作业调度方式分为 4 级

• 作业调度
• 交换调度
• 进程调度
• 线程调度

作业调度（宏观调度、高级调度）

• 对外存输入井上的大量作业进行选择，对选择的作业分配资源，建立相应进程。作业执行完毕时，回收资源

交换调度（中级调度）

• 将处于外存交换区中的就绪状态或等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区

进程调度（微观调度、低级调度）

• 选取一个处于就绪状态的进程占用处理机，之后，进行上下文切换以便建立与占用处理机进程相适应的执行环境

线程调度

• 选取一个处于就绪状态的线程进入执行状态

(三) 作业调度

(1) 功能

1、记录系统中各作业的状况

• 系统为每个作业建立一个 JCB 记录作业信息（包括作业名、作业类型、资源要求、资源使用情况、优先级（数）、当前状态等），系统通过 JCB 感知作业的存在
• 作业进入后备状态时，系统为其建立 JCB；作业进入完成状态后，系统撤销其 JCB

2、从后备队列中选择一部分作业投入运行（涉及调度算法）

3、为被选中的作业做好执行前的准备（建立进程、为进程们分配系统资源）

4、作业执行结束时的后处理

(2) 目标

公平性：对所有作业应该是公平的

利用率：应使设备有高的利用率

作业量：每天执行尽可能多的作业

响应时间：有快的响应时

(3) 作业周转时间

注：_ 代表下标

作业i的周转时间：T_i=T_ei - T_si

其中T_ei为作业 i 的完成时间，T_si 为作业 的提交时间

平均周转时间：

作业i的周转时间：T_i=T_wi＋T_ri

T_wi 主要指作业 i 由后备状态到执行状态的等待时间，它不包括作业进入执行状态后的等待时间，T_ri 主要指执行时间

(四) 进程调度

(1) 功能

1、记录所有进程的运行状况（静态和动态）

2、当进程出让 CPU 或调度程序剥夺执行状态进程占用的 CPU 时，选择适当的进程分派 CPU

• 进程调度的一个主要功能是按照一定的策略选择，一个处于就绪状态的进程，使其获得处理机执行，而不同的系统设计目的，有着不同的选择策略，并且这些策略决定了调度算法的性能

3、完成上下文切换，用户态执行进程 A 通过时钟中断或系统调用进入 OS核心的进程调度器，完成：

• 保存进程 A 的上下文，恢复进程 B 的上下文（CPU 寄存器和一些表格的当前指针）
• 用户态执行进程 B 代码
• 需要注意的是，当上下文切换之后，指令和数据快速缓存 cache 通常需要更新，使得执行速度降低

进程上下文切换的步骤：

• 决定是否做上下文切换
• 保存当前执行的进程上下文
• 采用合理的调度算法，选择一个处于就绪状态进程
• 恢复所选进程的上下文，将控制权交给所选进程

(2) 时机

• 正在执行的进程执行完毕
• 进入睡眠等待状态
• 执行进程中调用了P，原语
• 调用了 P 原语，从而因为资源不足而阻塞，调用 V 原语操作激活了等待资源的进程队列
• 执行中进程提出I/O请求
• 分时系统中时间片已经用完系统进程执行完毕，调度用户进程
• 就绪队列中某进程优先权高于当前执行的进程

(3) 进程调度性能评价

进程调度算法的评价方法，可以从定性和定量两个角度考虑：

定性衡量

• 调度的可靠性
• 调度的简洁性

定量衡量

• CPU 利用率
• 进程在队列中的等待时间与执行时间之比

(五) 调度算法

(1) 先到先服务调度（FCFS）

将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先后先服务的方式进行调度处理，这是一种最普遍和最简单的方法。

在没有特殊理由要优先调度某类作业或进程时，从处理的角度来看，FCFS 方式是一种最适合的方式，因为无论是直接追加或是取出一个队列元素，在操作上都是非常简单的，直观上看该算法在一般意义上是公平的，也就是说每个作业或者进程都按照他们在队列中等待的时间长短来决定他们是否优先享受服务，不过对于那些执行时间较短的作业或进程来说，如果他们在某些执行时间很长的作业或进程到达之后再到达，则他们将等待的时间会很长。

进程：P1、P2、P3

时间：24、3、3

如果按照 FCFS 执行，如下图

但是很显然，因为P1 执行时间很长、P2、P3 就需要等很久，在某种意义上，这也是不公平的

如果可能先将短的执行，是不是会更好呢，这就是我们后面想要讲的最短作业优先法

(2) 最短作业优先法（SJF）

将每个进程与其下一个CUP区间段相关联，当CPU可用时，它会赋给具有最短后续CPU区间的进程

A：两种方式

非抢占性：一旦一个进程开始执行就需完成该次任务

抢占性：如果新来的进程CPU区间段比当前进程的时间段小，则优先选择新进程。称为SRTF(Shorest Remaining Time First)

B：分析

最短专业优先法就是选择那些估计需要执行时间最短的作业投入执行，为他们创建进程和分配资源

直观上来说，采用这种调度算法可以使得系统在同一时间内处理的作业个数最多，从而吞吐量也就大于其他调度方式

但是其致命缺点就是对于一个有不断作业进入批处理系统来说，这种方式可能会使得那些长作业永远得不到被调度的机会

C：优先权调度

• 每个进程都有优先权具有最高优先权的进程分配给CPU
• SJF算法作为优先权算法的特例。优先权为下一个CPU区间的倒数。CPU区间越大，优先权越小
• 导致的问题：饥饿（starvation)——低优先权的进程可能永远也不会运行（无穷阻塞）
• 解决方案：老化(aging)——逐渐增加在系统中等待很长时间的进程的优先权

(3) 例题分析

A：题目

根据下表格，分别计算 FCFS、SJF 算法的平均等待时间

B：FCFS 方式

FCFS平均等待时间= (0＋(7-2)＋(11-4)＋(12-5)) / 4 = 4.75ms

C：SJF（非抢占式）

SJF平均等待时间 = (0 + (7-4)+(8-2) +(12-5))/4 =4ms

D：SJF（抢占式）

平均等待时间 = (9 + 1 + 0 +2) / 4 = 3

(3) 轮转法调度（RR）

A：基本概念

轮转法的基本思路是让每个进程在就绪队列中的等待时间与享受服务的时间成正比，也就是说将CPU的处理时间分成固定大小的时间片（10ms~100ms），如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则他将释放所占有的CPU，而排到就绪队列的末尾，等待下一次调度。同时进程调度程序又去调度当前就绪队列中的第1个进程或作业

• 只能调度分配可抢占资源：如CPU、内存、外存
• 作业调度不适用轮转法
• 时间片长度的确定：q = R / N_max

时间片长度的选择会直接影响系统的开销和响应时间，如果时间片长度过短，则调度程序剥夺处理器的次数过多，这将使进程上下文切换的次数也大大增加，从而加重系统开销，反过来如果时间片程度选择过长，比方说一个时间片能保证就去队列中所需要执行时间最长的进程能执行完毕，则轮转法又变成了原来先来先服务法

B：例题

进程：P1、P2、P3、P4

区间：53、17、68、24

时间片q＝20ms（毫秒）

使用轮转法的图示

甘特图为（时间片q＝20ms)

(4) 多级队列调度算法

多级队列调度算法将系统中不同类型或性质的就绪进程固定分配到不同的就绪队列中，每个就绪队列可以采用自己的调度算法；而在队列之间，通常采用固定优先权的抢占调度方式。这种调度算法可针对不同用户进程的需求，提供不同的调度策略

同时就绪队列分为：前台与后台

每个队列有自己的调度方法：

• 前台：RR 80％
• 后台：FCFS 20％

调度必须在队列之间完成

• 按优先权进行调度
• 按时间片进行调度

例如下图，上面的优先级高，分配的是系统的一些进程，下面一些优先级低，分配的就是一些普通的进程

(5) 多级反馈轮转调度（RRMF)

轮转法中，加入到就绪队列的进程有三种情况：

• 时间片用完
• I/O请求或进程互斥导致阻塞
• 新创建进程进入就绪队列

对这三种进程区别对待，采用不同的时间片或优先权，有望能进一步改善系统服务质量和效率

多级队列调度与多级反馈队列调度区别：

• 多级反馈队列调度中就绪队列的设置不是像多级队列调度一样按作业性质划分，而是按时间片的大小划分
• 多级队列调度中的进程固定在某一个队列中，而多级反馈队列调度中的进程不固定
• 多级队列调度中每个队列按作业性质不同而采用不同的调度算法，而多级反馈队列调度中除了个别队列外，均采用相同的调度算法

(6) 线性优先级调度（SRR）

线性优先级调度：采用两种队列进行服务：

某进程在 t1时刻被创建，在t时刻的优先级：P(t)=a*(t-t1)(t1<t<t1’) 在 t1` 时刻进入享受服务队列，在时刻 t，进程的优先级：P(t)=a(t-t1)+b(t-t1’)

何时进行队列间的调度： 新创建进程队列的头一个进程的优先权与享受服务队列中最后一个进程的优先权相等时享受队列为空

如果 b > a > 0，SRR --> FCFS 如果 a > b = 0，SRR --> RR

SRR是对FCFS和RR调度算法的折衷算法

(7) 最高响应比优先法（HRN）

最高响应优先法是对FCFS方式和SJF方式的综合平衡

响应比定义：R = (W + T) / T = 1 + W / T

T为该作业估计需要的执行时间，W为等待时间

(七) 实时调度

操作系统是实时系统中的重要组成部分之一，其处理和控制的正确性不仅仅取决于计算的逻辑结果，而且取决于计算和处理结果产生的时间

实时操作系统具有以下特点：

• 有限等待时间（决定性）
• 有限响应时间
• 用户控制
• 可靠性高
• 系统出错处理能力强

硬件实时（hard real-time）

• 系统需要在保证的时间内完成任务

软件实时(soft real-time)

• 系统要求关键进程比其他进程拥有更高的优先权。

实时操作系统具有以下功能：

• 进程或线程切换速度快
• 快速的外部中断响应能力
• 基于优先级的随时抢占性调度策略

(八) 总例题练习

1、以下哪些算法与作业的执行时间有关（C D）

A：优先级调度 B：RR C：SJF D：HRN E：FCFS

先说明对应算法是什么？

A：优先级调度、B：轮转法调度、C：最短作业优先法、D：最高响应比优先法、E：先到先服务调度

分析：

A. 优先级调度和作业的执行时间无关

B. 轮转法调度，每个时间片都是一样，和作业的预期执行时间并无关联

C. 最短作业优先法和预期执行时间有关，有比较时间大小的过程

D. 响应比=响应时间/要求服务的时间，和全过程的时间都有关系

E. 先来先服务，就是就绪队列顺序问题了，和时间无关

2、判断

作业调度是高级调度，进程调度是低级调度（√）

在各种作业调度算法中，SJF会使每个作业的等待时间最短（×）

在一个兼顾分时系统和批处理系统中，通常把终端作业称为前台作业，把批量作业称为后台作业（√）

3、设有三道作业，他们的提交时间及执行时间由下表给出：

(1) 计算在单道程序环境下，采用先来先服务调度算法和最短作业优先算法的平均周转时间

平均周转时间 = (2.0 + 2.9 + 3.2) / 3 = 2.7 ( 小时 )

(2) 计算在单道程序环境下，采用最短作业优先算法的平均周转时间

平均周转时间 = (2.0 + 3.4 + 1.6) / 3 = 2.3 ( 小时 )

(3) 计算在单道程序环境下，采用抢占式最短作业优先算法的平均周转时间

由于抢占的原因，所以列表格就不是很方便了，可以自己简单画一个流程图

8.5 —（0.7s）① — 9.2 — （0.2s）② — 9.4 —（0.5s）③ — 9.9 — （1.3s）① — 11.2 — （1.4s）② — 12.6

平均周转时间 = ((11.2 - 8.5) + (12.6 - 9.2) + (9.9 - 9.4)) / 3 = 2.2

抢占式没对答案，如果有错欢迎私聊我改正

如果还要求，求响应比一类的，看着表格直接代入公式即可

声明：本文内容均为手打修改整理所得，配图非原创（前几篇操作系统相关都是原创素材、内容），参考慕课公开课、清华大学出版书籍、吉大珠海学院等等，侵删

结尾

邮箱：ideal_bwh@163.com

如果能帮到你的话，那就来关注我吧！

如果您更喜欢微信文章的阅读方式，可以关注我的公众号

如果您更加喜欢PC端的阅读方式，可以访问我的个人博客

域名：www.ideal-20.cn