プロセス制御 - SEGAWA`s Web Site

プロセスの
状態・制御・スケジューリング
オペレーティングシステム
第7回
並 行 処 理(1)

割込みが頻繁に起きる

割込み処理が迅速に行われる

割り込まれたプログラムと
割込み処理プログラムが
同時に実行されているようにみえる
並 行 処 理(2)



TSSはタイマー割込みにより,複数の利用者のプ
ログラムを同時に実行する
物理的CPUがひとつでも,複数の擬似的CPUで
複数のプログラムを(見かけ上)同時に実行する
ことができる
並行処理
CPUがひとつだけなら,
ある時点では
ひとつのプログラムしか
実行されていない
プ ロ セ ス の 状 態(1)




プロセスは3つの状態を遷移する
実行中(状態)(running)
 物理的CPUが割り当てられていて,実際に処
理が進んでいる
実行可能状態(ready)
 物理的CPUが割り当てられるのを待っている
待ち状態(wait)
 何らかの事象が起きるのを待っている
プ ロ セ ス の 状 態(2)
プロセス消滅
プロセス生成

矢印の方向にだけ遷移する
プ ロ セ ス の 状 態(3)

状態遷移のきっかけの例
① 実行中→実行可能状態

タイムスライス分の割当て時間経過

このようなプロセスは,CPUが割り当てられ
れば,直ちに実行中になる
② 実行可能状態→実行中

CPUが割り当てられる
プ ロ セ ス の 状 態(4)
③ 実行中→待ち状態

データ入力が必要になった(事象待ち)

このようなプロセスは,CPUが割り当てられ
ても,実行中になれない

CPUの割り当て対象としない
④ 待ち状態→実行可能状態

必要なデータ入力が終了(事象発生)
プ ロ セ ス の 状 態(5)
プロセス消滅
プロセス生成
赤矢印の遷移が
ない理由

矢印の方向にだけ遷移する
プロセスの実行制御
ク リ テ ィ カ ル レ ー ス(1)



並行処理されている複数のプロセス
同じデータを同時に読み書き
 読むだけなら問題ない
タイミングにより誤った結果
ク リ テ ィ カ ル レ ー ス(2)


銀行口座の残高更新
① 残高読み出し
② 残高再計算
③ 計算結果の書き込み
入金と引出しが同時に行われたら?
ク リ テ ィ カ ル レ ー ス(3)
① 50,000
③ 60,000
⑤と⑥を実行する
タイミングにより
結果が変わる!
② 50,000
④ 35,000
60,000円
35.000円
⑤ 60,000
⑥ 35,000
⑤と⑥が逆になると,
60,000が残高!
これが残高!
クリティカルセクション


際どい部分(critical section)
 あるプロセス中で,他のプロセスと同時に実行
すると問題が起こりうる部分
クリティカルセクションを実行するプロセスをひと
つにする
 排他制御
同期基本命令

プロセスの制御を行う

いろいろある

代表例 セマフォ(semaphore)
セ マ フ ォ(1)


Dijkstra,E.W. が提案
腕木信号とか手旗信号(旧交通博物館)
セ マ フ ォ(2)


排他的に実行されるふたつの命令
 P 命令と V命令
その引数である変数(セマフォ変数)
セ マ フ ォ(3)



命令P(sem)
セマフォsemの値を1減らす
結果のsemの値
 正または0 → Pを呼び出したプロセスの実行
は続く
 負 → Pを呼び出したプロセスは待ち状態にな
る
セ マ フ ォ(4)




semを1増やした結果が
負または0ということは
増やす前は負ということ!
semを負にしたプロセスが
命令V(sem)
あるはず!
semの値を1増やす
それは待ち状態
Vを呼び出したプロセスの実行は続く
semの値が負または0
P(sem)で待ち状態になったプロセスが
あるはずなので,そのひとつを実行
可能状態にする
セ マ フ ォ(5)
入金処理が先
このP命令でsが 0
入金処理は先に進む
出金処理が後
sは-1となり,
待ち状態となる
出金処理が
実行可能状態
残高60,000円
このV命令でsが 0
入金処理終了
セ マ フ ォ(6)

セマフォの初期値の値の数だけのプロセスが命
令Pを通過できる
スケジューリング
どのプロセスにCPUを割り当てるか!
プロセスの特性



もっぱら計算中心のもの
 CPUを長時間使う
入出力中心のもの
 CPUの比重は低い
うまく割り当てると効率が良くなる
スケジューリング方法(1)
① 到着順

実行可能状態になったプロセスから順に

計算中心のプロセスが実行状態になると,
他のプロセスはなかなか実行状態にならな
い
スケジューリング方法(2ー1)
② 優先度順

プロセスに優先度を付ける

優先度の高いものから実行

実行中のプロセスより優先度の高いプロセ
スが実行可能状態になったとき,どうする?
スケジューリング方法(2ー2)


優先度の高いプロセスに切り替える
 プリエンプティブスケジューリング(preemptive
scheduling 横取りスケジューリング)
優先度の低い実行中のプロセスを継続
 ノン プリエンプティブスケジューリング
(nonpreemptive scheduling)
スケジューリング方法(3)
③ ラウンドロビン

順番にタイムスライス分の時間だけ実行す
る

プロセスA,B,C

A→B→C→A→…
スケジューリング方法(4)



実際にはもっと複雑
いくつかのスケジューリング方法を組み合わせる
 ラウンドロビン+優先度順
他の点を考慮したスケジューリング
スケジューリング方法(5)


優先度順の優先度が変化
一定時間,実行中だと優先度を下げる
 優先度が上の実行可能状態のプロセスがあ
れば,そちらを実行
補 足(1)

並列処理
 複数のCPUで複数のプログラムを実行

マルチコアの出現で身近に
補 足(2)

スケジューリング
 説明したものは,CPUの割り当て
 プロセススケジューリング


入出力スケジューリング
入出力装置の割り当て
ま と め(1)

プロセスの状態
 実行中(状態)
 実行可能状態
 待ち状態
ま と め(2)
プロセス消滅
プロセス生成

矢印の方向にだけ遷移する
ま と め(3)

平行処理されている複数のプロセス

同じデータを同時に読み書き

タイミングによる問題を起こす

クリティカルレース
 排他制御
ま と め(4)

スケジューリング
 到着順
 優先度順
 ラウンドロビン
 …