高响应比优先调度算法

来自计算思维百科
跳转至: 导航搜索
高响应比优先调度算法1.jpg

在很多任务都在等待执行时,我们会考虑让等待时间很长的任务优先执行,这种思想就是高响应比优先调度算法。高响应比优先调度算法是操作系统CPU调度中的一种调度算法,它既能照顾短作业,又保证长作业不会长时间得不到服务的,是一种考虑到整体服务效率的算法。

基本概念

高响应比优先调度算法,就是为每个作业引入动态优先权,并使作业的优先权随着等待时间的增加而以速率a提高,保证长作业在等待一定的时间后。必然有机会分配到处理机。作业调度方式为非抢占式。

优先权公式定义如下:

高响应比优先调度算法2.png

算法实施过程如下:

  1. 设置一个就绪队列;
  2. 若就绪队列中作业数多于1个且当前有作业使用CPU,则按照优先权公式,对照计算就绪队列中每个作业的优先权,否则直接执行作业;
  3. 按照优先权数值排序,优先权数值越高,则作业越先被执行;
  4. 等待当前作业使用完CPU,按照步骤3计算好的队列顺序执行作业;
  5. 重复步骤3、4直到所有作业执行完毕。

应用范围

高响应比优先调度算法可用于工业生产中生产工具使用顺序的安排等

使用方法及步骤

  1. 设置一个就绪队列;
  2. 若就绪队列中作业数多于1个且当前有作业使用CPU,则按照优先权公式,对照计算就绪队列中每个作业的优先权,否则直接执行作业;
  3. 按照优先权数值排序,优先权数值越高,则作业越先被执行;
  4. 等待当前作业使用完CPU,按照步骤3计算好的队列顺序执行作业;
  5. 重复步骤3、4直到所有作业执行完毕。

应用案例

应用1-流水线产品生产顺序安排

案例:某流水线负责生产汽车玩具的车轮,车盖,车身和座位(两人座),其中车身,车盖,座位,车轮生产时间分别为80s,50s,20s,10s。车轮,车身,座位生产原料相继隔5 秒到达,车盖原料在车轮生产后10s到达。只有一条流水线。为了提高成品的生产效率,应该如何安排零件的生产顺序?

解决步骤:

1. 车轮最先到达,生产时间最短,所以先生产;车轮在流水线第一生产次序,5秒后到达的车身、座位原料等待5s

2. 计算车身,座位优先权:

高响应比优先调度算法3.png

高响应比优先调度算法4.png

由于1.6025>1.25,车身生产次序排第二 此时车盖原料等待80s,座位原料等待5+80=85s

3. 计算车盖、座位优先权:

高响应比优先调度算法5.png

高响应比优先调度算法6.png

由于5.25>2.6,座位生产次序排第三

4. 车盖在流水线第四生产次序

在这个解决方案中,生产车轮,车盖,车身和座位就是四个任务,这四个任务到达先后顺序不同,任务执行的时间也不相同。车轮因为先到,就先被生产了,后面等待的车身和座位谁先执行,就由等待时间与生产时间两个因素决定,原则上,等待时间相对生产时间越大的,优先被生产,这就体现在第2步中优先级的计算中,这种优先级的计算就体现了等待时间越长,优先级越高的思想。

可以体现的计算思维

高响应比优先调度算法对响应时间短的优先进行处理,对等待时间长的以某种速率提高其优先权,从而保证了不同类型的任务都及时得到执行,体现了计算思维的调度和折中特点,是一种提高整体任务执行效率的解决方案。