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を割り込みベクタの表に記述されているアドレスに設定する。(先週探したソースに記述されている部分)

アクティブなプロセスが複数ある場合は、それを入れ換えながら実行する。プロセスが自発的に入れ換えるかどうかによって二種類のスケジューリングがある。

プロセスは定期的にイベントをチェックする。(Poling) 割り込まれない。

プロセスはイベントが起こると追い出される。

最近では割り込みのオーバヘッドは大きいし、同期は、結局、元のプロセスがあるタイミングに来るまで待つ必要がある(lockとか)ので、Poling の方が効率が良い。デバイス側で割り込みをキューにいれて待っているような方法もある。


CPU-I/O Burst cycle

ファイルシステムの所で学んだように、バッファリングを使うと、プロセスの状態は、CPUを使って計算している部分(CPU burst)、OSのAPIを呼び出してユーザメモリ上のデータと外部機器(I/O)や他のプロセスにデータを転送している部分(I/O burst)の二種類に分かれる。後者は、DMAを使うとCPUを占有せずに処理されるが、バスの容量は食ってしまう。

アプリケーションによって、CPU を食うもの(CPU bound)と、I/Oを食うもの(I/O bound)がある。MPEG等では、両方を定期的(periodical)に使う。さらに、ユーザの入力に反応する(Interactive)なものがある。


Gantt Chart

CPUの割当ての様子はGantt Chartという一種の棒グラフを使うと良い。


スケジューリングの基準


Scheduling Algorithm

依存性がある場合は、PART 図などが用いられることが多い。プロジェクトマネジメントなどで使われる。


Real-time Scheduling Algorithm

どれくらいの時間の間隔で、どれくらいの時間を使うのか?

m 個のperiodic イベントのうち、イベント i がP i 秒間に C i 秒間のCPU時間を使うとする。


m
Σ Ci/Pi < 1
i=1

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

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

頻度(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 上から写したものを見付けた場合は失格としてます。


Shinji KONO / Fri Dec 22 13:04:14 2023