スケジューリングアルゴリズムとは
スケジューリングアルゴリズムとは、レディキューにいるプロセスのうち、次にプロセッサを使わせるものを選ぶ決まりです。決まりが違うと、利用者が待たされる時間は大きく変わります。
役所の窓口で考えます。手続きが24分かかる人の後ろに、3分で終わる人が2人並んでいます。この順番だと、3分の人のうち最後の人は27分も待ちます。
このレッスンのゴール
メモ
先着順、最短ジョブ優先、ラウンドロビンを、待ち時間で比べることができる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| バースト時間 | プロセスがプロセッサを使う必要のある時間 | 24分 |
| 待ち時間 | 動き始めるまでに、キューで待った時間の合計 | |
| ターンアラウンド時間 | 着いてから終わるまでの、すべての時間 | |
| 先着順（FCFS） | 着いた順に、最後まで動かす方法 | |
| 最短ジョブ優先（SJF） | 必要な時間が短いものから動かす方法 | |
| 飢餓 | いつまでも順番が回ってこないこと |
学生が入力するセルは、このプレビューでは空白です。
待ち時間とターンアラウンド時間
このレッスンでは、全員が時刻0に着くことにします。プロセスAからCは、必要な時間が24分、3分、3分です。
待ち時間は、動き始めるまでに待った時間です。ターンアラウンド時間は、着いてから終わるまでの時間で、待ち時間に必要な時間を足したものです。
先着順は着いた順に最後まで動かす
先着順（FCFS）は、いちばん単純な方法です。着いた順に並べ、先頭を最後まで動かします。途中で止めません。
長い仕事が先頭にいると、後ろの短い仕事は長く待たされます。この現象をコンボイ効果と呼びます。大きな荷物の後ろで、列が進まない様子に似ています。
例: 先着順で24、3、3
| プロセス | 必要な時間 | 動き始め | 待ち時間 | 終わった時刻 |
|---|---|---|---|---|
| A | 24 | 0 | 0 | 24 |
| B | 3 | 24 | 24 | 27 |
| C | 3 | 27 | 27 | 30 |
| 平均 | 17 | 27 (ターンアラウンド) |
学生が入力するセルは、このプレビューでは空白です。
最短ジョブ優先は短いものから
最短ジョブ優先（SJF）は、必要な時間が短いものから動かします。窓口なら、3分の人を先に済ませて、24分の人を最後にします。
短い仕事が長い仕事の後ろで待たなくなるので、平均の待ち時間はいちばん短くなります。同じ3人でも、順番を入れかえるだけで、平均は17分から3分に下がります。
例: 最短優先で3、3、24
| プロセス | 必要な時間 | 動き始め | 待ち時間 | 終わった時刻 |
|---|---|---|---|---|
| B | 3 | 0 | 0 | 3 |
| C | 3 | 3 | 3 | 6 |
| A | 24 | 6 | 6 | 30 |
| 平均 | 3 | 13 (ターンアラウンド) |
学生が入力するセルは、このプレビューでは空白です。
よくある間違い
注意
「最短ジョブ優先がいつも最良だ」と考える人が多くいます。平均の待ち時間は、たしかにいちばん短くなります。ただし、動く時間を先に知る必要があります。短い仕事が来続けると、長い仕事は飢餓になります。
ラウンドロビンは公平に少しずつ
ラウンドロビンは、タイムスライスずつ順に動かし、残れば列の最後に戻す方法です。短い仕事は、長い仕事を待たずに早く終わります。
タイムスライスが大きすぎると、先着順と同じになります。小さすぎると、切りかえばかり増えて、仕事が進みません。ここでは4分にします。
例: ラウンドロビンで24、3、3
| プロセス | 必要な時間 | 終わった時刻 | 待ち時間 | 求め方 |
|---|---|---|---|---|
| A | 24 | 30 | 6 | 30 から 24 を引く |
| B | 3 | 7 | 4 | 7 から 3 を引く |
| C | 3 | 10 | 7 | 10 から 3 を引く |
| 平均 | 約5.7 | 合計17を3で割る |
学生が入力するセルは、このプレビューでは空白です。
3つの方法を同じ3人で比べる
| 方法 | 動く順 | 平均の待ち時間 |
|---|---|---|
| 先着順 | A、B、C | 17分 |
| 最短ジョブ優先 | B、C、A | 3分 |
| ラウンドロビン（4分） | A、B、C、A、A、... | 約5.7分 |
学生が入力するセルは、このプレビューでは空白です。
Linuxは優先度で順番を変える
本物のOSは、プロセスに優先度をつけます。Linux には nice 値があります。0が標準で、大きいほど「他に先を譲る」プロセスです。
nice だけを打つと、今の値が出ます。nice -n 5 nice は、値を5にして nice を動かすので、5が出ます。ふつうの利用者は、値を大きくすることだけができます。
今の nice 値を出す
niceここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
5にして動かす
nice -n 5 niceここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
Linuxのスケジューリング方針
Linux には、いくつかの方針があります。ふつうのプロセスは SCHED_OTHER です。SCHED_FIFO と SCHED_RR は、決まった時間に必ず動かしたい仕事のための、優先度1から99の方針です。
次のコマンドは、この3つの優先度の範囲を出します。
方針ごとの優先度の範囲
chrt -m | head -n 3ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。