オペレーティングシステム　其の八　20170614

並行プログラミング

並行でないプログラミングのことを逐次プログラミングという．
　→処理の流れが一つしかない．通常のプログラミング言語はこっちのほうを想定している．

並行にして何がいいのか

　・ブロック状態にあるプロセスを別の処理の流れで出来たらうれしい．
　・I/O-boundプロセスの待ち時間を有効に使いたい．
　・マルチコアの性能を活かしたい．

並行にすることにより

　・プロセスは自分勝手に動く．
　　→競合してしまうことがある．
　　　→相互排除により、プロセス、スレッドの足並みをそろえる機能を付与したい．
　・実行順序が無数にある．
　　→ここで別のスレッドが来たらバグになるかななんてことを考えながら描く必要がある．
　・スレッド間で資源を共有している．
　　→別スレッドが共有資源の内容を書き換えてしまうことがある．

共有ファイルによって生じるバグ

　スレッドの買いで出てきたhello****の問題がその例．出力結果が毎回違うなんてことがある．これを直すのは大変．

共有メモリによって生じるバグ

　スレッド１のインクリメント関数をスレッド２から呼ぶことを考える．
　
　スレッド１と２でインクリメント関数を１回ずつ呼ぶ場合
写真を挿入

　ちょっと順番が変わるだけで実行結果が変わってきてしまう．

　→各スレッドが非同期に（勝手に）共有資源にアクセスしてしまったがために生じた問題．データを壊してしまった．
　　→処理のタイミングをそろえる（同期する）必要がある．

　共有資源にアクセスできるスレッドを一度に一つにする．
　　→このタイミング、場所のことをクリティカルセクションという．

　一度に一つのスレッドしかアクセスできないようにすること
　　→相互排除（mutual exclusion / mutex）

相互排除

　必要なこと
　　・１クリティカルセクションに１スレッド
　　・アクセスしていないならば直ちに入れる
　　・少なくとも１つはクリティカルセクションに入れる
　　・必ずいつかはクリティカルセクションに入れる

　アイデアはいろいろあるが、スレッドが交互にしか入れなかったり、同時に入れてしまったり、デッドロックが起こってしまったりして完全に実現するのはなかなかに難しい．

デッドロック

　お互いがお互いを待っている状態．詰んでる．
　実行するための要素がお互いの中にある．
　　例）家を借りるのに銀行口座が必要だが、口座を開くためには住所が必要

ぬけのない相互排除は難しい

　ふつうは同期に必要なソフトウェア（同期プリミティブ）が用意されている．

同期プリミティブの例（ロック）

　Look(lock)：変数lockに鍵をかける
　Unlock(lock)：lockの鍵を解除する

　どうやって実現するのか？？
　　これまでの失敗例はロックの確認とロックのための値を書く部分が分離されていた．
　　　→この２ステップを分離不可能（アトミック）な状態にすればいい．
　　　　→二つのことを同時に実行する専用命令を用いる．

Test and set 命令

int test_and_set(int *mem){
　int old =*mem;
　if(0==*mem){
　　*mem=1;
　}
　return old;
}

Exchange命令

int exchange(int *mem, int val){
　int old=*mem;
　*mem=val;
　return old;
}

これはval=1にすると、test and set命令と同じことをしていることになる．

これらの命令を用いると、ロックしたかどうかの確認とロックのどちらも同時にできる．

Test and setを利用してロックを実現してみる

void Lock(*lock){
　while(test_and_set(*lock)==1); //ロック成功になるまでビジーループ
}

void Unlock(*lock){
　*lock=0;
}

このようなロックの実現方法はスピンロックと呼ばれる．

今度はexchange命令を使って実現してみる

void Lock(*lock){
　while(exchange(*lock,1)==1); //ロック成功になるまでビジーループ
}

void Unlock(*lock){
　*lock=0;
}

これでOK．

pthreadでのロック

　pthreadではロック変数とLockとUnlockがあらかじめ入っている．

pthread_mutex_t lock; //lock変数の宣言

pthread_mutex_lock(&lock);

//この間がクリティカルセクション

pthread_mutex_unlock(&lock);

これで実現できている．これを使うことで、スレッドの共有資源へのアクセス競合が起きなくなる．

マエカワの備忘録的な何か

思い立ったが吉日