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

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

加藤 真平

東京大学 大学院情報理工学系研究科

[email protected]

１．PFLab（加藤研）のウェブサイトからダウンロードできます。 ⇒http://www.pf.is.s.u-tokyo.ac.jp/ja/classes/ ２．紙資料も配布します。

講義概要

• 受講生に求める基礎知識

– C言語の理解

– コンピュータアーキテクチャの基礎の理解

• メモリ管理、割り込み、CPUモード

• 参考図書

– Silberschatz, Galvin, and Gagne, Operating System Concepts 8th

Edition,

Wiley

• 成績

– 試験の点数で決定

– 試験は持ち込み不可

– 授業に出席していた人で試験の結果が悪い人は追試験あり

• 出席をとるが出席点はなし

講義スケジュール（予定）

1. OSの概要（4/9） 2. プロセス管理（4/16） 3. プロセス間交信＆スレッド（4/23） 4. プロセス同期（5/7） 5. プロセス同期（5/14） 6. CPUスケジューリング （5/21） 7. CPUスケジューリング （5/28） 8. メモリ管理（6/4） 9. メモリ管理＆I/Oシステム（6/11） 10. I/Oシステム（6/18） 11. ファイルシステム（6/25） 12. プロテクション＆セキュリティ (7/2) 13. バッチシステム＆分散システム＆まとめ（7/9） 14. 試験（7/23） 論文も読んでみましょう。 ACM SOSP USENIX OSDI USENIX ATC USENIX NSDI ACM ASPLOS

CPU Scheduling

• 基本概念

• スケジューリングの尺度

基本概念

• マルチプログラミングで得られる最大

限のCPU使用率を上げること

– マルチプログラミング

• １台のコンピュータで同時に複

数のプログラムを実行すること

• CPUとI/O処理のサイクル

– プロセスはCPUによる処理とI/O待

ちをしているという２つのサイク

ルで成立

CPU スケジューラ

•

実行可能状態のプロセスのなかからプロセスをひとつ選び、

CPUによる実行を許可

– どのように選ぶかが問題であり、 – この話が本日と来週の講義の主テーマ

•

CPUスケジューラが呼び出されるタイミング

1. プロセス状態が変わるとき

Run  wait, wait  ready, run  terminate

2. タイマー割り込み 3. I/O割り込み

•

Nonpreemptiveスケジューリング

– 上記１のタイミングでしかスケジューリングしない場合 – すなわちプロセス自らCPU使用を放棄しない限りスケジューラが起動 されない、横取りされない

•

Preemptive（横取り）スケジューリング

– プロセス実行中にスケジューラが起動され、実行中のプロセスから他

Dispatcher

• Dispatcher：スケジューラによって 選択されたプロセスにCPUの実行 を与えるカーネルモジュール • Dispatcher latency – 実行中のプロセスを止めて他の プロセスの実行再開を行うまで の時間 • Dispatcherがやる仕事 – 実行していたユーザプロセスの 状態をPCBに退避 – 次に実行するプロセスの以前の 状態をPCBから取り出し、CPU レジスタにセット、メモリ管理 ユニットの内容設定 – ユーザプロセスに実行を戻す タイマ割り込み Scheduler Process P0 Dispatcher Process P1 Kernel

スケジューリング 評価の指標

• CPU 使用率 – CPUが実際にプロセスを処理している割合 • スループット – ある時間内にいくつのプロセスを処理できるかの 能力 • ターンアラウンドタイム – あるプロセスを投入してから終了するまでの時間 • 待ち時間 – 実行可能待ち行列(ready queue)にどのくらいの時間 プロセスが滞在していたか • 応答時間 – 要求を出してから最初の応答が戻ってくるまでの 時間 – Time-sharing環境や実時間処理において必要とされ る尺度 最大のCPU使用率 最大のスループット 最小のターンアラウンドタイム 最小の待ち時間 最小の応答時間

補足

• CPU利用率 (CPU utilization)

– CPUの動作時間／システム稼働時間 • CPUの動作時間＝システム稼働時間－アイドル時間 – OSによるオーバヘッドも込 – 利用率が高い方が良 • 逐次実行： 10/20 = 50.0% • 並行実行： 10/11 = 90.9%

• 待ち時間

– プロセス完了までに実行可能キューで待つ時間の合計 • 逐次実行： (0+10)/2 = 5 sec (プロセス当たり平均） • 並行実行： (0+1)/2 = 0.5 sec (プロセス当たり平均） – ここでは、待ち→実行可能からすぐに実行状態に移ったと仮定

補足

• スループット（throughput）

– CPUが単位時間当たりに行う仕事量(完了するプロセス数) – バッチ処理の登場で，スループットが向上 (vs. OSなし) • 逐次処理： 2プロセス/20 sec = 0.100 • 並行処理： 2プロセス/11 sec = 0.181

• ターンアラウンド時間（turnaround time）

– プロセスの実行を要求してから完了するまで (含 待ち時間) • 逐次処理： (10+20)/2 = 15 sec. (平均) • 並行処理： (10+11)/2 = 10.5 sec. (平均) – 同時に要求されたと仮定

補足

• 応答時間（response time）

– プロセスの実行要求から最初の応答までの時間 • TSSや対話型システム – ユーザがシステムに何らかの指示を出してから最初の応答 が返るまでの時間 » × 処理が完了するまでの時間 • バッチ処理システム – ターンアラウンド時間とほぼ同等の基準 • 逐次処理： (0+10)/2 = 5 • 並行処理： (0+1)/2 = 0.5

古典的スケジューリングアルゴリズム

• FCFS

• SJF

• Priority Scheduling

First-Come, First-Served (FCFS) Scheduling

• 仮定

– プロセスがP1, P2, P3の順番に到着

• 待ち時間

– P1 = 0; P2 = 24; P3 = 27

• 平均待ち時間

– (0 + 24 + 27)/3 = 17

P₁ P₂ P₃ 24 27 30 0

Process

Burst Time

P1

24

P2

3

P3

3

First-Come, First-Served (FCFS) Scheduling

• 仮定

– プロセスがP2, P3, P1の順番に

到着

• 待ち時間

– P1 = 6; P2 = 0; P3 = 3

• 平均待ち時間

– (6 + 0 + 3)/3 = 3

• 短いプロセスを先に実行すると平

均待ち時間が短縮

Process

Burst Time

P1

24

P2

3

P3

3

P₁ P₃ P₂

補足

• FCFS: Fist Come First Service（到着順）

• 最初に実行可能キューに到着したプロセスから

CPUを割当て

– 実行可能キューをFIFO (First In First Out)キューとして実現

プロセス (PCB) プロセス (PCB) プロセス (PCB)

...

CPU 実行可能キュー キューの末尾 キューの先頭 到着 終了

補足

処理時間 （到着順序） ターンアラウンド時間 _{平均ターンアラ} ウンド時間 A B C 0～10:A 10～15:B 15～35:C 10 15 35 20 0～10:A 10～30:C 30～35:B 10 35 30 25 0～5:B 5～15:A 15～35:C 15 5 35 18 0～5:B 5～25:C 25～35:A 35 5 25 22 0～20:C 20～30:A 30～35:B 30 35 20 28 0～20:C 20～25:B 25～35:A 35 25 20 27

• 3つのプロセス

A:10, B:5, C:20 が時

刻０に到着

– ＜プロセス名:

処理時間＞と

表記

• 処理の長いプロセ

スが先に到着した

場合に問題

Shortest-Job-First (SJF) Scheduling

• 各プロセスはCPU burst処理する時間を保持

– プロセスが実行を始めてI/O waitあるいは終了するまでの時間

• 一番短いCPU burst時間を持つプロセスに実行権を付与

• 2タイプ

– Nonpreemptive • CPUを与えたらCPU burst時間を使い切るまでCPUの横取りなし – Preemptive • もし、新しいプロセスが到着し、そのCPU burst時間が現在実行しているプロセ スの残りのCPU burst時間よりも短ければ、CPUを横取りして新しいプロセスに 実行権を付与 – Shortest-Remaining-Time-First (SRTF)と呼ばれている

• 決められてプロセス群の最小平均待ち時間を達成するには、SJF

が最適

• 仮定

• 平均待ち時間

– (0 + 6 + 3 + 7)/4 ＝4

Non-Preemptive SJFの例

P₁ P₃ P₂ P₄

Process

Arrival Time

Burst Time

P1

0.0

7

P2

2.0

4

P3

4.0

1

P4

5.0

4

Preemptive SJFの例

• 仮定

• 平均待ち時間

– (9 + 1 + 0 +2)/4 ＝3

• 平均ターンアラウンド時間

– (16+5+1+6)/4 ＝ 7

P₁ P₂ P₃ 4 2 11 0 P₄ 5 7 P₂ P₁ 16

Process

Arrival

Time

Burst

Time

P1

0.0

7

P2

2.0

4

P3

4.0

1

P4

5.0

4

補足

• SJF: Shortest Job First（最短時間順）

• 最も短い処理時間のプロセスから順にCPU

• 各プロセスの処理時間

– 通常、予め知ることはできない – 厳密には実現困難

補足

プロセス 到着時間 処理時間 A 0 7 B 2 4 C 5 3 D 8 6 平均ターンアラウンド時間 {7+(14-2)+(10-5)+(20-8)}/4 = 9 A B C D 7-0 14-2 10-5 20-8 A B C D 平均ターンアラウンド時間 {14+(6-2)+(9-5)+(20-8)}/4 = 8.5 14-0 6-2 9-5 20-8 横取りありの場合

次のCPU Burst時間をどうやって予測するか？

• 直前の実際のCPU burst時間から、指数平均(exponential

average)を使って推測

:

Define

4.

1

0

,

3.

burst

CPU

next

the

for

value

predicted

2.

burst

CPU

of

lenght

actual

1.

















_{n 1} th n

n

t



1



.

1

n

n

n



t







_







指数平均

•



を限りなく０に近づけると

–



_n+1

=



_n

– 過去の予測を重視

•



を限りなく１に近づけると

–



_n+1

= t

_n

– 直前の実際のCPU Burst時間を重視

• 式を展開してみると、、、



_n+1

=



t

_n

+(1 -



)



t

_n-1

+

…

+(1 -



)

j



t

_n-j

+

…

+(1 -



)

n-1

_t

n



0

•



も(1 -



) も1以下なので，t

_n

に対する重みはt

_n-1

に対するもの以上



1



.

1 n n n



t







_







次のCPU Burst時間の予測





.

t

_{n n} n









_1





1



α＝1/2、t0＝10の場合

Priority Scheduling

• 各プロセスに優先番号（integer）を付与

– 小さい値＝高い優先順位

• 高いプライオリティを持つプロセスにCPUを割当て

– Preemptive

– Non-preemptive

• SJFはPriority Schedulingの一種

– プライオリティは次の予測CPU burst時間

• 問題

– 飢餓(Starvation)

• 低いプロセスはいつまでたっても実行されない

• 解決法

– エージング(Aging )

• プロセスを実行するごとに優先番号を増

Round Robin (RR)

• 各プロセスにCPU時間単位(time quantum)を割り当て

– 10 milliseconds

–

200 milliseconds

• プロセスがtime quantum時間CPUを使用すると処理が中

断され、ready queueの最後に移動

• Ready queueの先頭からプロセスを取り出し、そのプロ

セスにCPU資源を割り当て

RR(time quantum=20)の例

• 一般にSJFに比べて平均ターンアラウンド時

間が大きくなるが、応答性能は良

P₁ P₂ P₃ P₄ P₁ P₃ P₄ P₁ P₃ P₃ 0 20 37 57 77 97 117 121 134 154 162

Process

Burst Time

P1

53

P2

17

P3

68

P4

24

RRの性質

• もし、nプロセスがready queueにあり、time

quantumがqならば、

– 各プロセスはCPU時間の1/nを得ることができ、さら

に一回実行権を得る毎にq時間のCPU時間を獲得

– 全プロセスは(n-1)q時間以上待たされることがない

RRの性質

• qが十分に大きいと、FCFSとなる

• qの大きさを小さくすると、、、

– コンテキストスイッチにかかるオーバヘッドが増大

• 例えば、コンテキストスイッチにかかる時間が1 msecとし、qを1 msec とするとどうなる？

RRの性質

• 平均ターンアラウンド時間は、time quantumの値に依存

• 一般的に、1回のtime quantumでほとんどのプロセスの実行が終

了できる値に設定すると平均ターンアラウンド時間は短縮

補足

• Round Robin: TSS の基本的なスケジューリング方式

• 一定時間だけ CPU を割り当て

– タイムスライス／タイムクオンタム – 割り当て時間を過ぎると • 他のプロセスに CPU を切り替え • CPU の横取り

• 実行可能キューは FIFO

プロセス (PCB) ... CPU 実行可能キュー キューの末尾 キューの先頭 到着 _プロセス 終了 (PCB) プロセス (PCB) 横取り (タイムスライスの満了)

補足

プロセス 処理時間 A 10 B 5 C 20 平均ターンアラウンド時間 {23+17+35}/3 = 25 A B C 23 17 A, B, C の順に到着 時刻0から一斉にスケジューリング タイムスライス＝4とする

Multilevel Queue

• 実行可能キュー(Ready queue)をプロセス の性質に応じていくつかのキューに分割 例） foreground (interactive) background (batch) • キュー毎に独自のスケジューリングアル ゴリズムを持たす foreground – RR background – FCFS • キュー間でのスケジューリング

– Fixed priority scheduling; (foregroundを 処理したのちbackgroundなど) • 飢餓の可能性あり – Time slice ： それぞれのキューに適切 なCPU時間を割り当て（PRの foregroundに80％，残りのFCFSの backgroundに20％など）

補足

プロセスはキュー間で 移動しない プロセス (PCB) ... CPU 割当て ラウンドロビンスケジューリング実行可能キュー キューの末尾 キューの先頭 終了 プロセス (PCB) プロセス (PCB) 横取り (タイムスライスの満了) プロセス (PCB) ... CPU 割当て FCFSスケジューリング実行可能キュー キューの末尾 キューの先頭 終了 プロセス (PCB) プロセス (PCB) プロセス (PCB) ... CPU 割当て 優先度スケジューリング実行可能キュー キューの末尾 キューの先頭 終了 プロセス (PCB) プロセス (PCB) 優先度・タイムスライス などで振り分け キュー間のスケジ ューリングが必要 ラウンドロビンや 優先度等

Multilevel Feedback Queueの例

• 待ち行列:

– Q₀ – time quantum 8 msec – Q₁ – time quantum 16 msec – Q₂ – FCFS

• スケジューリング

– A new job enters queue Q₀ which is served FCFS. When it gains CPU, job receives 8 milliseconds. If it does not finish in 8 milliseconds, job is moved to queue Q₁.

– At Q₁ job is again served FCFS and receives 16 additional milliseconds. If it still does not complete, it is

Multilevel Feedback Queueの例

• 待ち行列:

– Q₀ – time quantum 8 msec – Q₁ – time quantum 16 msec – Q₂ – FCFS • スケジューリング – Q₀ に投入されたジョブはFCFSで8 milliseconds間処理 – その後 まだ終了していない場合Q₁に 移動 – Q₁ でFCFSで16 milliseconds間処理 – まだ終了していない場合Q₂に移動

Multilevel Feedback Queue一般論

• プロセスを様々な待ち行列に移動

– 実行時間に応じて待ち行列を変更

• Multilevel-feedback-queue schedulerの設定

– 待ち行列の数

– 各待ち行列のスケジューリングアルゴリズム

– プロセスを低いレベルの待ち行列に移す条件

– プロセスを高いレベルの待ち行列に移す条件

– プロセスがサービスを必要としたときにどのレベルの待ち行

列に入れるかを決めるメソッド

補足

プロセスをキュ ー間で移動 プロセス (PCB) ... CPU 割当て 優先度 n 実行可能キュー キューの末尾 キューの先頭 終了 プロセス (PCB) プロセス (PCB) プロセス (PCB) ... CPU 割当て 優先度 n-1 実行可能キュー キューの末尾 キューの先頭 終了 プロセス (PCB) プロセス (PCB) プロセス (PCB) ... CPU 割当て 優先度1 実行可能キュー キューの末尾 キューの先頭 終了 プロセス (PCB) プロセス (PCB) 優先度・タイムスライス などで振り分け 多くの場合、各キューはラウンドロビン (他のアルゴリズムとの複合も可能)

補足

• 多重レベルフィードバックの効果

– 入出力バウンドなプロセスはCPU処理時間が短い傾向

• 優先度が下がらず対話型プロセスの応答性が向上

– CPUバウンドなプロセスの優先度が低

• 入出力待ち等の時間は割り当てられる

➡CPU処理と入出力処理のオーバラップ

• CPU利用率／スループットの向上 • 時間がかかる入出力は早目に要求し，待つ間に他の仕事

– 何にバウンドするかは前もってわからない

• CPU利用情報を記録しそれを基に判断

補足

• 多重レベルフィードバックの効果（続き）

– 同優先度プロセスが複数ある場合でも，ラウン

ドロビンにより応答性を確保

– 無限の延期も回避される

• アルゴリズムの工夫

– 入出力バウンドなプロセスの優先度を向上

– 他のスケジューリングアルゴリズムと混在

• 最も一般的なスケジューリングアルゴリズム

– UNIX等