操作系统学习笔记第三章：处理机调度与死锁（王道考研）

墨蓝 2022-10-08 00:53 262阅读 0赞

> 本文章基于网课： [2019 王道考研 操作系统][2019 _]  
> 考试复习推荐资料：[操作系统复习总结 - 百度文库 (baidu.com)][- _ _baidu.com]
> 
> --------------------
> 
> 需要相关电子书的可以关注我的公众号`BaretH`后台回复操作系统  
> ![image-20210616202753852][]  
> [第一章：操作系统概述][Link 1]  
> [第二章：进程管理][Link 2]  
> 后续章节陆续推出…

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

### 三、处理机调度与死锁 ###

*   *  3.1 处理机调度
     *   *  3.1.1 什么是调度
         *  3.1.2 高级、中级、低级调度
         *  3.1.3 进程调度的时机、切换、过程
     *  3.2 调度算法的性能指标
     *  3.3 调度算法
     *   *  3.3.1 先来先服务算法
         *  3.3.2 短作业优先算法
         *  3.3.3 高响应比优先算法
         *  3.3.4 时间片轮转算法
         *  3.3.5 优先级调度算法
         *  3.3.6 多级反馈队列调度算法
         *  总结
     *  3.4 死锁
     *   *  3.4.1 什么是死锁
         *  3.4.2 死锁、饥饿、死循环区别
         *  3.4.3 死锁产生的必要条件
         *  3.4.4 什么时候发生死锁
         *  3.4.5 死锁处理策略
         *  \--- 预访死锁
         *  \--- 避免死锁
         *  \--- 死锁检测和解除

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

## 3.1 处理机调度 ##

![image-20210607114140294][]

### 3.1.1 什么是调度 ###

![image-20210406144658935][]

### 3.1.2 高级、中级、低级调度 ###

1️⃣ **高级调度**

![image-20210607113932723][]

2️⃣ **中级调度**

![image-20210607114006483][]

3️⃣ **低级调度**

![image-20210607114022249][]

**三层调度的联系、对比**：

![image-20210607114104369][]

### 3.1.3 进程调度的时机、切换、过程 ###

![image-20210607142454694][]

1️⃣ **进程调度的时机**：

![image-20210607141952128][]

![image-20210607142213592][]

2️⃣ **进程的切换与过程**

![image-20210607142403309][]

3️⃣ **进程调度的方式**

> 所谓进程调度方式，是指当某个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要处理，即有优先权更高的进程进入就绪队列，此时应如何分配处理机。通常有以下两种进程调度方式：

![image-20210607142312014][]

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

## 3.2 调度算法的性能指标 ##

> 不同的调度算法具有不同的特性，在选择调度算法时，必须考虑算法的特性。为了比较处理机调度算法的性能，人们提出了很多评价准则，下面介绍其中主要的几种：
> 
> ![image-20210607143942705][]

**CPU利用率**

![image-20210607143107502][]

**系统吞吐量**

![image-20210607143145955][]

**周转时间**

![image-20210607143346062][]

![image-20210607143405565][]

**等待时间**

![image-20210607143445486][]

**响应时间**

![image-20210607143454293][]

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

## 3.3 调度算法 ##

操作系统中存在多种调度算法，有的调度算法适用于作业调度，有的调度算法适用于进程调度，有的调度算法两者都适用。下面介绍几种常用的调度算法：

![image-20210614134416596][]

### 3.3.1 先来先服务算法 ###

![image-20210607144108757][]

示例：

![image-20210607144131183][]

### 3.3.2 短作业优先算法 ###

![image-20210607144314793][]

**非抢占式短作业优先算法示例**：

![image-20210607144605511][]

**抢占式短作业优先算法示例**：

![image-20210520185735870][]![image-20210607144800025][]

**注意**：

![image-20210607144912183][]

### 3.3.3 高响应比优先算法 ###

> FCFS算法是在每次调度的时候选择一个等待时间最长的作业（进程）为其服务。但是没有考虑到作业的运行时间，因此导致了对短作业不友好的问题；SJF算法是选择一个执行时间最短的作业为其服务。但是又完全不考虑各个作业的等待时间，因此导致了对长作业不友好的问题，甚至还会造成饥饿问题。
> 
> 能不能设计一个算法，即考虑到各个作业的等待时间，也能兼顾运行时间呢？这就引入了高响应比优先算法

![image-20210607145246648][]

**示例**：

![image-20210607145307977][]

### 3.3.4 时间片轮转算法 ###

![image-20210520200621378][]

**示例**：

![image-20210520200329376][]

![image-20210520200502700][]

![image-20210520200546274][]

### 3.3.5 优先级调度算法 ###

![image-20210520201154350][]

**示例**：

![image-20210520200758452][]

![image-20210520200843233][]

**补充**：

![image-20210520201128101][]

### 3.3.6 多级反馈队列调度算法 ###

> FCFS算法的优点是公平；SJF算法的优点是能尽快处理完短作业，平均等待/周转时间等参数很优秀；时间片轮转调度算法可以让各个进程得到及时的响应；优先级调度算法可以灵活地调整各种进程被服务的机会。
> 
> 能否对其他算法做个折中杈衡？得到一个综合表现优秀平衡的算法呢——多级反馈队列调度算法

![image-20210520201726465][]

**示例**：

![image-20210520201506732][]

### 总结 ###

![image-20210612090807007][]

![image-20210520201814784][]

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

## 3.4 死锁 ##

![image-20210607203814274][]

### 3.4.1 什么是死锁 ###

`死锁`指在并发环境下，多个进程在运行过程中因争夺资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象；发生死锁后若无外力干涉，这些进程都无法向前推进。

**死锁和阻塞的区别**：阻塞是由于资源不足引起的排队等待现，死锁的进程处于阻塞状态，但仅依靠自己，无法继续运行。

### 3.4.2 死锁、饥饿、死循环区别 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTczNDA0_size_16_color_FFFFFF_t_70_pic_center]

### 3.4.3 死锁产生的必要条件 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTczNDA0_size_16_color_FFFFFF_t_70_pic_center 1]

### 3.4.4 什么时候发生死锁 ###

![image-20210521190759725][]

### 3.4.5 死锁处理策略 ###

![image-20210614140151232][]

1.  **预防死锁**：破坏死锁产生的四个必要条件中的一个或几个
2.  **避免死锁**：用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
3.  **死锁的检测和解除**：允许死锁的发生，不过操作系统会负责检测岀死锁的发生，然后采取某种措施解除死锁

### — 预访死锁 ###

> \*\*预防死锁 \*\*即破坏死锁产生的四个必要条件中的一个或几个
> 
> ![image-20210614140244421][]

![image-20210614140344590][]

![image-20210614140457837][]

![image-20210614140517759][]

![image-20210614140538682][]

### — 避免死锁 ###

> **避免死锁** 即用某种方法防止系统进入不安全状态，从而避免死锁，通常采用`银行家算法`
> 
> ![image-20210614140558845][]

1️⃣ **什么是安全序列**

假定某系统有n个进程并发执行，对于某个时刻T0，划分系统安全和不安全的标准如下：

系统能够按照某种进程顺序<P1,P2,…,Pn>执行，当轮到每个进程Pi执行时，都能满足该进程对资源的最大需求，则该系统处于安全状态，否则为不安全状态，其中<P1,P2,…,Pn>称为安全序列

2️⃣ **安全序列、不安全状态、死锁的联系**

*  所谓`安全序列`，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个
 *  如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了`不安全状态`。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况
 *  系统处于`安全状态`，则一定不会发生`死锁`；如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）
    
    因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想

3️⃣ **银行家算法**

![image-20210614140922703][]

![image-20210614140824462][]

![image-20210614140844647][]

### — 死锁检测和解除 ###

![image-20210614141518884][]

![image-20210614141440296][]

1️⃣ **死锁的检测**

![image-20210614141540388][]

![image-20210607204719526][]

![image-20210607204708036][]

2️⃣ **死锁的解除**

![image-20210614141623029][]

[2019 _]: https://www.bilibili.com/video/BV1YE411D7nH?from=search&seid=16840790228518028454
[- _ _baidu.com]: https://wenku.baidu.com/view/18cb95d626fff705cc170af5.html
[image-20210616202753852]: /images/20221005/95199ff71dbf418fa9f0ad03a88d69b0.png
[Link 1]: https://blog.csdn.net/qq_45173404/article/details/117965896
[Link 2]: https://bareth.blog.csdn.net/article/details/118035716
[image-20210607114140294]: /images/20221005/9cefb19ad2f74bffb756cb01c5bd47a0.png
[image-20210406144658935]: /images/20221005/50e1ce12d88841ac9f201b38fbab4b1b.png
[image-20210607113932723]: /images/20221005/8794679672114964b4a0f977c8aef308.png
[image-20210607114006483]: /images/20221005/ee6eb8e022bc45f4a952c9bf539d11ee.png
[image-20210607114022249]: /images/20221005/5497cf1c3ccf4a7ba593e8e2981130e2.png
[image-20210607114104369]: /images/20221005/53f5b43afed6488aa108fb0554cc4a58.png
[image-20210607142454694]: /images/20221005/c41e9943108a4824bda692be027def27.png
[image-20210607141952128]: /images/20221005/8fac6d992380448aa7c8be7e0482bc49.png
[image-20210607142213592]: /images/20221005/164637fc024d49379e984548f81b7509.png
[image-20210607142403309]: /images/20221005/b4b1cb4a58f845e7a026c14a8d5b33c6.png
[image-20210607142312014]: /images/20221005/4e6dcdcbd2844642a0eee95c890c965a.png
[image-20210607143942705]: /images/20221005/29c33fbf0c9c4263869a7876310137c5.png
[image-20210607143107502]: /images/20221005/10f71abf2efa4a6f867424c3fa1fc735.png
[image-20210607143145955]: /images/20221005/0871dec819ad418e96e129de716e00c2.png
[image-20210607143346062]: /images/20221005/3d890a7d87f04fa0b07e6fff8576c800.png
[image-20210607143405565]: /images/20221005/d28d7bdde17040ba8714f6a9a8218613.png
[image-20210607143445486]: /images/20221005/782eb6bcf59945378081cc12065196ac.png
[image-20210607143454293]: /images/20221005/997b4ac031fe4c82a3a871af7616cc23.png
[image-20210614134416596]: /images/20221005/cf8737b95131491884a870f23d9a033f.png
[image-20210607144108757]: /images/20221005/e2c7b249336c4daa87489fef596c6962.png
[image-20210607144131183]: /images/20221005/70b58c5685184b98abcd98ee451adeb5.png
[image-20210607144314793]: /images/20221005/5d2c96cebe5347e9a4eb9232fa307811.png
[image-20210607144605511]: /images/20221005/a3022e948f404744bf9b18bc8ee34964.png
[image-20210520185735870]: https://img-blog.csdnimg.cn/img_convert/728842268269a09fe11f2df41842bf06.png
[image-20210607144800025]: /images/20221005/ba11d9c48a484be58087fe50c84c2707.png
[image-20210607144912183]: /images/20221005/4cffbf09754c4b5bbe63249db67cc396.png
[image-20210607145246648]: /images/20221005/0d8b4201027b4199a5b6152bc1078e1e.png
[image-20210607145307977]: /images/20221005/142adac18b5543b8b3a656ad7bc36097.png
[image-20210520200621378]: /images/20221005/68ab23415ac34a3b90f3559fe5a3bc4d.png
[image-20210520200329376]: /images/20221005/a23dc79ae174434199ab639642103396.png
[image-20210520200502700]: /images/20221005/e193c50e835f43408f41680e077218ad.png
[image-20210520200546274]: /images/20221005/cecf774adc08457f83cf5de12593c51a.png
[image-20210520201154350]: /images/20221005/1ee831b8326043ffa567baf9f0ac71c4.png
[image-20210520200758452]: /images/20221005/a0199c7283c94158b7f370840addf945.png
[image-20210520200843233]: /images/20221005/53cf94f0c2b24dbca41b2bd9b46b49b9.png
[image-20210520201128101]: /images/20221005/7629257bbadf4241ba85053f3c9cde2e.png
[image-20210520201726465]: /images/20221005/15611be1111848eea5d4cb078410d456.png
[image-20210520201506732]: /images/20221005/db3c1ccf28154b8ebd5794c3d0e6b683.png
[image-20210612090807007]: /images/20221005/b7706b4365bf42cdac54b30e12676705.png
[image-20210520201814784]: /images/20221005/326726ab1b4546e3a5c46bcf9945b184.png
[image-20210607203814274]: /images/20221005/4165fc7de0654e32b32da08c4426531b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTczNDA0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221005/ed20a000950f490d9e05604c2c5697f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MTczNDA0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221005/6dc54e650566483fb1e56201ed31d16c.png
[image-20210521190759725]: /images/20221005/d8144bc06ee3492c998ec282945ec33c.png
[image-20210614140151232]: /images/20221005/ed73e4bc81c54ba4a8a2d99b7e624194.png
[image-20210614140244421]: /images/20221005/edac517058304af0bc4aaf9f8f53b0f5.png
[image-20210614140344590]: /images/20221005/672d94d9ea344723a99334ed875a5e61.png
[image-20210614140457837]: /images/20221005/9442f5312a304249b6cab34c1eb7341d.png
[image-20210614140517759]: /images/20221005/6776796b5c4943a0b7c93e38ec99624a.png
[image-20210614140538682]: /images/20221005/3215abd5b61f492d9d6533a7e7cd6ab5.png
[image-20210614140558845]: /images/20221005/42fe03fcf3f2434f965299dd47841c0a.png
[image-20210614140922703]: /images/20221005/d63f0de7f74a4765a1dbc33b1565ca3a.png
[image-20210614140824462]: /images/20221005/aeef117e3928487baec7b92e0340b316.png
[image-20210614140844647]: /images/20221005/969680358a494ea08c5a54c229af6568.png
[image-20210614141518884]: /images/20221005/1af925818a46446ba62fbadb4dc06ba1.png
[image-20210614141440296]: /images/20221005/a7e5a1106d4a4af883b7bffd8cbe2dc5.png
[image-20210614141540388]: /images/20221005/bb725674ced74f5c8914fcfa8993fe74.png
[image-20210607204719526]: /images/20221005/fb14afcba27f401daf61c79514004ffc.png
[image-20210607204708036]: /images/20221005/555523eda00c424db34fb0586ae2b7d1.png
[image-20210614141623029]: /images/20221005/f1b27780a2bb466cbd2408241746873c.png