キーワードのまとめです。

3. 並行プロセス

プロセス競合

リソースを取り合うなど、互いに他のプロセスの存在を意識しなければならないが、自分自身の処理の進行のためにはそれらは不要

プロセス協調

複数のプロセスが互いに協調して情報交換を行いながら共通の目的のために処理を進める
互いに他のプロセスを必要とする

プロセス統合

プロセスの相互干渉についての研究のこと
プロセスの同期に重点を置いている

プロセス干渉

相手プロセスの中断など、はっきり他のプロセスに影響を与えるもの

プロセス同期

プロセス統合と同意

ブロードキャスト

メッセージを他のプロセス全てに送る

待ち状態

リンク

プロセス間のデータ伝送媒体
ソケット、チャネル、ポートなどと呼ばれる

コンシューマ

クリティカルセクション

分割してはならないプログラムの部分
命令列が混合して実行されることのないようにすることで、排他制御を実現する

デッドロック

全てのプロセスが互いに他のプロセスがリソースを解放するのを待ち合う状態となり、どのプロセスも先に進めないようになること

ダイニング・フィロソファ問題

オペレーティングシステムにたびたび生じるリソース競合を抽象化した問題
- 5人の哲学者がテーブルについている、各哲学者は考えることと食べることを繰り返す
- 食べる時は両側に置いてある箸を2本取って食べる（箸は5本しかないため、自分の両隣りが食べていない時のみ食べることができる）

ディスパッチャ

イベント変数

状態変化（イベント）の発生やその履歴を伝えるためにアクセスされる、プロセス間の共通変数

スタベーション問題

プロセス間通信

ロッキング

メッセージ

メッセージ転送

各プロセスは処理を実行するのに他のプロセスを必要とする
このような気候をメッセージ転送（交換）という

排他制御

排他的にプログラムを実行し、共通変数へのアクセスを同時には一つのプログラムに限ること

AND条件

OR条件

NOT条件

マルチプレクシング

OR条件を伴うイベント通知問題
プロセスは複数のイベントによって起動され、イベントの種類によって異なった行動をとる

プロデューサ/コンシューマ問題

プロデューサとコンシューマの操作を統合させる問題のこと
プロデューサ
- メッセージをバッファに入れる操作を行うプロセス
コンシューマ
- バッファからメッセージを取り出し、処理を行うプロセス

SEMAPHORE S = N # バッファスロット数
SEMAPHORE M = 0 # バッファ内メッセージ数
MESSAGE BUFFER[N] # Nスロットのバッファ

# プロデューサ
{
	int I=0
	while(true){
		P(S)
		BUFFER(I) = message
		V(M)
		I=(I+1) mod N
	}
}

# コンシューマ
{
	int J=0
	while(true){
		P(M)
		message = BUFFER(J)
		V(S)
		J=(J+1) mod N
	}
}

リーダ/ライタ問題

リーダとライタプロセス間の同期問題
- ライタによる書き込み操作の後、レコードが矛盾のないデータを有していることを保証しなければならない
- リーダがレコードから矛盾のないデータを得ることを保障しなければならない
リーダ
- レコードからデータの読み出しをするプロセス
ライタ
- レコードにデータを書き出すプロセス

SEMAPHORE W=1

# ライタ
while(true) {
	P(W)
	write()
	V(W)
}

# リーダ
SEMAPHORE M=1
int R=0

while(true) {
	P(M)
	if (R==0) P(W)
	R=R+1
	V(M)
	read()
	P(M)
	R=R-1
	if (R==0) V(W)
	V(M)
}

擬似デッドロック

CPUの数がプロセスの数より少ない時、CPUは現在クリティカルセッション内にいる低い優先度のプロセスから取り上げられ、優先度の高いプロセスの待ちループの繰り返しに当てられる
しかし優先度の存在のため永久に待ち状態が解消されない現象が起こる

実行可能状態

リソース

セマフォア

プロセス間の信号を伝達するのに用いられる整数型の変数
PとV命令が定義されている

P/V/P_or/P_and

P(S) {
	if(S>=1) {
		S=S-1
	} else {
		Pを実行したプロセスをSの待ち行列に入れる
	}
}

V(S) {
	if(|L|>=1) { # Lは待ち行列にあるプロセス数
		待ち行列からプロセスを一つ取り出し、実行可能状態に変える
		Vを実行したプロセスも実行可能状態にし、制御をディスパッチャへ移す
	} else {
		S = S+1
	}
}

WAIT/POST

1ビットのWAITビットと1ビットのPOSTビットを用いてプロセス同期を行う方式

send/receive

send
- メッセージを相手プロセスへ送る
receive
- 送り元プロセスからメッセージを一つ受け取る

ブロッキング/ノンブロッキング

メッセージがないときや、空きスロットがないときにプロセスを停止する方式をブロッキング方式という
プロセスを中断しないで状態変数を返すものをノンブロッキング方式という

シーケンサ

短調増加の整数型の変数
整理券（番号札）

イベントカウント

現在サービス中のシーケンサを記憶しておくもの

Test and Set 命令

/* M: メモリロケーション, R: レジスタ */

TS M, R
{
	R=(M);
	M=1;
}

Swap命令

/* M: メモリロケーション, R: レジスタ */

SW M, R
{
	T=(M);
	M=(R);
	R=(T)
}

advance

サービスの完了に対応、イベントカウントを1増加させ、次の客を受け入れ、サービスを開始する
- advance(E)

await

客が待合室でサービスの順番を待つことに対応
- await(E, v)
  - Eがvに等しくなるまでプロセスを一時停止させる命令

ticket

現在のSの値を返すとともにSを1増加させる操作
- ticket(S)

wait/signal

P命令はwait命令
V命令はsignal命令

wait_or

発生したイベント全てを取り出す命令
- wait_or(e1, e2, …, en, A)
  - Aはどのイベントが発生したかという情報を返すパラメタ

wait_and

アイドルプロセス

CPUの数だけある優先度0のプロセス
他に実行可能なプロセスがなければアイドルプロセスが選択される

親プロセス

プロセスが他のプロセスを生成した時、生成したプロセスを子プロセス、生成した方のプロセスを親プロセスという

子プロセス

CREATE PROCESS

子プロセスを生成する

DELETE PROCESS

プロセスを削除する

SUSPEND PROCESS

あるプロセスが別のプロセス（自分自身でも良い）の実行を一時停止する

RESUME PROCESS

一時停止されたプロセスを再開始する