江小南

V1

2023/04/17阅读:56主题:萌绿

【操作系统】调度算法的评价指标与调度算法

1. 调度算法的评价指标

1. CPU利用率

CPU利用率:指CPU“忙碌”的时间占总时间的比例。

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

2. 系统吞吐量

系统吞吐量:单位时间内完成作业的数量。

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

3. 周转时间

周转时间,是指从作业被提交给系统开始,到作业完成为止的这段时间间隔。

它包括四个部分:作业在外存后备队列上等待作业调度(高级调度)的时间、进程在就绪队列上等待进程调度(低级调度)的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。后三项在一个作业的整个处理过程中,可能发生多次。 对于用户来说,更关心自己的单个作业的周转时间。对于操作系统来说,更关心系统的整体表现,因此更关心所有作业周转时间的平均值。 说明:带权周转时间必然>=1,同时带权周转时间与周转时间都是越小越好。

对于周转时间相同的两个作业,实际运行时间长的作业在相同时间内被服务的时间更多,带权周转时间更小,用户满意度高。

对于实际运行时间相同的两个作业,周转时间短的带权周转时间更小,用户满意度更高。

4. 等待时间

等待时间,指进程/作业处于等待处理机状态时间之和,等待时间越长,用户满意度越低。

对于进程来说,等待时间就是指进程建立后等待被服务的时间之和,在等待I/O完成的期间其实进程也是在被服务的,所以不计入等待时间。

对于作业来说,不仅要考虑建立进程后的等待时间,还要加上作业在外存后备队列中等待的时间

一个作业总共需要被CPU服务多久,被I/O设备服务多久一般是确定不变的,因此调度算法其实只会影响作业/进程的等待时间。当然,与前面指标类似,也有“平均等待时间”来评价整体性能。

5. 响应时间

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

2. 调度算法

1. 先来先服务(FCFS,First Come First Serve)

算法思想:主要从“公平”的角度考虑(类似于我们生活中排队买东西的例子)。

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

作业/进程调度:用于作业调度时,考虑的是哪个作业先到达后备队列;用于进程调度时,考虑的是哪个进程先到达就绪队列。

是否可抢占:非抢占式的算法。

优点:公平、算法实现简单。

缺点:排在长作业(进程)后面的短作业需要等待很长时间,带权周转时间很大,对短作业来说用户体验不好。即FCFS算法对长作业有利,对短作业不利

是否会导致饥饿:不会。

说明:饥饿,表示某作业/进程长期得不到服务。

2. 短作业优先(SJF,Shortest Job First)

算法思想:追求最少的平均等待时间、最少的平均周转时间、最少的平均带权周转时间。

算法规则:最短的作业/进程优先得到服务(所谓“最短”,是指要求服务时间最短)。

作业/进程调度:即可用于作业调度,也可用于进程调度。用于进程调度时称为“短进程优先(SPF,Shortest Process First)算法”

是否可抢占:SJF和SPF是非抢占式的算法。但是也有抢占式的版本——最短剩余时间优先算法(SRTN,Shortest Remaining Time Nest)。

优点:“最短的”平均等待时间、平均周转时间。

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

是否会导致饥饿:会。如果源源不断有短作业/进程进来,可能使长作业/进程长时间得不到服务,产生“饥饿”现象。如果一直得不到服务,则称为“饿死”。

注意

  1. 如果没有特别说明,则“短作业/进程优先算法”默认是非抢占式的。
  2. 抢占式的短作业/进程优先调度算法(最短剩余时间优先,SRNT算法)的平均等待时间、平均周转时间最少的说法更准确。

3. 高响应比优先(HRRN,Highest Response Ratio Nest)

算法思想:要综合考虑作业/进程的等待时间和要求服务的时间。

算法规则:在每次调度时先计算各个作业/进程的响应比,选择响应比最高的作业/进程为其服务。 作业/进程调度:既可用于作业调度,也可用于进程调度。

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

优缺点:综合考虑了等待时间和运行时间(要求服务时间)。等待时间相同时,要求服务时间短的优先(SJF的优点);要求服务时间相同时,等待时间长的优先(FCFS的优点);对于长作业来说,随着等待时间越来越长,其相应比也会越来越大,从而避免了长作业饥饿的问题。

是否会导致饥饿:不会。

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

算法思想:公平地、轮流地为各个进程服务,让每个进程在一定时间间隔内都可以得到响应。

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

作业/进程调度:用于进程调度(只有作业放入内存建立了相应的进程后,才能被分配处理机时间片)。

是否可抢占:若进程未能在时间片内运行完,将被强行剥夺处理机使用权,因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到。

优点:公平;响应快,适用于分时操作系统。

缺点:由于高频率的进程切换,因此有一定开销;不区分任务的紧急程度。

是否会导致饥饿:不会。

补充:时间片不能太大也不能太小。一般来说,设计时间片时要让切换进程的开销占比不超过1%。

时间片轮转调度通常用于分时操作系统,更注重“响应时间”,因此不计算周转时间。

5. 优先级调度算法

算法思想:随着计算机的发展,特别是实时操作系统的出现,越来越多的应用场景需要根据任务的紧急程度来决定处理顺序。

算法规则:调度时选择优先级最高的作业/进程。

作业/进程调度:即可用于作业调度,也可用于进程调度。甚至,还会用于I/O调度中。

是否可抢占:抢占式、非抢占式都有。非抢占式只需要在进程主动放弃处理机时进行调度,非抢占式还需在就绪队列变化时,检查是否会发生抢占。

优点:用优先级区分紧急程度、重要程度,适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。

缺点:若源源不断地有高优先级进程进来,则可能导致饥饿。

是否会导致饥饿:会。

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

算法思想:对其他调度算法的这种权衡。

算法规则

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

作业/进程调度:用于进程调度。

是否可抢占抢占式的算法。在k级队列的进程中运行过程中,若更上一级的队列(1~k-1级)中进入了一个新进程,则由于新进程处于优先级更高的队列中,因此新进程会抢占处理机,原来运行的进程放回k级队列队尾。

优缺点:对各类型进程相对公平(FCFS的优点);每个新到达的进程都可以很快得到响应(RR的优点);短进程只用较少的时间就可以完成(SPF的优点);不必实现估计进程的运行时间(避免用户作假);可灵活地调整对各类进程的偏好程度,比如CPU密集型进程、I/O密集型进程(扩展:可以将因I/O而阻塞的进程重新放回原队列,这样I/O型进程就可以保持较高优先级)。

是否会导致饥饿:会。

3. 小结

注意:这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标,但是不关心“响应时间”,也并不区分任务的紧急程度,因此对于用于来说,交互性很糟糕。因此这三种算法一般适合于早期的批处理系统,当然,FCFS算法也常结合其他的算法使用,在现在也扮演着很重要的角色。 注意:比起早起的批处理操作系统来说,由于计算机造价大幅降低,因此之后出现的交互式操作系统(包括分时操作系统、实时操作系统等)更注重系统的相应时间、公平性、平衡性等指标。而这几种算法恰好能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。(比如UNIX使用的就是多级反馈队列调度算法)。

分类:

后端

标签:

操作系统

作者介绍

江小南
V1