处理机调度算法

处理机调度算法

由于进程的数量多于处理机，因此不能并行地处理各个进程，处理机调度就是从就绪队列中按一定的算法选择一个进程分配处理机给他。

先来先服务

先来先服务（first come first serve）调度算法从“公平”的角度考虑，按照进程/作业的先后顺序进行服务。

其最大的缺点是对长作业有利，对短作业不利，就像A和B同时去银行办业务，A的业务只需要2分钟，B的业务需要2个小时，但是B比A就早到一会儿，A要在这干等2个小时，这种算法真的是“公平”吗？

短作业优先

短作业优先（shortest job first）调度算法就是为了解决先来先服务对短作业不利的问题，执行时间最短的进程优先得到服务。

可能导致的问题，产生饥饿，若源源不断的短作业来到就绪队列，则会使长作业得不到服务；

高响应比优先

综合先来先服务和短作业优先，综合考虑短作业和长作业。

高响应比优先（highest response ratio next），每次选择响应比最高的进程为其服务首先给出响应比的定义：

响应比 = （等待时间 + 要求服务时间） / 要求服务时间

我们发现等待时间越长响应比越高，要求服务时间越短响应比越高。综合考虑到了长服务时间的进程和短服务时间的进程。其并不会产生饥饿，对于一长作业而言，随着其服务时间增加其响应比也会增加，总会得到满足的。

以上三种算法只关心用户的公平性，并未考虑响应时间，因此不适合实时交互性系统，只适合批处理系统。

时间片轮转

时间片轮转（Round Robin），公平，轮流为每个进程服务，按照到达顺序，轮流让每个进程执行一个时间片，若一个时间片不足以执行完所有任务，一个时间片执行完后，os回收处理机执行权利，将其插到队尾。

公平、响应快，但是由于高频率的进程切换产生额外的开销、并未考虑到任务的紧急程度。

优先级调度

调度时总是选择优先级最高的进程。

若不断有高优先级的进程进入就绪队列，会使得低优先级的进程迟迟不能得到处理机。

多级反馈调度

综合了上述算法的终极算法。

详细算法：

1）、设置多级队列，各队列优先级从高到低，时间片从小到大，操作系统调度时总是优先处理低优先级的队列的队首元素，只有上级队列为空时才会调度下级的队列。

2）、新的进程到达是首先进入一级队列，其很容易就可以得到操作系统的处理机，若其在当前时间片内没执行完，就将其放入下一级队列的队尾。

优缺点：

其对各种进程都是相对公平的，每个新来的进程都可以很快得到响应，短进程只需较少的时间就可以执行完，此外其还可以避免用户造假

其还是会导致饥饿的，当渊源不断进程进入，长时间要求是进程可能在下级队列久久得不到调度。