算法介绍

基本思想

一个多级的排队系统。有16个排队队列，但实际上可以编译定义更多或更少的队列。系统刚运行的时候一般不会使用这么多的队列，而仅使用其中几个。进程的优先级基本上由其所在队列的优先级所决定。选择进程运行的时候，调度器将从最高优先级队列中的进程开始选，如果有，则选取队首进程运行；若没有，则到下一个次优先级的队列中去选进程去执行。

CPU时间分配和防止系统挂起（hang）

进程调度中既要给与高优先级进程更多的机会去运行，但同时也要防止系统老是被一个高优先级的进程所占用，出现低优先级进程的“进程饥饿”，最后甚至造成系统挂起的问题。Minix3采用以下的方法。

首先，队列内采取时间片轮转的方法。每个进程都有一个时间片，每次时间片用完，调度器都要进行进程调度。优先级高的进程一般有较大的时间片。对于某个优先级队列中的进程而言，一个进程运行完它的时间片后就会被放到原先优先级队列的尾部并分配一个新的时间片，使得队列中的进程能轮转地公平的得到运行的机会。

其次，对于队列间，采取如下动态优先级的策略。

但如果队列中只有一个进程，那这个进程在时间片运行完后，仍会立即继续下一个时间片地运行。为了防止这种情况，但一个进程连续两个时间片地运行完后，将被放在一个较低的运行队列中。

而当进程没有妨碍其他进程的运行（即其时间片用完后，调度器调度了其他的进程运行）时，它的优先级又会不断提高直到到它能回到的（所允许的）最大优先级。这样，原先的被降低了优先级的进程在不妨碍别的进程下运行的情况下，能有机会逐步地回到原来的优先级。

Minix进程阻塞策略

如果程序阻塞后，它将由被移出调度队列。然后调度器再在调度队列中剩下的进程中选择一个程序运行。一个阻塞进程被唤醒后，得到的只是阻塞前所剩余的时间片。并将被放到原来调度队列的队首。