大家好，我是讯享网，很高兴认识大家。



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

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

小结：

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

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

作业调度方式分为 4 级

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

交换调度（中级调度）

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

线程调度

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

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

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

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

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

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

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

响应时间：有快的响应时

注：_ 代表下标

作业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、记录所有进程的运行状况（静态和动态）

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

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

进程上下文切换的步骤：

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

定性衡量

定量衡量

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

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

进程：P1、P2、P3

时间：24、3、3

如果按照 FCFS 执行，如下图

讯享网

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

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

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

A：两种方式

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

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

B：分析

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

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

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

C：优先权调度

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

A：基本概念

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

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

B：例题

进程：P1、P2、P3、P4

区间：53、17、68、24

时间片q＝20ms（毫秒）

使用轮转法的图示

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

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

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

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

调度必须在队列之间完成

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

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

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

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

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

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

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

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

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

最高响应优先法是对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

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

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

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

邮箱：

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

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

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

域名：www.ideal-20.cn