Operating System I #2

Chapter 6 - プロセス間同期

Chapter 4まででマルチタスクの実現のための仕組みを説明しましたが、マルチタスクであるが故に起きる問題があります。

クリティカルセクション(Critical Section Problem)

ある計算機上で複数のプロセスが動いているとき、競合が発生することがあります。具体的には:

• 共有している変数の変更


• DBにおけるテーブルの更新（Operating System Conceptには挙げられていますが、実際にはDBの場合はこんなにシンプルじゃない気がする）


• ファイルの更新

というようなものが挙げられます。あるプロセスとあるプロセスが同時にこういった処理を行うと、最終的な結果に不整合が発生することが考えられます（2009年8月9日時点のWikipediaの解説がわかりやすいです）。

こういった処理をクリティカル・セクション（Critical Section:以下"CS")と呼びます。

クリティカルセクションを処理する

CSを処理するプログラムは次のようなセクションにわかれます。

• entry section: CS処理の前処理（資源のロックなど）


• critical section


• exit section: CS処理の後処理（資源のロックの解放など）


• remainder section: 残りの処理（要するにクリティカルセクションとは関係ない処理

それと同時に、CSを処理するプログラムには次の3つの性質が求められます:

1. 相互排他: あるプロセスがCSを処理している間は、別のプロセスはCSを処理できない
   
   
   
   • 原文ではMutal Exclusionで、これは割と有名なMutexの語源らしい
   
   
   
   


2. 連続性: CSの入り口（entry sectionね、たぶん）で待っているプロセスのみ、次にCSを処理するプロセスとして選ばれうる
   
   
   
   • でも、Progressの意味合いからすると「Critical sectionを処理せずにremainder sectionを処理することはない」または「Critical sectionに入れないからといって、critical sectionを飛ばしてremainder sectionに入っちゃうようなプロセスは選んであげない」のようにも読めるのだよなあ
   
   
   
   


3. 有限の待ち時間: プロセスがentry sectionで待たされる時間は有限か、制限がある（原文では"There exists a bound, or limit on the number of times..."となっており、boundはcritical sectionが有限時間で終わる（ことが推奨される）こと、limitは有限時間でcritical sectionを負えないプロセスは強制終了するべきであることを意味している、と思う）

ピーターソンの方法

上記の性質を満たすCS問題の解法として、2つのフラグ変数と1つの状態変数を用いる"ピーターソンの方法"があります。2つのフラグ変数というわけで、この方法はプロセスがふたつの場合にしか利用できません。

PiとPjの場合を見てみます。

int turn;

boolean flag[2];

do{

  // entry section

  flag[i] = TRUE;

  turn = j;

  while( flag[j] && turn == j);


  // Here is cretical section

  // exit section

  flag[i] = FALSE;

  // remainder section

}while(1);

// ※C言語でシンタックスハイライトしていますが、C言語ではありません

// entry sectionでturn = jする理由がいまいちわからないなー

同期ハードウェア

ピーターソンの方法はソフトウェア的な実現でしたが、ハードウェア的な実現もできます。

セマフォ

ピーターソンの方法や、ハードウェアを利用した方法を抽象化したのがセマフォです。

セマフォは整数値を持つオブジェクトで、WaitとSignalという2つの操作だけが提供されています。

Waitは次のように表現されます:

wait(s){

  while( s <= 0)

    ;

  s--;

}

Signalはこうです:

signal(s){

  s++;

}

例によってC言語ではありませんので念のため...

waitがentry sectionのための関数で、signalがexit sectionのための関数です。間違えると混乱する点が、セマフォの初期値は0ではないということです。

要するに:

• 初期値nのセマフォ


• CSを処理する前（entry section, セマフォではwaitですね）にデクリメントする


• CSが終わったら（exit sectionなのでセマフォではsignal）インクリメントする


• waitしたとき、セマフォが0になっていたら待ち続ける

ということなので、結果的に:

• n個のプロセスがcritical sectionに入っていたらセマフォは0


• n+1個めのプロセスはwait内で待ち続ける


• いずれかのプロセスがsignalすればセマフォは1なので、n+1個めのプロセスがCSに入る


• →CSに入るプロセスの数をn個に制限できる！

ということになります。

バイナリセマフォ（Mutex）

で、初期値が1のセマフォなら同時にCSに入れるプロセスの数は1個なので、相互排他が実現できていることになります。n>1の場合と異なり特殊なので、特別にバイナリセマフォとも呼ばれますし、Mutex（ミューテックス）とも呼ばれます。

セマフォの場合、ピーターソンの方法と違ってCSを処理したいプロセスがn個あっても大丈夫なので、非常に実用的です。実用的なのでいろんな本に載っていて、学術的なテキスト（Operating System Concepts）に載っていてちょっとびっくりしました...

参考文献

1. ”Operating System Concepts” 2004/12 (Abraham Silberschatz他)


2. Wikipedia - セマフォ


3. Wikipedia - ミューテックス


4. ファイヤープロジェクト - セマフォ