オペレーティングシステム 其の九 20170621
相互排除についてもう少し詳しく
ロックの見直し
ロックは①ロックされているかの確認、②ロックをかけるための値を書く．この二つをアトミックに処理する必要がある．
ビジーループをかけるスピンロックについてもやったが、これだと長い処理の時CPUの無駄遣いになってしまう．
そこで出てくるのが次のアイデア．
ブロッキングロック
システムコールによってブロック、起床をOSに依頼する方法
→ブロックするのでその分CPUが節約できる．ただ、コンテキストスイッチが必要になってくる．
sys_wait：signalが呼ばれるまでブロック
sys_signal：ブロックしているスレッドを起床させる
この命令をtest_and_set命令と組み合わせてロックを実現することができる．
void Lock(int *lock){ while(1){ if(test_and_set(*lock)==0){ //0が返ってくるのはロックが取得できた時 return; } sys_wait(lock); //ロックが取得できなかったらブロック } } void Unlock(int *lock){ *lock=0; sys_signal(lock); //待っているスレッドを起床させる }
セマフォア
別の同期プリミティブ．一度にNスレッド入れるようにしたいと考えられたもの．
→カウントアップ、カウントダウン（0の時はブロック）で制御する．
→基本は排他的なカウンタ
最大でNスレッドまでクリティカルセクションに入れるようにする命令で、N=1の時はロックと同じでバイナリセマフォと呼ぶ．N>1の時、カウンティングセマフォと呼ぶ．
なぜカウンティングセマフォを使うのか？
複数スレッドがクリティカルセクションに入るということはその分競合を起こしてしまう可能性があるということ．
→この場合、バイナリセマフォ（ロック）で相互排除してやる必要がある．
それ以上に、N個だけ入れるという交通制御をわかりやすくするために導入している．
Producer-Consumer問題
課題は「有限のバッファを安全に共有したい」ということ．
パイプラインにおいてバッファは共有資源になっている．
→相互排除しなければ、競合してしまう可能性がある．
バッファの状態に応じて挙動を変える必要がある．
リングバッファ
環状にバッファを定義．これにより、空き数とデータ個数を把握する．
空き数が0だった場合はproducerを待たせ、データ数が0だった場合はconsumerを待たせる．
カウンティングセマフォ、ロックと組み合わせることによってこの問題を解決できる．
条件変数
クリティカルセクション内で条件成立を待ちたい．
→ロックをかけたままビジーループを回すという方法がある．
・ビジーループ
・クリティカルセクションに長時間滞在してしまうし、デッドロックする可能性も出てくる
条件付きクリティカルセクション
cond_wait(cond,lock)
・lockを解除し、ブロックする
・起床時にlockを取得
cond_signal(cond)
・ブロックしているスレッドを起床させる
一回lockから抜け出すことで、クリティカルセクションに長期滞在することを防いでいる．
これを用いることでProducer-Consumer問題が解決する．
Lock(lock); while(condition==false){ cond_wait(cond,lock); //condが達成されていなかったらlock外に出る /*critical section*/ } Unlock(lock); cond_signal(cond); //条件を満たしたらlockの中に戻る
これが基本形．
Dining Philosopher問題
これについては資料参照．
解決法の一つは、一人は逆側の端からとるようにすること．しかし、これでも、じきにデッドロックが起こってしまう．
