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

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

Download Report