进程调度算法

一、进程调度算法的评价指标

1. cpu利用率：

利用率=cpu忙碌时间/总时间

1. 系统吞吐量：

系统吞吐量=总共完成了多少道作业/总共花费的时间

1. 周转时间：
2. 周转时间： 周转时间=作业完成时间-作业提交时间
3. 平均周转时间： 平均周转时间=各作业周转时间之和/作业数量
4. 带权周转时间： 带权周转时间=作业周转时间/作业实际运行的时间
5. 平均带权周转时间： 平均带权周转时间=各作业带权周转时间之和/作业数量
6. 等待时间：

进程/作业 等待被服务的时间之和

平均等待时间即各个 进程/作业 等待时间的平均值

1. 响应时间：

从用户提交请求到首次产生响应所用的时间

二、调度算法（早期批处理系统）

Tips：各种调度算法的学习思路

• 算法思想
• 算法规则
• 这种调度算法是用于**作业调度**还是**进程调度**？
• 抢占式？非抢占式？
• 优点核缺点
• 是否会导致***饥饿***（某进程/作业长期得不到服务）

1. 先来先服务（FCFS）

image-20200325150609731

2. 短作业优先（SJF）

1. 短作业/进程优先调度算法：每次调度时选择**当前已到达**且**运行时间最短**的作业/进程。
2. 最短剩余时间优先算法：每当有进程加入**就绪队列改变时就需要调度**，如果新到达的进程**剩余时间**比当前运行时间的进程剩余时间**更短**，则由新进程**抢占**处理机，当前运行进程重新回到就绪队列。另外，当一个**进程完成时也需要调度**。

image-20200325152858734

3. 高响应比优先

响应比： 响应比=（等待时间+要求服务时间）/要求服务时间

**高响应比优先算法规则**：在每次调度时先计算各个作业/进程的*相应比*，选择*相应比最高的*作业/进程为其服务

image-20200325154733465

知识回顾

image-20200325154848100

三、调度算法（交互式系统）

1. 时间片轮转调度算法（RR）——常用于分时操作系统

    \*\*\*算法规则：\*\*\*按照各进程到达就绪队列的顺序，轮流让各个进程执行一个\*\*时间片\*\*（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。

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

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

image-20200325163257508

2. 优先级调度算法

    \*\*\*算法规则：\*\*\*每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程

    \*\*\*抢占式的优先级调度算法：\*\*\*每次调度时选择\*\*当前已到达\*\*且\*\*优先级最高\*\*的进程。当前进程\*\*主动放弃处理机时\*\*发生调度。另外，当\*\*就绪队列发生改变时\*\*也需要检查是否会发生抢占。

    \*\*\*非抢占的优先级调度算法：\*\*\*每次调度时选择\*\*当前已到达\*\*且\*\*优先级最高\*\*的进程。仅在当前进程\*\*主动放弃处理机时\*\*发生调度。

    \*\*\*优先级调度算法的补充：\*\*\*

• 就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近就绪队列队头的位置
• 根据优先级是否可以动态改变，可将优先级分为**静态优先级**和**动态优先级**两种。
• 静态优先级：创建进程时确定，之后一直不变。
• 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。
• 系统进程优先级**高于**用户进程
• 前台进程优先级**高于**后台进程

+ 如果某进程在就绪队列中等待了很长时间，则可以适当提高其优先级

+ 如果某进程占用处理机运行了很长时间，则可以适当降低其优先级

+ 如果一个进程频繁地进行I/O操作，则可适当提升其优先级

• 操作系统更**偏好于I/O型进程（或称I/O繁忙型进程）**

+ I/O设备和CPU可以\*\*并行\*\*工作。如果优先让I/O繁忙型进程优先运行的话，则越有可能让I/O设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升。

+ 注：与I/O型进程相对的是\*\*计算型进程（或称CPU繁忙型进程）\*\*

image-20200325171035937

3. 多级反馈队列调度算法

    \*\*\*算法规则：\*\*\*

1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
2. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾。
3. 只有第K级队列为空时，才会为K+1级队头分配时间片。

 \*\*\*抢占式的算法：\*\*\*在K级队列的进程运行过程中，若上级的队列（1~K-1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回K级队列队尾。

 ![image-20200325173853530](https://img-wqnmd.obs.cn-south-1.myhuaweicloud.com/image-20200325173853530.png)

知识回顾

image-20200325174051062