648 行目は動的優先度の言 fr 算です。式の詳細はあとで説 明しますが、プロセスカ以リープしていた時間の統言十値を もとに計算される一 5 ~ 十 5 の値になります。つまり、ス リーフ畤間が長いと bonus の値がプラスになって優先度 が - ヒがり、スリーフ畤間が短いとマイナスになって優先度 が - ドがります。 そして、 650 ~ 654 行目では、静的優先度と動的優先度を 加算してプロセスの優先度を計算し、効な値の範囲 ( 100 ~ 139 ) を超えた場合の補正をおこなっています。 こで、 648 行目の bonus の言算について詳しくみて いきましよう。 648 行目のマクロ CURRENT-BONUS() は、プロ セスのポーナスを計算するマクロで、以下のように定義さ れています。このマクロは以降の説明で何度も登場するの で、しつかり理解しておきましよう。 0126 : #define CURRENT—BONUS (p) \ 図 7 山 0 sleep-avg とポーナス 8 6 4 2 0 0 2e + 08 4e + 08 6e + 08 sleep—avg 8e + 08 1 e + 09 0127 : 0128 : (NS_TO_JIFF 工 ES( (p)—>sleep_avg) * \ MAX_BONUS / MAX_SLEEP_AVG) プロセス構造体のメンバー sleep_avg には、後述するス リーフ塒間がナノ秒単位で格納されています。 127 行目の NS-TO-JIFFIES() は、ナノ秒を jiffiesl の単位に変換す るマクロで、具体的には 10 , 000 , 000 で除算します。 では、 NS-TO-JIFFIES() については、あまり気にする 必要はありません。 sleep-avg の言算方法はあとで説明しますが、その最大 0096 : #define NS_MAX_SLEEP_AVG 値は以下のように定義されています。 ついても、 0 から MAX-BONUS までの範囲の値を返す とること力分かり、さらに、 CURRENT-BONUS(p) に sleep-avg) は、 0 から MAX-SLEEP-AVG までの値を したがって、 127 行目にある NS-TO-JIFFIES((p)-> (JIFFIES_TO_NS (MAX_SLEEP_AVG) ) 32 1 100HZ のクロック周期て増える内部カウンタ。 (MAX_USER_PRIO * PRIO_BONUS_RATIO/IOO) 0092 : #define MAX_BONUS 0091 : #define PRIO_BONUS_RATIO 25 次に MAX-BONUS の定義を示します。 ことが分かります。 定数値 MAX-USER-PRIO は、一般プロセス用に用 意された優先度 ( 100 ~ 139 ) の数である、、 40 " に置き換え られます。そして、 MAX-BONUS は、一一般プロセスの 優先度に反映するボーナスの範囲をその 25 % と定義して います。つまり、ボーナスは 0 ~ 10 の範囲で得られる ( 図 7 ) ので、プロセスの優先度は 11 段階の範囲を上がっ たり下がったりします ( 図では分かりにくいと思いますが、 sleep-avg が最大のときのポーナスは 10 です ) 。 こまでの説明か理解できたら、 648 行目の bonus の 引算に戻りましよう。 上記のように、 CURRENT-BONUS(p) は 0 ~ 10 の 値を返します。そこから 5 を引くため、 bonus にはー5~ 十 5 の値か設定されることになります。 タイムスライス Linux カーネルのタイムスライスとは、プロセスが ac ー tive キューに滞留できる時間の長さを表す力ウンタです。 実行中状態のプロセスは、クロック周期ごとにタイムスラ イスがデクリメントされ、カウンタ値が 0 になると ex- pired キューに移されます。 ただし、ユーザーと対話的に動くプロセスは例外で、ふ たたび active キューに登録されます。これは、応答性を 高めるためと、対話的プロセスはすぐにスリープしてラン キューから削除される可能「生があるからだと思われます。 タイムスライスの初期値は、 fork システムコールでプロ セスを生成するときに、 sched-fork() のなかで以下のよう に設定されます。 p—>time—slice current—>time_slice > > = 1 ・ (current—>time—slice 十 1) > > 1 ; UNIX MAGAZINE 2006 . 1

特集 V Linux のプロセス [ 1 ] 図 9 sleep-avg の値か言綻されたときの CURRENT-BONUS() DEF_TIMESLICE) ) CURRENT_BONUS (JIFFIES_TO_NS (MAX_SLEEP_AVG (MAX_SLEEP_AVG DEF_TIMESLICE) x MAX_BONUS MAX_SLEEP_AVG MAX_SLEEP_AVG = MAX_BONUS DEF_TIMESLICE x MAX_BONUS = 10 10 x 10 100 9 ステムを再起動するしかありません。 なぜここで停」 E 状態の説明を始めたかというと、スリー フ塒間の計算方法が停止状態によって異なるからです。 停止していたプロセスカ起きるとき、カーネルは優先度 を再言算するために recalc-task-prio() を呼び出します。 そして、このサプルーチンのなかでスリーフ畤間を言 - 算し 表 1 INTERACTIVE-SLEEP() の値 nice 値 —20 ー 19 ー 18 ー 17 ー 16 ー 15 ー 14 ー 13 ー 12 ー 11 ー 10 ー 9 ー 8 ー 7 n ice 値 秒 イ直 秒 ます。 0676 : 0677 : 0678 : 0679 : 0682 : 0683 : 0684 : 0685 : static int recalc—task—prio(task—t *P' if (_—sleep—time > NS—MAX—SLEEP—AVG) now ー p—>timestamp; unsigned 10 Ⅱ g long ——sleep—time unsigned 10 Ⅱ g long now) 0.29 0.39 (). 39 (). 39 0.39 0.49 0.49 0.49 (). 49 0.59 0.59 0.59 0.59 0.69 ー 6 ー 5 ー 4 ー 3 ー 2 -1 0 1 2 7 6 5 4 3 0.69 0.69 0.69 0.79 0.79 0.79 0.79 0.79 0.79 0.89 0.89 0.89 0.89 0.79 8 9 10 11 12 13 14 15 16 19 18 17 秒 0.99 0.99 0.99 0.99 1.09 1.09 1.09 1 . 19 1 .09 1.19 1.19 1 . 19 sleep—time else sleep—time NS_MAX_SLEEP_AVG ; sleep—time ; 679 行目の timestamp には、プロセスの状態が停止中 になった時刻が定されています。 679 ~ 685 行目では、変数 now に設定されている現在時 刻との差分からプロセスの停止時間を計算しますが、 NS- MAX-SLEEP-AVG ( 1 秒 ) よりも大きくならないよう にしています。 0687 : 0694 : 0695 : 0696 : 0697 : if (sleep-time > 0 ) { if (p->mm & & p->activated ! = s1eep—time>INTERACTIVE_SLEEP (P) ) p—>sleep-avg JIFFIES_TO_NS (MAX_SLEEP_AVG ー DEF_TIMESLICE) ; こでは川頁番を逆にして、 696 行目で設疋している sleep -avg の値をみてみましよう。この値が設定されたときの CURRENT-BONUS() は、図 9 のように、、 9 " になりま す。 こでのポイントは、長時間スリープしているプロセス は、最大値のポーナスが与えられるわけではないというこ とです。たとえば、 UNIX MAGAZINE 2006 . 1 while ( 1 ) { sleep(l) ; usleep ( 50000 の ; / / 0.5 秒 while ( 1 ) { のように長時間スリープするプロセスよりも、 35 は、 695 行目のマクロ INTERACTIVE-SLEEP() で計 プロセスが対話中かアイドルしているかを判断する閾値 しよう。 ナスが最大にならない程度の sleep-avg が設疋されるので くしてしまうかもしれません。これを避けるために、ポー 与えると、対話中のプロセスを蹴散らして CPU を喰い尽 このとき、アイドルしていたプロセスに最大のポーナスを く起きているプロセスはユーザーと対話中と推測できます。 時間スリープしているプロセスはアイドル中、ちよくちょ のユーザープロセスには同じⅲ ce 値か第殳定されていて、長 のは次のような理由からだと思われます。まず、ほとんど ナスを与えればよいような気がしますが、そうしていない 単純に考えると、スリープすればするほどたくさんボー カ皜くなります (top コマンドで確認してみましよう ) 。 のようにちよくちよく起きているプロセスのほうが優先度

特集 V Linux のプロセス [ 1 ] 図 6 イ憂先度を表す数値 ています。 . static—prio = MAX—PRIO—20, MAX-PRIO は 140 なので初期値は 120 、つまり、 nice 値 0 と等価な値が設定されます。 上記のように、プロセスの優先度は生まれたときに親プ ロセスから受け継がれます。その後、 ・タイムスライスを使いきったとき ・スリープしていたプロセスを起こす ( 停止中から実行可 能に移動する ) とき リシーを適用したものがリアルタイム・プロセスです。 に優先度を計算してプロセス構造体に再設定します。 このポリシーをプロセスに適用すると、 次に、優先度を言 t 算する effective-prio() をみていきま しよう。以下のコードは、 kernel/sched. c で定義されて ・一殳のプロセスよりも高い優先度が割り当てられる います。 ・ CPU の使用時間に応じた優先度の上げードげがない のように、カーネルから特別扱いを受けることができます。 static int effective—prio(task—t *p) 0641 : 0642 : プロセスにリアルタイム・スケジューリングのポリシー 0643 : int bonus , priO ; を適用するには、 sched-setscheduler システムコールを 0644 : if (rt-task(p) ) 0645 : 実行します。プロセスの優先度は、システムコールの引数 0646 : return p—>prio; で指定します。 0647 : bonus = CURRENT—BONUS (p) -MAX—BONUS/2 ; 0648 : こでは、、リアルタイム " という名前が使われています 0649 : が、いわゆるリアルタイム OS のような厳密な創未での実 0650 : priO = p¯>static—prio ー bonus; if (prio く MAX-RT-PRIO) 0651 : 時間性はなく、たんにヨ殳プロセスよりも優先的に実行す 0652 : prio = MAX—RT_PRIO ; るというだけです。 if (prio > MAX—PRIO—I) 0653 : 0654 : pri0 = MAX—PRIO-I ; 一方、一ヨ殳のプロセスでは、一 20 ~ 19 の nice 値を 100 0655 : 0656 : } ~ 139 に 1 対 1 で変換した値カ靖的優先度として言置され ます ( 図 6 ) 。もし、静的優先度と動的優先度を合わせた数 effective-prio() は、プロセス構造体へのポインタを引 値が 100 未満になった場合は、強制的に 100 に修正され 数に与えると、 0 ~ 139 の優先度が返ってくるサプルーチン ます。 です。 それでは、優先度の初期値はいつどこで設疋されるので 645 ~ 646 行目では、プロセスがリアルタイム・プロセ しようか。通常は、 fork システムコールの処理中に呼び出 スの場合、静的に設定されている優先度をそのまま呼出し される wake-up-new-task() によって、次のように親プ 元に返します。つまり、リアルタイム・プロセスでは優先 ロセスの優先度がコピーされます。 度の動的な調整はおこないません。 current—>prio p¯>prio 645 行目の rt-task() はリアルタイム・プロセスか否か 同様に、親プロセスの優先度もその親からコピーされる を判別するマクロで、以下のように定義されています。 ことになるので、親子関係を遡っていくと、 init プロセス #define rt-task(p) (p—>prio く MAX_RT—PRIO) ) の優先度カ源であることが分かります。 648 行目以降では、リアルタイムではない一般プロセス init プロセスの初期値は、 include/linux/init-task. h の場合の優先度を計算します。 で定義されており、優先度については以下の値が設定され 優先値 0 1 リアルタイム 2 プロセス 99 nice 値 優 先 ÖO ー ー 20 ー 19 一般 01 ー、 度 プロセス 0 0 0 ) 31 UNIX MAGAZINE 2006 . 1

1 , 373 ~ 1 , 374 行目の式はひどく複雑にみえますが、以 下のように川頁番を入れ替えてみると、じつはそれほと。難し くありません。 になった時刻が設定されています ( 2 , 902 行目 ) 。つまり、 now と timestamp の差分は、実行中状態にある時間 ( ラ ンタイム ) を表すわけです。 NS-MAX-SLEEP-AVG は、スリーフ時間の最大値 ( 1 ( 0 わ 1 の x 0.95 x 100 秒 ) をミリ秒で表した値に置き換えられます。つまり、ラ 10 ンタイムの最大値も 1 秒です。 1 , 374 行目の MAX-SLEEP-AVG はスリーフ畤間の このあと、ランタイムを CURRENT-BONUS() で割 最大値を表し、コンパイル時に 100 に展開されます。クロ り ( 2 , 800 行目 ) 、その結果をスリーフ畤間から引いていま ック割込みが 100Hz の場合は、 sleep-avg の最大値は 1 す ( 2 , 895 行目 ) 。 秒になります。 CURRENT-BONUS() は、 sleep-avg が大きいほど 実際には整数演算でだいぶ丸められてしまいますが、お 大きな値になるので、ランタイムも小さくなり、 sleep-avg おむね親プロセスの 95 % くらいの値になると考えてよいで も減りにくくなります。したがって、いったん動的優先度 しよう。たとえば、シェル端末をしばらく放置しておくと、 カ皜くなったプロセスは、その後も動的優先度が - ドがりに シェルプロセスの sleep-avg には 1.0 秒が設定されます。 くくなります。 そして、そこからコマンドを入力してプロセスを起動する 次は、スリーフ畤間を増加させる処理です。当然のこと と、 1 , 373 ~ 1 , 374 行目の計算結果は 0.9 秒になります。 ながら、スリーフ塒間はプロセスが停止中状態になると増 CHILD-PENALTY の値は、子プロセスの優先度を再 加します。しかし、ユーザーからみれば、、停止している " だ t 算するとき、親プロセスより下げる度合いを制御するパ けのプロセスでも、カーネル内部では以下の 2 つのどちら ラメータのようです。 かの状態で管理されています。 次に、スリープ時間が減少する処理をみてみましよう。 ・ TASK-INTERRUPTIBLE 以下は、 kernel/sched. c で定義されている schedule() か ・ TASK-UNINTERRUPTIBLE ら該当部分を抜き出したコードです。 TASK-INTERRUPTIBLE は割込み可能な停」 . E 状 2773 : prev = current ; で、外部から SIGINT などのシグナルを送るとプロセス Ⅱ 0 = sched—clock() ; 2788 : を起こすことができます。たとえば、 select や nanosleep if ( (now ー prev—>timestamp) 2789 : システムコールなどで自発的にスリープした場合は、この く NS_MAX_SLEEP_AVG) { 2790 : run t ime IIOW ー prev—>timestamp ; 羽になります。 if ( ( Ⅱ 0 ー prev—>timestamp) く 0 ) 2791 : 一方、 TASK-UNINTERRUPTIBLE は割込み不可 2792 : run_time } else 2793 : 能な停 IE 状態です。この状態のプロセスは、シグナルを送 2794 : run_time = NS_MAX_SLEEP_AVG ; っても起こすことはできません。ーヨ殳に、デバイスの I/O run-time / = (CURRENT—BONUS (prev) ? ・ 2800 : 待ちが発生した場合 ( 非自発的なスリープ ) に、この状態に prev->sleep-avg run_time ; なることが多いようです。 if ( (long)prev—>sleep—avg く = 0 ) たとえば、 NFS サーバーが停止すると、そのサーバー prev—>sleep—avg = 0 ; を NFS マウントしているホスト上のプロセスが固まって if (prev ! = next) { しまうことがあります。そのプロセスを強制終了させよう next—>timestamp = now; として、端末上で ctrl-c を入力しても、 SIGKILL を prev = context—switch(rq, prev, next) ; 送っても終了させることはできず、途方に暮れた経験のあ る人も多いと思います。これは、プロセスが TASK-UN- 2 , 773 行目の current は、スケジューラカ剛乎び出され INTERRUPTIBLE で停止しているためで、プロセスを る直前まで実行中だったプロセス構造体へのポインタです。 終了させるには NFS サーバーが復旧するのを待つか、シ 2 , 789 行目の timestamp には、プロセスの羽こ態が実行中 一三ロ 2895 : 2896 : 2897 : 2901 : 2902 : 2908 : 34 UNIX MAGAZINE 2006 . 1

子プロセスは、親プロセスの半分のタイムスライスを受 け取ります。同時に、親プロセスのタイムスライスも半分 になります。つまり、親が子に半分を分け与えています。 どこの世界でも、親は子に身を削られるものです。 の 50 タイムスライスをデクリメントする処理は、 100Hz 周 期 ( 10 ミリ秒ごと ) のクロック割込みハンドラから呼び出 される 2 scheduler-tick() のなかでおこなわれます。そし て、デクリメントの結果が 0 になったら、タイムスライス の再設定をおこないます。該当する部分のコードは、次の ード 0 10 20 30 40 60 70 特集マ Linux のプロセス [ 1 ] 図 8 優先度とタイムスライス値 80 十 十 十 十 十 十 十 十 十 十 十 十 十 十 十 十 十 十 十 ようになっています。 if (!——p->time-slice) { task—timeslice(p) ; p—>time—slice は、 kernel/sched. c で次のように定義されています。 タイムスライスを言 - 算する task-timeslice() のコ 的に、優先度カ皜いほど長いタイムスライスが得られます。 100 105 1 10 1 1 5 120 125 130 135 140 priority プ ( 停止 ) していた時間 3 を表す数値で、優先度の計算に使 タが登場しました。これは、文字どおりプロセスカ以リー の説明で、、、 ( プロセスの ) スリーフ寺間 " というパラメー プロセスの優先度を計算する effective-prio() について スリーオ寺間 由はよく分かりません ) 。 ( 優先度 120 のところでグラフの線が切れていますが、理 0059 : 0085 : 0086 : 0166 : 0167 : 0168 : 0169 : 0170 : 0171 : 0172 : 0173 : 0174 : 0175 : #define NICE—TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20 ) p—>static—prio) ; return SCALE—PRIO (DEF—TIMESLICE , else p—>static—prio) ; return SCALE—PRIO (DEF—TlMESLICE*4 , if (p—>static-prio く NICE—TO-PRIO(O) ) task—timeslice(task—t *p) static unsigned int / (MAX_USER_PRIO/2) , MIN-TIMESLICE) max(x * (MAX—PRIO ー prio) #def ine SCALE—PRIO (x , prio) \ #define DEF—TIMESLICE ( 100 * HZ / 1000 ) #define MIN—TIMESLICE max(5 * HZ / 1000 , 1 ) われます。 各プロセスのスリーフ畤間を管理するために、 構造体にメンバー変数 sleep-avg が用意され、 秒単位の値が十内されます。 プロセス こにナノ ます、初期値からみていきましよう。以下は、 wake-up- new-task() から該当部分を抜き出したコードです。 0088 : 1373 : 1374 : #define CHILD_PENALTY 95 p->sleep-avg = JIFFIES—TO—NS( CURRENT_BONUS (p) * CHILD_PENALTY / 100 * MAX_SLEEP_AVG / MAX—BONUS) ; task-timeslice() は、 100 ~ 139 の優先度に応じてタイ ムスライス値を計算する処理を実行します。じっと式を眺 めるよりも、グラフを描いたほうが -- - ・目暸然です ( 図 8 ) 。 クロック割込みの周期を 100HZ とすると、 1 タイムス ライスは 10 ミリ秒になります。よって、タイムスライス の最大値は 800 ミリ秒で、最小値は 10 ミリ秒です。 タイムスライスの引算方法は、 nice 値 ( 優先度 120 ) が 0 よりも小さいかどうかで異なります ( 171 行目 ) 。基本 2 具イ柘勺なⅡ日しの頂番は、 IRQO 発生→ timer-interrupt() → do- timer 」 nterrupt() → do-timer-interrupt-hook() → update- process-times() → scheduler-tick() てづ - UNIX MAGAZINE 2006 . 1 wake-up-new-task() は、 fork システムコールの処理 中に呼び出されるサプルーチンです。 前述したように、マクロ CURRENT-BONUS() の計 算では sleep-avg を参照します。 1 , 373 ~ 1 , 374 行目を実 行する時点で sleep-avg には何が常内されているのかとい うと、 wake-up-new-task() カ剛乎び出される前に、親プロ セスの sleep-avg がコピーされています。 3 ランキュー内で待機していた時間を含む場合もあります。 33

算しています。このマクロはプロセスの静的優先度 (nice 得られると、 728 行目での sleep-avg の増加量も大きくな 値 ) を入力にとり、表 1 の結果を出力します ( 実際の出力は ります。この言 fr 算は、おそらく、前回の実行時に低い動的 ナノ秒単位ですが、秒に変換しています ) 。 優先度が与えられていたプロセスに高い優先度を与えるよ うにするためではないかと思います。 この表から分かるとおり、 nice 値が小さい ( 静的優先度 の高い ) プロセスは、すこしスリープしただけで、、対話中で 710 ~ 718 行目では、プロセスが起きる前の停」 - E 状態が はない " と判断されるようです。一方、 12 以上の nice 値 TASK-UNINTERRUPTIBLE だった場合の処理をお こない、 sleep-avg が INTERACTIVE-SLEEP() を超 が設定されたプロセスは、 695 行目の条件式が成立するこ えないようにしています。つまり、 I / O 待ちで停止してい とはありません。なぜなら、 683 行目で sleep-time の最 たプロセスは、いくら長くスリープしても上限で抑えられ 大値を 1 秒に制限しているからです。 ることになります。 694 行目の条件式では、カーネルスレッドではないこと 728 ~ 731 行目では、 sleep-avg に sleep-time を加算 と、起床前・の ) 大が TASK-UNINTERRUPTIBLE で し、最大値を超えないように調整しています。 はなかったことを確認しています。 けっきよく、プロセスは、 I / O 待ちのようにスリープさ } else { せられたときより、自発的にスリープしたときのほうが優 先度カ皜くなる傾向があります。 最後に、 735 行目で effective-prio() を呼び出し以上 の処理で更新された sleep-avg を用いて優先度の再十算を おこないます。 ☆ 0698 : 0703 : sleep-time * = (MAX—BONUS CURRENT_BONUS (p) ) ? 、一三ロ if (p->activated if (p->sleep-avg > = INTERACTIVE_SLEEP (p) ) sleep—time else if (p->sleep—avg + sleep—time > = INTERACTIVE_SLEEP (p) ) p—>sleep—avg INTERACTIVE_SLEEP (p) ; sleep—time 0710 : 0711 : 0712 : 0713 : 0714 : 0715 : 今回はスケジューラの概要と、スケジューリングに使用 されるパラメータについて説明しました。 次回は、スケジューラとディスパッチャのコードについ て解説します。 ( しらさき・ひろお IIJ) [ 文献 ] 0716 : 0717 : 0718 : p—>sleep—avg + = sleep—time ; if (p—>s1eep-avg>NS-MAX-SLEEP_AVG) p—>sleep—avg = NS—MAX—SLEEP—AVG ; 0728 : 0729 : 0730 : 0731 : 0732 : 0733 : 0734 : return effective—prio(p) ; 0735 : 0736 : 以下の条件のいずれかが成立する場合は、 698 ~ 733 行 目の else 文プロックが実行されます。 ・カーネルスレッドである。 ・起床する前の状態が TASK-UNINTERRUPTIBLE だった。 ・スリーフ畤間が短い。 703 行目では、 sleep-avg が小さいほど sleep-time が大 きくなるような言 t 算をしています。大きな sleep-time が [ 1 ] 「 IA -32 インテルアーキテクチャ・ソフトウェア・テべロッパー ズ・マニュアル」生・中・一ド ) 、 2004 年 (http://www.intel. com/jp/developer/download/) 36 UNIX MAGAZINE 2006 . 1