- 进程调度算法
调度算法的评价指标
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算法也常结合其他的算法使用,在现在也扮演着很重要的 角色。
如果您需要转载,可以点击下方按钮可以进行复制粘贴;本站博客文章为原创,请转载时注明以下信息
张柏沛IT技术博客 > 操作系统入门(十三)调度算法——先来先服务算法、短作业优先算法 和 高响应比优先算法