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

Transcription

1 1.PFLab( 加藤研 ) のウェブサイトからダウンロードできます 2. 紙資料も配布します オペレーティングシステム 加藤真平東京大学大学院情報理工学系研究科 shinpei@is.s.u-tokyo.ac.jp 2018/5/14 第 5 回オペレーティングシステム 1

2 講義概要 受講生に求める基礎知識 C 言語の理解 コンピュータアーキテクチャの基礎の理解 メモリ管理 割り込み CPUモード 参考図書 Silberschatz, Galvin, and Gagne, Operating System Concepts 8th Edition, Wiley 成績 試験の点数で決定 試験は持ち込み不可 授業に出席していた人で試験の結果が悪い人は追試験あり 出席をとるが出席点はなし 2018/5/14 第 5 回オペレーティングシステム 2

3 講義スケジュール ( 予定 ) 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 2018/5/14 第 5 回オペレーティングシステム 3

4 CPU Scheduling 基本概念 スケジューリングの尺度 古典的スケジューリングアルゴリズム 2017/5/8 第 5 回オペレーティングシステム 4

5 基本概念 マルチプログラミングで得られる最大限の CPU 使用率を上げること マルチプログラミング 1 台のコンピュータで同時に複数のプログラムを実行すること CPU と I/O 処理のサイクル プロセスは CPU による処理と I/O 待ちをしているという 2 つのサイクルで成立 2017/5/8 第 5 回オペレーティングシステム 5

6 CPU スケジューラ 実行可能状態のプロセスのなかからプロセスをひとつ選び CPU による実行を許可 どのように選ぶかが問題であり この話が本日と来週の講義の主テーマ CPU スケジューラが呼び出されるタイミング 1. プロセス状態が変わるとき Run wait, wait ready, run terminate 2. タイマー割り込み 3. I/O 割り込み Nonpreemptive スケジューリング 上記 1 のタイミングでしかスケジューリングしない場合 すなわちプロセス自ら CPU 使用を放棄しない限りスケジューラが起動されない 横取りされない Preemptive( 横取り ) スケジューリング プロセス実行中にスケジューラが起動され 実行中のプロセスから他のプロセスに実行権が移動 2017/5/8 第 5 回オペレーティングシステム 6

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

8 スケジューリング評価の指標 CPU 使用率最大のCPU 使用率 CPUが実際にプロセスを処理している割合 スループット最大のスループット ある時間内にいくつのプロセスを処理できるかの能力最小のターンアラウンドタイム ターンアラウンドタイム あるプロセスを投入してから終了するまでの時間 待ち時間最小の待ち時間 実行可能待ち行列 (ready queue) にどのくらいの時間プロセスが滞在していたか 応答時間最小の応答時間 要求を出してから最初の応答が戻ってくるまでの時間 Time-sharing 環境や実時間処理において必要とされる尺度 TS 環境においてはターンアラウンドタイムは重要ではない 2017/5/8 第 5 回オペレーティングシステム 8

9 補足 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 ( プロセス当たり平均 ) ここでは 待ち 実行可能からすぐに実行状態に移ったと仮定 2017/5/8 第 5 回オペレーティングシステム 9

10 補足 スループット (throughput) CPU が単位時間当たりに行う仕事量 ( 完了するプロセス数 ) バッチ処理の登場で, スループットが向上 (vs. OS なし ) 逐次処理 : 2 プロセス /20 sec = 並行処理 : 2 プロセス /11 sec = ターンアラウンド時間 (turnaround time) プロセスの実行を要求してから完了するまで ( 含待ち時間 ) 逐次処理 : (10+20)/2 = 15 sec. ( 平均 ) 並行処理 : (10+11)/2 = 10.5 sec. ( 平均 ) 同時に要求されたと仮定 2017/5/8 第 5 回オペレーティングシステム 10

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

12 古典的スケジューリングアルゴリズム FCFS SJF Priority Scheduling Round Robin Scheduling 2017/5/8 第 5 回オペレーティングシステム 12

13 First-Come, First-Served (FCFS) Scheduling 仮定 プロセスが P1, P2, P3 の順番に到着 待ち時間 P1 = 0; P2 = 24; P3 = 27 平均待ち時間 ( )/3 = 17 Process P1 24 P2 3 P3 3 Burst Time P 1 P 2 P /5/8 第 5 回オペレーティングシステム 13

14 First-Come, First-Served (FCFS) Scheduling 仮定 プロセスが P2, P3, P1 の順番に到着 待ち時間 P1 = 6; P2 = 0; P3 = 3 平均待ち時間 ( )/3 = 3 短いプロセスを先に実行すると平均待ち時間が短縮 Process Burst Time P1 24 P2 3 P3 3 P 2 P 3 P /5/8 第 5 回オペレーティングシステム 14

15 補足 FCFS: Fist Come First Service( 到着順 ) 最初に実行可能キューに到着したプロセスから CPU を割当て 実行可能キューを FIFO (First In First Out) キューとして実現 実行可能キュー 到着 プロセス (PCB)... プロセスプロセス CPU (PCB) (PCB) 終了 キューの末尾 キューの先頭 2017/5/8 第 5 回オペレーティングシステム 15

16 補足 処理時間 ( 到着順序 ) ターンアラウンド時間 A B C 平均ターンアラウンド時間 0~10:A 10~15:B 15~35:C ~10:A 10~30:C 30~35:B ~5:B 5~15:A 15~35:C ~5:B 5~25:C 25~35:A ~20:C 20~30:A 30~35:B ~20:C 20~25:B 25~35:A つのプロセス A:10, B:5, C:20 が時刻 0 に到着 < プロセス名 : 処理時間 > と表記 処理の長いプロセスが先に到着した場合に問題 2017/5/8 第 5 回オペレーティングシステム 16

17 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 が最適 2017/5/8 第 5 回オペレーティングシステム 17

18 Non-Preemptive SJF の例 仮定 Process Arrival Time Burst Time 平均待ち時間 ( )/4 =4 P P P P P 1 P 3 P 2 P /5/8 第 5 回オペレーティングシステム 18

19 Preemptive SJF の例 仮定 Process Arrival Time Burst Time 平均待ち時間 ( )/4 =3 平均ターンアラウンド時間 ( )/4 = 7 P P P P P 1 P 2 P 3 P 2 P 4 P /5/8 第 5 回オペレーティングシステム 19

20 補足 SJF: Shortest Job First( 最短時間順 ) 最も短い処理時間のプロセスから順にCPU 各プロセスの処理時間 通常 予め知ることはできない 厳密には実現困難 2017/5/8 第 5 回オペレーティングシステム 20

21 補足 プロセス到着時間処理時間 A 0 7 B 2 4 C 5 3 D 8 6 A B C D 横取りありの場合 A B C D 平均ターンアラウンド時間 {14+(6-2)+(9-5)+(20-8)}/4 = 8.5 平均ターンアラウンド時間 {7+(14-2)+(10-5)+(20-8)}/4 = /5/8 第 5 回オペレーティングシステム 21

22 次の CPU Burst 時間をどうやって予測するか? 直前の実際の CPU burst 時間から 指数平均 (exponential average) を使って推測 t n actual lenght of n n 1, 0 1 Define : th predicted value for CPU burst the next 1. t n 1 n n CPU burst 直前の実測値と過去の予測値とを重み付け 2017/5/8 第 5 回オペレーティングシステム 22

23 指数平均 1. n t 1 n n を限りなく 0 に近づけると n+1 = n 過去の予測を重視 を限りなく 1 に近づけると 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 に対するもの以上 2017/5/8 第 5 回オペレーティングシステム 23

24 t n 1 n 1 次の CPU Burst 時間の予測. n α=1/2 t0=10 の場合 2017/5/8 第 5 回オペレーティングシステム 24

25 Priority Scheduling 各プロセスに優先番号 (integer) を付与 小さい値 = 高い優先順位 高いプライオリティを持つプロセスに CPU を割当て Preemptive Non-preemptive SJF は Priority Scheduling の一種 プライオリティは次の予測 CPU burst 時間 問題 飢餓 (Starvation) 低いプロセスはいつまでたっても実行されない 解決法 エージング (Aging ) プロセスを実行するごとに優先番号を増 2017/5/8 第 5 回オペレーティングシステム 25

26 Round Robin (RR) 各プロセスに CPU 時間単位 (time quantum) を割り当て 10 milliseconds 200 milliseconds プロセスが time quantum 時間 CPU を使用すると処理が中断され ready queue の最後に移動 Ready queue の先頭からプロセスを取り出し そのプロセスに CPU 資源を割り当て 2017/5/8 第 5 回オペレーティングシステム 26

27 RR(time quantum=20) の例 Process Burst Time P1 53 P2 17 P3 68 P4 24 P 1 P 2 P 3 P 4 P 1 P 3 P 4 P 1 P 3 P 一般に SJF に比べて平均ターンアラウンド時間が大きくなるが 応答性能は良 2017/5/8 第 5 回オペレーティングシステム 27

28 RR の性質 もし n プロセスが ready queue にあり time quantum が q ならば 各プロセスは CPU 時間の 1/n を得ることができ さらに一回実行権を得る毎に q 時間の CPU 時間を獲得 全プロセスは (n-1)q 時間以上待たされることがない 2017/5/8 第 5 回オペレーティングシステム 28

29 RR の性質 q が十分に大きいと FCFS となる q の大きさを小さくすると コンテキストスイッチにかかるオーバヘッドが増大 例えば コンテキストスイッチにかかる時間が 1 msec とし q を 1 msec とするとどうなる? 2017/5/8 第 5 回オペレーティングシステム 29

30 RR の性質 平均ターンアラウンド時間は time quantum の値に依存 一般的に 1 回の time quantum でほとんどのプロセスの実行が終了できる値に設定すると平均ターンアラウンド時間は短縮 2017/5/8 第 5 回オペレーティングシステム 30

31 補足 Round Robin: TSS の基本的なスケジューリング方式 一定時間だけ CPU を割り当て タイムスライス / タイムクオンタム 割り当て時間を過ぎると 他のプロセスに CPU を切り替え CPU の横取り 実行可能キューは FIFO 実行可能キュー 到着 プロセス... プロセスプロセス CPU (PCB) (PCB) (PCB) キューの末尾キューの先頭 終了 横取り ( タイムスライスの満了 ) 2017/5/8 第 5 回オペレーティングシステム 31

32 補足 プロセス 処理時間 A 10 平均ターンアラウンド時間 { }/3 = 25 B 5 C 20 A, B, C の順に到着時刻 0 から一斉にスケジューリングタイムスライス =4 とする A B C /5/8 第 5 回オペレーティングシステム 32

33 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% など ) 2017/5/8 第 5 回オペレーティングシステム 33

34 補足 優先度 タイムスライスなどで振り分け 優先度スケジューリング実行可能キュー プロセス (PCB) キューの末尾 プロセス (PCB) キューの末尾... プロセス CPU 割当て (PCB) FCFS スケジューリング実行可能キュー... プロセス CPU 割当て (PCB) プロセス (PCB) キューの先頭 プロセス (PCB) キューの先頭 終了 プロセスはキュー間で移動しない 終了 キュー間のスケジューリングが必要 ラウンドロビンや優先度等 ラウンドロビンスケジューリング実行可能キュー プロセス (PCB) キューの末尾... プロセス CPU 割当て (PCB) プロセス (PCB) キューの先頭 横取り ( タイムスライスの満了 ) 終了 2017/5/8 第 5 回オペレーティングシステム 34

35 Multilevel Feedback Queue の例 待ち行列 : Q 0 time quantum 8 msec Q 1 time quantum 16 msec Q 2 FCFS スケジューリング A new job enters queue Q 0 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 1. At Q 1 job is again served FCFS and receives 16 additional milliseconds. If it still does not complete, it is preempted and moved to queue Q /5/8 第 5 回オペレーティングシステム 35

36 Multilevel Feedback Queue の例 待ち行列 : Q 0 time quantum 8 msec Q 1 time quantum 16 msec Q 2 FCFS スケジューリング Q 0 に投入されたジョブは FCFS で 8 milliseconds 間処理 その後まだ終了していない場合 Q 1 に移動 Q 1 で FCFS で 16 milliseconds 間処理 まだ終了していない場合 Q 2 に移動 2017/5/8 第 5 回オペレーティングシステム 36

37 Multilevel Feedback Queue 一般論 プロセスを様々な待ち行列に移動 実行時間に応じて待ち行列を変更 Multilevel-feedback-queue scheduler の設定 待ち行列の数 各待ち行列のスケジューリングアルゴリズム プロセスを低いレベルの待ち行列に移す条件 プロセスを高いレベルの待ち行列に移す条件 プロセスがサービスを必要としたときにどのレベルの待ち行列に入れるかを決めるメソッド 2017/5/8 第 5 回オペレーティングシステム 37

38 補足 優先度 タイムスライスなどで振り分け プロセス (PCB) キューの末尾 優先度 1 実行可能キュー... プロセス CPU 割当て (PCB) プロセス (PCB) キューの先頭 終了 プロセス (PCB) キューの末尾 プロセス (PCB) キューの末尾 優先度 n-1 実行可能キュー... プロセス CPU 割当て (PCB) 優先度 n 実行可能キュー... プロセス CPU 割当て (PCB) プロセス (PCB) キューの先頭 プロセス (PCB) キューの先頭 終了 プロセスをキュー間で移動 終了 多くの場合 各キューはラウンドロビン ( 他のアルゴリズムとの複合も可能 ) タイムスライスを過ぎたら少し低い優先度のキューへ 待ちが長くなったら少し高い優先度のキューへ 2017/5/8 第 5 回オペレーティングシステム 38

39 補足 多重レベルフィードバックの効果 入出力バウンドなプロセスは CPU 処理時間が短い傾向 優先度が下がらず対話型プロセスの応答性が向上 CPU バウンドなプロセスの優先度が低 入出力待ち等の時間は割り当てられる CPU 処理と入出力処理のオーバラップ CPU 利用率 / スループットの向上 時間がかかる入出力は早目に要求し, 待つ間に他の仕事 何にバウンドするかは前もってわからない CPU 利用情報を記録しそれを基に判断 2017/5/8 第 5 回オペレーティングシステム 39

40 補足 多重レベルフィードバックの効果 ( 続き ) 同優先度プロセスが複数ある場合でも, ラウンドロビンにより応答性を確保 無限の延期も回避される アルゴリズムの工夫 入出力バウンドなプロセスの優先度を向上 他のスケジューリングアルゴリズムと混在 最も一般的なスケジューリングアルゴリズム UNIX 等 2017/5/8 第 5 回オペレーティングシステム 40