# Chapter 4 (Process Scheduling) / The Linux Scheduling Algorithm

## Scheduler Classes
- Linuxのスケジューラは異なる種類のプロセスに対して異なるアルゴリズムを用いてスケジューリングすることが出来るようになっている
- この構造を scheduler classes という
    - 各scheduler classは優先度を持っている
    - 実行可能状態のプロセスが存在するようなscheduler classのうち、最も優先度の大きいものが採用される
    - そのscheduler classが次に実行するプロセスを決定する
- CFSは`kernel/sched_fair.c`に実装されていて、Linuxの`SCHED_NORMAL`とPOSIXの`SCHED_OTHER`に登録されている

## Process Scheduling in Unix Systems
- Unixのスケジューラはナイス値を優先度として使う
- これはシンプルに見えるが、いくつかの病的な問題を引き起こす

### 1. 各nice値にどれくらいのtimesliceを割り当てるかを決める必要がある
- 割り当ての決め方によって、スケジューラとして好ましくない挙動になりうる
- 具体例1
    - プロセスA(nice:0)とプロセスB(nice:+20)を考える
    - nice値0に対応するtimesliceを100msとして、nice値+20に対応するtimesliceを5msとする
    - するとプロセスAは20/21、プロセスBは1/21の時間が割り当てられる
    - nice値にいくらのtimesliceを割り当てるのが最適なのかを考える必要が出てきてしまう
- 具体例2
    - プロセスA(nice:+20)とプロセスB(nice:+20)
    - 5ms毎にコンテキストスイッチが起こり、非効率的
- 具体例3
    - プロセスA(nice:0)とプロセスB(nice:0)
    - 切り替えまで100msかかってしまう
- たとえCPUをたくさん使うタスクであったとしてもnice値が大きいプロセスはバックグラウンドに行きがちだし、nice値が小さいプロセスはフォアグラウンドにいきやすくなる
- これは理想からは大きく離れている

### 2. nice値の差に対応するtimesliceの差が、nice値の絶対値によって変わってしまう
- 本来nice値は普通は相対的な値として扱われるもの
- nice値の絶対値によって、nice値の一定の差に対応するtimesliceの差が変わるのは好ましくない
- 具体例
- 以下のようにtimesliceを割り当てたとする
    - nice値0: 100ms
    - nice値1: 95ms
    - nice値18: 10ms
    - nice値19: 5ms
- nice値0と1の間の差は0.95倍であり、理想に近い
- nice値18と19の間の差は0.5倍であり差が大きい

### 3. カーネルが測れる単位である必要がある
- nice値にtimesliceを割り当てるときに、カーネルが計測可能な時間である必要がある
- timesliceは多くのOSではタイマーの1単位の整数倍になる
- これはいくつかの問題を引きおこす
    1. 最小のtimesliceがタイマーの精度によって制限される
    2. timesliceの差がタイマーの精度によって制限される
    3. timesliceの絶対的な長さがタイマーの1単位の長さによって変わる

### 4. インタラクティブ性能を向上するためにプロセスの起動をどのように扱うか
- 新しく起動したタスクはすぐ動き初めて欲しいので優先度を高くしたい
- インタラクティブ性能を向上させる
- 一方で、残りのタスクを犠牲にして1つのプロセスに多くの処理時間を与えることになりうる

---

- CFSはこれらの問題の多くを解決出来る
    - timesliceの代わりに、CPUの割合を割り当てる
    - スイッチングレートが変わる代わりに、CFSは一定の公平性を保つことが出来る

## Fair Scheduling
- 理想的で完全なマルチスレッディングを考える
    - 時間を無限小に区切ってN個のプロセスに割り当てる
    - ある(時間の)区間においてN個のプロセス全てが実行されている状態
    - 各プロセスが1/NのCPUパワーで同時に実行されるイメージ
- もちろんこれをそのまま実現するのは非効率的である
    - コンテキストスイッチのコスト
    - キャッシュが無駄になる
- なるべく細かい時間単位で区切りたいが、オーバーヘッドがあることに注意する
- そこでCFSでは一定の時間をいくらかずつの時間に分割して、各プロセスをラウンドロビン式に実行する
    - 次のプロセスを選ぶとき、今まで実行した時間が最も少ないものから選ぶ
- あるプロセスに割り当てる時間を、runnableなプロセスの個数の関数として計算する
- このときnice値をそのまま計算に使うのではなく、*weight*の計算に使う
    - *weight*はあるプロセスに割り当てられる時間の割合を表す
        - 優先度の大きいプロセスほど大きい*weight*
    - *weight*はnice値の相対的な差によって計算される
- 各プロセスには*targeted latency*(デフォルトでは20ms)に、そのプロセスの*weight*の全体に占める割合を掛けた分だけのtimesliceが与えられる
- *targeted latency*は小さいほど理想に近づくが、小さすぎるとコンテキストスイッチのコストが大きくなる
- 具体例
    - *targeted latency*を20msとする
    - 2つの優先度の等しいタスクを考える
    - このとき、優先度の絶対値によらずそれぞれのプロセスが10msずつ実行される
    - 優先度の等しいプロセスが4つなら、5msずつ実行される
    - 優先度の等しいプロセスが20個なら、1msずつ実行される
- プロセスの個数が無限だとすると
    - 各プロセスのtimesliceは0になる
    - スイッチングコストが爆発
- そこで、timesliceに下限を設ける
    - この下限を*minimum granularity*という(デフォルトでは1ms)
    - これにより、プロセスが無限にあったとしても少なくとも*minimum granularity*ずつは実行される
- プロセスが多くなりすぎると公平でなくなるが、実際のケースでプロセスが少ない場合は完全に公平になる
- 具体例再び
    - nice値0のプロセスAとnice値5のプロセスBの2つが実行される状況
    - プロセスBのweightが全体の1/3だとする
    - targeted latencyを20msとする
    - プロセスAには15ms、プロセスBには5msが割り当てられる
    - プロセスAのnice値が10で、プロセスBのnice値が15だったとしても同じ結果になる！
    - nice値の絶対値は関係ない
- CFSはプロセッサの処理時間の割合を割り当てるので*fiar scheduler*と呼ばれる(完全にfairなわけではないが)