[オペレーティングシステム] 05. CPUスケジューリングアルゴリズム

[プロセス実行サイクル]

CPUバースト -> I/Oバースト -> CPUバースト -> I/Oバースト -> ...

  |-------|          |--------|          |--|
  CPU実行           I/O待ち            CPU実行
  （計算）          （ディスク読み取り）  （計算）

CPUバウンドプロセス：長いCPUバースト、少ないI/Oバースト
I/Oバウンドプロセス：短いCPUバースト、多いI/Oバースト

[FCFS例]

プロセス  到着時間  CPUバースト
  P1        0         24
  P2        0          3
  P3        0          3

実行順序：P1 -> P2 -> P3

ガントチャート：
|----P1----|--P2--|--P3--|
0         24    27     30

待ち時間：P1=0, P2=24, P3=27
平均待ち時間：(0+24+27)/3 = 17

P2, P3, P1の順序だったら？
|P2|P3|----P1----|
0  3  6         30

待ち時間：P1=6, P2=0, P3=3
平均待ち時間：(6+0+3)/3 = 3（大きな差！）

[SJF例 - ノンプリエンプティブ]

プロセス  到着時間  CPUバースト
  P1        0         6
  P2        2         8
  P3        4         7
  P4        5         3

ガントチャート：
|--P1--|P4|---P3---|----P2----|
0      6  9      16         24

待ち時間：P1=0, P2=16, P3=5, P4=1
平均待ち時間：(0+16+5+1)/4 = 5.5

[SRTF（Shortest Remaining Time First）- プリエンプティブSJF]

プロセス  到着時間  CPUバースト
  P1        0         6
  P2        2         8
  P3        4         7
  P4        5         3

時間 0: P1開始（残り：6）
時間 2: P2到着（残り：8）-> P1継続（残り：4）
時間 4: P3到着（残り：7）-> P1継続（残り：2）
時間 5: P4到着（残り：3）-> P1継続（残り：1）
時間 6: P1完了 -> P4開始（残り：3）
時間 9: P4完了 -> P3開始（残り：7）
時間 16: P3完了 -> P2開始（残り：8）
時間 24: P2完了

ガントチャート：
|--P1--|P4|---P3---|----P2----|
0      6  9      16         24

次の予測値 = alpha * 最近の実測値 + (1 - alpha) * 前回の予測値

alpha = 0 なら最近の値を無視（前回の予測値のみ使用）
alpha = 1 なら前回の予測を無視（最近の実測値のみ使用）
通常 alpha = 0.5 を使用

[優先度スケジューリング例]（小さい数値 = 高い優先度）

プロセス  CPUバースト  優先度
  P1        10         3
  P2         1         1
  P3         2         4
  P4         1         5
  P5         5         2

実行順序：P2 -> P5 -> P1 -> P3 -> P4

ガントチャート：
|P2|--P5--|----P1----|P3|P4|
0  1      6        16 18 19

平均待ち時間：(6+0+16+18+1)/5 = 8.2

[ラウンドロビン例]（タイムクォンタム = 4）

プロセス  CPUバースト
  P1        24
  P2         3
  P3         3

ガントチャート：
|P1|P2|P3|P1|P1|P1|P1|P1|
0  4  7 10 14 18 22 26 30

P1：4単位実行 -> レディキューの末尾へ
P2：3単位実行（完了）
P3：3単位実行（完了）
P1：残り20単位を4ずつ分けて実行

待ち時間：P1=6, P2=4, P3=7
平均待ち時間：(6+4+7)/3 = 5.67

[多段キュースケジューリング]

高優先度
+------------------------------------------+
| システムプロセス       | FCFS              |
+------------------------------------------+
| 対話型プロセス         | RR (q=8)          |
+------------------------------------------+
| 対話型編集プロセス     | RR (q=16)         |
+------------------------------------------+
| バッチプロセス         | FCFS              |
+------------------------------------------+
| 学生プロセス           | FCFS              |
+------------------------------------------+
低優先度

上位キューが空になって初めて下位キューを実行（固定優先度）
またはキュー間の時間配分（例：80%対話型、20%バッチ）

[多段フィードバックキュー]

キュー 0: RR (q=8)   <--- 新しいプロセスがここに入る
  |
  | q=8以内に未完了ならキュー1へ移動
  v
キュー 1: RR (q=16)
  |
  | q=16以内に未完了ならキュー2へ移動
  v
キュー 2: FCFS

動作例：
- CPUバーストが短いプロセス：キュー0ですぐに完了（速い応答）
- CPUバウンドプロセス：キュー0 -> キュー1 -> キュー2へ下がる
- I/O完了後に復帰するプロセス：再びキュー0に上がる

結果：I/Oバウンド＋対話型プロセスに高い優先度
      CPUバウンドプロセスは低いキューで長い時間割り当て

// Linuxでのプロセッサアフィニティ設定
#define _GNU_SOURCE
#include <sched.h>

void set_cpu_affinity(int cpu_id) {
    cpu_set_t cpuset;
    CPU_ZERO(&cpuset);
    CPU_SET(cpu_id, &cpuset);

    // 現在のスレッドを特定のCPUにバインド
    sched_setaffinity(0, sizeof(cpuset), &cpuset);
}

[CFS動作原理]

各プロセスのvruntimeを追跡
vruntimeが最も小さいプロセスを次に実行

vruntime増加率 = 実際の実行時間 / 重み（nice値ベース）

nice値が低い（優先度が高い）プロセス：
  -> 重みが大きい -> vruntimeがゆっくり増加 -> より頻繁にスケジューリング

nice値が高い（優先度が低い）プロセス：
  -> 重みが小さい -> vruntimeが速く増加 -> あまりスケジューリングされない

[CFSのRed-Blackツリー]

         vruntimeでソート

              (P3: 50)
             /        \
        (P1: 30)    (P5: 70)
        /    \          \
   (P2: 20) (P4: 40)  (P6: 80)

最も左のノード（P2, vruntime=20）が次の実行対象

挿入/削除/検索：O(log N)保証

// CFSで次に実行するプロセスを選択（概念的コード）
struct task_struct *pick_next_task_fair(struct rq *rq) {
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct rb_node *left;

    // Red-Blackツリーで最も左のノードを選択
    // = vruntimeが最も小さいプロセス
    left = rb_first_cached(&cfs_rq->tasks_timeline);
    if (!left)
        return NULL;

    struct sched_entity *se = rb_entry(left,
                                        struct sched_entity,
                                        run_node);
    return container_of(se, struct task_struct, se);
}

例：ターゲットレイテンシ = 20ms、実行可能プロセス = 4個

同一優先度なら各プロセスに5ms割り当て
プロセスが多すぎる場合は最小単位（min_granularity）を保証

[スケジューリングアルゴリズム比較]

アルゴリズム     プリエンプ  飢餓  利点              欠点
---------       --------  ----  ----              ----
FCFS            X         X     シンプル           コンボイ効果
SJF             X         O     最適待ち時間       バースト予測困難
SRTF            O         O     SJFより良い性能    バースト予測困難
優先度          両方       O     柔軟             飢餓（エイジング必要）
ラウンドロビン    O         X     公平、良い応答     q選択が重要
多段キュー       O         O     差別化サービス     キュー間移動不可
多段FBキュー     O         可能   最も柔軟         パラメータ設定複雑
CFS             O         X     公平なCPU分配     実装が複雑