1. 解説 (40 分)
2. グループワーク (35 分)
3. CTF (10 分)
4. グループワーク (5 分)
5. リフレクションシート記入 (10 分)2024-04-12 のものと同じ。
https://lsnl.jp/~ohsaki/lecture/os/2024/#10-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 方式の中で最も大きい (ターンアラウンド時間の観点では最悪の性能) こともわかる。
「レポート課題 2024-04-12」と同じ。
https://lsnl.jp/~ohsaki/lecture/os/2024/#10-10
※次回は講義形式で前半の総復習をします。 前半の内容で理解が不十分なもの、 疑問が残っているもの、 もっと知りたいものを整理しておいてください。 次回の授業では、 授業中に「みなさんが聞きたいこと」を書き込んでもらって、 それらについて私が解説します。
- 様々な言語を使用していて他言語のやり方をやってしまったりなどの混乱はないのですか?
使用する言語を切り替えた瞬間は多少はあります。が、そのほとんどは文法の違いに
起因したもので、文法の違いは入力時に機械的にチェックされるのでそれほど困りま
せん。- 講義内で先生が利用しているchatGPTにコマンドラインから質問をなげるものはchatGPTのAPIを契約してそれを利用しているのか、スクレイピングを利用しているのかどちらですか?
スクレイピングに相当します。ChatGPT の API は使用していません。Chrome をリモー
トデバッグモードで起動し、外部のプログラムから制御しています。プログラムは以
下のページで公開しています。
chatgpt-el
https://github.com/h-ohsaki/chatgpt-el- 講義ありがとうございました。
- CTFのグループ名が幾分ましになってよかった。
- 講義ありがとうございました。文字カウントがなくなっていたので少し不便でした
- レポート送信フォームで文字数カウントが出なくなりました。どの端末で操作しても表示されなかったのですが、原因はなんでしょうか?
指摘ありがとう。先日、リフレクションシートやレポート提出フォームを作り直した
のですが、その時に誤って文字数カウントの JavaScript コードを削除していました。
修正したので、今は直っていると思います。