5章 カーネルの同期処理
最終更新：ID:z8LCWIsc4Q 2011年06月08日(水) 18:31:49履歴
5.1 カーネルは要求をどのように処理するか 
- 競合状態を避けるために様々な同期プリミティブを実装している。
5.1.1 カーネル内プリエンプション
- プリエンプト可能なカーネルはカーネルモードで実行中でも強制的なプロセス切り替えが可能。
- 計画的なプロセス切り替え:自発的にCPUを開放する。
- 強制的なプロセス切り替え:非同期のプロセス切り替え事象に反応する。
- プロセス切り替えはswitch_toマクロで実行される。
- プリエンプト可能なカーネルの動作例
- プリエンプト可能なカーネルの場合は、例外ハンドラ処理中に高い優先度のプロセスが実行可能となった場合に強制的なプロセス切り替えが発生する。
- 例外ハンドラ処理中ににクオンタムが満了した場合、プロセス切り替えが発生する。
- カーネルプリエンプト可能にすることでユーザプロセスの応答性がよくなるが、オーバーヘッドもある。
- カーネル内プリエンプションが明示的に禁止されておらず、ローカル割り込みが許可されている場合にカーネルプリエンプションが発生する。
5.1.2 同期の必要がある場合
- クリティカル区間とは、カーネル実行パスによって一度実行が開始されると、ほかのカーネル実行パスがコードの同じ箇所を実行する前に、最初のカーネル実行パスが終了している必要がある区間。
- シングルプロセッサシステムであれば、単純にカーネル内プリエンプションを禁止すればクリティカル区間が実現できる。
5.1.3 同期の必要がない場合
(4章で解説されている制約)
- 割り込みハンドラとタスクレットはリエントラントに実装する必要がない。
- ソフト割り込みとタスクレットからアクセスされるCPUごとの変数は同期処理が不要。
- 単一のタスクレットからだけアクセスされるデータは同期処理が不要。
5.2 同期プリミティブ
| 同期技法 | 説明 | 同期範囲 |
| CPUごとの変数 | CPUごとに持つデータ | すべてのCPU |
| アトミック操作 | カウンタに対するアトミックな「読み込み、更新、書き出し」命令 | すべてのCPU |
| メモリバリア | 命令実行順序の変更を回避 | ローカルCPUまたはすべてのCPU |
| スピンロック | ビジーウェイトによるロック | すべてのCPU |
| セマフォ | プロセスの実行中断(休止)によるロック | すべてのCPU |
| 順次ロック | アクセスカウンタに基づいたロック | すべてのCPU |
| ローカル割り込み禁止 | ローカルCPUで割り込みの禁止 | ローカルCPU |
| ローカルソフト割り込み | ローカルCPUで遅延処理の禁止 | ローカルCPU |
| RCU(Read-Copy-Update) | ポインタを利用した共有データへのロック不要アクセス | すべてのCPU |
5.2.1 CPUごとの変数
- CPUごとに配列を用意して、カーネル内プリエンプションを禁止すればCPU間の同期処理は必要なくなる。
- 非同期処理(割り込みハンドラや遅延処理)との間には同期処理が必要。
5.2.2 アトミック操作（不可分操作）
- 80x86のアトミックな命令
- アラインメント境界をまたがない1回のメモリアクセス。メモリアクセスを行わない命令。
- inc/decがメモリバススチールされない場合。単一プロセッサシステムではメモリバススチールは発生しない。
- オペコードがlockバイト(0xf0)でプレフィックスされている命令。メモリバスをロックする。
- オペコードがrepバイト(0xf2,0xf3)でプレフィックスされている命令はアトミックではない。
- LinuxではCPUのアトミックな命令を利用して、atomic_t型に対してアトミックな処理を行うための関数・マクロを用意している。
5.2.3 最適化処理とメモリバリア
- コンパイラの最適化による命令の並び替えからクリティカル区間を守る必要がある。
- 最適化処理バリアは、volatileキーワードでコンパイラの命令の並び替えを抑制する。
- メモリバリアは、前後の命令をシリアル化して実行することを強制する。最適化バリアの役割も果たす。
- メモリバリアの実装はシステムアーキテクチャに依存する。
- 80x86でメモリバリアとして機能する命令
- I/Oポートを操作するすべての命令。
- オペコードがlockバイトでプレフィクスされているすべての命令。
- 制御レジスタ、システムレジスタ、デバッグレジスタを変更するすべての命令。
- lfence/sfence/mfence
- iretなどのいくつかの特殊な命令。
5.2.4 スピンロック
- スピンロックはマルチプロセッサ環境に特化して設計されたロック機構。
- ビジーウェイトとして実装されているが、多くのカーネル資源はコンマ数ミリ秒程度の開放待ちなのでCPUを開放するよりも効率的。
- スピンロックによるクリティカル区間ではカーネル内プリエンプションは禁止だが、ビジーウェイトの間は許可されている。
- スピンロックの操作を行うマクロはアトミック操作で実装され、別のCPUからの更新の影響を受けないようになっている。
5.2.4.1 カーネル内プリエンプションを伴うspin_lockマクロ
(マクロの詳細)
- xchgb命令がアトミックな命令。
5.2.4.2 カーネル内プリエンプションを伴わないspin_lockマクロ
- lockバイトでプレフィックスされたdecb命令がアトミックな命令。
5.2.4.3 spin_unlockマクロ
- movb命令で取得済みのスピンロックを開放する。
5.2.5 読み書き用スピンロック
- データを変更するカーネル実行パスがないときに限って、複数のカーネル実行パスから同じデータを同時にアクセスできる。
5.2.5.1 読み込み用ロックの取得と解除
- read_lock()マクロで読み込みロックを行う。
- 書き込みロックが行われている場合、ロックが解除されるまでビジーウェイトする。
5.2.5.2 書き出し用ロックの取得と解除
- write_lock()マクロで書き出しロックを行う。
- lockバイトでプレフィックスされたaddl命令がアトミックな命令。
5.2.6 順次ロック
- 書き手に高い優先度を与える以外は読み書きスピンロックに似ている。
- 書き手は読み手が動いていても操作できる一方、読み手は有効な値を得られるまで何度も同じデータの読み込みを繰り返す必要がある。
- 読み手がクリティカル区間に入るときにカーネル内プリエンプションを禁止する必要はない。書き手はスピンロックを取得するため自動的にカーネル内プリエンプションが禁止される。
- 典型的な使用例はシステム時間を操作するデータの保護。
- 順次ロックの条件
- 書き手が変更し、読み手が参照するポインタは、保護したいデータに含めることはできない。(書き手は読み手がいても操作可能)
- 読み手のクリティカル区間の処理に、副作用があってはならない。
5.2.7 Read-Copy Update（RCU）
- RCUの利点
- 複数の読み手と複数の書き手が同時に実行することができる。
- ロックフリーのため、オーバーヘッドが小さい。
- RCUの利用制限
- 動的に確保され、ポインタ経由で参照されるデータだけをRCUの保護対象にする。
- RCUが保護するクリティカル区間では、カーネル実行パスの休止を許さない。
- 書き手がデータの更新を行うとき、ポインタを参照してそのデータまるごとの複製を作成する。
- 更新が終了するとポインタが更新済みの複製を指すように変更する。ポインタ更新時にはメモリバリアを使用する。
- 書き手がポインタを更新しても、、古いデータの複製をすぐに開放できないことがRCUの問題点。すべてのrcu_read_lock()がrcu_read_unlock()される必要がある。
- rcu_read_unlock()を実行するタイミング(静穏状態quiescent statusを通過)
- CPUがプロセス切り替えを実行
- CPUがユーザモードの実行を開始
- CPUがアイドルループを実行
5.2.8 セマフォ
- Linuxの提供するセマフォ
- カーネル実行パスが使用するカーネルセマフォ
- ユーザモードプロセスが使用するSystem V IPCセマフォ(19.3.3)
- スピンロックと同様に資源が開放されるまでカーネル実行パスは実行をやめるが、ビジーウェイトはせず休止する。
- 休止しても問題がない機能でのみ使用可能。
- semaphore型
- count:資源の利用可能数を表すatomic_t型。
- wait:待ちキューリストのアドレス。
- sleepers:セマフォ上にプロセスが待機しているかを示すフラグ。
5.2.8.1 セマフォの取得と開放
- 開放:up()関数
- countメンバをインクリメントする。待ちキューリストにプロセスがいたら起床する。
- 取得:down()関数
- countメンバをデクリメントする。countが負になったら、TASK_UNINTERRUPTIBLEに移行する。スピンロックを取得して、待ちキューリスト追加する。
- セマフォが取得できなかった場合、プロセスは休止状態になるため、割り込みハンドラや遅延処理からはdown()関数が使用できない。代わりにdown_trylock()関数を利用する。
- セマフォは取得可能な場合がほとんどのため、その場合に合わせて実装している。そのため複雑な処理となっている。
5.2.9 読み書き用セマフォ
- 読み書き用スピンロックに似ている。
- 書き出し用セマフォ取得には読み書き用セマフォが取得されていない必要がある。
- FIFO順に読み込みはすべて起床され、書き出しは排他的に起床される。
- rw_semaphore型
- count:書き出し中のプロセス数とセマフォロック取得待ちのカーネル実行パスの和、読み込み中と書き出し中のプロセスの合計数を保持。
- wait_list:待ちプロセスのリストのアドレスを保持。
- wait_lock:待ちキューリストとrw_semaphore自身を保護するスピンロック。
5.2.10 完了通知
- マルチプロセッサシステムでセマフォを操作するときに発生する競合状態を解決するために導入された。
- complet()関数やwait_for_completion()関数が同時に実行されないことを保証するためにスピンロックを利用している。
5.2.11 ローカル割り込み禁止
- ハードウェア機器がIRQシグナルを発生してもカーネル実行パスの処理を継続できるようにする。
- クリティカル区間から出る際の割り込みの許可は、処理が入れ子になっている可能性があるので前の状態を戻すようにする。
- local_irq_enable()マクロ：sti命令でeflagsレジスタのIFフラグを1に変更。
- local_irq_disabled()マクロ：cli命令でeflagsレジスタのIFフラグを0に変更。
5.2.12 遅延処理の禁止と許可
- 遅延処理の禁止と許可はカレントプロセスのthread_infoディスクリプタのpreempt_countメンバのsoftirqカウンタによって行う。(ソフト割り込みを禁止)
- local_bh_disable()マクロ:ローカルCPUのsoftirqカウンタをインクリメント。
- local_bh_enable()マクロ:ローカルCPUのsoftirqカウンタをデクリメント。
- 遅延処理が許可されたら、保留されているソフト割り込みを確認して実行する。プロセス切り替え要求の保留を確認してpreempt_schedule()関数を呼び出す。
5.3 カーネルデータアクセスの同期
- システム並列度は以下の2つの要素に依存する。
- 同時に動作可能なI/Oデバイスの数
- CPUの数
- I/Oスループットを最大化するためには、割り込み禁止の時間はできるだけ短くするべき。
- CPUを効率よく利用するためには、スピンロックを利用する同期プリミティブの利用を可能なかぎり避けるべき。
- 同期の使用例
- 共有データをatomic_t型で宣言しアトミックな命令を使用して、スピンロックや割り込み禁止を行わない。
- 共有する連結リストの追加は割り込みが行われたとしても破壊されない順番で行う。更に、メモリバリアプリミティブで順番の変更を抑制する。
5.3.1 スピンロック、セマフォおよび割り込み禁止の選択
5.3.1.1 例外がアクセスするデータの保護
- セマフォを使用する。単一プロセッサでもマルチプロセッサシステムでも利用可能。
5.3.1.2 割り込みがアクセスするデータの保護
- 同じ種類の割り込みハンドラは複数実行することができないので割り込みハンドラで共有されていないデータには同期プリミティブは必要ない。
- 共有されているデータの場合
- 単一プロセッサシステムではクリティカル区間で割り込みを禁止する。
- マルチプロセッサシステムではローカル割り込みを禁止し、スピンロックか読み書き用スピンロックを取得する。
5.3.1.3 遅延処理がアクセスするデータ保護
- 単一プロセッサシステムでは競合状態にはならない。
| データにアクセスする遅延処理の種類 | 保護方法 | |
| ソフト割り込み | スピンロック | |
| 単一のタスクレット | 必要なし | 同じ種類のタスクレットは同時に実行できない |
| 複数のタスクレット | スピンロック |
5.3.1.4 例外と割り込みがアクセスするデータの保護
- 割り込みハンドラは再入可能ではなく、例外に割り込まれない。
- 単一プロセッサシステムでは、問題ない。
- マルチプロセッサシステムでは、スピンロックを利用する。セマフォがいい場合もあるが、ビジーウェイトしながらセマフォを取得をする。
5.3.1.5 例外と遅延処理がアクセスするデータの保護
- 5.3.1.4 例外と割り込みがアクセスするデータの保護と同様。
5.3.1.6 割り込みと遅延処理がアクセスするデータの保護
- 遅延処理を実行中は、ローカル割り込みを禁止する。
- マルチプロセッサシステムではスピンロックを使用する。
5.3.1.7 例外処理、割り込み処理、遅延処理がアクセスするデータの保護
- ローカル割り込み禁止とスピンロックを利用する。
5.4 競合状態回避の例
5.4.1 参照カウンタ
- atomic_t型のカウンタを利用して、メモリページ・モジュール・ファイルのような資源の保護を行う。
- 参照カウントが0になったら資源を開放可能。
5.4.2 ビッグカーネルロック
- 2.0では、1度に1つのプロセッサだけがカーネルモードで動作することを保証するスピンロックとして実装されていた。
- 2.6では、古いコードを保護するために使われている。
- 応答性向上のために、2.6.10以降ではスピンロックからセマフォに実装が変更されている。
5.4.3 メモリディスクリプタの読み書き用セマフォ
- 複数の軽量プロセスで共有されるメモリディスクリプタを保護する。
5.4.4 スラブキャッシュリストのセマフォ
- スラブキャッシュデスクリプタのリストを保護する。
- マルチプロセッサシステムとカーネル内プリエンプト可能な単一プロセッサシステムで必要とされる。
5.4.5 iノードのセマフォ
- ファイルシステムはあらゆるプロセスが参照・更新するので競合が発生しやすい。
- 複数のセマフォを取得する必要がある場合は、デッドロックを避けるためアドレス順に取得する。
最新コメント