- 进程调度算法

调度算法的评价指标

CPU利用率：CPU忙碌的时间/总时间

系统吞吐量：单位时间内总共完成多少道作业/进程

周转时间：作业完成的时刻 - 作业提交的时刻，也等于 作业/进程等待时间 + 作业/进程运行时间。

周转时间 = 作业在作业队列等待被高级调度的时间 + 进程在就绪队列等待被低级调度的时间 + 进程运行的时间 + 进程等待IO操作的时间。

平均周转时间：各作业周转时间之和 / 作业数

带权周转时间：作业周转时间 / 作业实际运行的时间，带权周转时间 >= 1，越小越好。

平均带权周转时间：各作业带权周转时间之和 / 作业数

等待时间： 进程/作业 处于等待CPU状态的时间之和。等于周转时间 - 运行时间。

响应时间：从用户提交作业请求到该作业第一次占有CPU的时间。

下面正式介绍各种调度算法，需要从下面6个方面思考每种算法：

a. 这种算法的设计出来解决什么问题（算法思想）

b. 这种算法的规则

c. 这种算法用于作业调度还是进程调度

d. 这种算法是抢占式还是非抢占式

e. 优缺点

f. 是否倒是饥饿（某个进程长期得不到运行机会）

先来先服务算法 FCFS

算法思想：从公平角度出发而设计出来的算法；

算法规则：按作业/进程的到达的先后顺序进行服务；

用于作业/进程调度：用于作业调度时，先到达作业队列的作业先服务；用于进程调度时，先到达就绪队列的进程先服务；

是否可抢占：非抢占算法；

优点：公平且算法简单；

缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大。即FCFS对长作业有利，对短作业不利。（试想一下，你去买一杯奶茶，排在你前面的人要买20杯）

是否导致饥饿：不会。任何一个进程都能得到服务，尽管可能有些进程要等很久。

短作业优先 SJF/SPF

算法思想：追求最少的平均等待时间 和 带权周转时间；

算法规则：已经到达的进程中运行时间（是用户要求的或提供的运行时间）最短的作业/进程先得到服务；

用于作业/进程调度：可用于作业调度 和 进程调度。用于进程调度时 称为“短进程优先（SPF, Shortest Process First）算法”；

是否可抢占：非抢占算法，也有抢占式的版本——最 短剩余时间优先算法（SRTN）；

优点：可以获得理论上最短的平均等待时间和平均周转时间；

缺点：不公平，对长作业不利，长作业可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的， 并不一定真实，不一定能做到真正的短作业优先。

是否导致饥饿：会。如果源源不断地有短作业/进程到来，可能使长作业/进 程长时间得不到服务，产生“饥饿”现象。

例子（非抢占式）：

例子（抢占式）：

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

抢占式的短作业优先算法比非抢占式的更优，因为每次进程切换都会重新计算作业的剩余运行时间，得到最新的最优运行进程。

高响应比优先 HRRN（HRRF）

算法思想：响应是指作业进入系统后到它开始持有CPU所花的时间，高响应是指尽可能让每个进入系统的作业不一定都尽早的处理完，但要都尽早的持有过CPU，让用户感觉自己的进程得到的响应，已经在运行了，而不是一动不动。

该算法综合考虑作业/进程的等待时间和要求运行的时间；

算法规则：选择响应比高的作业/进程先服务，响应比 = （等待时间 + 要求服务的时间） / 要求服务的时间；

要求服务的时间，即运行时间，占有CPU的时间，但运行时间是用户预估的，提前输入到系统的，因此叫做 要求服务的时间。

用于作业/进程调度：皆可；

是否可抢占：非抢占算法，只有当前运行的作业/进程主动放弃 处理机时，才需要调度，才需要计算响应比；

优点：综合考虑了等待时间和运行时间（要求服务时间） 。等待时间相同时，要求服务时间短的优先 ；要求服务时间相同时，等待时间长的优先 。对于长作业来说，随着等待时间越来越久，其响应比也会 越来越大，从而避免了长作业饥饿的问；

缺点：没有考虑到作业/进程的紧急程度；如果要求服务的时间预估错误，则高响应比算法不再有效。

是否导致饥饿：不会。

这3种算法主要关心对用户的公平性、平均周转时间、平均等待时间等指标，但 是不怎么关心“响应时间”，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。

因此这三种算 法一般适合用于早期的批处理系统，而不适合交互式系统。当然，FCFS算法也常结合其他的算法使用，在现在也扮演着很重要的 角色。

更多内容请关注微信公众号