处理机调度算法( RR 、HRRF)

1. P117页,练习15:最高响应比( HRRF)

处理机调度算法( RR 、HRRF)

2. P119页,练习22(2):时间片轮转( RR )

处理机调度算法( RR 、HRRF)

3. 现设定采用三级反馈队列调度算法,三个队列分别为0、1和2,对应时间片为2、4、8。现有四个进程A、B、C、D,到达时刻分别为0、5、7、12,执行时间分别为7、4、13、2。请写出整个进程调度过程,包括每个时间段,执行的进程,执行后进程状态,各个队列内进程的变化。

处理机调度算法( RR 、HRRF)

4. 从以下几个方面比较各个调度算法的优缺点:

(1).资源利用率  (2).吞吐率  (3).周转率  (4).响应时间  (5).公平性  (6).适用范围

一、先来先服务(FCFS)
  按照作业/进程进入系统的先后次序进行调度,先进入系统者先调度;即启动等待时间最长的作业/进程。是一种最简单的调度算法,即可用于作业调度,也可用于进程调度

  1.比较有有利于长作业进程,不利于段作业进程

  2.适合批处理系统,不适合分时系统  

  3.不利于I/0繁忙型作业而有利于CPU繁忙型作业
二、最短作业优先算法(SJF)
  从队列中选出一个估计运行时间最短的作业优先调度,即可用于作业调度,也可用于进程调度

  1.能够克服FCFS算法偏爱长作业的缺点,但执行效率也不高

  2.忽视了作业等待时间,进入系统时间长但计算时间长的长作业等待时间会很长,出现就饿现象

  3.缺少剥夺机制,对分时、实时处理不理想

  4.实现该算法要先知道作业运行时间,否则调度就没有依据

三、最短剩余时间优先算法(剥夺式SJF算法)

  若在进程运行过程中若有所需CPu时间比正在进行的进程时间更短的进程,则先执行最短CPU用时的进程

  1.相比非剥夺式SJF算法,剥夺式算法所需的平均等待时间和平均周转时间都更短
四、最高响应比优先算法(HRRF)

  HRRF式算法是一种介于FCFS算法和SJF算法之间的一种非剥夺式算法,既考虑作业等待时间有考虑作业处理时间。

  响应比 = 作业周转时间  /作业处理时间

      = (作业等待时间 + 作业处理时间 ) / 作业处理时间

      = 1+ 作业等待时间 / 作业处理时间

  1.既照顾短作业又不会使长作业的等待时间过长,能有效改善调度性能

  2.每次计算各道作业的响应会导致一定时间开销,性能比SJF算法略差

五、优先级调度算法

  根据确定的优先级来选取进程/进程,总是选择就绪队列中优先级最高者投入运行。通过用户定义的非剥夺式或剥夺式算法分为 静态和动态 优先级算法

  1.静态优先级算法简单,但是会出现饥饿现象,是某些低优先级/线程无限期地被推迟执行

  2.动态优先级会使个进程的优先级随时间而改变,原则上是:正在运行的进程随着CPU占有时间增加,逐渐降低其优先级;就绪队列中等待的CPU进程随等待时间的增加而逐渐提高其优先级,克服了静态优先级的饥饿问题

六、轮转调度算法(BR)

  也称时间片调度。调度程序每次把CPU分配个就绪队列首进程使用规定的时间间隔,称为时间片,就绪队列中的每个进程/线程轮流地运行一个时间片,当时间片耗尽时就强迫当前运行进程让出处理器,转而排列到就绪队列尾部,等待下一轮调度。、

  1.BR调度是一种剥夺式调度,系统在进程切换上的开销比较大,开销与时间片大小有关。

  2.若时间片取值太小,将导致大多数进程都不可能在一个时间片内运行完毕,就会频繁的切换。开销显著增大,所以从系统效率看,时间片取大一点好。

  3.若时间片长度较大,那么随着就绪队列中进程数目增加,轮转一次所耗费总时长变长,即对每个进程的响应速度放慢,甚至时间片大到让进程足以完成其所有任务,RR调度算法便退化成FCFS算法。

  4.为满足用户对响应时间的要求,要么限制就绪队列中进程数量,要么采用变化的时间片长度,根据当前负载状况及时调整时间片大小。所以,确定时间片长度要从数目、切换开销、系统效率和响应时间等多方面因素加以考虑。

七、多级反馈队列调度算法(MFQL)

  又称反馈循环队列,主要思想是:由系统建立多个就绪队列,每个队列对应于一个优先级,第一个队列的优先级最高,第二个队列的优先级次之,其后队列的优先级依次降低。较高优先级队列分配较短时间片,较低优先级队列分配较长时间片。

  1.可能会导致“饥饿”问题,假如有一个长作业进入系统,它最终必将移入优先级最低的就绪队列当中,若其后又源源不断的短作业进入系统,且形成稳定的作业流,则长作业一直等待,陷入“饥饿状态”。解决方法是对于低优先级中等待时间较长的,进程提升其优先级,从而让它获得运行机会。

  2.MLFQ算法具有良好性能,能满足各类应用需要。对于分时交互型短作业,系统通常刻在第一队列规定的时间片内完成工作。

上一篇:2016HDU校赛


下一篇:opcache分享