2.2.3操作系统（时间片轮转优先级调度算法多级反馈队列）

左手的ㄟ右手 2023-10-01 21:36 30阅读 0赞

**目录**

调度算法

1.时间片轮转( RR, Round-Robin )

2.优先级调度算法

1. 非抢占式优先级调度算法

2. 抢占式优先级调度算法

3.思考

4.多级反馈队列

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

> ![6c077b7a8d9e4ee8a2176b4d2f267b7e.png][] 个人主页：[个人主页][Link 1]  
> ![78ebf3e975d74a4ab1d20c57ee7b2791.png][] 系列专栏：[操作系统][Link 2]

###  ###

## 调度算法    ##

### 1.时间片轮转( RR, Round-Robin ) ###

例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用**时间片轮转**调度算法，分析时间片大小分别是2、5时的进程运行情况。

**常用于分时操作系统，更注重“响应时间”，因而此处不计算周转时间**

**1. 时间片大小为2**

![ca6e65086f804ea0b420e6d2b05c8511.png_pic_center][]

![在这里插入图片描述][e170b43c59b842bbb04e1f2c8c5c7b08.png_pic_center]

![在这里插入图片描述][15a43000e9964c18bee02d1b8f3e6dca.png_pic_center]

**2. 时间片大小为5**

![在这里插入图片描述][cedee8e9a0b34629b3fa5bebc184f59f.png_ppic_center]

如果**时间片太大**，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法**退化为先来先服务**调度算法，并且**会增大进程响应时间**。因此**时间片不能太大**。

另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境），因此**如果时间片太小**，会导致**进程切换过于频繁**，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见**时间片也不能太少**

![在这里插入图片描述][b86658083bfe494396c9d39ca866e76c.png_pic_center]

###  ###

### 2.优先级调度算法 ###

#### 1. 非抢占式优先级调度算法 ####

例题：各进程到达就绪队列的时间、需要的运行时间、进程优先数如下表所示。使用**非抢占式**的**优先级**调度算法，分析进程运行情况。（注：**优先数**越大，**优先级**越高）

![在这里插入图片描述][2f5b2e97283f449dbcd04bc1bc20a976.png_pic_center]

#### 2. 抢占式优先级调度算法 ####

例题：各进程到达就绪队列的时间、需要的运行时间、进程优先数如下表所示。使用**抢占式**的**优先级**调度算法，分析进程运行情况。（注：**优先数**越大，**优先级**越高）

![在这里插入图片描述][bf81e4c5ae4b4cd493853ba1917dca3a.png_pic_center]

*  就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置。
 *  根据优先级是否可以动态改变，可将优先级分为**静态优先级**和**动态优先级**两种。  
    ①、 **静态优先级** ：创建进程时确定，之后一直不变。  
    ②、 **动态优先级** ：创建进程时有一个初始值，之后会根据情况动态地调整优先级。
 *  **I/O设备和CPU可以并行工作。如果优先让I/O繁忙型进程优先运行的话，则越有可能让I/O设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升**

![在这里插入图片描述][dd180c5a668b49d6ab9fff6b8287f996.png_pic_center]

![在这里插入图片描述][eaf752526695489b991945a01a8f8e73.png_pic_center]

### 3.思考 ###

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

### 4.多级反馈队列 ###

例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用**多级反馈队列**调度算法，分析进程运行的过程

![在这里插入图片描述][864de455e6b447fa8ae14da7b1bb4ca3.png_pic_center]

![在这里插入图片描述][4087d97ef5eb42ffb8bb57c2c5f3efb0.png_pic_center]

![在这里插入图片描述][8ec4f5b31b2c43e19f1a4fcc4b637bae.png_pic_center]

![在这里插入图片描述][3a800ca7cc144f0e9a99dd703bfab19b.png_pic_center]

![在这里插入图片描述][0efec1dbb3664a588c53675488663af1.png_pic_center]

![在这里插入图片描述][ca2e21370dac4d03a6cdab0c5b9d63bb.png_pic_center]

![在这里插入图片描述][a0b2f73695604a11a441e18286610b9c.png_pic_center]

![在这里插入图片描述][62d322bad2fb4978b592235919fddb92.png_pic_center]

![在这里插入图片描述][d98a164c2bcd441c8493b83fc988b18e.png_pic_center]

![在这里插入图片描述][dc093b01dca043b6a0aa9715fefa4c44.png_pic_center]

![在这里插入图片描述][56605b349f92411eb07d6fc727b16f35.png_pic_center]

![在这里插入图片描述][9c0b8dd80f9949a9a4c2c595c1f5cea0.png_pic_center]

![在这里插入图片描述][760638d19e9a449fb2161f5c2b05d35d.png_pic_center]

![在这里插入图片描述][f2a6b7f5ac054d769e03884ef3bb7d53.png_pic_center]

![在这里插入图片描述][a11fcf1202524741b02b85a779320d7f.png_pic_center]

![在这里插入图片描述][974345f9476a430ab328189f530ddae0.png_pic_center]

![在这里插入图片描述][e7e13f2477a348a6b8233a4321d75e37.png_pic_center]

![在这里插入图片描述][92ebc7a2611c49a8a58601b6d1a402a4.png_pic_center]

注：比起早期的批处理操作系统来说，由于计算机造价大幅降低，因此之后出现的交互式操作系统（包括分时操作系统、实时操作系统等）更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也能较好地满足**交互式系统**的需求。因此这三种算法适合用于交互式系统。（比如UNIX使用的就是多级反馈队列调度算法）

###  ###

[6c077b7a8d9e4ee8a2176b4d2f267b7e.png]: https://img-blog.csdnimg.cn/6c077b7a8d9e4ee8a2176b4d2f267b7e.png
[Link 1]: https://blog.csdn.net/Javascript_tsj?type=blog
[78ebf3e975d74a4ab1d20c57ee7b2791.png]: https://img-blog.csdnimg.cn/78ebf3e975d74a4ab1d20c57ee7b2791.png
[Link 2]: https://blog.csdn.net/javascript_tsj/category_11676356.html?spm=1001.2014.3001.5482
[ca6e65086f804ea0b420e6d2b05c8511.png_pic_center]: https://img-blog.csdnimg.cn/ca6e65086f804ea0b420e6d2b05c8511.png#pic_center
[e170b43c59b842bbb04e1f2c8c5c7b08.png_pic_center]: https://img-blog.csdnimg.cn/e170b43c59b842bbb04e1f2c8c5c7b08.png#pic_center
[15a43000e9964c18bee02d1b8f3e6dca.png_pic_center]: https://img-blog.csdnimg.cn/15a43000e9964c18bee02d1b8f3e6dca.png#pic_center
[cedee8e9a0b34629b3fa5bebc184f59f.png_ppic_center]: https://img-blog.csdnimg.cn/cedee8e9a0b34629b3fa5bebc184f59f.png#ppic_center
[b86658083bfe494396c9d39ca866e76c.png_pic_center]: https://img-blog.csdnimg.cn/b86658083bfe494396c9d39ca866e76c.png#pic_center
[2f5b2e97283f449dbcd04bc1bc20a976.png_pic_center]: https://img-blog.csdnimg.cn/2f5b2e97283f449dbcd04bc1bc20a976.png#pic_center
[bf81e4c5ae4b4cd493853ba1917dca3a.png_pic_center]: https://img-blog.csdnimg.cn/bf81e4c5ae4b4cd493853ba1917dca3a.png#pic_center
[dd180c5a668b49d6ab9fff6b8287f996.png_pic_center]: https://img-blog.csdnimg.cn/dd180c5a668b49d6ab9fff6b8287f996.png#pic_center
[eaf752526695489b991945a01a8f8e73.png_pic_center]: https://img-blog.csdnimg.cn/eaf752526695489b991945a01a8f8e73.png#pic_center
[864de455e6b447fa8ae14da7b1bb4ca3.png_pic_center]: https://img-blog.csdnimg.cn/864de455e6b447fa8ae14da7b1bb4ca3.png#pic_center
[4087d97ef5eb42ffb8bb57c2c5f3efb0.png_pic_center]: https://img-blog.csdnimg.cn/4087d97ef5eb42ffb8bb57c2c5f3efb0.png#pic_center
[8ec4f5b31b2c43e19f1a4fcc4b637bae.png_pic_center]: https://img-blog.csdnimg.cn/8ec4f5b31b2c43e19f1a4fcc4b637bae.png#pic_center
[3a800ca7cc144f0e9a99dd703bfab19b.png_pic_center]: https://img-blog.csdnimg.cn/3a800ca7cc144f0e9a99dd703bfab19b.png#pic_center
[0efec1dbb3664a588c53675488663af1.png_pic_center]: https://img-blog.csdnimg.cn/0efec1dbb3664a588c53675488663af1.png#pic_center
[ca2e21370dac4d03a6cdab0c5b9d63bb.png_pic_center]: https://img-blog.csdnimg.cn/ca2e21370dac4d03a6cdab0c5b9d63bb.png#pic_center
[a0b2f73695604a11a441e18286610b9c.png_pic_center]: https://img-blog.csdnimg.cn/a0b2f73695604a11a441e18286610b9c.png#pic_center
[62d322bad2fb4978b592235919fddb92.png_pic_center]: https://img-blog.csdnimg.cn/62d322bad2fb4978b592235919fddb92.png#pic_center
[d98a164c2bcd441c8493b83fc988b18e.png_pic_center]: https://img-blog.csdnimg.cn/d98a164c2bcd441c8493b83fc988b18e.png#pic_center
[dc093b01dca043b6a0aa9715fefa4c44.png_pic_center]: https://img-blog.csdnimg.cn/dc093b01dca043b6a0aa9715fefa4c44.png#pic_center
[56605b349f92411eb07d6fc727b16f35.png_pic_center]: https://img-blog.csdnimg.cn/56605b349f92411eb07d6fc727b16f35.png#pic_center
[9c0b8dd80f9949a9a4c2c595c1f5cea0.png_pic_center]: https://img-blog.csdnimg.cn/9c0b8dd80f9949a9a4c2c595c1f5cea0.png#pic_center
[760638d19e9a449fb2161f5c2b05d35d.png_pic_center]: https://img-blog.csdnimg.cn/760638d19e9a449fb2161f5c2b05d35d.png#pic_center
[f2a6b7f5ac054d769e03884ef3bb7d53.png_pic_center]: https://img-blog.csdnimg.cn/f2a6b7f5ac054d769e03884ef3bb7d53.png#pic_center
[a11fcf1202524741b02b85a779320d7f.png_pic_center]: https://img-blog.csdnimg.cn/a11fcf1202524741b02b85a779320d7f.png#pic_center
[974345f9476a430ab328189f530ddae0.png_pic_center]: https://img-blog.csdnimg.cn/974345f9476a430ab328189f530ddae0.png#pic_center
[e7e13f2477a348a6b8233a4321d75e37.png_pic_center]: https://img-blog.csdnimg.cn/e7e13f2477a348a6b8233a4321d75e37.png#pic_center
[92ebc7a2611c49a8a58601b6d1a402a4.png_pic_center]: https://img-blog.csdnimg.cn/92ebc7a2611c49a8a58601b6d1a402a4.png#pic_center