オペレーティングシステム

5. スケジューリング (1)

授業の流れ・チーム分けの方針・態度目標

2024-04-12 のものと同じ。

https://lsnl.jp/~ohsaki/lecture/os/2024/#10-1

内容目標

- スケジューリング (scheduling)、スケジューラ (scheduler)、スケジューリングアルゴリズム (scheduling algorithm) の違いを理解し、他人に説明できるようになる。

- 効率的なスケジューリングが困難である 4 つの理由を理解し、他人に説明できるようになる。

- 横取りなし (ノンプリエンプティブ) のスケジューリングと、横取りあり (プリエンプティブ) のスケジューリングが、それぞれどのような用途に向いているかを理解する。

- FCFS (First-Come First-Served) スケジューリングの動作をトレースし、ターンアラウンドタイムを計算できるようになる。

課題

資料

Scheduling disciplines
https://en.wikipedia.org/wiki/Scheduling_(computing)#Scheduling_disciplines

Turnaround time
https://en.wikipedia.org/wiki/Turnaround_time

課題 1

オペレーティングシステムにおける、 「スケジューリング (scheduling)」、 「スケジューラ (scheduler)」、 「スケジューリングアルゴリズム (scheduling algorithm)」とは何か。

課題 2

オペレーティングシステムにおいて、 効率的なスケジューリングが困難である理由を 4 つ説明せよ。

課題 3

横取りなし (ノンプリエンプティブ) のスケジューリングと、 横取りあり (プリエンプティブ) のスケジューリングは、 それぞれどのような用途に向いているか。

課題 4

下表に示すプロセス P1〜P4 を、 FCFS (First-Come First-Served) スケジューリングを用いて実行した時の、 各プロセスのターンアラウンド時間をそれぞれ答えよ。

| プロセス  | 生成時刻 [スロット]    | 計算時間 [スロット]   |
|----------+---------------------+---------------------|
| P1       |                   0 |                   4 |
| P2       |                   2 |                   8 |
| P3       |                   4 |                   2 |
| P4       |                  10 |                   2 |

略解

課題 1

次に実行すべきプロセスを選択すること (行為) が「スケジューリング」であり、 その選択方法 (計算手順) が「スケジューリングアルゴリズム」である。 オペレーティングシステム (= ソフトウェア) において、 スケジューリングを実施するソフトウェアが「スケジューラ」である。

課題 1 のヒント: 専門用語の読み解き方

情報工学の分野では、 カタカナ語が過度なまでに多用される。 専門用語はカタカナで理解するのではなく、 元の英語で理解するのがポイントである。

上の「スケジューリング (scheduling)」、 「スケジューラ (scheduler)」、 「スケジューリングアルゴリズム (scheduling algorithm)」の例で説明しよう。

まず、それぞれの英単語の品詞を理解する。 特に、schedule には名詞と動詞の両方が存在する。 名詞としての schedule なのか、 動詞としての schedule なのかを理解する。

scheduling は単語の形 (末尾が -ing) からわかるように、 schedule (動詞) の動名詞である。 scheduling は schedule (動詞) の動名詞なので、 「schedule すること」という名詞の意味を持つ。

scheduling algorithm は「動名詞 + 名詞」の形なので、 scheduling algorithm における動名詞 scheduling は動名詞の形容詞用法 (名詞を修飾する形容詞としての動名詞) である。

動名詞の形容詞用法には、 「sleeping bagy (眠っている赤ん坊)」と「sleeping bag (眠ることのための袋)」の 2 つのパターンがある。 scheduling algorithm は、 意味から考えて「スケジュールすることのためのアルゴリズム (纂法)」であることがわかる。

scheduler は名詞である。 語尾が -er で終わっていることから、 「schedule する人もしくはモノ」を意味することがわかる。

これらの英単語の意味や、 英語の文法を正確に頭に入れてから、 課題 1 の「略解」を読んでみよ。

課題 2

- プロセスの切り替えに時間がかかる (頻繁に切り替えると CPU が無駄になる)
- プロセスはブロックされるかもしれない (ブロックされると CPU を割り当てられなくなる)
- 必要な計算量は事前にわからない (事前にスケジューリング計画を立てるのが困難)
- 何が重要かは用途による (何が「良い」スケジューリングなのかは状況による)
※ 具体的な例を考えて、これら 4 つが本当に困難である理由であるかを理論的に説明できるようにせよ。

課題 3

横取りなし (ノンプリエンプティブ) → バッチ (サーバ向けの OS)
横取りあり (プリエンプティブ) → 会話型 (一般的なエンドユーザ向けの OS)
※ なぜそうなのかを理論的に説明できるようにせよ。

課題 4

FCFS (First-Come First-Served)

P1 ========
P2     ----================
P3         ----------------====
P4                     --------====
   + + + + + + + + + + + + + + + + + + + + + + + +
   0         5         10        15        20

ターンアラウンドタイム
P1: 4 [スロット]
P2: 10 [スロット]
P3: 10 [スロット]
P4: 6 [スロット]
平均: 7.5 [スロット]

レポート課題 2024-05-17

「レポート課題 2024-04-12」と同じ。

https://lsnl.jp/~ohsaki/lecture/os/2024/#10-10

質問

- 先生のお気に入りの言語はありますか? あればどのような点で他の言語と異なりますか?

アセンブリ言語、Perl、Python、シェル (シェルスクリプト)、Emacs Lisp が特に好
きです。

アセンブリ言語 → 代用できないオンリーワン
Perl → 日常会話を交すような感覚でプログラムが書ける
Python → 直交性が高くてキレイ
シェル → UNIX の伝統、恐しいほどの記述力
Emacs Lisp → Emacs を自由に簡単にカスタマイズできる

- 授業後にCTFを1から解き直したい場合は、別のユーザーネームを取得していいのでしょうか?

はい。

要望

なし

コメント

- 講義ありがとうございました。

- みんなで考えながら問題を解くのは楽しかったです。

- CTFでは各課題の理解を深めづらいです。(CTFに学んだことが活かせない)