【调度】操作系统中调度算法（FCFS、RR、SPN（SJF）、SRT、HRRN）

决策模式

决策模式说明选择函数在执行的瞬间的处理方式&＃xff0c;通常分为以下两类&＃xff1a;

非抢占&＃xff1a;一旦进入运行状态&＃xff0c;就不会终止直到运行结束。

抢占&＃xff1a;当前正在运行的进程可以被打断&＃xff0c;并转移到就绪态。

 一个调度算法是否能抢占&＃xff0c;对进程的顺序有着极大的影响。

先来先服务FCFS

  先来先服务是最简单的策略&＃xff0c;也成为先进先出FIFO。首先它是一个非抢占的。如字面的意思&＃xff0c;它根据进程到达时间决定先运行哪一个进程。

  这里给出一个实际的例子。以表格的形式表现出在FIFO策略下各进程的情况。

简单说就是依次执行完成&＃xff0c;从时间轴上来看

以表格的形式展现&＃xff1a;

其中开始时间是上一个进程的结束时间

      结束时间&＃61;开始时间&＃43;服务/执行时间

      周转周期&＃61;结束时间-到达时间

      带权周转时间&＃61;周转时间/服务时间

最短进程优先SPN

也称最短作业优先&＃xff08;Short Job First,SJF&＃xff09;。它也是一个非抢占的。是根据服务的时间经行选择。在这里要注意下到达时间的顺序。比如实例中单纯以大小来排序的话是E-A-C-D-B,但正确的排序一定是A-B为开头。以时间为顺序&＃xff1a;

例子中A运行结束时间为3&＃xff0c;这时只有B进程等待。所以A运行结束后直接运行B。B结束后时间点到9&＃xff0c;CDE都在等待。这个时候就选择服务时间最少的E&＃xff0c;然后是较少的C&＃xff0c;最后是D。以表格的形式展示&＃xff1a;

最短剩余时间优先SRT

SRT是针对SPN增加了抢占机制的版本&＃xff0c;就好比例子中B运行时间非常长&＃xff0c;在这期间其他所有的进程都在等待&＃xff0c;如果将其中断&＃xff0c;先处理所需时间少的&＃xff0c;运行效率会有显著提升。一定要先明确SRT是抢占的。先给出时间为顺序的图&＃xff1a;

1. A先运行至2&＃xff0c;B到达等待。

2. A运行到3结束&＃xff0c;B开始运行。

3. B开始运行&＃xff0c;运行到4时&＃xff0c;C进程到达&＃xff0c;且C只需要4&＃xff0c;此时B还需要5。所以先运行C&＃xff0c;B继续等待。

4. C运行时间点到达6时&＃xff0c;D到达&＃xff0c;D需要5&＃xff0c;进入等待&＃xff0c;排在B后。

5. C运行结束&＃xff0c;此时时间点是8&＃xff0c;E到达&＃xff0c;运行时间只要2&＃xff0c;小于等待的BD&＃xff0c;直接运行。

6. C运行结束&＃xff0c;B开始运行。

7. B运行结束&＃xff0c;D开始运行。

以表格的形式展现&＃xff1a;

轮转RR

轮转也称时间片技术&＃xff08;time slicing&＃xff0c;SL&＃xff09;&＃xff0c;对于轮转法&＃xff0c;最重要的是时间片的长度。轮转算法以一个周期&＃xff08;q&＃xff09;产生中断&＃xff0c;当中断发生时&＃xff0c;当前运行的程序置于就绪队列&＃xff08;队尾&＃xff09;中&＃xff0c;然后基于FCFS选择下一个就绪作业运行。在这里我们以时间片q&＃61;1举例。

q&＃61;1&＃xff0c;所以一次只能运行一个时间片。

0&＃xff1a;A1运转&＃xff08;右标表示运行了几个&＃xff09;

1&＃xff1a;A2运转

2&＃xff1a;B1运转&＃xff0c;A3等待&＃xff08;B开始&＃xff09;

3&＃xff1a;A3运转&＃xff0c;B2等待

4&＃xff1a;B2运转&＃xff0c;C1等待&＃xff0c;&＃xff08;A结束&＃xff09;

5&＃xff1a;C1运转&＃xff0c;B3等待&＃xff08;C开始&＃xff09;

6&＃xff1a;B3运转&＃xff0c;D1等待&＃xff0c;C2等待

7&＃xff1a;D1运转&＃xff0c;C2等待&＃xff0c;B4等待&＃xff08;D开始&＃xff09;

8&＃xff1a;C2运行&＃xff0c;B4等待&＃xff0c;E1等待&＃xff0c;D2等待

9&＃xff1a;B4运行&＃xff0c;E1等待&＃xff0c;D2等待&＃xff0c;C3等待

10&＃xff1a;E1运行&＃xff0c;D2等待&＃xff0c;C3等待&＃xff0c;B5等待&＃xff08;E开始&＃xff09;

11&＃xff1a;D2运行&＃xff0c;C3等待&＃xff0c;B5等待&＃xff0c;E2等待

12&＃xff1a;C3运行&＃xff0c;B5等待&＃xff0c;E2等待&＃xff0c;D3等待

13&＃xff1a;B5运行&＃xff0c;E2等待&＃xff0c;D3等待&＃xff0c;C4等待

14&＃xff1a;E2运行&＃xff0c;D3等待&＃xff0c;C4等待&＃xff0c;B6等待

15&＃xff1a;D3运行&＃xff0c;C4等待&＃xff0c;B6等待&＃xff08;E结束&＃xff09;

16&＃xff1a;C4运行&＃xff0c;B6等待&＃xff0c;D4等待

17&＃xff1a;B6运行&＃xff0c;D4等待&＃xff08;C结束&＃xff09;

18&＃xff1a;D5运行&＃xff0c;D6等待&＃xff08;B结束&＃xff09;

19&＃xff1a;D6运行

20&＃xff1a;D结束

表格展示&＃xff1a;

高响应比优先HRRN

高响应比优先调度算法

高响应比优先调度算法主要用于作业调度&＃xff0c;该算法是对FCFS调度算法和SJF调度算法的一种综合平衡&＃xff0c;同时考虑每个作业的等待时间和估计的运行时间。在每次进行作业调度时&＃xff0c;先计算后备作业队列中每个作业的响应比&＃xff0c;从中选出响应比最高的作业投入运行。 

响应比的变化规律可描述为&＃xff1a;

响应比&＃61;&＃xff08;等待时间&＃43;服务时间&＃xff09;/服务时间

根据公式可知&＃xff1a;

当作业的等待时间相同时&＃xff0c;则要求服务时间越短&＃xff0c;其响应比越高&＃xff0c;有利于短作业。

当要求服务时间相同时&＃xff0c;作业的响应比由其等待时间决定&＃xff0c;等待时间越长&＃xff0c;其响应比越高&＃xff0c;因而它实现的是先来先服务。

对于长作业&＃xff0c;作业的响应比可以随等待时间的增加而提高&＃xff0c;当其等待时间足够长时&＃xff0c;其响应比便可升到很高&＃xff0c;从而也可获得处理机。克服了饥饿状态&＃xff0c;兼顾了长作业。

原文&＃xff1a;https://blog.csdn.net/xieminyao123/article/details/79116985