スポンサーリンク
OS

【OS】同期

同期が必要な理由

プロセス間の連携を必要とする同時実行には、プロセスが相互に通信し、アクションを同期することが必要です。共有データの不整合を引き起こす可能性がある。

クリティカルセクション

クリティカルセクションとは、単一のリソースに対して、複数の処理が同時に実行されると問題が生じてしまう。

n個のプロセスを考えるP={p_0, p_1, ... p_{n-1}}

各プロセスにはクリティカルセクションセグメントがある

クリティカルセクションの例

P0(プロセス) P1(プロセス) x;(変数)
x=0; 0
x++; 1
x=0; 0
printf x; 0 (output)
x++; 1
printf x; 1 (output)

プロセスのクリティカルセクション

クリティカルセクションの問題の解決法

クリティカルセクションの問題の解決策は次の要件を満たす必要があります。

Mutual Exclusion

p_iがクリティカルセクションで実行されている場合、他のプロセスはクリティカルセクションで実行できない

Progress

プロセスがクリティカルセクションにない場合、クリティカルセクションに入ることを希望するプロセスの1つが選択されて、クリティカルセクションに入ることができます。

Bounded Waiting

プロセスがクリティカルセクションに入るようにリクエストを行った後、そのリクエストが許可される前に他のプロセスがクリティカルセクションに入ることができる回数に制限をつける

ピータソンの解決策

最新のアーキテクチャでの動作が保証されてない。

int型変数 turnはどのセクションがクリティカルセクションに入るかを示している。bool型変数 flag[]はプロセスがクリティカルセクションに入る準備ができているかどうかを示す。例えばflag[i] = trueはプロセスp_iの準備ができていることを示している。

クリティカルセクションに入るための条件(①〜③を満たす)

① flag[j] = false か turn = i
② Progressが満たされている
③ Bounded-waitingが満たされている

p_iアルゴリズム

同期のハードウェアサポート

memory barriers

メモリモデルは、コンピュータアーキテクチャがアプリケーションプログラムに対して行うメモリ保証。他のすべてのプロセッサに伝播するメモリの任意の 変化(可視化)を強制的命令です。

強い順序付け

1つのプロセッサのメモリ変更が他のプロセッサにすぐ見えるようにする

弱い順序付け

1つのプロセッサのメモリの変更が他のプロセッサにすぐ見れない場合がある。

 

Hardware instructions

Test_and_Set()

解決策

falseに初期化されたbool型変数lock

compare_and_swap()

解決策

0に初期化されたbool型変数lock

Atomic variables(原子変数)

comare-and-swapなどの命令は、他の同期ルールの一部として使用される

int や boolなどの基本的なデータ型の変数で、割り込み不可の更新を提供するものです。

ミューテックスロック

以前の解決策は複雑で、一般にアプリケーションプログラマはアクセスできない。

acquire()とrelease()

これら2つの関数はアトミックに実装する必要になる。最初にロックを取得し、次にロックを解除することによりクリティカルセクションを保護する。

アトミック:
トランザクションに含まれるタスクが全て実行されるか、あるいは全く実行されないことを保証する性質をいう。 口座Aから口座Bに対し1万円送金する場合を考えたとき、送金操作は次の2操作によって行われる。

①口座Aの残高から1万円を引く
②口座Bの残高に1万円を加える

原子性が保証されるとは、上の操作1、2が全て行われるか、あるいは全く行われないことを指す。どちらか片方だけが実行された場合、銀行全体の預金残高に矛盾が発生してしまう。

acquire()

release()

解決策

Busy waiting:プロセスが条件が成り立つかどうかを定期的にチェックする手法の一種。空ループを回すことによってロックした
*空ループを回すことからスピンロックという

セマフォ

プロセスが高度な方法でアクティビィティを同期するためにツール。プロセスがクリティカルセクションにある間、クリティカルセクションに入ろうとする他のプロセスはwait()で継続的にループする必要があり、これはCPUのリソースを浪費する。(これはスピンロックと呼ばれる、)

int型変数Sとwait()とsignal()を使用する(元々はP()とV()と呼ばれていた)

セマフォの使用

int型変数S

Counting semaphore

0\leq S \leq \infty

Binary semaphore

S01
これは、mutex lock と一緒

セマフォの実装

2つのプロセスが同じセマフォで同時にwait()とsignal()を実行できないことを保証する必要がある。

wait()

signal()

busy waiting無しのセマフォの実装

ビジー待機無しで実装する方法は、各セマフォを待機キューに関連付けることです。プロセスがクリティカルセクションにある場合、クリティカルセクションに入ろうとする他のプロセスは、ブロック操作で待機キューに入れる。

変数とblock()とwakeup()

変数

block()

操作を呼び出すプロセスを適切な待機キューに配置する

wakeup()

待ち行列内のプロセスを1つ削除し、ready行列に配置する

wait()

signal()

モニター

プロセス同期のための便利で効果的なメカニズムを提供する高レベルの抽象化する。モニター内で一度にアクティブにできるプロセスは1つ

モニターの疑似コード

モニターの概略図

liveness

livenessは、プロセスが確実に進行するためにシステムが満たす必要がある一連のプロパティをさす。

プロセスは、mutex lockやセマフォなどの同期ツールを取得しようとする間、無期限に待機する場合がある。その待機はProgressとbounded-waitingの基準に違反する。

Deadlock

2つ以上のプロセスが、1つの待機中のプロセスによってのみ発生する可能性のあるイベントを無制限に待機する

 Deadlockの他の形式

Starvation

プロセスは、一時停止されているセマフォキューから削除される

Priority Inversion

優先順位の低いプロセスが優先順位の高いプロセスに必要なロックを保持しているスケジューリングの問題

スポンサーリンク