操作系统-------进程和线程调度算法+调度算法的评价指标(周转时间,等待时间等等)
目录
(基于王道)
一,调度算法的评价指标:
调度算法的评价指标大体如下:
1. CPU利用率
CPU利用率指CPU忙碌的时间占总的时间的比例:
如:某个计算机只支持单道程序,若刚开始需要在cpu上运行5秒, 再用打印机运行5秒,再回到cpu运行5秒,则:
cpu利用率 = (5+5)/(5+5+5)=66.66%
打印机利用率= 5 / (5+5+5)=33.33%
2.系统吞吐量
系统吞吐量=单位时间内完成的作业数量
例如:某计算机完成了10道作业,共用了100秒,则系统吞吐量为 10/100 = 0.1道/秒
3.周转时间+带权周转时间
周转时间:作业从提交给系统开始,到作业完成为止的这段时间间隔。
一般由四个部分组成:
1.作业在外存后备队列中等待作业调度(高级调度)的时间
2.进程在就绪队列上等待进程调度(低级调度)的时间
3.进程在cpu上的执行时间
4.进程等待I/O操作的时间
后三项在一个作业的整个处理过程中,可能发生多次。
但是这样计算难免有点复杂,所以单个作业的周转时间一般计算为:
但是对于系统而言,更关心的是平均周转时间:
问题:从上面我们可以知道周转时间其实是由 等待时间+在cpu上实际执行时间 组成的。所以在相同的周转时间下,有的作业运行时间长,有的运行时间短,但所表示的东西是不同的,但在周转时间下,确是一样的。所以在计算周转时间时,要把运行时间也考虑上,因此就引入了带权周转时间。
对于周转时间相同的两个作业,实际运行时间长的作业在相同的时间内被服务的时间更多,带权周转时间更小,用户满意度更高。反之亦然。
4.等待时间
等待时间:对进程而言,等待时间就是进程建立后等待被服务的时间之和。在等待I/O服务完成时,其实进程也是被服务的,所以不计入等待时间。
二,调度算法
进程和线程调度算法经典主要的一共是六种:
1.先来先服务(FCFS,first come first serve)
2.短作业优先(SJF,shortest job first)
3.高响应比优先(HRRN)
4.时间片轮转算法(RR)
5.优先级调度算法
6.多级反馈队列算法
1.先来先服务(FCFS)
饥饿:进程长时间得不到执行。
FCFS算法对短作业不利的原因:就如排队买奶茶,有的人排队买几十杯,但有的人只买一杯,这么的话,买一杯奶茶的人体验就会很不好。
抢占:即得不到执行的进程or线程,抢夺正在执行的进程or线程的资源来让自己执行。
那我们看一下,FCFS的调度指标是怎么算的:
2.短作业优先
为什么短作业优先可以达到最少的等待时间、周转时间、带权周转时间呢?
答:因为短作业的运行时间短,所以它的周转时间肯定就比较短,再加上短作业优先,即每次都会优先给短作业分配cpu让它先运行,所以周转时间肯定少。同理带权周转时间也是。那么等待时间=周转时间-运行时间,对于短作业而言,周转时间很小,运行时间也很小,那么等待时间肯定也很小。既然这样那么平均下来的话,虽然有长作业等比较久,但是总的来说,还是比较小的。(抢占式的比非抢占式的平均周转时间、平均等待时间还要更低)
3.高响应比优先算法
高响应比优先算法:在选择调入cpu的进程时,会考虑进程的 等待时间 和 要求服务的时间。然后算一个响应比,选择响应比较高的进程运行。
特点:高响应比算法结合了短作业优先和FCFS算法的优点:
1.当等待时间相同时:要求服务时间越小,响应比越大,越容易放入cpu运行。
2.当要求服务时间相同时:等待时间越长,响应比越大,越容易放入cpu运行。
如果一个进程很久得不到运行,那么它的等待时间就会很长,从而提高响应比,所以响应比优先算法并不会出现饥饿情况。
前三种算法归纳:“
4.时间片轮转算法
时间片轮转和FCFS(先来先服务算法)一样,都是公平性很强的。
时间片轮转算法不会区分任务的重要程度,而且频繁的进程切换也会导致系统的开销很大。
5.优先级调度算法
系统会根据进程的优先级来把优先级高的放到cpu上运行。但是有可能会导致优先级低的进程发生饥饿。
优先级算法有分抢占式的和非抢占式的。
非抢占式:每次调度时,选择最高优先级的进程。
抢占式:当进程主动放弃cpu时,选择最高优先级的进行执行。和当就绪队列发生改变时,也要检测是否可以发生抢占。
补充:
优先级调度算法还分为:静态优先级和动态优先级两种:
静态优先级:优先级一旦确定下来就不变了
动态优先级:进程创建时,会有一个初始的优先级,但之后会根据情况动态地修改优先级。
一般来说,但一个进程占着cpu运行了很长时间时,可以降低它的优先级,而当一个进程在就绪队列中等了很久时,可以提高它的优先级。另外一个补充:就是系统是偏爱I/O型的进程的,因为若I/O繁忙型的进程先运行的话,则越有可能让I/O设备今早地投入运行,进而增加系统的吞吐量。(I/O设备和cpu是可以并行运行的)
6.多级反馈队列调度算法
多级反馈队列调度算法:结合了之前几种调度算法的优点。
多级反馈队列会维持多个就绪队列,每个就绪队列的优先级都不同,而且每个就绪队列的时间片大小也不同。
新来的进程会先进入第一级队列,按FCFS算法规则对进程进行调用,若使用完第一级队列的时间片后还没执行完该进程,就会把这个进程放到第二级队列的队尾,由于就绪队列们的时间片是从小到大的,所以会有短作业优先算法的优点,即短作业先运行。以此类推。当前一级的队列为空,才进行下一级就绪队列的时间片分配。由于使用了时间片,所以也具有时间片轮转算法的优点。