Operating System Lecture No.4

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 burst)、OSのAPIを呼び出してユーザメモリ上のデータと外部機器(I/O)や他のプロセスにデータを転送している部分(I/O burst)の二種類に分かれる。後者は、DMAを使うとCPUを占有せずに処理されるが、バスの容量は食ってしまう。

アプリケーションによって、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
Σ C_i/P_i < 1
i=1

であれば、スケジューリングできる。

Deterministic model
Queueing models

前もって予測できるのか? Predictivity 予測できないのか? Emergent

Dead line scheduling
Rate monotinic scheduling

頻度(Rate)の高いプロセスの実行時間が来たら、今実行しているプロセスを preempt して、高い方を実行する。CPUに余裕があれば確実にスケジューリング出来る。

ただし、non periodic task には対処できない。

    Subject: Lecture on Operating System Lecture Exercise 4.2
    Subject: Lecture on Operating System Lecture Exercise 4.3
    Subject: Lecture on Operating System Lecture Exercise 4.4
    Subject: Lecture on Operating System Lecture Exercise 4.5

として、2つ個別のメールで出して下さい。

レポートを、まだ一つも出してない人には割り当てられません。

英語の問題を英語で書き写して、その後に解答すること。(問題の訳は必要ありません)

解答は日本語とします。

ChatGPTで自己採点(400文字以内)してから提出すること

ChatGPTの自己採点もレポート含めること

Web 上から写したものを見付けた場合は失格としてます。