xv6はマルチプロセッサ、複数のCPUが独立してコードを実行する環境下で動作している。これらのマルチプロセッサの環境では、CPUは同一の物理アドレスを利用し、データ構造を共有する; xv6はそれぞれが干渉しないようにするためのメカニズムを導入する必要がある。単一プロセッサでも、xv6はいくつかのメカニズムを利用して、割り込みハンドラが非割り込みハンドラから干渉されることを防ぐために同様のメカニズムを利用する必要がある。xv6は、どちらにも低レベルの同一の考え方を利用している: ロックである。ロックは相互実行、つまり複数のCPUのうち、ある時間においてたった一つのCPUがロックを保持するということを保証する機構を提供する。もしxv6は特定のロックを保持している間しかデータ構造にアクセスしないならば、xv6はそのデータ構造に対してたった一つのCPUのみがアクセスしていることを保証することができる。このような状況下のことを、データ構造をロックしている、と呼ぶ。
本章では、xv6では何故ロックが必要なのか、どのようにしてロックを実装しているのかについて見ていき、これをどのようにして利用するかについて見る。注目すべきなのは、xv6のコード上でロックを確保するときは、あなたはあなた自身に、他のプロセッサがそのコードの所望の行動を変えられていないかチェックしなければならない、ということである(例えば、他のプロセッサが同一のコード行を実行しているか、他のコード行で変数を変更している可能性がある、ということである)。また、もし割り込みハンドラが実行されると何が起きるか、ということについても考えなければならない。どちらのケースでも、単一のCの文は複数のマシン命令に変換され、他のプロセッサや割り込みによって、そのCの文を実行している途中で分断される可能性があるということである。また、本ページのコード列はシーケンシャルに実行されるとは考えてはいけない、もしくは、単一のCの文がアトミックに実行されるとは考えてはいけない。並列に動作することによって、プログラムの正確性を推測することはより難しくなるのである。
ロックが必要な例として、いくつかのプロセッサが、IDEディスクなどの単一のディスクをxv6上で共有していることを考える。ディスクドライバのメカニズムは、まだ未実行なディスクリクエストのリンクリストを管理しており(4121行目)、プロセッサは新しいリクエストを、並列にそのリストに追加していく(4254行目)。もしここで並列なリクエストが発生しなければ、リンクリストを以下のように実装することができる:
1 struct list {
2 int data;
3 struct list *next;
4 };
5
6 struct list *list = 0;
7
8 void
9 insert(int data)
10 {
11 struct list *l;
12
13 l = malloc(sizeof *l);
14 l->data = data;
15 l->next = list;
16 list = l;
17 }この実装が正しいことを証明するのは、データ構造とアルゴリズムの授業において、典型的な練習問題である。
この実装が正しいと証明されたとしても、少なくともマルチプロセッサ上では正しくない。もし2つの異なるCPUがinsertを同時に実行開始すると、どちらのコードも16行目を実行する前に15行目を実行する(図4-1を参照のこと)。もしこのようなこととが発生すると、listは2つのノードのnext値として設定される。16行目でlistへの代入の文が同時に実行されると、2番目の文は最初の文を上書きする; 最初に代入を実行した分のノードは消失してしまう。この類の問題は「レースコンディション」と呼ばれる。このレースの問題は、2つのCPUの厳密なタイミングに依存し、メモリ操作がどのような順番で実行されるかに依存するため、再現することが難しい。例えば、insertをデバッグ中にprint文を追加すると、タイミングが変わるためこのレース状態が消失してしまう可能性がある。
レースコンディションを回避するための典型的な方法はロックを使うことである。ロックにより排他実行を保証し、たった1つのCPUが同時にinsertを実行することを保証する; これにより、上記のシナリオが発生することは不可能となる。以下のコードは、上記のコードにいくつかプログラムを追加した、正しくロック機構を導入したバージョンである(ナンバリングされていない部分が、新たに追加したプログラムである)。
6 struct list *list = 0;
struct lock listlock;
7
8 void
9 insert(int data)
10 {
11 struct list *l;
12 `acquire`(&listlock);
13 l = malloc(sizeof *l);
14 l->data = data;
15 l->next = list;
16 list = l;
release(&listlock);
17 }私達は、データをロックすると言うが、正確にはロックによりデータに適用されるいくつかの不変条件が保護されたというのが正しい。不変条件は、データ操作の間に保持されているべきデータの特性である。典型的には、処理の正しい動作はその不変式がその処理が開始されたときに真であるかに依存する。処理は一時的にその不変条件を侵害するときがあるが、処理が完了する迄には修復できていなければならない。例えば、リンクリストのケースは、不変条件は変数listがリストの最初のノードを指しており、各ノードのnextフィールドが次のノードを指しているといものである。insertの実装は、lがリストの最初のノードであるが、lの次のポインタがリストの次のノードを指していない(これにより不変条件が崩れるが、15行目で復元される)。そして、listはlを指してはいない(16行目で修復される)。私達がチェックしたレースコンディションは上記の部分で発生する。それは、2番目のCPUがリストの不変条件が一時的に崩されたときに発生するからである。ロックの正しい使い方は、ある時間にたった一つのCPUがあるデータ構造を操作し、そのデータ構造の不変条件が崩れている最中に他のCPUがそのデータ構造を触らないようにすることである。
xv6はロックをstruct spinlockとして表現する(1501行目)。データにおいてそれが「ロックされている」というのは、そのワードがゼロであればロックが入手可能であるということで、非ゼロであればロックされているということである。論理的には、xv6は次のようなコードを実行してxv6はロックを獲得する。
21 void
22 `acquire`(`struct spinlock` *lk)
23 {
24 for(;;) {
25 if(!lk->locked) {
26 lk->locked = 1;
27 break;
28 }
29 }
30 }残念ながら、上記のコードではマルチプロセッサで正しく排他制御を実現できる保証はない。2つ以上のマルチプロセッサが同時に25行目を実行し、lk->lockedがゼロであることを確認すると、同時に26行目を実行し、27行目に移る。これにより、2つ以上の異なるCPUがロックを獲得し、排他実行の特性が破られることになってしまう。レースコンディションを避ける支援を行うどころか、上位のacquire関数の実装自体がレースコンディションを持っている。この問題は、25行目と26行目が別々に実行されることである。上記のルーチンを正しく実行するためには、25行えと26行目が「アトミック(atomic)」(つまり、分割されることなく)実行されなければならない。
上記の2つの文をアトミックに実行するためには、xv6は386の特別なハードウェア命令,、xchg(0569行目)に頼らなければならない。1つのアトミックな操作によってxchgはメモリの内容とレジスタの内容をスワップする。関数acquire(1574行目)はこのxchg命令をループで繰替えして実行している;各繰り返しでは、lk->lockedを読み込み、アトミックに1を設定する(1583行目)。もしロックが保持されていれば、lk->lockedは既に1であるため、xchgは1を返してループを継続する。もしxchgが0を返したならば、acquireはロックを正しく獲得に成功したということであるーlockedは0から1に変化するーそうして、ループは終了する。
ロックが一度獲得されるとacquireはデバッグのためにそれを記録し、CPUとスタックトレースはロックを獲得したことを記録する。プロセスがロックを獲得しリリースを忘れると、その情報によりロックの解除を忘れた犯人を特定することが出来る。このようなデバッグフィールドは、ロックによって保護されており、ロックが確保されているときにしか編集することができない。release関数(1602行目)はacquireの逆である: デバッグフィールドをクリアし、ロックを解放する。
システムデザインでは、クリーンな、モジュールを用いた抽象化を行わなければならない:つまり特定の機能について、呼び出し元が呼び出し先の実装がどのような実装になっているのかについて知る必要が無いのがベストである。しかしロックはこのモジュール性を邪魔するものである。例えば、CPUが特定のロックを保持していたとすると、そのロックを獲得しようとする任意の関数fは呼び出すことができない: 何故ならば、fがあるロックを獲得しようとすると、呼び出し元はfが戻るまで同一のロックを解放することができず、これは永遠にスピンし続けるか、デッドロックを引き起す。
呼び出し元と呼び出し先でロックの情報を隠すという方法は透明性の無い解決法である。ある共通の、透明性のあるが、不完全な回答は「再帰ロック(recursive lock)」を用い、呼び出し元により確保されたロックをさらに獲得することができるようにする方法である。この方法の問題は、不変条件の保護には利用できないということである。insertがacquire(&listlock)を呼び出した後は、このロックを他の関数が確保することはないと仮定しており、他のどのような関数も上記のリスト操作を行っている最中ではないという仮定を行っている。さらに重要なことに、全てのリストが不変条件を保持しているということである。再帰ロックを持ったシステムでは、insertはacquireを実行した後にどのような仮定を置く必要も無い:おそらく、insertの呼び出し元が既にロックを保持しておりリストデータ構造を編集中であるため、acquireは成功するしかないのである。不変条件は、保持しているか、そうでないかのどちらかである。リストは、もはやそれらを保護しない。ロックは呼び出し元と呼び出し先が互いに異なるCPUを互いに保護するときに重要である; 再帰ロックはこの特徴を諦める。
明快な解決法は存在しないため、ロックは関数の仕様の一部として考えるべきである。プログラマは関数はfが必要なロックを保持している関数fを起動しないように調整する必要がある。ロックは、これらを強制的に私達の抽象化の世界へ引きずり込むものなのである。
xv6はレースコンディションを避けるためにロックを利用して注意深くプログラムされている。シンプルな例としてIDEドライバがある(4100行目)。本章の最初に述べたように、iderw(4254行目)はディスクリクエストを扱うためのキューを持っており、プロセッサは新しいリクエストを並列にリストに挿入していく(4269行目)。
このリストと他の不変条件をドライバ内で保護するためには、iderwはidelock(4265行目)を獲得し、関数の最後で解放する。練習問題1では、本章の最初で紹介したレースコンディションにおいて、キュー操作の後にacquireを移動することによってどのようにレースコンディションが発生するのかについて見る。レースコンディションを発生させることは簡単なことではなく、だからこそレースコンディションのバグを見つけることは難しく、この練習問題は挑戦する価値のあるものである。xv6にはレース状態は無いと思われる。
ロックの利用における難しい部分は、いくつのロックを使い、どのデータと不変条件について、ロックで保護するかを決定することである。これにはいくつかの基本的な法則が存在する。まず、他のCPUからいつでも同時に読み書きをすることのできる変数については、ロックを導入して2つの操作がオーバラップすることを防ぐべきである。2番目に、ロックは不変条件を保護するということを思い出して欲しい: もし不変条件が複数のデータ構造について発生するならば、典型的に全てのデータを単一のロックで保護し、不変条件が維持されることを保証しなければならない。
上記のルールは、ロックが必要な場合については述べているが、ロックが必要でない場合については説明してない。また、ロックは並列性を減少させるため、ロックをし過ぎるのも効率が良くない。もし効率性が重要ではないのなら、単一のプロセッサだけを利用してロックについて考慮しないようにすれば良い。カーネルのデータ構造を保護するためには、カーネルに入るためのロックを取得して、カーネルから出るときにロックを解放する。大くの単一プロセッサのオペレーティングシステムは、マルチプロセッサに移植するためにこのアプローチが取られ、これは「ジャイアントカーネルロック(giant kernel lock)」と呼ばれる。しかしこのアプローチは真の並列性を犠牲にしている: 一度に、たった一つのプロセッサしかカーネルを実行することができないらである。もしカーネルが重たい計算をしないならば、より細粒度な複数のロックを利用して、複数のCPUが同時にカーネルを実行できるようにすべきである。
究極的には、ロックの粒度の選択は並列プログラミングの練習問題になる。xv6は複数の粗粒度のロックデータ構造を持っている; 例えば、xv6はプロセステーブルとその不変条件を保護するために1つのロックを利用しており、これは第5章で説明する。より細粒度のアプローチとしては、プロセステーブルのエントリ毎にロックを持つことによって、別々のエントリで動作するスレッドが並列に動作するようにできる。しかし、これは複数のロックを持つ必要があるためプロセステーブル全体で不変条件を保つために複雑な操作が必要なる。xv6のロックの例が、どのようにしてロックを利用するかについての理解に役に立つことを希望する。
カーネルを通過するコードは、いくつかのロックを獲得する必要があるが、全てのコードパスはロックを同じ順番に獲得していく必要がある。 もしそうでなければ、デッドロックする危険性が生じる。 ロックAとBを獲得する、2つのコードが存在するとするが、1つのパスはロックをA→Bの順番で獲得し、もう一つはロックをB→Aの順番で獲得するとする。 この状況では、コードパスが1ロックAを獲得しロックBを獲得する前に、コードパス2がロックBを獲得する可能性があるため、デッドロックが発生し得る。 これにより、コード1はロックBが必要で、これはコード2が保持しており、コードパス2はロックAが必要で、これはコードパス1が保持しているという状況が発生し、どちらのコードも先に進むことができなくなる。 このようなデッドロックを避けるためには、全てのコードパスはロックを同一の順番で獲得しなければならない。 デッドロックの回避は、何故ロックを関数の使用として含めなければならないかを説明する例となる: 呼び出し元は一貫した順番で関数を呼び出さなければ、関数内で獲得するロックを同じ順番で獲得できなくなるからである。
xv6は粗粒度のロックを利用し、またxv6がシンプルなため、xv6は短めのロックの順番チェーンしか持っていない。
最も長いロックでも、2つである。
例えば、ideintrはwakeupを呼び出しているときにideウロックを保持し、wakeupはptableのロックを獲得する。
sleepとwakeupを呼び出す例はいくつか存在する。
このオーダリングは、sleepとwakeupが複雑な不変条件を持っており、これについては第5章で議論する。
ファイルシステムでは、ディレクトリからファイルを正しくアンリンクするために、まずディレクトリのロックを獲得し、その後そのディレクトリのファイルのロックを獲得するため、2つのロックが必要になる。
xv6は、常に最初にディレクトリのロックを獲得し、次にファイルのロックを獲得する。
xv6はあるCPUで割り込みハンドラが動作している最中に、同じデータに対して他のCPUからアクセスが発生しないようにロックで保護をしている。例えば、タイマ割り込みハンドラ(3364行目)はticksをインクリメントするが、他のCPUが同時にsys_sleepに入ると、その変数を利用する(3723行目)。tickslockロック変数により、2つのCPUが単一の変数にアクセスすることを防ぐ。
単一のプロセッサでも、割り込みは同時に発生することがある: もし割り込みが許可されているならば、カーネルコードは動作を停止し、いつでも割り込みハンドラが呼び出される。iderwがidelockを保持している最中に、ideintrの割り込みが発生したとしよう。ideintrはidelockロック変数を獲得しようとするが、それは既に保持されており、それが解放されるまで待つ。この状況では、idelockは永遠に解放されない ー iderwのみがロックを解放できるが、iderwはideintrが終了しない限りは実行されないー従って、プロセッサおよびシステム全体がデッドロックとなる。
このような状況を避けるためには、もしロックが割り込みハンドラ中で利用されるならば、プロセッサはロックを保持しているときは決して割り込みを許可してはならない。xv6はより保守的である: xv6は割り込みが可能な状態でロックを保持することは無い。pushcli(1655行目)とpopcli(1666行目)を利用して、「割り込み不許可」の操作のスタックで管理している(cliはx86の命令で割り込みを不許可にする命令である。) acquireはロックを獲得する前にpushcliを呼び出し(1576行目)、ロックを解放した後にpopcliを呼び出す(1621行目)。
pushcli(1655行目)とpopcli(1666行目)はcliとstiのラッパーとしての役割だけではない: これらはカウントを行っており、pushcliを2回呼んだときに、popcliを2回呼び出すことによりその操作を取り消すことができる; この方法により、もしコードが2つの異なるロックを獲得すると、どちらのロックも解放されなければ割り込みが有効とはならない。
xchgによりロックを獲得する(1583行目)前に、acquireがpushcliを実行することが重要である。もしこれらが逆であれば、ロックを獲得してから割り込みが有効な数サイクルの間に、不幸にも割り込みが発生するとデッドロックが発生する。同様に、releaseがpopcliをする前に、xchgによりロックを解放することが重要である。
割り込みハンドラと非割り込みコードの相互作用により、再帰ロックが何故問題になるのかについての良い例が得られる。xv6が再帰ロックを利用すると(1番目のacquireが許可されてから、同じCPUで2番目のacquireが許可される)、割り込みハンドラは、非割り込みコードのクリティカルセクション上で動作する可能性がある。
割り込みハンドラが動作すると、依存している不変条件がハンドラによって一時的に破壊されるため、システムの破壊を起こす可能性がある。例えば、ideintr(4202行目)のリンクリストが正しく実装されているとする。
xv6が再帰ロックを利用すると、ideintrはiderwが動作している最中に動作することができるようになり、リンクリストを操作している最中に割り込みが入ることにより不定な状態となる可能性がある。
本章では、プロセッサはプログラムの命令を、そのプログラムの書いてある順番に実行するものとして説明してきた。しかし多くのプロセッサでは、命令をアウトオブオーダに実行して性能を向上させている。もしある命令の実行に長いサイクル数あ必要なのであれば、プロセッサはその命令を速く発行して、他の命令とオーバラップさせることでプロセッサのストールを避けたくなる。例えば、プロセッサが命令AとBを順番に実行し、これらの命令ん依存が無いとすると、まず命令Bを、命令Aを実行する前に発行して命令Aが完了したときに、命令Bも完了させる。しかし同時に、これはソフトウェアのリオーダリングが発生し、誤った動作が発生する可能性がある。
例えば、release内でlk->lockedの操作にxchgを利用するのではなく、単に0を代入するのではどうだろう。
この答えば不明瞭で、x86のプロセッサの世代によってメモリオーダリングの保証が異なるからである。もしlk->locked=0のリオーダが許可され、popcliの後に配置されると、ロックが解放される前に他のスレッドの割り込みが許可されるため、acquireにより破壊されるされる可能性がある。このメモリオーダリングのプロセッサ毎の不明瞭さを避けるためには、xv6はリスクを取らず常にxchgを利用し、プロセッサがリオーダリングしないことを保証している。
並列性のプリミティブと並列プログラミングはアクティブな研究領域であり、ロックを用いたプログラミングは未だに挑戦的なものである。同期キューなどの、高レベルの構造を元にしてロックを利用するのがベストではあるが、xv6はそれを利用していない。もしロックを利用して読者がプログラムを作るのなら、レースコンディションを認識できるツールを使うのが賢い選択だ。何故ならば、ロックが必要な不変条件のプログラムは簡単にミスを起こしやすいからだ。
プーザプログラムでも、ロックは必要ではあるが、xv6のアプリケーションは1つのスレッドしか存在せず、プロセスはメモリをシェアしないため、xv6のアプリケーションではロックは必要ない。
アトミック命令を利用してロックを実装することもできるが、それは高価である。しかし殆どのオペレーティングシステムはアトミック命令を利用している。
アトミック命令はロックがカウントされる場合は、自由に操作することが難しい。もし1つのプロセッサがローカルキャッシュ上に置かれているロックを持っている場合、他のプロセッサがロックを獲得するためには、ロックを保持しているラインをプロセッサのキャッシュから他のプロセッサのキャッシュに移動しなければならない。これにはキャッシュラインの無効化とキャッシュラインのコピーが必要になる。他のプロセッサのキャッシュへ、キャシュラインをフェッチすることは、ローカルキャシュからフェッチするのよりも高価の操作になる。
ロックによりこのような高価な操作が発生することを防ぐために、多くのオペレーティングシステムはロックフリーなデータ構造とアルゴリズムを利用しており、アトミックな命令とそのアルゴリズムを避けるようにしている。例えば、本章の最初に説明したリンクリストはリストの検索時にはロックは必要とせず、リストにアイテムを挿入する場合にのみ、アトミック命令を利用している。
acquireからxchgを除去せよ。xv6を動作させると、何が発生するか？iderwのacquireをsleepの前に移動させよ。レースコンディションははっせい するか？xv6をブートし、stressfsを実行してみると良い。ダミーループによりクリティカルセクションを増加させると、どのようになるか？説明せよ。- バッファ上のflagsをアトミック操作以外で設定せよ: プロセッサはflagsのコピーをレジスタにロードし、レジスタを操作し、ライトバックする。
従って2つのプロセスがflagsを同時に書き込まないことが重要である。
xv6は、
B_BUSYビットを処理するときのみbuflockを確保し、B_VALIDおよびB_WRITEフラグを操作するときはロックを保持しない。なぜこれでも安全なのか？