操作系统原理第五章：CPU调度

柔光的暖阳◎ 2023-07-15 06:00 11阅读 0赞

### 目录 ###

*  1 CPU调度基本概念
 *   *  1.1 基本概念
     *  1.2 CPU调度的时机
     *  1.3 CPU调度方案
 *  2 CPU调度算法
 *   *  2.1 先来先服务(FCFS)
     *  2.2 短作业优先(SJF)
     *  2.3 优先级
     *  2.4 RR时间片轮转
     *  2.5 多级队列和多级反馈队列

# 1 CPU调度基本概念 #

## 1.1 基本概念 ##

CPU调度就是就从就绪队列中选择一个进程来分配CPU的过程，进行CPU调度的原因是为了实现多道，使得CPU有更高的利用率，之所以进程能够进行CPU调度是因为进程的特点，进程执行过程中分为两个脉冲一个是**CPU脉冲 (CPU Burst)**，一个是 **I/O 脉冲 (I/O Burst)**，即在 CPU 上执行和等待 I/O ，进程的执行以 CPU 脉冲开始，其后跟着 I/O 脉冲，进程的执行就是在这两个状态之间进行转换，如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70]  
观察CPU脉冲的统计后发现，CPU 脉冲的分布，在系统中存在许多短 CPU 脉冲，只有少量的长 CPU 脉冲，比如 I/O 型作业具有许多短 CPU 脉冲，而 CPU 型作业则会有几个长 CPU 脉冲，这个分布规律对CPU 调度算法的选择是非常重要的，下图是对CPU脉冲的统计直方图，横轴是时间，竖轴是频率，可以发现频率在`0~8ms`的高频脉冲是比较多的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 1]

## 1.2 CPU调度的时机 ##

当CPU空闲时，OS就选择内存中的某个就绪进程，并给其分配CPU，以下是进程状态转换图，当某个进程从`running`状态离开时，就代表当前CPU就空闲了，图中红色和蓝色的箭头都代表着会发生CPU调度：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 2]  
CPU的调度可能发生在以下情况：

*  **从运行转到等待 (Switches from running to waiting state)**：非抢占式调度；
 *  **从运行转到就绪 (Switches from running to ready state)**：抢占式调度，时间片到；
 *  **从等待转到就绪 (Switches from waiting to ready)**：抢占式调度，若某个在就绪队列的进程优先级较高，则会抢占CPU，所以是抢占式调度；
 *  **终止运行 (Terminates)**：非抢占式调度。

## 1.3 CPU调度方案 ##

CPU调度方案分为以下两种：

*  **非抢占方式 (nonpreemptive)**：把处理机分配给某进程后，便让其一直执行，直到该进程完成或发生某事件而被阻塞时，才把处理机分配给其它进程，不允许其他进程抢占已经分配出去的处理机，其优点是实现简单、系统开销小，适用于大多数批处理系统环境，缺点是难以满足紧急任务的要求，不适用于实时、分时系统要求
 *  **抢占方式（Preemptive mode）**：允许调度程序根据某个原则，去停止某个正在执行的进程，将处理机重新分配给另一个进程

对于抢占方式，抢占有如下的原则：

*  **时间片原则**：各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。这个原则适用于分时系统；
 *  **优先权原则**：通常对一些重要的和紧急的进程赋予较高的优先权。当这种进程进入就绪队列时，如果其优先权比正在执行的进程优先权高，便停止正在执行的进程，将处理机分配给优先权高的进程，使之执行；
 *  **短作业优先原则**：当新到达的作业比正在执行的作业明显短时，将暂停当前长作业的执行，将处理机分配给新到的短作业，使之执行。

# 2 CPU调度算法 #

设计CPU调度算法的性能指标有如下几点：

*  **CPU利用率**：使CPU尽可能的忙碌；
 *  **吞吐量**：单位时间内运行完的进程数；
 *  **周转时间**：进程从提交到运行结束的全部时间 ；
 *  **等待时间**：进程在就绪队列中等待调度的时间片总和；
 *  **响应时间** ：从进程提出请求到首次被响应的时间段，在分时系统环境下不是输出完结果的时间

> 注：调度算法影响的是等待时间 ， 而不能影响进程真正使用CPU 的时间和 I/O 时间

## 2.1 先来先服务(FCFS) ##

先来先服务 (First-Come-First-Served)，其算法思想和字面意思一样，就是**先到来的进程，先被调度**，这是最简单的调度算法，FCFS属于非抢占方式，一旦一个进程占有处理机，它就一直运行下去，直到该进程完成或者因等待某事件而不能继续运行时才释放处理机。FCFS 算法易于实现，表面上很公平 ，实际上有利于长作业，不利于短作业；有利于 CPU 繁忙型，不利于 I/O 繁忙型，可以看下面的例子。

假设有  P 1 P\_1 P1， P 2 P\_2 P2， P 3 P\_3 P3 三个进程，所需的CPU脉冲时间分别为24，3，3，如下表：

<table> 
 <thead> 
 <tr> 
 <th>进程</th> 
 <th>CPU脉冲时间</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> P 1 P_1 P1</td> 
 <td>24</td> 
 </tr> 
 <tr> 
 <td> P 2 P_2 P2</td> 
 <td>3</td> 
 </tr> 
 <tr> 
 <td> P 3 P_3 P3</td> 
 <td>3</td> 
 </tr> 
 </tbody> 
</table>

现设三个进程到来的顺序是  P 1 P\_1 P1， P 2 P\_2 P2， P 3 P\_3 P3，那么该调度的Gantt图如下：  
![在这里插入图片描述][20200315205128644.png]  
各个进程的等待时间如下表：

平均等待时间为  t = 0 + 24 + 27 3 = 17 t=\\frac\{0 + 24 + 27\}\{3\}=17 t=30\+24\+27=17。

现假设三个进程到来的顺序是  P 2 P\_2 P2， P 3 P\_3 P3， P 1 P\_1 P1，那么该调度的Gantt图如下：  
![在这里插入图片描述][20200315205538192.png]  
各进程的等待时间如下表：

平均等待时间为  t = 6 + 0 + 3 3 = 3 t=\\frac\{6 + 0 + 3\}\{3\}=3 t=36\+0\+3=3。

由上面两个例子可以看出，在先来先服务算法中，进程到来的次序对平均等待时间的影响是很大的，这里有个专业名词叫做 **护航效应 (Convoy effect)**

> **护航效应 (Convoy effect)**：
> 
>  *  假设有一个CPU进程和许多I/O型进程
>  *  当CPU进程占用CPU运行时， I/O型进程可能完成了其I/O操作，回到就绪队列等待CPU， I/O设备空闲
>  *  CPU进程释放CPU后， I/O型进程陆续使用CPU，并很快转为I/O操作，CPU空闲

在这种情况下，CPU和 I/O 设备并没有得到有效的利用。

## 2.2 短作业优先(SJF) ##

短作业优先 (Shortest-Job-First)，其算法思想是关联到每个进程下次运行的 CPU 脉冲长度，调度最短的进程，由于进程是不断调入到就绪队列中的，其整个就绪队列中的最短作业，也是动态变化的，此时就要面临一个问题了，若现在到来了一个所需CPU脉冲时间最短的一个进程，那么是让当前执行的进程让位，还是等当前进程执行完再执行，所以有如下两种策略：

*  **非抢占式调度**：一旦进程拥有 CPU ， 它的使用权限只能在该 CPU 脉冲结束后让出；
 *  **抢占式调度** ：发生在有比当前进程剩余时间片更短的进程到达时，也称为最短剩余时间优先调度

短作业优先SJF算法是最优的，因为对一组指定的进程而言，它给出了最短的平均等待时间，如下面的例子：

现有四个进程  P 1 P\_1 P1， P 2 P\_2 P2， P 3 P\_3 P3， P 4 P\_4 P4，他们的到达时间和所需CPU脉冲时间如下表：

<table> 
 <thead> 
 <tr> 
 <th>进程</th> 
 <th>到达时间</th> 
 <th>CPU脉冲时间</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> P 1 P_1 P1</td> 
 <td>0</td> 
 <td>7</td> 
 </tr> 
 <tr> 
 <td> P 2 P_2 P2</td> 
 <td>2</td> 
 <td>4</td> 
 </tr> 
 <tr> 
 <td> P 3 P_3 P3</td> 
 <td>4</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td> P 4 P_4 P4</td> 
 <td>5</td> 
 <td>4</td> 
 </tr> 
 </tbody> 
</table>

若采用抢占式的调度，其调度Gantt图如下：  
![在这里插入图片描述][20200315211403893.png]  
平均等待时间为  t = 9 + 1 + 0 + 2 4 = 3 t=\\frac\{9 + 1 + 0 + 2\}\{4\}=3 t=49\+1\+0\+2=3。

若采用非抢占式的调度，其调度Gantt图如下：  
![在这里插入图片描述][20200315211626608.png]  
平均等待时间为  t = 0 + 6 + 3 + 7 4 = 4 t=\\frac\{0 + 6 + 3 + 7\}\{4\}=4 t=40\+6\+3\+7=4。

--------------------

虽说短作业优先算法是最优的算法，但是实际上在实现起来确实很难的，因为要不断的统计各个进程所需的CPU脉冲时间，这显然实现难度高，就算能实现，其开销也会非常大，所以实际应用中是估计进程所需时间，可以通过先前的CPU脉冲长度及计算指数均值进行估计。

综上所述，采用SJF有利于系统减少平均周转时间,提高系统吞吐量，一般情况下SJF调度算法比FCFS调度算法的效率要高一些, 但实现相对要困难些。如果作业的到来顺序及运行时间不合适，会出现**饥饿现象**，例如，系统中有一个运行时间很长的作业JN，和几个运行时间小的作业，然后，不断地有运行时间小于JN的作业的到来，这样，作业JN就因得不到调度而饿死。另外，作业运行的估计时间也有问题。

## 2.3 优先级 ##

上面所讲的短作业优先算法实际上是优先级算法的一个特例，短作业优先算法将作业所需时间定为衡量优先级的量，表示优先级的量一般为一个整数，这里假定越小的数优先级越高，下面  P 1 P\_1 P1， P 2 P\_2 P2， P 3 P\_3 P3， P 4 P\_4 P4， P 5 P\_5 P5 五个进程的调度状况如下：

<table> 
 <thead> 
 <tr> 
 <th>进程</th> 
 <th>CPU脉冲时间</th> 
 <th>优先级</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> P 1 P_1 P1</td> 
 <td>10</td> 
 <td>3</td> 
 </tr> 
 <tr> 
 <td> P 2 P_2 P2</td> 
 <td>1</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td> P 3 P_3 P3</td> 
 <td>2</td> 
 <td>4</td> 
 </tr> 
 <tr> 
 <td> P 4 P_4 P4</td> 
 <td>1</td> 
 <td>5</td> 
 </tr> 
 <tr> 
 <td> P 5 P_5 P5</td> 
 <td>5</td> 
 <td>2</td> 
 </tr> 
 </tbody> 
</table>

根据优先级，其调度顺序为  P 2 P\_2 P2， P 5 P\_5 P5， P 1 P\_1 P1， P 3 P\_3 P3， P 4 P\_4 P4，平均等待时间为 8.2 。

那么进程的优先级如何确定呢？通常在进程创建时确定，且在整个生命期中保持不变，这种叫**静态优先级**，静态优先级就会出现饥饿问题，即某个进程若优先级非常低，它几乎永远得不到CPU调度。

> 一个很有意思的例子：当MIT的IBM7094机器于1973年关掉时，人们发现一个于1967年提交的一个低优先权的进程还没有得到运行。

解决方法是**老化**，根据进程等待时间的延长提高其优先数，也就是**动态优先级**，优先级会根据等待时间不断调整。考虑改变优先级的因素通常有进程的等待时间，已使用CPU的时间，资源使用情况等。

## 2.4 RR时间片轮转 ##

RR (Round Robin)，这个算法主要用在分时系统里，这个算法的思想是每个进程将得到小单位的 CPU 时间 (时间片)，通常为 10-100 毫秒 。时间片用完后，该进程将被抢占并插入就绪队列末尾。

例如有四个进程  P 1 P\_1 P1， P 2 P\_2 P2， P 3 P\_3 P3， P 4 P\_4 P4 如下表，设时间片大小为 20：

<table> 
 <thead> 
 <tr> 
 <th>进程</th> 
 <th>CPU脉冲时间</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> P 1 P_1 P1</td> 
 <td>53</td> 
 </tr> 
 <tr> 
 <td> P 2 P_2 P2</td> 
 <td>17</td> 
 </tr> 
 <tr> 
 <td> P 3 P_3 P3</td> 
 <td>68</td> 
 </tr> 
 <tr> 
 <td> P 4 P_4 P4</td> 
 <td>24</td> 
 </tr> 
 </tbody> 
</table>

其调度Gantt图如下：  
![在这里插入图片描述][20200315214436798.png]  
一般来说，RR的平均周转时间比SJF长，但响应时间要短一些。

对于时间片轮转算法，确定时间片大小是非常重要的，若时间片过大，则每个进程都能在单个时间片能完成，则时间片轮转等价于先来先服务算法，若时间片过小，则各个进程要频繁的切换，造成大量的资源开销。

## 2.5 多级队列和多级反馈队列 ##

多级队列的意思是把进程根据其某种属性进行分类，每一类的进程都会组成一个就绪队列，也就是说在操作系统中会有多个就绪队列，每个进程固定的处在自己所属的队列中，对于不同的队列，也可以有自己专属的调度算法，那么此时就要进行队列的调度，可以给每个队列设置不同的优先级，若是固定优先级，则会产生饥饿问题。那么另一种解决方案就是基于时间片的算法，给定 时间片调度，即个队列得到一定的 CPU 时间，进程在给定时间内执行，如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 3]  
若某个进程在一个优先级较低的队列中，那么它就会一直处于饥饿状态，解决方案是多级反馈队列调度，存在多个就绪队列，具有不同的优先级，各自按时间片轮转法调度，它与多级队列的不同是它**允许进程在队列之间移动**，当一个进程执行完一个完整的时间片后被抢占处理器，**被抢占的进程优先级降低一级而进入下级就绪队列，如此继续，直至降到进程的基本优先级**。而一个进程从阻塞态变为就绪态时要提高优先级，最后会将I/O型和交互式进程留在较高优先级队列，如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70]: /images/20230528/dbb46d790c2843609f1f58b6b0745793.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 1]: /images/20230528/35b1586ce483424f98e3326a5e19cc8a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 2]: /images/20230528/1016486715b84e75a0a7d5157f1acac4.png
[20200315205128644.png]: /images/20230528/6ca2871955114ec48957fc0f64e77096.png
[20200315205538192.png]: /images/20230528/bfb49da93c244fec9d432baecfa3346e.png
[20200315211403893.png]: /images/20230528/d4a8b99633044724b220f129c9124494.png
[20200315211626608.png]: /images/20230528/c3ee91ff07c244118f77b7dafff9f11b.png
[20200315214436798.png]: /images/20230528/0cde9d834b154da192db0fdce1337ea4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 3]: /images/20230528/7bcf21b2ec9243cfad1cc390ceb44da5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 4]: /images/20230528/1297b7f5d5b64635a9aba70f47bd890b.png