操作系统中的调度算法

先来先服务FCFS

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

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

简单说就是依次执行完成，从时间轴上来看

以表格的形式展现：

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

      结束时间=开始时间+(服务or执行)时间

      周转周期=结束时间-到达时间

      带权周转时间=周转时间/服务时间

最短进程优先SPN

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

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

最短剩余时间优先SRT

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

1. A先运行至2，B到达等待。

2. A运行到3结束，B开始运行。

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

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

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

6. C运行结束，B开始运行。

7. B运行结束，D开始运行。

以表格的形式展现：

轮转RR

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

q=1，所以一次只能运行一个时间片。

0：A1运转（右标表示运行了几个）

1：A2运转

2：B1运转，A3等待（B开始）

3：A3运转，B2等待

4：B2运转，C1等待，（A结束）

5：C1运转，B3等待（C开始）

6：B3运转，D1等待，C2等待

7：D1运转，C2等待，B4等待（D开始）

8：C2运行，B4等待，E1等待，D2等待

9：B4运行，E1等待，D2等待，C3等待

10：E1运行，D2等待，C3等待，B5等待（E开始）

11：D2运行，C3等待，B5等待，E2等待

12：C3运行，B5等待，E2等待，D3等待

13：B5运行，E2等待，D3等待，C4等待

14：E2运行，D3等待，C4等待，B6等待

15：D3运行，C4等待，B6等待（E结束）

16：C4运行，B6等待，D4等待

17：B6运行，D4等待（C结束）

18：D5运行，D6等待（B结束）

19：D6运行

20：D结束

表格展示：

高响应比优先HRRN

高响应比优先调度算法

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

该算法实际上是一种动态优先调度算法，它以响应比作为作业或进程的动态优先权，其目的是既照顾短作业，又考虑到作业的等待时间，使长作业不会长期等待；但每次调度前，都要进行响应比计算，会增加系统开销。

1、响应比 = 响应时间 / 要求服务时间 = (等待时间 + 要求服务时间) / 要求服务时间
2、作业周转时间＝完成时间－提交时间
3、作业带权周转时间＝周转时间 / 运行时间

根据公式可知：

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

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

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

下图为手写实例，字不太好，多多包涵，勿喷。