クリティカルセクション

ウェブページの来訪者数を表すカウンタのプログラムを例にとって説明する。カウンタのプログラムはおおまかに次の処理からなる。

1. ディスク等の記憶装置上のファイルから現在のカウンタの値をメモリに読み出す
2. メモリ上でカウンタの値を1増やす
3. カウンタの値をメモリから記憶装置に書き戻す

実際はこれらの処理それぞれが複数の細かい命令群からなるのが普通である。

プログラムのプロセスは常に1つだけ実行されるが、個々のアクセスはタスク化され、それを処理する複数のスレッドに分配されるものとする。

ここで、現在ディスクに書き込まれているカウンタの値が100だったとする。

ユーザーAがこのウェブページを訪れ、カウンタプログラムのスレッドAが実行され始めたとしよう。スレッドAは処理1でカウンタの値を読み出し（値は100）、処理2で値を増やす（値は101）。次に処理3で値を書き戻すのだが、ここでユーザーBがウェブページを訪れたことにより別のスレッドBが実行され、すぐさまコンテキストスイッチが起きて処理がスレッドBに移されたとする。スレッドBがカウンタの値を読み出すと値は100になる。なぜならば、スレッドAがまだ処理3を完了していないため、ディスク上の値は変化していないからである。そして、スレッドBは値を増やし、その結果の101という値をディスクに書き込み、スレッドを終了する。次に再びスレッドAに処理が移り、スレッドAは処理3を行ない、ディスクには101という値が書き込まれて、スレッドAも処理を終える。

結果として、ユーザーAとユーザーBの2人がページを訪れたので、本来カウンタの値は2増えて102にならなければならないのに、最終的にディスクに書き込まれた値は101となり、破綻をきたす。

以上の処理を時間に沿ってまとめたものが以下の表である。

ディスク上の値	スレッドA（値）	スレッドB（値）
100	スレッド発生
100	処理1(100)
100	処理2(101)
100	待機	スレッド発生
100		処理1(100)
100		処理2(101)
101		処理3(101)
101		スレッド終了
101	処理3(101)
101	スレッド終了

排他制御をしたクリティカルセクションとは、1つのスレッドのみが使用権を得ることができるプログラム上の処理領域である。この使用権はロック (lock) と呼ばれることもある。

あるスレッドが排他制御をしたクリティカルセクションに入っている間は、別のスレッドはクリティカルセクションに入ることができない。普通はそのスレッドは待機状態になる。

このカウンタプログラムの場合、プログラムの最初、つまり上の場合でいうと処理1の前に排他制御のロックを獲得してクリティカルセクションに入るという処理を付け加える必要がある。そして、スレッドが終了する前に排他制御のロックを解放してクリティカルセクションから出るという処理を付け加えれば完了である。

ここで、先ほどと同様にスレッドAが処理1、処理2を終わらせて処理3を実行する前に、スレッドBが発生したとする。しかし、ここで既にスレッドAがロックを獲得してクリティカルセクションに入っていることから、スレッドBはロックを獲得できず処理を開始できないため待機状態となる。そしてスレッドAが処理を終え、クリティカルセクションから出ると他のスレッドがロックを獲得できるようになり、スレッドBが待機を解除して処理を再開する。結果として、意図したとおりの正しい動作になる。

以上の処理を時間に沿ってまとめたものが以下の表である。なおクリティカルセクションはCSと略している。

ディスク上の値	スレッドA（値）	スレッドB（値）	CSの所有者
100	スレッド発生
100	CSに入る		スレッドA
100	処理1(100)
100	処理2(101)
100	待機	スレッド発生
100		CSに入ることに失敗
101	処理3(101)	待機
101	CSから出て、スレッド終了
101		CSに入る	スレッドB
101		処理1(101)
101		処理2(102)
102		処理3(102)
102		CSから出て、スレッド終了