当进程被中断（被输入输出设备或时钟等），或进程执行软中断指令，或进程结束时，系统将决定接下来运行哪个进程。
队列优先级：
Minix的进程调度使用多级队列，每个队列的优先级不同。
见 kernel/proc.h 中：
/* Scheduling priorities for p_priority. Values must start at zero (highest
* priority) and increment. Priorities of the processes in the boot image
* can be set in table.c. IDLE must have a queue for itself, to prevent low
* priority user processes to run round-robin with IDLE.
*/
#define NR_SCHED_QUEUES 16 /* MUST equal minimum priority + 1 */
#define TASK_Q 0 /* highest, used for kernel tasks */
#define MAX_USER_Q 0 /* highest priority for user processes */
#define USER_Q 7 /* default (should correspond to nice 0) */
#define MIN_USER_Q 14 /* minimum priority for user processes */
#define IDLE_Q 15 /* lowest, only IDLE process goes here */
EXTERN struct proc *rdy_head[NR_SCHED_QUEUES]; /* ptrs to ready list headers */
EXTERN struct proc *rdy_tail[NR_SCHED_QUEUES]; /* ptrs to ready list tails */
服务进程所用的队列通常比用户进程所用的队列优先级更高；而驱动进程所用的队列通常比服务进程所用的队列优先级更高；而时钟和系统任务使用的队列，是所有队列中优先级最高的。
时间片：
用户进程的时间片通常相对较小；驱动进程和服务进程通常应该运行直至阻塞，但实际上被分配了大却有限的时间片。
在每一个时钟节拍，都将检查当前正在运行的进程是否用完了它的时间片，如果是，则它将被放到队尾，然后选择下一个进程运行。
见 /kernel/clock.c 中：
PRIVATE int clock_handler(hook)
irq_hook_t *hook;
{
/* This executes on each clock tick (i.e., every time the timer chip generates
* an interrupt). It does a little bit of work so the clock task does not have
* to be called on every tick. The clock task is called when:
*
* (1) the scheduling quantum of the running process has expired, or
......
*/
......
/* Check if do_clocktick() must be called. Done for alarms and scheduling.
......
*/
if ( ...... || (proc_ptr->p_ticks_left <= 0)) {
prev_ptr = proc_ptr; /* store running process */
lock_notify(HARDWARE, CLOCK); /* send notification */
}
......
}
上面函数clock_handler()中的lock_notify()将导致下面的函数do_clocktick()被调用。
见 /kernel/clock.c 中：
PRIVATE int do_clocktick(m_ptr)
message *m_ptr; /* pointer to request message */
{
......
/* A process used up a full quantum. The interrupt handler stored this
* process in 'prev_ptr'. First make sure that the process is not on the
* scheduling queues. Then announce the process ready again. Since it has
* no more time left, it gets a new quantum and is inserted at the right
* place in the queues. As a side-effect a new process will be scheduled.
*/
if (prev_ptr->p_ticks_left <= 0 && priv(prev_ptr)->s_flags & PREEMPTIBLE) {
lock_dequeue(prev_ptr); /* take it off the queues */
lock_enqueue(prev_ptr); /* and reinsert it again */
}
......
}
上面函数do_clocktick()中的lock_enqueue()实际调用了下面的函数enqueue()，从而选择下一个进程运行。
见 /kernel/proc.c 中：
PRIVATE void enqueue(rp)
register struct proc *rp; /* this process is now runnable */
{
/* Add 'rp' to one of the queues of runnable processes. This function is
* responsible for inserting a process into one of the scheduling queues.
* The mechanism is implemented here. The actual scheduling policy is
* defined in sched() and pick_proc().
*/
int q; /* scheduling queue to use */
int front; /* add to front or back */
/* Determine where to insert to process. */
sched(rp, &q, &front);
/* Now add the process to the queue. */
if (rdy_head[q] == NIL_PROC) { /* add to empty queue */
rdy_head[q] = rdy_tail[q] = rp; /* create a new queue */
rp->p_nextready = NIL_PROC; /* mark new end */
}
else if (front) { /* add to head of queue */
rp->p_nextready = rdy_head[q]; /* chain head of queue */
rdy_head[q] = rp; /* set new queue head */
}
else { /* add to tail of queue */
rdy_tail[q]->p_nextready = rp; /* chain tail of queue */
rdy_tail[q] = rp; /* set new queue tail */
rp->p_nextready = NIL_PROC; /* mark new end */
}
/* Now select the next process to run. */
pick_proc();
}
上面函数enqueue()中的函数sched()和函数pick_proc()将在下面解释。
调度策略：
需要选择一个进程运行的时候，系统会检查最高优先级队列是否为空，若非空，则选择队首进程开始运行，若为空，则对优先级低一级的队列进行类似检查，依此类推。
见 /kernel/proc.c 中：
PRIVATE void pick_proc()
{
/* Decide who to run now. A new process is selected by setting 'next_ptr'.
* When a billable process is selected, record it in 'bill_ptr', so that the
* clock task can tell who to bill for system time.
*/
register struct proc *rp; /* process to run */
int q; /* iterate over queues */
/* Check each of the scheduling queues for ready processes. The number of
* queues is defined in proc.h, and priorities are set in the task table.
* The lowest queue contains IDLE, which is always ready.
*/
for (q=0; q < NR_SCHED_QUEUES; q++) {
if ( (rp = rdy_head[q]) != NIL_PROC) {
next_ptr = rp; /* run process 'rp' next */
if (priv(rp)->s_flags & BILLABLE)
bill_ptr = rp; /* bill for system time */
return;
}
}
}
进程的时间片用完后，将被认为是就绪的，并被放置到所在队列的尾部。
特殊考虑的是：
如果一个进程用完了时间片之后，发现在其之前运行的进程也是它，则其将被放置到优先级更低的队列的尾部；如果其它进程依然没有机会运行，系统将再次降低其优先级；如此持续，保证所有进程都有机会运行。
如果一个进程用完了时间片，但并未妨碍其它进程的运行，则其将被放置到更高优先级的队列中。
IDLE进程独占使用优先级最低的队列，以确保当没有进程需要运行时，IDLE进程可以运行。
见 /kernel/proc.c 中：
PRIVATE void sched(rp, queue, front)
register struct proc *rp; /* process to be scheduled */
int *queue; /* return: queue to use */
int *front; /* return: front or back */
{
/* This function determines the scheduling policy. It is called whenever a
* process must be added to one of the scheduling queues to decide where to
* insert it. As a side-effect the process' priority may be updated.
*/
static struct proc *prev_ptr = NIL_PROC; /* previous without time */
int time_left = (rp->p_ticks_left > 0); /* quantum fully consumed */
int penalty = 0; /* change in priority */
/* Check whether the process has time left. Otherwise give a new quantum
* and possibly raise the priority. Processes using multiple quantums
* in a row get a lower priority to catch infinite loops in high priority
* processes (system servers and drivers).
*/
if ( ! time_left) { /* quantum consumed ? */
rp->p_ticks_left = rp->p_quantum_size; /* give new quantum */
if (prev_ptr == rp) penalty ++; /* catch infinite loops */
else penalty --; /* give slow way back */
prev_ptr = rp; /* store ptr for next */
}
/* Determine the new priority of this process. The bounds are determined
* by IDLE's queue and the maximum priority of this process. Kernel task
* and the idle process are never changed in priority.
*/
if (penalty != 0 && ! iskernelp(rp)) {
rp->p_priority += penalty; /* update with penalty */
if (rp->p_priority < rp->p_max_priority) /* check upper bound */
rp->p_priority=rp->p_max_priority;
else if (rp->p_priority > IDLE_Q-1) /* check lower bound */
rp->p_priority = IDLE_Q-1;
}
/* If there is time left, the process is added to the front of its queue,
* so that it can immediately run. The queue to use simply is always the
* process' current priority.
*/
*queue = rp->p_priority;
*front = time_left;
}