|
次のページ
前のページ
目次へ
12. カーネルメカニズム
この章では、Linux カーネルが提供しなければならない汎用的なタスクとメカニズム のいくつかについて解説する。それらは、カーネルの他の部分(すなわちこの章で述べら れるいくつかのタスクやメカニズム以外の部分)が効率よく協調動作するために必要なも のである。
12.1 ボトムハーフハンドラ
図表(11.1) ボトムハーフハンドラのデータ構造
カーネルにタスク処理をさせる場合、この時点では処理をさせたくない、という時が
しばしばある。割り込みを処理させる場合は、特にそうである。割り込みが起こると、
プロセッサは実行中の処理を停止し、オペレーティングシステムがその割り込みを適切
なデバイスドライバに伝達する。しかし、デバイスドライバに割り込みを処理させる
場合、割り込み処理中には、システム上で他の処理を実行できない。したがって、デバ
イスドライバは、割り込みの処理にあまり時間を掛けてはいけない。他方、その場で直
ぐに処理せずとも、何の問題もないケースもしばしば存在する。Linux のボトムハーフ
ハンドラが発明されたのは、デバイスドライバやその他のカーネルルーチンがそうした
仕事を一旦キュー上に置いて、あとで処理できるようにするためである。図表(11.1)で
は、ボトムハーフハンドラに関するカーネルのデータ構造体が示されている。
32 個までの異なるボトムハーフハンドラが存在し得る。
カーネルのボトムハーフハンドラのいくつかは、デバイス固有のものであるが、 それ以外は汎用的である。
デバイスドライバやカーネルの他の部分が仕事を後回しにする必要があるときは
いつも、その仕事を、たとえばタイマーキューのような、適切なキューに置き、
カーネルにシグナルを送って、ボトムハーフ処理の実行が必要であることを伝える。
それをするには、
12.2 タスクキュー(task queue)
図表(11.2) タスクキュー
タスクキューは、カーネルが仕事を後回しにする方法である。
カーネル内の何らかのルーチン、たとえばデバイスドライバは、タスクキューを 作成し利用することができるが、次の 3 つのタスクキューは、カーネルによって 作成され管理されている。
タスクキューが処理されるとき、キューの最初の要素に対するポインタがキュー から削除されて、ヌルポインタ(null pointer)と置き換えられる。実際、この削除 処理は、排他的な操作(atomic operation)なので、割り込みできないように なっている。次に、キュー上の個々の要素が自分の処理ルーチンを順番に呼び出す。 キュー上の要素はしばしば静的に割り当てられたデータである。しかし、割り当て られたメモリを破棄する固有のメカニズムは存在しない。タスクキュー処理ルーチン は単にリスト上の次の要素の処理に移るだけである。割り当てられたカーネルメモリ を確実に適宜再利用可能にするためには、タスク自体がその処理をしなければならな い。
12.3 タイマー(timer)
図表(11.3) システムタイマー
オペレーティングシステムには、将来の特定の時間にタスクを処理できるような
スケジューリング機能が必要である。そして、スケジューリングにより、タスクを
比較的正確な時間に実行できるようなメカニズムが必要とされる。この点、オペレーテ
ィングシステムをサポートしようとするプロセッサには、必ずプログラム可能なイン
ターバルタイマーがあり、それが定期的にプロセッサに割り込みを掛けている。この
定期的な割り込みは、システムクロックティックと呼ばれる。それは、メトロノームに
似た働きをして、システムの活動を指揮している。
Linux は時刻管理に対して非常にシンプルな見方をしている。
Linux は、時間を起動時からのクロックティック(clock tick)によって計る。すべての
システムタイマーはその計測を基にしており、その計測方法は、広く利用されている
変数名にちなんで
Linux には二種類のシステムタイマーがある。どちらのキュールーチンも、ある
システム時間に呼び出されるのだが、それらは実装においてやや異なっている。
図表(11.3) では、両方のメカニズムが示されている。
どちらの方法の場合でも、タイマーの残り時間を計る際の指標として
12.4 待ち行列(wait queue)プロセスは、何らかのシステムリソースを待たなければならない状態になること
がよくある。たとえば、あるプロセスがファイルシステム上のあるディレクトリを記述
する VFS inode を必要としていのだが、その inode がバッファキャッシュにない時
などである。
その場合、そのプロセスは、そのフィアルシステムを保持する物理メディアから
当該 inode が持ってこられるまで待ってから、処理を継続しなければならない。
wait_queue *task *next 図表(11.4) 待ち行列
Linux カーネルはシンプルなデータ構造体である
プロセスが待ち行列の終端に付け加えられるとき、そのプロセスは、割り込み可能 か割り込み不可能かのいずれの場合もあり得る。割り込み可能なプロセスは、たとえば タイマー の終了といったイベントや、待ち行列上で待っている間に受信したシグナルによって 割り込まれるかもしれない。待ち行列上のプロセスの状態(state)はそれを反映して いて、その状態は INTERRUPTIBLE(割り込み可能) か UNINTERRUPTIBLE(割り込み不可) のいずれかである。待ち行列上に置かれたプロセスは 現時点では動作させつづけられ ず、スケジューラが次ぎのプロセスを選んだときに、その待ちプロセスはサスペンド状 態となる。( 脚注 1)
待ち行列が処理されるとき、待ち行列上のすべてのプロセスの状態(state)は、 RUNNING(実行中)にセットされる。 プロセスが実行キューから削除されていた場合は、再度実行キュー上に置かれる。 スケジューラが次に実行されるとき、待ち行列上にあるプロセスは、もう今は待ち 状態ではないので、実行されるべき候補者となっている。 待ち行列上のプロセスがスケジューラによって実行されるとき、それが最初に行う ことは、自分を待ち行列上から削除することである。待ち行列はシステムリソースへの アクセスを同期させるためにも使用できるので、Linux はそれらを使って、セマフォ を実装している。
12.5 バズロック (Buzz Locks)これは、スピンロック(spin locks)と呼ばれることのほうが多い仕組みであり、 データ構造やコードを保護するプリミティブな方法である。これは、一度にひとつの プロセスしか重要なコード領域に入れないようにするものである。 Linux においては、データ構造体のフィールドへのアクセスを制限するために利用され るのだが、その際、一つの単精度整数フィールドを使用したロックの仕組みを提供して いる。 その領域に入ろうとする個々のプロセスは、ロックの初期値を 0 から 1 へと変更しよ うとする。現在値が 1 の場合、タイトループ(tight loop)のコード内でスピニング (spining)しながら、再度それを試みる。 そのロック機構を保持するメモリ領域へのアクセスは排他的(atomic)なものでなけれ ばならず、その値の読み出し、それが 0 であることの検証、そしてその値の 1 への 変更といった処理は、他のプロセスから割り込まれることがない。大部分の CPU アーキテクチャでは、特別な命令によってこの仕組みをサポートしているが、 キャッシュされていないメインメモリを利用してバズロック(buzz lock)を実現する こともできる。
占有中のプロセスがコードの重要領域から離れるとき、バズロックの値をデクリメン トして、その値を 0 に戻す。ロック上でスピニングしているプロセスは、この時に 読み出しを行うと、0 を読み出す。それを最初に読み出したプロセスが、その値をイン クリメントして 1 にし、重要領域へと入る。
12.6 セマフォ(semaphore)セマフォは、コードやデータ構造の重要な領域を保護するために利用される。 たとえば、ディレクトリを記述する VFS inode のような重要なデータへの個々のアクセ スは、そのプロセスに代わってカーネルコードによって実行される。あるプロセスが 使用している重要なデータ構造体に対する、他のプロセスによる変更を許すことは 非常に危険である。これを実現するひとつの方法は、アクセスされる重要なデータの 周囲でバズロックを使用することだが、これは単純なアプローチなので、良好な システムパフォーマンスは期待できない。それに替えて、Linux はセマフォを使用 して、コードやデータの重要領域へのアクセスを一度にひとつのプロセスにしか 許さないようにしている。リソースへアクセスしようとするそれ以外のプロセス は、領域がフリーになるまで待たされる。待ちプロセスはサスペンドされ、 システム上の他のプロセスは通常通り実行を続けることが可能である。
Linux の
セマフォの初期値が 1 であるとすると、最初にやって来たプロセスは、そのカウ ントが正であることを確認し、そこから 1 を引いて 0 にする。これでプロセスは、 コードかリソースの重要部分を「占有」したことになり、それがセマフォによって 保護される。プロセスがその重要な領域を離れるとき、セマフォのカウントをインクリ メントする。最善のケースは、その重要領域を所持しようとする他のプロセスが存在し ない場合である。Linux は、この最も一般的なケースで効率よく動くようにセマフォを 実装している。
あるプロセスの占有中に他のプロセスが重要領域に入ろうとする場合、そのプロセス
も
重要領域の占有者がセマフォの count をインクリメントして、もしその値が 0 以下 ならば、そのリソースを待ちながらスリープしているプロセスが存在する。最良のケー スでは、セマフォの count は初期値である 1 に戻されているので、それ以上の仕事は 必要がない。 占有プロセスは waking フィールドの値をインクリメントして、セマフォの待ち行列で スリープ状態にあるプロセスを目覚めさせる。待ちプロセスが起きると、waking フィールドの値は 1 なので、重要領域に入ってもよいことがわかる。プロセスは waking フィールドの値をデクリメントし、その値を 0 に戻し、実行を続ける。セマフ ォの waking フィールドへのアクセスはすべて、セマフォのロックを使用したバズロッ クにより保護されている。 (脚注 1)REVIEW NOTE: タスクを割り込み可能な状態で停止させて、次にスケジューラ が実行される際に、そのタスクが実行されるとはどういうことか? 待ち行列上でスリー プ状態にあるプロセスは、目覚めさせられるまで、実行されないはずである。
次のページ 前のページ 目次へ |
[ |