Process Synchronization

同期が必要な理由
いつオペレーティングシステムでRace Conditionが発生しますか?

割り込みハンドラはKernelモードの実行中に割り込みが発生しました
→両方ともカーネルコードなのでkernel address spaceを共有
→ソリューション:disable/enable割り込み機能

プロセスはシステム呼び出しでkernelモードで実行されていますが、コンテキスト切替が発生します.
→解決策:カーネルモードでCPUを奪わない

マルチプロセッサ共有メモリ内のカーネルデータ
→ソリューション1:一度に1つのCPUしかカーネルに入れない方法
→ソリューション2:カーネル内の共有データにアクセスするたびにデータをロック/ロック解除する方法

プロセス同期の問題

共有データの同時アクセスは、データの不一致(不一致)を招きます.

の一貫性を維持するためには、コラボレーションプロセス間の実行順序を決定するメカニズムが必要である.

Race condition

複数のプロセスが共有データ

に同時にアクセスする.

データの最終計算結果は、最終処理データの流れ

に依存する.

の競合を阻止するために、同時プロセスは

を同期する必要があります.

クリティカルセキュリティ問題(臨界領域問題)

n共有データを同時に使用する場合、

.

各プロセスのコードセグメントには、共有データにアクセスするコードセグメント

という重要なコードセグメントがある.

Problem

プロセスが臨界領域にある場合、他のすべてのプロセスは臨界領域に入ることができません.

Initial Attempts to Solve Problem

2つのプロセスがあると仮定する:P 0,P 1
プロセスの一般的な構造

do{
	entry section - 이용해서 critical section을 락 걸어줌
	critical section
	exit section - 다쓰면 락 풀어줌
	remainder section
} while (1);

プロセスは、同期→同期変数を実行するためにいくつかの変数を共有できます.

計画ソリューションの条件を満たす

Mutual Exclusion(反発)

プロセスPiがキーセクションを実行している場合、他のすべてのプロセスはキーセクション

にアクセスできません.

Progress(進捗)

重要な部分に誰もいない場合、重要な部分に入りたいプロセスがある場合は、重要な部分に入るようにしなければなりません.

Bounded Waiting(有限キュー)

プロセス要求が臨界領域に入ることから、その要求が許可されるまで、他のプロセスが臨界領域に入る回数は限られなければならない→

を起動できない.

家庭

すべてのプロセスの実行速度は0

より大きい.

プロセス間の相対的な実行速度を仮定しない.

解決アルゴリズム

回転の使用

上記のアルゴリズムは,P 0が臨界セグメントを用いた後,P 1が臨界セグメントを聞くだけで再び反転する.

タグを使用したチェック

回転とマークを同時に使用

ピーターソンアルゴリズム
→3つの条件はすべて満たすが、CPUとメモリ待ちを継続する.(Busy Waiting = spin lock)

Synchronization Hardware

がハードウェア上での原子化テストと修正をサポートする場合、前の問題は解決されます:

.

Semaphores

抽象の前の方法-抽象型

共有リソースの取得および返却のための抽象信号

Semaphore S

integer variable

は、次の2つの原子演算のみで

にアクセスできます.
P(S)→データ共有のプロセス
V(S)→返却プロセス

Critical Section of n Processes

Synchronization variable
semaphore mutex; // mutual exclusion / initially 1: 1개가 CS에 들어갈 수 있다

Process Pi
do {
		P(mutex);        // if positive, dec-&-enter, Otherwise, wait.
		critical section
		V(mutex);        // Increment semaphore
		remainder section
} while (1);

busy-wait効率低下

Block / Wakeup Implementation

Semaphore定義:

typedef struct
{
	int value;             // semaphore
	struct process *L;     // process wait queue
} semaphore;

blockとwakeupを仮定します.

block:カーネルはblockを呼び出すプロセスを保留し、そのプロセスのPCBを信号量のwaitキュー

に入れる.

wakeup(P):ブロックされたプロセスPを起動し、そのプロセスのPCBをreadyキュー

に移動する

Implementation

Semaphore演算は現在

と定義されている.
→通常、Block/wakeupの方が良い
→非常保護の長さが短い場合、Block/Wakeupのオーバーヘッドはビジー-待機オーバーヘッドよりも大きい可能性があります

Two Types of Semaphores

Counting semaphore

ドメインが0より大きい任意の整数値

リソースカウント

用

Binary semaphore(=mutex)

0または値1の信号量

は主に反発(lock/unlock)

に用いられる.

Deadlock and Starvation

Deadlock

無期限に2つ以上のプロセスが互いに衝突するイベントを待つ現象

.

SおよびQが1に初期化する信号量

2つのリソースが必要な2つのプロセスは条件を満たすことができず、相手のリソースを無限に待つことができます.

Starvation

indefinite blocking.

細い麻布キューからプロセスが保留されている理由から抜け出すことができません

Classical Problems of Synchronization

Bounded-Buffer Problem(Producer-Consumer Problem)

Shared data

バッファ自体とバッファ動作変数(空/満バッファの開始位置)

Synchronization variables

反発→Needバイナリ信号量(データ共有のための反発)

リソースカウント→Need整数信号量(残りの満/空バッファ数を示す)

→首都コードで表示

Synchronization variables
semaphore full = 0, empty = n, mutex = 1;

Producer
do{
	produce an item in x

	P(empty);
	P(mutex);

	add x to buffer

	V(mutex);
	V(full);

}while(1);

Consumer
do{
	P(full);
	P(mutex);

	remove an item from buffer to y

	V(mutex);
	V(empty);

	consumer the item in y

}while(1);

Readers-Writers Problem

あるプロセスがデータベースに書き込まれている場合、他のプロセスは

にアクセスできません.

同時に複数の人が

を読む

solution

作成者がデータベースアクセス許可証を取得していない場合、待機中のすべてのリーダがデータベース

にアクセスできる.

ライタは、1つのリーダが待機していない場合に、

へのデータベースアクセスを許可する.

作成者がデータベースにアクセスしていると、リーダーは

へのアクセスを禁止されます.

の作成者がデータベースを離れてこそ、リーダーが

にアクセスできるようになります.

Shared data

DB自体

readcount//現在データベースにアクセスしているリーダーの数

Synchronization variables

コード(キー)反発アクセス反発mutex//共有変数readcountを確保するために使用

db//readerおよび作成者は、共有データベース自体のロール

に正しくアクセスできます.
→首都コード
Shared data
int readcount = 0;
DB;
Synchronization variables
semaphore mutex = 1, db = 1;

Writer

P(db);

writing DB is performed

V(db);

!Starvation 발생 가능

Reader

P(mutex);
readcount++;
if(readcount == 1) P(db); //block writer
V(mutex);          // readers follow

reading DB is performed

P(mutex);
readcount--;
if(readcount == 0) V(db); // enable writer
V(mutex);

書き込み側が読み取り可能な状態になる前に、書き込みを続けると、書き込み側が餓死する可能性があります
→優先度をキューに入れて、徐々にwriterの優先度を上げていけばいい

Dining-Philosophers Problem

Synchronization variables
semaphore chopstick[5];
//initially all values are 1

Philosopher i
do {
	P(chopstick[i]);
	P(chopstick[i+1]%5);

	eat();

	V(chopstick[i]);
	V(chopstick[i+1]%5);

	think();

} while (1);

以上のソリューションの問題

Deadlock

かもしれません

すべての哲学者が同時に飢餓で左箸を取ったのは

だった.

ソリューション

4人の哲学者だけが机の上に座ることができます

両方の箸が取れる時だけ箸を持つことができます.

非対称

偶数(奇数)哲学者は左(右)箸から

を取った.
Sol 2水道コード

enum{thinking, hungry, eating} state[5];
semaphore self[5] = 0;
semaphore mutex=1;

Philosopher i
do{
	pickup(i);
	eat();
	putdown(i);
	think();
} while(1);

Monitor

Semaphoreに存在する問題

符号化が困難

の正しさを証明するのは難しい.

のボランティアが必要です

一度のミスがすべてのシステムに与える致命的な影響

問題例

ハイレベルの同期構造

は、コンカレント・プロセス間で抽象データ型を安全に共有することを保証する

モニタの

は一度に1つのプロセスしか実行できません

プログラマ明示的な符号化を必要としない同期制約

条件変数

を使用して、プロセスがディスプレイで待機していることを確認します.

条件変数はwaitと信号演算のみでアクセスできます

x.wait()を呼び出すプロセスは、他のプロセスがx.signal()を呼び出すまで保留されます.

x.signal()は、保留中のプロセスを正しく復元します.保留中のプロセスがなければ、何も起こりません.