プロセスのスケジューリング2

プロセスのスケジューリング２
リアルタイムスケジューリング
もう少し違ったスケジュール法
もう少し違ったスケジュール法
• 要求条件が違うと、
スケジュール法も違ったものが欲しくなる
• 例：
リアルタイム要求
もう少し違ったスケジュール法
• 要求条件が違うと、
スケジュール法も違ったものが欲しくなる
• 例：
• ⇒
リアルタイム要求
リアルタイムって？
リアルタイムとは
• 訳すると 「実時間」
リアルタイムとは
• 訳すると 「実時間」
• 「締切時間を気にする」ということ
リアルタイムとは
• 訳すると 「実時間」
• 「締切時間を気にする」ということ
– ある時間までに処理して欲しい
リアルタイムとは
• 訳すると 「実時間」
• 「締切時間を気にする」ということ
– ある時間までに処理して欲しい
– １）「３秒後までに」
「Ｘ時Ｙ分までに」
リアルタイムとは
• 訳すると 「実時間」
• 「締切時間を気にする」ということ
– ある時間までに処理して欲しい
– １）「３秒後までに」
「Ｘ時Ｙ分までに」
• 「タイマーをかけた」というよりは、
その時間内にコンピュータが反応して欲しい
リアルタイムとは
• 訳すると 「実時間」
• 「締切時間を気にする」ということ
– ある時間までに処理して欲しい
– １）「３秒後までに」
「Ｘ時Ｙ分までに」
• 「タイマーをかけた」というよりは、
その時間内にコンピュータが反応して欲しい
例： 戦闘機の防御システム
攻撃を受けてからある時間内に反応しないと
こちらが被害を受ける
リアルタイムとは
• 訳すると 「実時間」
• 「締切時間を気にする」ということ
– ある時間までに処理して欲しい
– １）「３秒後までに」
「Ｘ時Ｙ分までに」
• 「タイマーをかけた」というよりは、
その時間内にコンピュータが反応して欲しい
例： エンジンの燃料噴射制御
状況を0.x秒で分析して、噴射に反映したい
遅いとレスポンスが悪くなる
リアルタイムとは
• 訳すると 「実時間」
• 「締切時間を気にする」ということ
– ある時間までに処理して欲しい
– １）「３秒後までに」
「Ｘ時Ｙ分までに」
– ２）「やたら長くはない (適当な) 時間までに」
• 銀行のATMやみどりの窓口
５分も待たせたら客は帰ってしまうだろう
リアルタイムとは
• 訳すると 「実時間」
• 「締切時間を気にする」ということ
– ある時間までに処理して欲しい
– １）「３秒後までに」
「Ｘ時Ｙ分までに」
– ２）「やたら長くはない (適当な) 時間までに」
• 銀行のATMやみどりの窓口
５分も待たせたら客は帰ってしまうだろう
間に合わなくても破壊的なことにはならないが
リアルタイムとは
• 訳すると 「実時間」
• 「締切時間を気にする」ということ
– ある時間までに処理して欲しい
– １）「３秒後までに」
「Ｘ時Ｙ分までに」
– ２）「やたら長くはない (適当な) 時間までに」
–…
いろいろあるだろう
（前の到着順や処理時間順スケジューリングは
いつ実行するのでもよかった）
ことば（覚えておこう）
• ハードリアルタイム
– その時間までに処理できないと
壊滅的な打撃を受けるようなリアルタイム
• 兵器の例、機械の制御の例
ことば（覚えておこう）
• ハードリアルタイム
– その時間までに処理できないと
壊滅的な打撃を受けるようなリアルタイム
• 兵器の例、機械の制御の例
• ソフトリアルタイム
– その時間までに処理できて欲しいが
できなくても壊滅的な打撃は受けない
リアルタイム
• ATMや窓口の例
リアルタイム・スケジューリング
リアルタイム・スケジューリング
• リアルタイム（締切）の要求がある時の
スケジューリング
リアルタイム・スケジューリング
• リアルタイム（締切）の要求がある時の
スケジューリング
「デッドライン」と呼ぶ
リアルタイム・スケジューリング
• リアルタイム（締切）の要求がある時の
スケジューリング
• 先着順 や 処理時間順 は
リアルタイムではない
リアルタイム・スケジューリング
• リアルタイム（締切）要求がある時の
スケジューリング
• 先着順 や 処理時間順 は
リアルタイムではない、なぜなら
– 先着順で、前の人の処理が非常に長いと、
自分は何時になるか、分からない
リアルタイム・スケジューリング
• リアルタイム（締切）要求がある時の
スケジューリング
• 先着順 や 処理時間順 は
リアルタイムではない
– 先着順で、前の人の処理が非常に長いと、
自分は何時になるか、分からない
– 処理時間順では、処理時間が短い人が
後から次々と到着すると、先に入られて
自分は何時になるか、分からない
リアルタイム・スケジューリング
• リアルタイム（締切）要求がある時の
スケジューリング
• 先着順 や 処理時間順 は
リアルタイムではない
– 先着順で、前の人の処理が非常に長いと、
自分は何時になるか、分からない
– 処理時間順では、処理時間が短い人が
後から次々と到着すると、先に入られて
自分は何時になるか、分からない
別のスケジューリング方法が必要
ラウンドロビン・スケジューリング
• 一定時間ずつ順番にCPUを割り当てる
Ａ
Ｂ
Ｃ
Ｆ
Ｅ
Ｄ
順番に割り当てる
一定時間経ったら次の人へ
ラウンドロビン・スケジューリング
• 一定時間ずつ順番にCPUを割り当てる
– 一定時間＝「タイムスライス」と呼ぶ
– 一定時間CPUを使うと強制的に交代させる
Ａ
Ｂ
Ｃ
Ｆ
Ｅ
Ｄ
順番に割り当てる
一定時間経ったら次の人へ
ラウンドロビン・スケジューリング
• 一定時間ずつ順番にCPUを割り当てる
– 一定時間＝「タイムスライス」と呼ぶ
– 一定時間CPUを使うと強制的に交代させる
Ａ
Ｂ
Ｃ
Ｆ
Ｅ
Ｄ
順番に割り当てる
一定時間経ったら次の人へ
ラウンドロビンの語源は
自分で調べてみよ
ラウンドロビンの性質は？
• リアルタイムか？
Ａ
Ｂ
Ｃ
Ｆ
Ｅ
Ｄ
ラウンドロビンの性質は？
• リアルタイムか？
– 各人は必ずタイムスライス経過で打ち切られる
Ａ
Ｂ
Ｃ
Ｆ
Ｅ
Ｄ
ラウンドロビンの性質は？
• リアルタイムか？
– 各人は必ずタイムスライス経過で打ち切られる
– タイムスライス×N人で必ず廻ってくる
Ａ
Ｂ
Ｃ
Ｆ
Ｅ
Ｄ
ラウンドロビンの性質は？
• リアルタイムか？
– 各人は必ずタイムスライス経過で打ち切られる
– タイムスライス×N人で必ず廻ってくる
– ⇒ (Ｎが一定なら) 一定時間内に処理される
Ａ
Ｂ
Ｃ
Ｆ
Ｅ
Ｄ
ラウンドロビンの性質は？
• リアルタイムか？
– 各人は必ずタイムスライス経過で打ち切られる
– タイムスライス×N人で必ず廻ってくる
– ⇒ (Ｎが一定なら) 一定時間内に処理される
Ａ
Ｂ
Ｃ
Ｆ
Ｅ
Ｄ
ある人がCPUを長時間占有する
ことはない （必ず取上げ）
ラウンドロビンの性質は？
• リアルタイムか？
– 各人は必ずタイムスライス経過で打ち切られる
– タイムスライス×N人で必ず廻ってくる
– ⇒ (Ｎが一定なら) 一定時間内に処理される
Ａ
Ｂ
Ｃ
Ｆ
Ｅ
Ｄ
ある人がCPUを長時間占有する
ことはない （必ず取上げ）
プリエンプション
ラウンドロビンの性質は？
• リアルタイムか？
– 各人は必ずタイムスライス経過で打ち切られる
– タイムスライス×N人で必ず廻ってくる
– ⇒ (Ｎが一定なら) 一定時間内に処理される
Ａ
Ｂ
Ｃ
Ｆ
Ｅ
Ｄ
ある人がCPUを長時間占有する
ことはない （必ず取上げ）
Nが増えれば、時間は延びる
⇒ 必ずしも締切は守られない
ラウンドロビンの性質は？
• リアルタイムか？
– 各人は必ずタイムスライス経過で打ち切られる
– タイムスライス×N人で必ず廻ってくる
– ⇒ (Ｎが一定なら) 一定時間内に処理される
Ａ
ある人がCPUを長時間占有する
ことはない （必ず取上げ）
Ｂ
Ｃ
Ｆ
Ｅ
Ｄ
Nが増えれば、時間は延びる
⇒ 必ずしも締切は守られない
リアルタイムだが、ハードではない
ラウンドロビンの性質は？
• ハードリアルタイムにしたければ？
Ａ
Ｂ
Ｃ
Ｆ
Ｅ
Ｄ
ラウンドロビンの性質は？
• ハードリアルタイムにしたければ？
– 人数を制限する
Ａ
Ｂ
Ｃ
Ｆ
Ｅ
Ｄ
ラウンドロビンの性質は？
• ハードリアルタイムにしたければ？
– 人数を制限する
• Nを超えないようにする
• ⇒ 参加する時の手続きに「関門」を設け、
Nを超えるときは参加させず、
参加をあきらめさせる
Ａ
Ｂ
Ｃ
Ｆ
Ｅ
Ｄ
ラウンドロビンの使い道
• 対話型の仕事 (アプリケーション) に使う
– WindowsやLinuxで普通に使われている
ラウンドロビンの使い道
• 対話型の仕事 (アプリケーション) に使う
– WindowsやLinuxで普通に使われている
– Windows ⇒ 複数の窓を開く・裏で印刷…
• ユーザをあまり待たせずに応答する
ラウンドロビンの使い道
• 対話型の仕事 (アプリケーション) に使う
– WindowsやLinuxで普通に使われている
– Windows ⇒ 複数の窓を開く・裏で印刷…
• ユーザをあまり待たせずに応答する
– Linux ⇒ サーバーでは多数の相手からの要求を
同時並行に処理するために使う
• ユーザをあまり待たせずに応答する
ラウンドロビンの使い道
• 対話型の仕事 (アプリケーション) に使う
– WindowsやLinuxで普通に使われている
– Windows ⇒ 複数の窓を開く・裏で印刷…
• ユーザをあまり待たせずに応答する
– Linux ⇒ サーバーでは多数の相手からの要求を
同時並行に処理するために使う
• ユーザをあまり待たせずに応答する
どちらも、ハードリアルタイムではない。
ラウンドロビンの使い道
• 対話型の仕事 (アプリケーション) に使う
– WindowsやLinuxで普通に使われている
– Windows ⇒ 複数の窓を開く・裏で印刷…
• ユーザをあまり待たせずに応答する
– Linux ⇒ サーバーでは多数の相手からの要求を
同時並行に処理するために使う
• ユーザをあまり待たせずに応答する
どちらも、ハードリアルタイムではない。
（参加プロセス数を制限していない）
ラウンドロビンの使い道
• 対話型の仕事 (アプリケーション) に使う
– WindowsやLinuxで普通に使われている
– Windows ⇒ 複数の窓を開く・裏で印刷…
• ユーザをあまり待たせずに応答する
– Linux ⇒ サーバーでは多数の相手からの要求を
同時並行に処理するために使う
• ユーザをあまり待たせずに応答する
どちらも、ハードリアルタイムではない。
人間を相手にしているので、ソフトで間に合う
ラウンドロビンの使い道
• 対話型の仕事 (アプリケーション) に使う
– 銀行のATMやみどりの窓口など
ラウンドロビンの使い道
• 対話型の仕事 (アプリケーション) に使う
– 銀行のATMやみどりの窓口など
– 人間が相手の場合、3～5秒程度は待たせてOK
• それ以上になると文句を言う
• ATMや予約窓口のアプリは、１つ１つの操作が
中断できない (中断すると途中状態が保存される)
ので、タイムスライスによる中断は要注意
ラウンドロビンの使い道
• 対話型の仕事 (アプリケーション) に使う
– 銀行のATMやみどりの窓口など
– 人間が相手の場合、3～5秒程度は待たせてOK
• それ以上になると文句を言う
• ATMや予約窓口のアプリは、１つ１つの操作が
中断できない (中断すると途中状態が保存される)
ので、タイムスライスによる中断は要注意
これも、完璧なハードリアルタイムでなくてよい。
人間を相手にしているので、ソフトで間に合う
周期的な仕事のあるリアルタイム
• もう１つのリアルタイム ⇒ 周期的な仕事
周期的な仕事のあるリアルタイム
• もう１つのリアルタイム ⇒ 周期的な仕事
– 装置制御などで周期的に処理が必要な事がある
• 例： 0.1秒ごとにチェックして対応する
周期的な仕事のあるリアルタイム
• もう１つのリアルタイム ⇒ 周期的な仕事
– 装置制御などで周期的に処理が必要な事がある
• 例： 0.1秒ごとにチェックして対応する
• 「周期スレッド」と呼ぶ
周期的な仕事のあるリアルタイム
• もう１つのリアルタイム ⇒ 周期的な仕事
– 装置制御などで周期的に処理が必要な事がある
• 例： 0.1秒ごとにチェックして対応する
• 「周期スレッド」と呼ぶ
– 処理の間隔も処理時間も決まっている
• 但し、間隔・時間の違う複数の仕事が同時に存在
周期的な仕事のあるリアルタイム
• もう１つのリアルタイム ⇒ 周期的な仕事
– 装置制御などで周期的に処理が必要な事がある
• 例： 0.1秒ごとにチェックして対応する
• 「周期スレッド」と呼ぶ
– 処理の間隔も処理時間も決まっている
• 但し、間隔・時間の違う複数の仕事が同時に存在
• また、リアルハードタイムを要求
周期的な仕事のあるリアルタイム
• もう１つのリアルタイム ⇒ 周期的な仕事
– 装置制御などで周期的に処理が必要な事がある
• 例： 0.1秒ごとにチェックして対応する
• 「周期スレッド」と呼ぶ
– 処理の間隔も処理時間も決まっている
• 但し、間隔・時間の違う複数の仕事が同時に存在
• また、リアルハードタイムを要求
– これに対するスケジューリングとして
• 締切り順、レートモノトニックなどがある
締切り順(EDF)スケジューリング
• EDF = Earliest Deadline First
締切り順(EDF)スケジューリング
• EDF = Earliest Deadline First
• 締切時刻までの時間余裕が短いものほど
優先して先に処理する
– Aの余裕が5でBの余裕が3なら、Bを先に実行
締切り順(EDF)スケジューリング
• EDF = Earliest Deadline First
• 締切時刻までの時間余裕が短いものほど
優先して先に処理する
– Aの余裕が5でBの余裕が3なら、Bを先に実行
時間
プロセスA
プロセスB
開
始
実行
開
始
残っている処理
実行
実行
実行
残っている処理
次に実行する
プロセスを決める
時間余裕(5)
時間余裕(3)
締
切
締
切
締切り順(EDF)スケジューリング
• EDF = Earliest Deadline First
• 締切時刻までの時間余裕が短いものほど
優先して先に処理する
– Aの余裕が5でBの余裕が3なら、Bを先に実行
– 予めプロセスの実行処理時間が分かっていなけ
ればならない
締切り順(EDF)スケジューリング
• 例： （教科書p32）
スレ
ッド
実行可能に
なった時刻
残りの
実行時間
処理完了
締切時間
Ａ
1
6
18
Ｂ
3
8
30
Ｃ
4
1
35
Ｄ
7
2
13
Ｅ
9
4
25
余裕
時間
割当て優先度
小さいほど高優先
締切り順(EDF)スケジューリング
• 例： （教科書p32）
スレ
ッド
実行可能に
なった時刻
残りの
実行時間
処理完了
締切時間
余裕
時間
Ａ
1
6
18
18-6
=12
Ｂ
3
8
30
30-8
=22
Ｃ
4
1
35
35-1
=34
Ｄ
7
2
13
13-2
=9
Ｅ
9
4
25
25-4
=21
割当て優先度
小さいほど高優先
締切り順(EDF)スケジューリング
• 例： （教科書p32）
スレ
ッド
実行可能に
なった時刻
残りの
実行時間
処理完了
締切時間
余裕
時間
Ａ
1
6
18
18-6
=12
2
Ｂ
3
8
30
30-8
=22
4
Ｃ
4
1
35
35-1
=34
5
Ｄ
7
2
13
13-2
=9
1
Ｅ
9
4
25
25-4
=21
3
割当て優先度
小さいほど高優先
レートモノトニック
スケジューリング
• RMS = Rate Monotonic Scheduling
レートモノトニック
スケジューリング
• RMS = Rate Monotonic Scheduling
• 起動される頻度が高いプロセス(スレッド)ほど
レートモノトニック
スケジューリング
• RMS = Rate Monotonic Scheduling
• 起動される頻度が高いプロセス(スレッド)ほど
高い優先度を割当てる
レートモノトニック
スケジューリング
• RMS = Rate Monotonic Scheduling
• 起動される頻度が高いプロセス(スレッド)ほど
高い優先度を割当てる
• （ややこしいので詳細は省略）
– こんな名前のものがある、程度にしよう
レートモノトニック
スケジューリング
• RMS = Rate Monotonic Scheduling
• 起動される頻度が高いプロセス(スレッド)ほど
高い優先度を割当てる
• （ややこしいので詳細は省略）
– こんな名前のものがある、程度にしよう
– (横取り可能＆固定優先度) のスケジューリ
ングでは「最適」と知られている
リアルタイムスケジューリングの
考え方が理解できましたか？
〇
次へ
64
×