當(dāng)進(jìn)程被中斷（被輸入輸出設(shè)備或時(shí)鐘等），或進(jìn)程執(zhí)行軟中斷指令，或進(jìn)程結(jié)束時(shí)，系統(tǒng)將決定接下來運(yùn)行哪個(gè)進(jìn)程。
隊(duì)列優(yōu)先級(jí)：
Minix的進(jìn)程調(diào)度使用多級(jí)隊(duì)列，每個(gè)隊(duì)列的優(yōu)先級(jí)不同。
見 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 */
服務(wù)進(jìn)程所用的隊(duì)列通常比用戶進(jìn)程所用的隊(duì)列優(yōu)先級(jí)更高；而驅(qū)動(dòng)進(jìn)程所用的隊(duì)列通常比服務(wù)進(jìn)程所用的隊(duì)列優(yōu)先級(jí)更高；而時(shí)鐘和系統(tǒng)任務(wù)使用的隊(duì)列，是所有隊(duì)列中優(yōu)先級(jí)最高的。
時(shí)間片：
用戶進(jìn)程的時(shí)間片通常相對(duì)較小；驅(qū)動(dòng)進(jìn)程和服務(wù)進(jìn)程通常應(yīng)該運(yùn)行直至阻塞，但實(shí)際上被分配了大卻有限的時(shí)間片。
在每一個(gè)時(shí)鐘節(jié)拍，都將檢查當(dāng)前正在運(yùn)行的進(jìn)程是否用完了它的時(shí)間片，如果是，則它將被放到隊(duì)尾，然后選擇下一個(gè)進(jìn)程運(yùn)行。
見 /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 */
}
......
}
上面函數(shù)clock_handler()中的lock_notify()將導(dǎo)致下面的函數(shù)do_clocktick()被調(diào)用。
見 /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 */
}
......
}
上面函數(shù)do_clocktick()中的lock_enqueue()實(shí)際調(diào)用了下面的函數(shù)enqueue()，從而選擇下一個(gè)進(jìn)程運(yùn)行。
見 /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();
}
上面函數(shù)enqueue()中的函數(shù)sched()和函數(shù)pick_proc()將在下面解釋。
調(diào)度策略：
需要選擇一個(gè)進(jìn)程運(yùn)行的時(shí)候，系統(tǒng)會(huì)檢查最高優(yōu)先級(jí)隊(duì)列是否為空，若非空，則選擇隊(duì)首進(jìn)程開始運(yùn)行，若為空，則對(duì)優(yōu)先級(jí)低一級(jí)的隊(duì)列進(jìn)行類似檢查，依此類推。
見 /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;
}
}
}
進(jìn)程的時(shí)間片用完后，將被認(rèn)為是就緒的，并被放置到所在隊(duì)列的尾部。
特殊考慮的是：
如果一個(gè)進(jìn)程用完了時(shí)間片之后，發(fā)現(xiàn)在其之前運(yùn)行的進(jìn)程也是它，則其將被放置到優(yōu)先級(jí)更低的隊(duì)列的尾部；如果其它進(jìn)程依然沒有機(jī)會(huì)運(yùn)行，系統(tǒng)將再次降低其優(yōu)先級(jí)；如此持續(xù)，保證所有進(jìn)程都有機(jī)會(huì)運(yùn)行。
如果一個(gè)進(jìn)程用完了時(shí)間片，但并未妨礙其它進(jìn)程的運(yùn)行，則其將被放置到更高優(yōu)先級(jí)的隊(duì)列中。
IDLE進(jìn)程獨(dú)占使用優(yōu)先級(jí)最低的隊(duì)列，以確保當(dāng)沒有進(jìn)程需要運(yùn)行時(shí)，IDLE進(jìn)程可以運(yùn)行。
見 /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;
}