Operating System Lecture No.4
Menu
CPU Scheduling
たくさんあるプロセスの内容を表すデータ構造は、メモリやディスクに格納されている。Linux の場合は、 include/linux/sched.h などに格納されている。fs/file.c で file descriptor を参照する時に current というのが参照されている
arch/x86/include/asm/current.hここで task_struct を返すのがわかる。
この構造体が、一つあるいは複数の実際のCPUや実メモリに割り当てられている。 割り当ては、 CPUの持つ割り込みの仕組みを使って実現されている。
CPUの動作を決めているレジスタやPC(プログラムカウンタ)を、メモリに格納して、システムメモリ上の割り込み処理ルーチンを実行する。つまり、メモリをシステムメモリに切替えて、PCを割り込みベクタの表に記述されているアドレスに設定する。(先週探したソースに記述されている部分)
アクティブなプロセスが複数ある場合は、それを入れ換えながら実行する。プロセスが自発的に入れ換えるかどうかによって二種類のスケジューリングがある。
- non-preemptive プロセスがOSのAPIを呼び出して自発的に入れ換える
- preemptive タイマや割り込み等により自動的に入れ替わる
プロセスは定期的にイベントをチェックする。(Poling) 割り込まれない。
プロセスはイベントが起こると追い出される。
最近では割り込みのオーバヘッドは大きいし、同期は、結局、元のプロセスがあるタイミングに来るまで待つ必要がある(lockとか)ので、Poling の方が効率が良い。デバイス側で割り込みをキューにいれて待っているような方法もある。
CPU-I/O Burst cycle
- CPU burst
- I/O burst
- Buffering
アプリケーションによって、CPU を食うもの(CPU bound)と、I/Oを食うもの(I/O bound)がある。MPEG等では、両方を定期的(periodical)に使う。さらに、ユーザの入力に反応する(Interactive)なものがある。
- CPU bound ひたすら計算する
- I/O bound メモリの転送を多く(throughput)要求する
- Interactive 素早い応答(response)を要求する
Gantt Chart
CPUの割当ての様子はGantt Chartという一種の棒グラフを使うと良い。
スケジューリングの基準
- CPU utilizatoin
- Throughput
- Turnaround time
- Waiting time
- Reponse time
Scheduling Algorithm
- First-Come, First Served
きたものから順に処理する
- Shortest-Job-First
一番早く終わるものから処理する
- Priority Scheduing
順番を決めておく
- Round-Robin Scheduling
Quantum の時間で一旦中断し、公平に処理する
- Multilevel Queue Scheduling
Priorityをより一般的にする
- Multilevel Feedback Queue Scheduling
Priorityを可変にする
依存性がある場合は、PART 図などが用いられることが多い。プロジェクトマネジメントなどで使われる。
Real-time Scheduling Algorithm
どれくらいの時間の間隔で、どれくらいの時間を使うのか?
m 個のperiodic イベントのうち、イベント i がP i 秒間に C i 秒間のCPU時間を使うとする。
m
Σ Ci/Pi < 1
i=1
であれば、スケジューリングできる。
- Deterministic model
- Queueing models
- Dead line scheduling
- Rate monotinic scheduling
頻度(Rate)の高いプロセスの実行時間が来たら、今実行しているプロセスを preempt して、高い方を実行する。CPUに余裕があれば確実にスケジューリング出来る。
ただし、non periodic task には対処できない。
Lock などがある場合
Real-time programming で資源管理が必要な場合、資源を握っているプロセスは、資源を要求するプロセスと同じ優先順位を持つ必要がある。(prioirity inheritance)I/O bound なプロセスの優先順位を下げると全体のパフォーマンスが下がってしまう。
問題4.1 シミューレータ
プロセスシミュレータ Rustプロセスシミュレータ Golang
問題4.2-4.3教科書の問題
割り当てられた教科書の問題を解け。
Subject: Lecture on Operating System Lecture Exercise 4.2 Subject: Lecture on Operating System Lecture Exercise 4.3として、2つ個別のメールで出して下さい。
レポートを、まだ一つも出してない人には割り当てられません。
英語の問題を英語で書き写して、その後に解答すること。(問題の訳は必要ありません)
解答は日本語とします。
ChatGPTで自己採点(400文字以内)してから提出すること
ChatGPTの自己採点もレポート含めること
Web 上から写したものを見付けた場合は失格としてます。