たまに気になるMinixカーネルの仕組みということでプロセス切り替えの仕組みというか次に動くプロセスを選択する仕組みであるpick_proc()を読んでみる。
読んでいるソースは2013/05/04時点でのgitツリーなので将来的には変更があるかも。
s/2014/2013/ だった＼(^o^)／
ファイルはkernel/proc.c。
1706 /*===========================================================================* 1707 * pick_proc * 1708 *===========================================================================*/ 1709 static struct proc * pick_proc(void) 1710 { 1711 /* Decide who to run now. A new process is selected an returned. 1712 * When a billable process is selected, record it in 'bill_ptr', so that the 1713 * clock task can tell who to bill for system time. 1714 * 1715 * This function always uses the run queues of the local cpu! 1716 */ 1717 register struct proc *rp; /* process to run */ 1718 struct proc **rdy_head; 1719 int q; /* iterate over queues */ 1720 1721 /* Check each of the scheduling queues for ready processes. The number of 1722 * queues is defined in proc.h, and priorities are set in the task table. 1723 * If there are no processes ready to run, return NULL. 1724 */ 1725 rdy_head = get_cpulocal_var(run_q_head); 1726 for (q=0; q < NR_SCHED_QUEUES; q++) { 1727 if(!(rp = rdy_head[q])) { 1728 TRACE(VF_PICKPROC, printf("cpu %d queue %d empty\n", cpuid, q);); 1729 continue; 1730 } 1731 assert(proc_is_runnable(rp)); 1732 if (priv(rp)->s_flags & BILLABLE) 1733 get_cpulocal_var(bill_ptr) = rp; /* bill for system time */ 1734 return rp; 1735 } 1736 return NULL; 1737 }
ここでの前提条件は今のMinixはSMPに対応していて、データ構造もpercpuの仕組みが取り入れられているということ。この辺りの話は前にカーネル／VM Advent Calendarで書いたところです。
まずはランキューを取得するところ。
1725 rdy_head = get_cpulocal_var(run_q_head);
get_cpulocal_var()はcpuごとのランキューを取得するということですが、このランキューの構造はというとkernel/cpulocals.hで以下のように定義されていて、proc構造体の配列でサイズはNR_SCHED_QUEUESとなってます。
71 /* CPU private run queues */ 72 DECLARE_CPULOCAL(struct proc *, run_q_head[NR_SCHED_QUEUES]); /* ptrs to ready list headers */ 73 DECLARE_CPULOCAL(struct proc *, run_q_tail[NR_SCHED_QUEUES]); /* ptrs to ready list tails */ 74 DECLARE_CPULOCAL(volatile int, cpu_is_idle); /* let the others know that you are idle */
NR_SCHED_QUEUES等の定義はinclude/minix/config.hに。
68 /* Scheduling priorities. Values must start at zero (highest 69 * priority) and increment. 70 */ 71 #define NR_SCHED_QUEUES 16 /* MUST equal minimum priority + 1 */ 72 #define TASK_Q 0 /* highest, used for kernel tasks */ 73 #define MAX_USER_Q 0 /* highest priority for user processes */ 74 #define USER_Q ((MIN_USER_Q - MAX_USER_Q) / 2 + MAX_USER_Q) /* default 75 (should correspond to nice 0) */ 76 #define MIN_USER_Q (NR_SCHED_QUEUES - 1) /* minimum priority for user 77 processes */
ここまで読むと、ランキューのサイズは16で、配列のインデックスはスケジューリング優先度とイコールとなっているのがわかりますね。。優先度は0～15で0が最優先。優先度0のタスクにアクセスするにはrun_q_head[0]という感じ。
run_q_headはproc構造体の配列なので優先度が同じプロセスが複数ある場合はランキューはどうなるのか？という疑問が出ますよね。kernel/proc.hによると優先度が同じプロセスはproc構造体のp_nextreadyを使ってリスト構造を作っているようです。
67 struct proc *p_nextready; /* pointer to next ready process */ 68 struct proc *p_caller_q; /* head of list of procs wishing to send */ 69 struct proc *p_q_link; /* link to next proc wishing to send */ 70 endpoint_t p_getfrom_e; /* from whom does process want to receive? */ 71 endpoint_t p_sendto_e; /* to whom does process want to send? */
ランキューのrun_q_head[n]でアクセスできるproc構造体はその優先度の中で最優先なプロセスというところでしょうか。
カレントcpuのランキューが取得できたらランキューを優先度の高い順から調べます。
1726 for (q=0; q < NR_SCHED_QUEUES; q++) {
チェック対象のランキューにプロセスがいなければ次の優先度へ。
1727 if(!(rp = rdy_head[q])) { 1728 TRACE(VF_PICKPROC, printf("cpu %d queue %d empty\n", cpuid, q);); 1729 continue; 1730 }
1727行目のif文でプロセスが見つかったらこのプロセスが次に動くプロセスになります。
プロセスが見つかったけどプロセスの状態チェックを入れます。プロセスが実行状態じゃないのにここに来たらバグですね。
1731 assert(proc_is_runnable(rp));
次のチェックですが、プロセスにBILLABLEビットが立っていたらrpをbill_ptrに代入します。
1732 if (priv(rp)->s_flags & BILLABLE) 1733 get_cpulocal_var(bill_ptr) = rp; /* bill for system time */ 1734 return rp;
bill_ptrはpercpuなproc構造体です。なのでkernel/cpulocals.hに定義があります。
55 DECLARE_CPULOCAL(struct proc *,bill_ptr);/* process to bill for clock ticks */
1732、1733行目はcpu利用時間をプロセスに足す必要があるプロセス（普通のユーザプロセス）の場合の処理という感じですかね。
そして最後に実行対象のプロセスを返して終了です。
もし実行対象のプロセスが全くなければNULLを返しています。
