ファイヤープロジェクト
セマフォ
2003-07-20T15:13+09:00   matsu
共有メモリの話題に入る前の準備としてセマフォについて記述する.
二つのプロセス(もしくはスレッド)A,Bが共有する変数xがあったとする.そしてA,B両者がxに1を足すとする.xが0なら処理後のxの状態が2になっていることを期待してみる.
  1. Aがx(=0)の値を読み込む.
  2. Aがx(=0)に1を足してそれをxに書き込む.
  3. Bがx(=1)の値を読み込む.
  4. Bがx(=1)に1を足してそれをxに書き込む.
  5. この時x=2.
上は「たまたま」正常なタイミングで動作した場合である.もしかしたら以下の状況なるかもしれない.
  1. Aがx(=0)の値を読み込む.
  2. Bがx(=0)の値を読み込む.
  3. Aがx(=0)に1を足してそれをxに書き込む.
  4. Bがx(=0)に1を足してそれをxに書き込む.
  5. この時x=1.
期待に反してx=1となってしまった.これは「たまたま」プロセスの切替えタイミングが悪く,同期をとって処理すべき変数xに対してA,Bが非同期で処理してしまったから起こった現象である.このような処理をクリティカルセクションという.誰かがxをクリティカルセクションを処理しているときに,別の誰かはxを処理できない様にする必要がある.
上の問題を解決するために,ロック変数yを考えてみる.変数yが0の時は別のプロセスはxに対して処理をせず,1なら処理をする.したがってA,Bはxに対して処理する前にyをチェック,変更する.先のタイミングが悪かったパターンは以下のようになる.
  1. Aはy(=1)を読み込む.
  2. Aはyが1なのでこれを0にする.
  3. Aがx(=0)の値を読み込む.
  4. Bはy(=0)を読み込む.
  5. Bはyが0なので待つ.
  6. Aがx(=0)に1を足してそれをxに書き込む.
  7. Aはyを1に戻す.
  8. Bはy(=1)を読み込む.
  9. Bはyが1なのでこれを0にする.
  10. Bがx(=1)の値を読み込む.
  11. Bがx(=1)に1を足してそれをxに書き込む.
  12. Bはyを1に戻す.
  13. この時x=2.
これでうまくいった.が,よく考えるとyに対してもまた最初のxと同じ状況が発生し得る.これではきりがないので,それを処理する間プロセスの切替えがおこらない何かが必要になる.これがセマフォ(semaphore)である.セマフォはDijkstraが発表したらしい.先のyがセマフォだったとすると,あるプロセスがyを読み込んで値を変更するまでの間,他のプロセスはyに対して処理しないことが保証されている.すなわちセマフォに対する処理はアトミックであることが保証されている.セマフォについてまとめてみた.
  • 0か正の整数をとる.
  • waitとsignalという二つの操作だけが可能.
  • waitをしたとき,値が1より大きければ値をデクリメントする.0ならば待つ.
  • signalをしたとき,値が0より大きくなるのを待っているプロセスがあれば,そのプロセスを再開する.なければ値をインクリメントする.
  • バイナリセマフォは0と1の二値をとる.
  • 汎用セマフォは0と複数の正の値をとる(例えば0,1,2).
こうすると,クリティカルセクションの処理は以下のようになる.
  1. セマフォにwait操作をする.
  2. クリティカルセクションの実行.
  3. セマフォにsignal操作をする.
これで問題は解決する.
セマフォを使用するための関数には以下の3つがある.
int semget(key_t key, int nsems, int semflg)
keyで指定したnsems個からなるセマフォ集合の識別子を取得する.semflgはオプションでパーミッションなどもここで設定する.semflgでIPC_EXCLを指定するとセマフォが一意となることが保証される(keyがセマフォのために既に使用されていればsemgetは失敗する).
int semop(int semid, struct sembuf *sops, unsigned nsops);
semidで指定したセマフォ集合の操作のメンバを操作する.sopsはセマフォに設定したい値を持つsembuf構造体のnsops個の配列である.
int semctl(int semid, int semnum, int cmd, ...)
semidで指定したセマフォ集合またはそれのsemnum番目のメンバの制御操作を行なう.操作はcmdで指定する.
多くの場合,関数を使用して以下のパターンでセマフォを処理する(と思う).
  1. semgetでセマフォを取得する.
  2. semopでロック.
  3. semopでアンロック.
  4. semctlでセマフォを削除.
以上を踏まえた上でサンプルを以下に示す.
これは親プロセスと子プロセスがそれぞれpまたはcと表示して1秒寝てまたpまたはcと表示するものである.そして親子で同期をとることによって,"pp "と"cc "がそれぞれ一まとまりとして表示されることを期待している.
gcc semaphore.c
とするとセマフォではなくただの変数をロックに使用している(ソース中「セマフォ気分」と書いてあるところ).以下実行結果.
pcc p cpc cp pc p cpc p cpc p cpc p cpc p cpc cp pc p cpp c 
と同期が取れていない.
gcc -DSYNC semaphore.c
とするとセマフォを使用して同期を取る.以下実行結果.
pp pp cc cc pp cc pp pp pp cc cc cc pp pp cc cc pp cc pp cc 
セマフォの効果がはっきりと分かって満足.
で,共有メモリの話でまずセマフォを出したのは,冒頭の話でいうところのxが,共有メモリ上のデータだからである(セマフォのサンプルでは簡単に標準出力への同期だった).そして複数のプロセスで共有するのだから,冒頭の話は当然問題として上がる.そしてその問題を解消する一つの方法がセマフォなのだ.
matsu(C)
Since 2002
Mail to matsu