読者です 読者をやめる 読者になる 読者になる

〆(.. )カリカリッ!! Minix3のpick_proc()

minix kernel

たまに気になる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を返しています。