この章では、Linux カーネルが提供しなければならない汎用的なタスクとメカニズム のいくつかについて解説する。それらは、カーネルの他の部分(すなわちこの章で述べら れるいくつかのタスクやメカニズム以外の部分)が効率よく協調動作するために必要なも のである。
図表(11.1) ボトムハーフハンドラのデータ構造
カーネルにタスク処理をさせる場合、この時点では処理をさせたくない、という時が
しばしばある。割り込みを処理させる場合は、特にそうである。割り込みが起こると、
プロセッサは実行中の処理を停止し、オペレーティングシステムがその割り込みを適切
なデバイスドライバに伝達する。しかし、デバイスドライバに割り込みを処理させる
場合、割り込み処理中には、システム上で他の処理を実行できない。したがって、デバ
イスドライバは、割り込みの処理にあまり時間を掛けてはいけない。他方、その場で直
ぐに処理せずとも、何の問題もないケースもしばしば存在する。Linux のボトムハーフ
ハンドラが発明されたのは、デバイスドライバやその他のカーネルルーチンがそうした
仕事を一旦キュー上に置いて、あとで処理できるようにするためである。図表(11.1)で
は、ボトムハーフハンドラに関するカーネルのデータ構造体が示されている。
[see:
include/linux/interrupt.h]
32 個までの異なるボトムハーフハンドラが存在し得る。
bh_base は、
カーネルの個々のボトムハーフ処理ルーチンへのポインタのテーブルである。bh_active と bh_mask は独自のビットセットを持っていて、その値
はどのようなハンドラがインストールされてアクティブになっているのかによる。
bh_mask にビット N がセットされた場合、bh_base の N 番目の
要素がそのボトムハーフハンドラのアドレスを含んでいる。bh_active に
ビット N がセットされた場合、スケジューラが合理的と考えた直後に N 番目の
ボトムハーフハンドラルーチンが呼び出される。それらのインデックスは静的に
定義されている。タイマー(timer)ボトムハーフハンドラは最優先であり(index 0)、
コンソール(console)ボトムハーフハンドラはそれに次ぐ優先度を持つ(index 1)等
である。
典型的には、ボトムハーフハンドラはそれらと関連したタスクのリストを持っている。
たとえば、イミディエート(immediate)ボトムハーフハンドラはイミディエートタスク
キュー(
tq_immediate)
を通じて処理を行うが、そのキューには即座に(immediately)処理される必要のある
タスクが含まれる。
カーネルのボトムハーフハンドラのいくつかは、デバイス固有のものであるが、 それ以外は汎用的である。
このハンドラは、システムの定時的なタイマーが割り込むときに、いつもアクティブと マークされ、カーネルのタイマーキューメカニズムを駆動するために使用される。
このハンドラは、コンソールメッセージを処理するために使用される。
このハンドラは、tty メッセージを処理するために使用される。
このハンドラは、一般的なネットワーク処理をこなす。
これは汎用ハンドラであり、いくつかのデバイスドライバが後で行おうとする仕事を キューに入れるために使用される。
デバイスドライバやカーネルの他の部分が仕事を後回しにする必要があるときは
いつも、その仕事を、たとえばタイマーキューのような、適切なキューに置き、
カーネルにシグナルを送って、ボトムハーフ処理の実行が必要であることを伝える。
それをするには、
bh_active の適切なビットを設定すればよい。
たとえば、ビット 8 が設定されるのは、ドライバが何かをイミディエートキュー上に
置いて、ボトムハーフハンドラが実行されて処理されるのを望む場合である。
bh_active のビットマスクがチェックされるのは、個々のシステムコールの
終了時であり、制御が呼び出しプロセスに戻る直前である。
何らかのビットがセットされていた場合、アクティブなボトムハーフハンドラが
呼び出される。ビット 0 がまず最初にチェックされて、次に 1 へと順次進んで、
31 までチェックされる。
[see: do_bottom_half(), in
kernel/softirq.c]
bh_active のビットは、個々のボトムハーフハンドラが呼び出されるたびに
クリアされる。すなわち、bh_active は一時的なもので、スケジューラが
呼び出されたその時点では意味を持つが、次の呼び出しがなされる際には意味を持たな
い。したがって、この方法を使えば、処理すべき仕事がない場合、ボトムハーフ処理
ルーチンは呼び出されない。
図表(11.2) タスクキュー
タスクキューは、カーネルが仕事を後回しにする方法である。
[see:
include/linux/tqueue.h]
Linux には、仕事をキュー上に置いて、後で処理をする汎用的なメカニズムがある。
タスクキューはしばしばボトムハーフハンドラと一緒に使用される。タイマータスク
キュー(timer task queue)は、タイマーキューボトムハーフハンドラ(timer queue
bottom half handler)が実行されるときに処理される。
タスクキューはシンプルなデータ構造体であり、図表(11.2)に示されるように、
tq_struct データ構造体の単純な連結リストであ
る。その個々の構造体には、ルーチンのアドレスとデータへのポインタが含まれてい
る。タスクキュー上の要素が処理されるとき、ルーチンが呼び出され、その際、ルーチ
ンへはデータへのポインタが渡される。
カーネル内の何らかのルーチン、たとえばデバイスドライバは、タスクキューを 作成し利用することができるが、次の 3 つのタスクキューは、カーネルによって 作成され管理されている。
このキューは、次のシステムクロックティック(clock tick)の出来るだけ直後に実行さ れるべき仕事をキューイングするために使用される。 クロックティックごとにこのキューがチェックされ、エントリが含まれているかどうか 確認される。エントリが含まれていた場合、タイマーキューボトムハーフハンドラが アクティブにされる。 スケジューラが次に実行される時には、タイマーキューボトムハーフハンドラが、 その他すべてのボトムハーフハンドラと伴に処理される。 このキューとシステムタイマーを混同してはいけない。後者は、ずっと洗練された メカニズムを持っている。
このキューも、スケジューラがアクティブなボトムハーフハンドラを処理するときに 処理される。イミディエート(immediate)ボトムハーフハンドラは、タイマーキュー ボトムハーフハンドラほど優先順位は高くないので、これらのタスクは後から実行 される。
このタスクキューは、スケジューラ自身によって処理される。これは、システム上の 他のタスクキューをサポートするために使用されるので、この場合、実行されるべき タスクは、タスクキューを処理するルーチン、たとえば、デバイスドライバである。
タスクキューが処理されるとき、キューの最初の要素に対するポインタがキュー から削除されて、ヌルポインタ(null pointer)と置き換えられる。実際、この削除 処理は、排他的な操作(atomic operation)なので、割り込みできないように なっている。次に、キュー上の個々の要素が自分の処理ルーチンを順番に呼び出す。 キュー上の要素はしばしば静的に割り当てられたデータである。しかし、割り当て られたメモリを破棄する固有のメカニズムは存在しない。タスクキュー処理ルーチン は単にリスト上の次の要素の処理に移るだけである。割り当てられたカーネルメモリ を確実に適宜再利用可能にするためには、タスク自体がその処理をしなければならな い。
図表(11.3) システムタイマー
オペレーティングシステムには、将来の特定の時間にタスクを処理できるような
スケジューリング機能が必要である。そして、スケジューリングにより、タスクを
比較的正確な時間に実行できるようなメカニズムが必要とされる。この点、オペレーテ
ィングシステムをサポートしようとするプロセッサには、必ずプログラム可能なイン
ターバルタイマーがあり、それが定期的にプロセッサに割り込みを掛けている。この
定期的な割り込みは、システムクロックティックと呼ばれる。それは、メトロノームに
似た働きをして、システムの活動を指揮している。
Linux は時刻管理に対して非常にシンプルな見方をしている。
Linux は、時間を起動時からのクロックティック(clock tick)によって計る。すべての
システムタイマーはその計測を基にしており、その計測方法は、広く利用されている
変数名にちなんで jiffies と呼ばれている。
Linux には二種類のシステムタイマーがある。どちらのキュールーチンも、ある
システム時間に呼び出されるのだが、それらは実装においてやや異なっている。
図表(11.3) では、両方のメカニズムが示されている。
[see:
include/linux/timer.h]
ひとつめは、古いタイマーメカニズムであり、
timer_struct データ構造体への 32 個のポインタによる静的配列と
アクティブタイマーのマスク
timer_active から構成されている。
タイマーがタイマーテーブル内のどこに置かれるかは、静的に定義されている。
(これは、ボトムハーフハンドラのテーブル bh_base にやや似ている。)
エントリがこのテーブルに付け加えられるのは、大抵の場合システム起動時である。
ふたつめは、それより新しいメカニズムであり、
timer_list データ構造体の連結リストを使用する。リストの要素は、
タイマー終了までの残り時間(expire time)の長さの順番で並べられている。
どちらの方法の場合でも、タイマーの残り時間を計る際の指標として jiffies を使用する。
それゆえ、5 秒間だけ実行されるタイマーは、まず 5 秒という時間を jiffies の単位に変換して、それを現在のシステム時間に加算することで、タイマーが
終了すべき時刻を jiffies 形式のシステム時間として獲得する。
システムクロックティッごとに、タイマーボトムハーフハンドラはアクティブとマーク
され、それによって、スケジューラが次に起動されるときに、タイマーキューが処理
される。タイマーボトムハーフハンドラは、両方のタイプのシステムタイマーを処理す
る。古いほうのシステムタイマーの場合、timer_active ビットマスクがチェ
ックされ、設定ビットが確認される。
[see: timer_bh(), in
kernel/sched.c]
[see: run_old_timers(), in
kernel/sched.c]
[see: run_timer_list(), in
kernel/sched.c]
アクティブタイマーの終了時間が経過した場合
(終了時間の値がシステムの jiffies の現在値よりも小さい場合)、
そのタイマールーチンが呼び出され、アクティブビットはクリアされる。新しい
システムタイマーの場合、timer_list 構造体の連結リストのエントリが
チェックされる。すべての終了時間タイマーがリストから削除され、そのルーチンが
呼び出される。新しいタイマーのメカニズムには、タイマールーチンに引数を渡せる
という利点がある。
プロセスは、何らかのシステムリソースを待たなければならない状態になること
がよくある。たとえば、あるプロセスがファイルシステム上のあるディレクトリを記述
する VFS inode を必要としていのだが、その inode がバッファキャッシュにない時
などである。
その場合、そのプロセスは、そのフィアルシステムを保持する物理メディアから
当該 inode が持ってこられるまで待ってから、処理を継続しなければならない。
[see:
include/linux/wait.h]
wait_queue
*task
*next
図表(11.4) 待ち行列
Linux カーネルはシンプルなデータ構造体である
wait_queue (図表(11.4)を参照)(訳注: この図表は原文においても GIF
ファイルではありません。)を使用しているが、これは、
task_struct のプロセスへのポインタと、待ち行列内の次の要素への
ポインタから構成されている。
プロセスが待ち行列の終端に付け加えられるとき、そのプロセスは、割り込み可能 か割り込み不可能かのいずれの場合もあり得る。割り込み可能なプロセスは、たとえば タイマー の終了といったイベントや、待ち行列上で待っている間に受信したシグナルによって 割り込まれるかもしれない。待ち行列上のプロセスの状態(state)はそれを反映して いて、その状態は INTERRUPTIBLE(割り込み可能) か UNINTERRUPTIBLE(割り込み不可) のいずれかである。待ち行列上に置かれたプロセスは 現時点では動作させつづけられ ず、スケジューラが次ぎのプロセスを選んだときに、その待ちプロセスはサスペンド状 態となる。( 脚注 1)
待ち行列が処理されるとき、待ち行列上のすべてのプロセスの状態(state)は、 RUNNING(実行中)にセットされる。 プロセスが実行キューから削除されていた場合は、再度実行キュー上に置かれる。 スケジューラが次に実行されるとき、待ち行列上にあるプロセスは、もう今は待ち 状態ではないので、実行されるべき候補者となっている。 待ち行列上のプロセスがスケジューラによって実行されるとき、それが最初に行う ことは、自分を待ち行列上から削除することである。待ち行列はシステムリソースへの アクセスを同期させるためにも使用できるので、Linux はそれらを使って、セマフォ を実装している。
これは、スピンロック(spin locks)と呼ばれることのほうが多い仕組みであり、 データ構造やコードを保護するプリミティブな方法である。これは、一度にひとつの プロセスしか重要なコード領域に入れないようにするものである。 Linux においては、データ構造体のフィールドへのアクセスを制限するために利用され るのだが、その際、一つの単精度整数フィールドを使用したロックの仕組みを提供して いる。 その領域に入ろうとする個々のプロセスは、ロックの初期値を 0 から 1 へと変更しよ うとする。現在値が 1 の場合、タイトループ(tight loop)のコード内でスピニング (spining)しながら、再度それを試みる。 そのロック機構を保持するメモリ領域へのアクセスは排他的(atomic)なものでなけれ ばならず、その値の読み出し、それが 0 であることの検証、そしてその値の 1 への 変更といった処理は、他のプロセスから割り込まれることがない。大部分の CPU アーキテクチャでは、特別な命令によってこの仕組みをサポートしているが、 キャッシュされていないメインメモリを利用してバズロック(buzz lock)を実現する こともできる。
占有中のプロセスがコードの重要領域から離れるとき、バズロックの値をデクリメン トして、その値を 0 に戻す。ロック上でスピニングしているプロセスは、この時に 読み出しを行うと、0 を読み出す。それを最初に読み出したプロセスが、その値をイン クリメントして 1 にし、重要領域へと入る。
セマフォは、コードやデータ構造の重要な領域を保護するために利用される。 たとえば、ディレクトリを記述する VFS inode のような重要なデータへの個々のアクセ スは、そのプロセスに代わってカーネルコードによって実行される。あるプロセスが 使用している重要なデータ構造体に対する、他のプロセスによる変更を許すことは 非常に危険である。これを実現するひとつの方法は、アクセスされる重要なデータの 周囲でバズロックを使用することだが、これは単純なアプローチなので、良好な システムパフォーマンスは期待できない。それに替えて、Linux はセマフォを使用 して、コードやデータの重要領域へのアクセスを一度にひとつのプロセスにしか 許さないようにしている。リソースへアクセスしようとするそれ以外のプロセス は、領域がフリーになるまで待たされる。待ちプロセスはサスペンドされ、 システム上の他のプロセスは通常通り実行を続けることが可能である。
Linux の
semaphore データ構造体には、
次のような情報が含まれている。
[see: include/asm/semaphore.h]
(
i386,
alpha)
このフィールドは、そのリソースを利用しようとするプロセスの数を監視するもので ある。正の値は、リソースが利用可能であることを意味する。負または 0 の値は、 待ち状態のプロセスがあることを意味する。初期値 1 は、そのリソースを利用できる のは一度にたったひとつのプロセスだけであることを意味する。プロセスがその リソースを利用したいとき、プロセスはその値(count)をデクリメントし、このリソース の利用を終了したとき、プロセスはその値をインクリメントする。
このフィールドは、そのリソースを待っているプロセス数のうち、そのリソースが 解放されたときに起こされることになっているプロセスの数を示すものである。
プロセスがそのリソースを待っているとき、それらのプロセスはこの待ち行列上に 置かれる。
waking フィールドにアクセスしているときは、バズロックが利用される。
セマフォの初期値が 1 であるとすると、最初にやって来たプロセスは、そのカウ ントが正であることを確認し、そこから 1 を引いて 0 にする。これでプロセスは、 コードかリソースの重要部分を「占有」したことになり、それがセマフォによって 保護される。プロセスがその重要な領域を離れるとき、セマフォのカウントをインクリ メントする。最善のケースは、その重要領域を所持しようとする他のプロセスが存在し ない場合である。Linux は、この最も一般的なケースで効率よく動くようにセマフォを 実装している。
あるプロセスの占有中に他のプロセスが重要領域に入ろうとする場合、そのプロセス
も count をデクリメントする。その count は現在 負(-1)となるので、その
プロセスは重要領域に入れず、そのかわり占有中のプロセスが退出するまで待たなけれ
ばならない。Linux は待ちプロセスをスリープさせ、占有プロセスがその重要領域から
退出する際にそのプロセスを目覚めさせる。待ちプロセスは自分自身をセマフォの
待ち行列に登録して、waking フィールドの値をチェックしながらループ状態に
入り、waking が 0 でなくなった時にスケジューラを呼び出す。
重要領域の占有者がセマフォの count をインクリメントして、もしその値が 0 以下 ならば、そのリソースを待ちながらスリープしているプロセスが存在する。最良のケー スでは、セマフォの count は初期値である 1 に戻されているので、それ以上の仕事は 必要がない。 占有プロセスは waking フィールドの値をインクリメントして、セマフォの待ち行列で スリープ状態にあるプロセスを目覚めさせる。待ちプロセスが起きると、waking フィールドの値は 1 なので、重要領域に入ってもよいことがわかる。プロセスは waking フィールドの値をデクリメントし、その値を 0 に戻し、実行を続ける。セマフ ォの waking フィールドへのアクセスはすべて、セマフォのロックを使用したバズロッ クにより保護されている。
(脚注 1)REVIEW NOTE: タスクを割り込み可能な状態で停止させて、次にスケジューラ が実行される際に、そのタスクが実行されるとはどういうことか？ 待ち行列上でスリー プ状態にあるプロセスは、目覚めさせられるまで、実行されないはずである。