排他制御

恐竜本6章です。今回は排他制御に関してですが、最後はほぼデータベースの話になっており、OSとはやや離れています。まあデータベースの仕組みはあまり詳しくないのでありがたいんですがね。

有限サイズバッファの並列アクセス問題

　共有メモリ上に置かれたバッファに並列アクセスする2つのプロセスを考える。片方がバッファに対して書き込み、もう片方がバッファから値を読み込む。ただし、バッファのサイズは有限で、

• 読み込み済み、書き込み済みのそれぞれの先頭ポインタ
• 読み込み側がまだ読み終わっていないデータの数

の変数を別に用意している。読み込み側はまだ読み終わっていないデータが残っていればそのデータを読み込んでポインタ位置を動かす。同時に、読み終わっていないデータの数を0に戻す。書き込み側は読み込み済みの、いわば上書きしてしまって良い領域にデータを次々に書き込むが、まだ読み込み前のデータまでは上書きしないようにする。これは、読み込みが終わっていないデータ数とバッファサイズを比較することで行う。

　上記の有限サイズバッファ問題で、読み込み済みデータ数という変数は両方のプロセスが読み書きする値となっている。マシン語の実行順によって、片方のプロセスAがメモリに書き込む前にもう片方のプロセスBが読み込んで加減算→Aが書き込み→Bが上書きというように動き、状態不整合が生じることがある。このような状態を競合状態という。競合状態に入らないようにするため排他制御機構が必要となる。

用語

• クリティカルセクション　並列的に同時実行されてはならないコード
• エントリーセクション　排他制御に入るためのリクエストを行うコード
• イグジットセクション　排他制御を終えるための処理を行うコード
• リマインダーセクション　クリティカル・エントリー・イグジット以外のコード

また、「良い排他制御機構」は次の性質を持つと定義される。

• Mutual exclusion クリティカルセクションが同時に実行されない
• Progress クリティカルセクションを誰も実行していないとき、次にクリティカルセクションに入るプロセスはリマインダーセクション以外（エントリー・イグジットセクション）を実行しているプロセスたちが決定する。また、この決定が無期限に延期されることはない。
• Bounded waiting クリティカルセクションに入ろうとしているプロセスの前に、何度も他のプロセスがクリティカルセクションに入り、永久に後回しにされ続けることがない。

ピーターソンのアルゴリズム

　ソフトウェア的に排他制御を実現する方法としてピーターソンのアルゴリズムが知られている。プロセスが2つの場合(添字：i,j)を考える。2つの変数turnとflagを用いて排他制御を行う。turnは現在実行を許されているプロセスの添字、flagは現在クリティカルセクションに入ろうとしているかどうかのフラグである。実際のコードとしては、

while True:
    flag[i]=True
    turn=j
    while flag[j] and turn==j:
        pass
    #critical section
    ...
    flag[i]=False
    #ramainder section
    ...

のようになる。ほぼ同時にwhile flag[j] and turn==jに入ったとき、あとから入ったほうがwhileに入る直前でturnを相手のプロセスの添字に変更するので、先に入っていたほうがwhileを抜けてcritical sectionに入る。一方で、あとからエントリーセクションに入った方は、もう片方の実行が終わるまで待ち続ける。

　なお、現在のコンピュータアーキテクチャでは機械語の実行のされ方がピーターソンのアルゴリズム提唱当時とは異なり、この方法が必ずしもうまく動くとは限らない。

同期ハードウェア命令

　現在ではハードウェア的にクリティカルセクションに入るプロセスを1つにする方法が用意される事が一般的である。この仕組をlockという。lockのトリビアルな実現方法として、クリティカルセクションの直前で割り込みを無効化し、出るときに再度有効化するというものがある。これはシングルプロセッサならいいかもしれないが、マルチプロセッサではパフォーマンスの低下が大きい。代わりに現代のコンピュータシステムでは排他制御用の特殊な命令を用意している。これら命令の動作は2種類のモデル化の方法がある。一つがTestAndSet、もう一つがSwapである。これらの命令はアトミックであり、命令の実行の途中で邪魔されることはない。

　TestAndSetは、引数にブール変数のポインタをとり、ポインタの中身をコピーしたあとtrueに書き換える。返り値として、trueに書き換える前の値を返す。TestAndSetを使った排他制御は以下のようになる。

while TestAndSet(getpointer(lock)):
    pass
#critical section
...
lock=False
#remainder section
...

(Pythonはポインタを取れないのでgetpointerという関数でポインタ取得できることにしている）

　lockがFalseなら最初のwhileはすぐに抜けてクリティカルセクションに入る。また、TestAndSetによってlockにTrueが入るので他のプロセスはwhileで待たされる。クリティカルセクション後にlock=Falseになるので他のプロセスがクリティカルセクションに入ることができる。

　Swapは2つの引数を取り、値を入れ替える。Swapを使った排他制御は以下の通り。

key=True
while key:
    Swap(getpointer(lock),getpointer(key))
#critical section
...
lock=False

lockに最初trueがはいっていればswapを行ったあとkeyにはtrueが入るのでwhileを抜けられない。falseが入っていればkeyとlockの中身が交換され、lockにtrue、keyにfalseが入るのでwhileを抜けてクリティカルセクションに入れる。

　TestAndSetとSwapを用いた上記排他制御はbounded-waitingが実現されていない。これはlock=Falseをした直後にこれらの命令を実行するプロセスが、一番最初にwhileに入ったプロセスとは限らないからである。これは、lock変数の代わりにwaitingというブール変数配列を用意し、クリティカルセクションを抜けるとき必ず自分のプロセス番号より後ろのwaitingをfalseにすることで解決できる。

セマフォ

　TestAndSetやSwapを直接使うには上記のような比較的長いコードが必要なのでより使いやすい排他制御としてセマフォが存在する。セマフォは内部にカウンタを有し、排他制御命令としてカウンタをインクリメント/デクリメントする命令が用意されている。デクリメント命令ではセマフォのカウンタが0の場合、カウンタをデクリメントできず、プログラムはカウンタが1以上になるのを待つことになる。そのため、プログラムがクリティカルセクションに入る前にカウンタをデクリメントし、出るときカウンタをインクリメントするようにすることでクリティカルセクションに入るプロセス数を制限できる。カウンタをデクリメントする命令をwait、インクリメントする命令をsignalという。当然カウンタに同時にアクセスできてはならず、内部的にTestAndSet等ハードウェア排他制御を使っている。

　signalされるのを待つ方法として、スピンロック（ビジーウェイト）とシステムのキューに並ばせる方法がある。スピンロックではCPU時間を使い続けてカウンタを監視し、他のプロセスがsignalした瞬間にクリティカルセクションに入る。システムのキューに並ぶ場合、セマフォオブジェクトにPCBのリストへのポインタを保持させておく。ただし、キューの消費の仕方には方法がたくさんあるので先に待ちに入ったものから順にクリティカルセクションに入れるとは限らない。

　スピンロックはCPUを浪費する。しかし、プロセスが待ち状態になってキューに入る方法と比べ、signalされるまでの時間が短いことが期待できるなら、コンテキストスイッチのオーバーヘッドを受けずに済むのでクリティカルセクションに入るまでの待ち時間が短くて済む。どちらの方法が効率的かは、クリティカルセクションの実行時間が大きく影響する。

デッドロック・スタベーション

リソースに対するロックの獲得順が逆になっているプロセスがあると、お互いのリソース解放待ちでお互い永久に待ち続ける現象が起こる。これがデッドロックである。また、ロック解放待ちしているプロセスが、実行される前に他のプロセスがロックを再度獲得し、永久に実行されないスタベーションという現象もある。ロック後の実行順をLast in first outになるようにしているとこういう現象が起こる。

優先順位の逆転

　プロセススケジューリングにおいて、優先度がL<M<Hとなっている3つのプロセスがあるとする。Lが先にロックを獲得し、Hが同じリソースのロック解放を待っているとき、Mがreadyに入ると、優先度がLより高いのでLより先にMが実行され、副次的にHよりも実行が先となる。これを優先順位の逆転という。これが起きるとHがいつまでも実行完了しない。NASAの火星探査プロジェクトでPathfinderという探査機がこの問題を起こして再起動を繰り返したことで有名である。これを防ぐには、高優先度のプロセスが待っているロックオブジェクトを専有しているプロセスが、高い優先度を一時的に継承するようにする。

古典的な同期問題

　排他制御の仕組みを議論するとき毎回引き合いに出される問題がいくつか存在する。前述の有限サイズバッファ問題もその一つである。

　Readers-Writers問題は、複数のReaderとWriterがいる状況を考える。Readerだけが複数いるときは互いに実行を妨げないが、ReaderとWriterが混在するときは実行が混在しないように排他制御したい。第一種のReaders-Writers問題では、ReaderがいるときWriterがあとから来ても、Writerが待たされるようにしたい。第二種では、Writerがあとから来たら、Writerの実行が真っ先に行われるようにしたい。第一種はwriterの実行を制御するセマフォwrt(初期カウンタ1)、現在存在するReader数readcount、Reader間でreadcountを操作するためのセマフォmutex(初期カウント1)の3オブジェクトを使って解決できる。Readerプロセスでは、readcountが1→0となるとき、wrtをsignalし、Writerが動けるようにする。反対に、0→1となるときwrtをwaitし、Writerがブロックされる。Writerプロセスはクリティカルセクションに入る前にwrtをwaitし、出るときsignalする。

　食事する哲学者の問題では、円卓上に哲学者が座っており、各哲学者の間には箸が1本置いてある。勝手なタイミングで哲学者が食事をするため右手と左手で箸を2本とろうとする。このとき、別の哲学者がすでに箸を使っている場合は、その哲学者が食事を終えて箸を置くまで待っている。片手で箸を取得できた場合は置かずに待っている。単純にセマフォを箸の本数分用意した場合、例えば全員が同時に左手で箸を取ったら全員が2本目の箸を取れず、デッドロックに入る。この問題に対する解としては、両方の箸が揃ったときだけ箸を両方取る、全員が同じ手で最初の箸を取らないようにする、などがある。

モニタ

　セマフォはwaitとsignalを組み合わせて排他制御するが、コーディングミスでsignalを忘れたりするとデッドロックとなる。また、signalが多すぎると排他制御ができない。これを防ぐため、モニタという、プログラミング言語の言語仕様が考えられた¹。モニタはブロックを形成し、中で排他制御が必要な処理や、変数が宣言される。モニタは同時に実行できるプロセスが1個となることが保証される。実装としてはコンパイル時にセマフォなどを使うコードに翻訳される。また、上記制御だけだと機能として貧弱なので、条件変数というものが用意されている。条件変数にはセマフォのようにwaitとsignalの2操作ができるが、セマフォと違い、誰もwaitしていない条件変数をsignalしても何も起こらない。また、waitすると、モニタの実行がそこで止まり、別のプロセスもモニタ内に入ることができる。

　条件変数のsignal後に最初に実行されるプロセスを決める方法として、waitに優先度を引数として与えられるようにし、最も優先度が高いものを実行する方法が取られることがある。

アトミックなトランザクション

　金融機関の取引などデータの整合性を保証しなければならないタスクではデータベースのトランザクション機能を使ってアトミックに操作を行う。OSでもデータの整合性を保つ必要があることが多く、今までアドホックに採用されてきたアプローチをデータベースのトランザクションに倣った手法に置き換える試みもある。そこで、以下ではアトミックなトランザクションの仕組みを述べる。

　トランザクションはアトミック性を保証しなければならない操作の集まりである。コンピュータが途中でエラーを起こしたりして再起動したあと、データベースはトランザクションが起きる前の状態、もしくは完全に完了した状態のいずれかに復旧できなければならない。トランザクション前の状態に戻すことをロールバックという。

　データベース操作のアトミック性保証のためには、write-ahead-loggingという手法を使う。これは、データベースを更新する前に、要求された操作をログに書き出し、不揮発性ストレージに保存するという手法である。異常終了後の復旧では、コミットまで記録されたトランザクションのみを実行する。コミットまでたどり着かずにログが途切れているトランザクションは破棄する。なお、ログの先頭からすべてのトランザクションをやり直すのは、既にデータベースに書き込み済みのトランザクションもやり直すことになり非効率である。そのため、トランザクションのデータベース書き込み後、ログの先頭にチェックポイント作成完了という情報を書き込む。以後の復旧時は最後に作成されたチェックポイント以降のトランザクションを復旧する。

　複数のトランザクションを並行して実行することは不可能ではないが読み込みと書き出し順序には注意が必要である。あるトランザクションの実行後、次のトランザクションを実行するようなトランザクションのスケジューリングをシリアルスケジュールという。これは並行実行ではない。シリアルスケジュールをが並行的なスケジュールに変形するためには、あるデータに着目したときの書き込みと読み込み(conflict operation)の順序が保存されており、かつ同一トランザクション内の操作順序が保存されていれば良い。例えば、以下のシリアルスケジュールを考える。上の行から下の行へと実行されるとする。

上のスケジュールは以下のスケジュールに変更できる。

変形後のスケジュールをconflict serializableなスケジュールという。

　conflict serializableなスケジュールを自然に実現する方法として、データアイテムに対してsharedもしくはexclusiveなロックを2相ロッキングの手法で取得することが挙げられる。2相ロッキングでは、必要なロックを順番にすべて取得(growing phase)、全ロック後にデータ操作、終了後ロックを解放(shrinking phase)する。解放後に新規のロックを取得しないようにする。

　別の方法として、タイムスタンプベースの方法もある。トランザクションにタイムスタンプを与え、あるデータに関して最後に実行されたRead/Writeの時刻と、トランザクションの時刻を比較する。既に実行されたRead/Writeよりもトランザクション時刻が前で、しかもまだそのトランザクションが未完了の場合、不整合を起こすような操作をトランザクションがやろうとすると却下される。結果として、そのトランザクションはアボートされ、ロールバックが起こる。一方、不整合にならない操作は許可される。すべての操作が却下されなければ、そのトランザクションは完遂できる。

所感

　急にボリュームが増えてびっくりしました。CS系の学部生でも、深いプログラミング経験なしでこの辺の話を学ぶ人もいると思います。全く経験がない状態でこれを読んだらひたすら実感がわかなくて大変だろうなあと思いました。そういう方は仮想通貨botを作ると否が応でもこの辺の話を勉強することになるので、一攫千金がてらやっていみてはいかがでしょうか（唐突）

1. C#で昔使っていたことがあり久々に聞きました。なお、Monitorを使って排他制御するのはやめようみたいな記事も出てきますね。