プロセスの状態・制御・スケジューリング

プロセスの
状態・制御・スケジューリング
オペレーティングシステム
第7回
今回の内容




並行処理
 並列処理
プロセスの状態
プロセスの実行制御
 クリティカルレース
 同期基本命令
スケジューリング
並行処理と並列処理
並 行 処 理(1)

割込みが頻繁に起きる

割込み処理が迅速に行われる

割り込まれたプロセスと
割込み処理のプロセスが
同時に実行されているようにみえる
並 行 処 理(2)



TSSはタイマ割込みにより,複数のプロセスを同
時に実行する
物理CPUがひとつでも,複数の擬似CPUで複数
のプロセスを(見かけ上)同時に実行することが
できる
並行処理
物理CPUがひとつだけなら,
ある時点では
ひとつのプロセスしか
実行されていない
並行処理と並列処理



物理CPUが複数あると,“本当”に複数のプロセ
スが同時に実行される
並列処理
最近は,マルチコアが普通になった(?)ので,当
たり前のことになった(?)
プロセスの状態
プ ロ セ ス の 状 態(1)
物理CPUがあれば,実行できる




プロセスは3つの状態を遷移する
プロセスの数の方が,
実行中(状態)(running)
物理CPUの数より多いのが普通
 物理CPUが割り当てられていて,実際に処理
が進んでいる
実行可能状態(ready) 物理CPUがあっても,
 物理CPUが割り当てられるのを待っている
処理を進められない
待ち状態(wait)
 何らかの事象が起きるのを待っている
プ ロ セ ス の 状 態(2)
プロセス消滅
プロセス生成

矢印の方向にだけ遷移する
プ ロ セ ス の 状 態(3)

状態遷移のきっかけの例
① 実行中→実行可能状態

タイムスライス分の割当て時間経過

このようなプロセスは,CPUが割り当てられ
れば,直ちに実行中になる
② 実行可能状態→実行中

CPUが割り当てられる
プ ロ セ ス の 状 態(4)
③ 実行中→待ち状態

データ入力が必要になった(事象待ち)

このようなプロセスは,CPUが割り当てられ
ても,実行中になれない

CPUの割り当て対象としない
④ 待ち状態→実行可能状態

必要なデータ入力が終了(事象発生)
プ ロ セ ス の 状 態(5)
プロセス消滅
プロセス生成
赤矢印の遷移が
ない理由

矢印の方向にだけ遷移する
プロセスの実行制御
ク リ テ ィ カ ル レ ー ス(1)



並行処理されている複数のプロセス
同じデータを同時に読み書き
 読むだけなら問題ない
タイミングにより誤った結果
ク リ テ ィ カ ル レ ー ス(2)


銀行口座の残高更新
① 残高読み出し
② 残高再計算
③ 計算結果の書き込み
入金と引出しが同時に行われたら?
⑤と⑥を実行する
タイミングにより
結果が変わる!
ク リ テ ィ カ ル レ ー ス(3)
しかも,どちらの
結果も誤り!
正解は
45,000円
① 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命令
その引数である変数(セマフォ変数)
 初期値を1とする
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)で待ち状態になったプロセスが
あるはずなので,そのひとつを実行
可能状態にする
クリティカルセクションを
P命令とV命令が囲む
セ マ フ ォ(5)
入金処理が先
このP命令でsが 0
入金処理は先に進む
出金処理が後
sは-1となり,
待ち状態となる
出金処理が
実行可能状態
残高60,000円
このV命令でsが 0
入金処理終了
セ マ フ ォ(6)

セマフォの初期値の値の数だけのプロセスが命
令Pを通過できる
 初期値は1でなくてもよい
スケジューリング
正確には,
プロセススケジューリング
どのような場合
(条件)
スケジューリングとは
実行中のプロセスを
実行可能状態にして,
実行可能状態のプロセス
の一つを選び,実行中に
する
選択基準
プロセスの特性



もっぱら計算中心のもの
 CPUを長時間使う
入出力中心のもの
 CPUの比重は低い
うまく割り当てると効率が良くなる
スケジューリング方法(1)
① 到着順

実行可能状態になったプロセスから順に

計算中心のプロセスが実行中になると,
他のプロセスはなかなか実行されない
スケジューリング方法(2)
② 優先度順

プロセスに優先度を付ける

優先度の高いものから実行

実行中のプロセスより優先度の高いプロセ
スが実行可能状態になったとき,どうするか
により,二つに分けられる(次のスライド)
スケジューリング方法(3)


優先度の高いプロセスを実行
 プリエンプティブスケジューリング(preemptive
scheduling 横取りスケジューリング)
優先度の低い実行中のプロセスを続けて実行
 ノン プリエンプティブスケジューリング
(nonpreemptive scheduling)
スケジューリング方法(4)
③ ラウンドロビン

順番にタイムスライス分の時間だけ実行す
る

例 プロセスA,B,C

A→B→C→A→…

ただし,タイムスライス分経過する前に,待ち
状態になると,次のプロセスが実行される
スケジューリング方法(5)

ラウンドロビンの例
 プロセスが三つ A,B,C
 タイムスライス 10ミリ秒
Aが実行中
 A → B → C → A → … の順序
10ミリ秒
10ミリ秒経過すると,
Bが実行される
BとCは実行
可能状態
スケジューリング方法(6)

ラウンドロビンの例(続)
 ただし,各プロセス共に途中でデータの入出
力のために待ち状態になる
Bが実行中になって
5ミリ秒後に
待ち状態になる
Cが実行される
このあたりで,待ち状態から
実行可能状態になっても,
次にBが実行されるのは…
スケジューリング方法(7)

実際にはもっと複雑

いくつかのスケジューリング方法を組み合わせる
スケジューリング方法(8)

“ラウンドロビン+優先度順”の例(1)
 プロセスと優先度
A>B>C
 その1
タイムスライス A を15ミリ秒,B を10ミリ秒,C
を5ミリ秒
 その2
タイムスライスは同じ
A → B → A → B → A → C を繰り返す
スケジューリング方法(9)

“ラウンドロビン+優先度順”の例(2)





プロセス A1,A2 (優先度は同じ)
プロセス B1,B2 (優先度は同じ)
A1,A2 の優先度 > B1,B2 の優先度
A1 → A2 → A1 → … (*)
A1,A2 が待ち状態の時に
B1 → B2 → B1 → …
ただし,A1,A2が実行可能状態になったら,(*)に戻
る
スケジューリング方法(10)


優先度順の優先度が変化することもある
実行された時間の合計がある値になると(実行
中になった回数でもよい),優先度を下げる
 優先度が上の実行可能状態のプロセスがあ
れば,そちらを実行
 “時間のかかるプロセスは後回し”という考え
方
補足

スケジューリング
 説明したものは,CPUの割り当て
 プロセススケジューリング


入出力スケジューリング
入出力装置の割り当て
ま と め(1)

プロセスの状態
 実行中(状態)
 実行可能状態
 待ち状態
ま と め(2)
プロセス消滅
プロセス生成

矢印の方向にだけ遷移する
ま と め(3)




平行処理されている複数のプロセス
同じデータを同時に読み書き
タイミングによる問題を起こす
クリティカルレース
 排他制御
 同期基本命令
ま と め(4)

スケジューリング
 到着順
 優先度順
 ラウンドロビン
 …