LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@torus0818

オペレーティングシステム　第3章 並行プロセス

Posted at

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

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

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?