2025-04-25 のものと同じ。
https://lsnl.jp/~ohsaki/lecture/os/2025/#12-1
- 代表的なスケジューリングアルゴリズム (最短ジョブ優先方式、最小残り時間優先方式、ラウンドロビン方式) の特徴を理解し、他人に説明できるようになる。
- 代表的なスケジューリングアルゴリズムの動作をトレースし、ターンアラウンド時間の観点からそれぞれのスケジューリングアルゴリズムの特性の違いを理解できるようになる。
- 最短ジョブ優先方式や最小残り時間優先方式を現実のスケジューラで用いる場合に、どのような困難さがあるかを理解し、他人に説明できるようになる。
- ラウンドロビン方式のクォンタムの設定が、何と何のトレードオフであるかを理解し、他人に説明できるようになる。
資料
Scheduling (computing)
https://en.wikipedia.org/wiki/Scheduling_(computing)
Shortest job next
https://en.wikipedia.org/wiki/Shortest_job_next
Shortest remaining time
https://en.wikipedia.org/wiki/Shortest_remaining_time
Round-robin scheduling
https://en.wikipedia.org/wiki/Round-robin_scheduling最短ジョブ優先方式 (SJF; Shortest Job First) と最小残り時間優先方式 (SRTF; Shortest Remaining Time First) の共通点と相違点をそれぞれ答えよ。
下表に示すプロセス P1〜P4 を、 SJF および SRTF スケジューリングを用いて実行した時の、 各プロセスのターンアラウンド時間および平均ターンアラウンド時間をそれぞれ答えよ。
| プロセス | 生成時刻 [スロット] | 計算時間 [スロット] |
|----------+---------------------+---------------------|
| P1 | 0 | 4 |
| P2 | 2 | 8 |
| P3 | 4 | 2 |
| P4 | 10 | 2 |課題 2 の表に示すプロセス P1〜P4 を、 RR (Round Robin) スケジューリングを用いて実行した時の、 各プロセスのターンアラウンド時間および平均ターンアラウンド時間をそれぞれ答えよ。 ただし、クォンタムは 1 [スロット] とし、 新規に生成されたプロセスはキューの末尾に追加されるとする。
RR スケジューリングにおけるクォンタムを増加させると、 オペレーティングシステムのどのような特性が向上し、 また逆にオペレーティングシステムのどのような特性が低下するかを答えよ。
SJF も SRTF もジョブの実行時間が既知であることを前提としている。
SJF は横取りなし (non-preemptive) であるが、 SRTF は横取りあり (preemptive) のスケジューリングアルゴリズムである。
※ SJF や SRTF には複数の名称があることに注意する。 例えば、 SJF (Shortest Job First) は、 SJN (Shortest Job Next) や SPN (Shortest Process Next) とも呼ばれる。
「ジョブ (job)」や「タスク (task)」は、 計算機上が実行する処理のひとまとまりを表す。 どのくらいの単位の処理をジョブと呼び、 どのくらいの単位の仕事をタスクを呼ぶかは決まっていない。 一般的に、 ジョブは比較的大きな処理を、 タスクは比較的小さな処理を表すことが多い。
FCFS や SJF のようなスケジューリングアルゴリズムは、 汎用のアルゴリズムである。 つまり、 プロセスのスケジューリングのために用いられる専用のアルゴリズムではない。 例えば FCFS は、 オペレーティングシステムにおけるプロセススケジューリングにも、 データベースにおけるトランザクションのスケジューリングにも、 ルータにおけるパケットのスケジューリングにも用いられる (ことがある)。 このため、FCFS や SJF のようなスケジューリングアルゴリズムでは、 ひとまとまりの処理を「ジョブ」と読んでいる。
オペレーティングシステムにおけるプロセスのスケジューリングでは、 「ジョブ」が「プロセス (もしくはスレッド)」に相当する。 従って、 プロセスのスケジューリングという文脈では、 「SJF は残り時間が最も短いジョブに CPU を割り当てる」と言っても、 「SJF は残り時間が最も短いプロセスに CPU を割り当てる」と言っても、 どちらも正しい表現である。 「ジョブ」と「プロセス」のどちらを使うかは、 何を表現したいかによる。
SJF (Shortest Job First)
P1: 4 [スロット]
P2: 12 [スロット]
P3: 2 [スロット]
P4: 6 [スロット]
平均: 6.0 [スロット]SRTF (Shortest Remaining Time First)
P1: 4 [スロット]
P2: 14 [スロット]
P3: 2 [スロット]
P4: 2 [スロット]
平均: 5.5 [スロット]ここでは、 プロセスの切り替え時間をゼロとしている。 SJF よりも、 SRTF のほうがターンアラウンド時間が小さくなっている。
RR (Round Robin)
P1: 5 [スロット]
P2: 14 [スロット]
P3: 5 [スロット]
P4: 4 [スロット]
平均: 7.0 [スロット]ここでも、課題 2 と同じく、 プロセスの切り替え時間をゼロとしている。 RR のターンアラウンド時間が、 SJF や SRTF よりも大きくなっている。
CPU の利用効率が向上する一方、 プロセスの応答性能が低下する (応答時間が増大する)。
以下は、 より多く (16 個) のプロセスを、 FCFS、 SJF、 SRTF、 RR でスケジューリングした時のシミュレーション結果である。 4 つのシミュレーションにおいて、 プロセスの生成時刻および計算時間はすべて同じである。
FCFS (First-Come First-Served)
SJF (Shortest Job First)
SRTF (Shortest Remaining Time First)
RR (Round Robin)
ジョブの実行時間や残り時間を利用する (逆に言えば、 それが既知の時にしか使えない) SJF や SRTF の平均ターンアラウンド時間が小さいことがわかる。 また、 RR のターンアラウンド時間は、 これら 4 方式の中で最も大きい (ターンアラウンド時間の観点では最悪の性能) こともわかる。
「レポート課題 2025-04-11」と同じ。
https://lsnl.jp/~ohsaki/lecture/os/2025/#10-10
※次回は講義形式で前半の総復習をします。 前半の内容で理解が不十分なもの、 疑問が残っているもの、 もっと知りたいものを整理しておいてください。 次回の授業では、 授業中に「みなさんが聞きたいこと」を書き込んでもらって、 それらについて私が解説します。