进程调度

关于进程调度需要先了解什么是进程，进程可以简单理解为正在运行的程序。而进程调度的两个关键性指标则是：响应时间与周转时间。

响应时间：

进程未运行到下次被选中运行的时间间隔。如：创建进程到第一次调度到进程的时间。再比如：进程切换后到下一次调度到该进程的时间间隔。

响应时间体现了交互感，如：敲下键盘到屏幕上出现对应的字符，自然是时间越短越好。即响应时间越短，交互性越好。

周转时间：

进程从启动开始到执行结束的时间间隔。周转时间可以体现性能，周转时间越短，从进程执行到结束所等待的时间越短。

性能和公平往往是互相矛盾的，优化性能必然会降低公平性，反之亦然。进程调度就是不断去平衡两者之间的关系，去权衡利弊。

进程的调度算法分为：先进先出（FIFO）调度算法、最短任务优先（SJF）调度算法、最短完成时间优先（STCF）调度算法、Round—Robin调度算法、高响应比优先调度算法、多级反馈队列调度算法。

先进先出（FIFO）调度算法：

设：有三个进程A、B、C，当他们的运行时间一致（10s）时：

平均周转时间： （10 + 20 + 30）/ 3 = 20s

平均响应时间： （0 + 10 + 10）/ 3 = 6.67s

当A进程运行时间为100s时：

平均周转时间： （100 + 110 + 120）/ 3 = 110s

平均响应时间： （0 + 100 + 110）/ 3 = 70s

此时，FIFO的缺点就很明显了。若耗时较短的进程放在耗时更长的进程之后，那么短进程将做出无谓的等待。

就像去超市买东西结账时，假如我们只买了一件商品，前面的人购物车堆满了商品。此时，我们都想让我们先结账，因为在我们看来，我们的结账速度很快。因此，这种效率很低。但如果超市开通一个新的零散结账通道给购买商品很少的客户，就可以提高效率。但很显然这是不可能的，因为超市无法对用户的商品购买量进行限制。

但这种零散结账的模式正是下一种算法：最短任务优先，让购买量较小的客户先结账。

最短任务优先（SJF）调度算法：

顾名思义，最短的进程先执行。按照上面的例子，如果A进程执行时间为100s，B、C不变仍为10s；A最长，所以最后执行。

平均周转时间： （10 + 20 + 120）/ 3 = 50s

平均响应时间： （0 + 10 + 20）/ 3 = 10s

但如果不是所有进程同时启动，而是随机启动，则此时最坏的情况就是A进程先执行，这时就又回到了最糟糕的情况：

平均周转时间： （100+（110-10） + （120 - 10））/ 3 = 103.3s

平均响应时间： （0 + （100-10） + （110-10））/ 3 = 63.3s

最短完成时间优先（STCF）调度算法：

在上一种算法中，仍然有可能回到最糟糕的情况。因此，我们假设进程的调度是可以抢占的，谁抢到优先权谁就先运行。那么短任务就可以在开始的时候直接运行，不需要等待很长时间，这就是最短完成时间优先调度算法。

因此，先进先出和最短任务优先都是非抢占式的，而最短完成时间是抢占式的调度算法。

关于抢占式，可能会有一些容易误解的地方。抢占式并不是说进程抢到CPU资源了，而是指优先级。进程调度实际上大部分都是由操作系统决定的，所谓抢占，只是表明该进程优先级要高一些，可能马上就会调度到它，下一个就是，同时也有可能除它以外还有优先级更高的进程或者和它同级的进程。

平均周转时间： （120 + （20-10） + （30-10））/ 3 = 50s

平均响应时间： （0 + 0 + 10）/ 3 = 3.3s

此算法在两项指标上都已经达到了最佳效果，这归功于抢占式。只要是抢占式，平均时间就不会比非抢占式的差。

Round—Robin调度算法：

其实，抢占式的响应时间还可以优化。在最短完成时间的基础上添加一个条件：指定每个进程最多运行固定的一段时间，轮询调度每一个进程，这就是“轮询调度”或“时间片轮转”。

这种“固定的时间段”就是“时间片”。如果要使用时间片的功能，就必然需要时间中断，并且时间片的长度必须是时钟周期的倍数。如： 时间中断是5s一次，那么时间片就是5s、10s、15s、20s ... ...

在上个算法的基础上添加2s的时间片，且三个进程同时启动：

平均周转时间： （120 + （30-2） + 30）/ 3 = 59.3s

平均响应时间： （0 + 2 + 4）/ 3 = 3s

高响应比优先调度算法：

高响应比优先调度算法（Highest Reponse Ratio First, HRRF）是非抢占式的，它同时考虑了每个进程的响应时间与周转时间。每次调度时，从所有进程中选出响应比最高的进程进行调度。

响应比 = （周转时间 + 响应时间）/ 周转时间

多级反馈队列调度算法：

多级反馈队列调度算法不需要事先知道各进程所需要的执行时间，实施过程如下：

1.设置多个就绪队列，并为其赋予不同的优先级。

2.赋予各队列中进程的时间片各不相同，优先级越高，时间片越小。

3.当一个新进程进入内存后，放入第一级队列末尾，按照FCFS原则等待调度。轮到该进程执行时，若能在该时间片内完成，便可以准备撤离系统；若在一个时间片结束时未能完成，则将其转入第二级队列末尾继续等待调度；若再不行则转入第三级队列末尾，以此类推。

4.当第一级队列为空时，才调度第二级队列；若在处理第n级队列中的某进程时，有一个新进程进入较高级队列中，则系统讲正在运行的进程放回第n级队列末尾，先执行较高级队列中的进程。