Red-Black-Tree

はじめに 動かしながらゼロから学ぶLinuxカーネルの教科書 第2版 上記の技術書を読んでいてLinuxスケジューラの話が出てきた。CFSもEEVDFも赤黒木を使っている。赤黒木とは何かを調べていくうちにAVL木との比較が面白かったので、両方Pythonで実装してベンチマークを取った。 実装コードはClaude (Anthropic) により生成。リポジトリは以下。 https://github.com/wasuken/avl-rb-tree 自己平衡二分探索木とは まず前提として、ただの二分探索木には問題がある。 挿入順: 1, 2, 3, 4, 5 1 \ 2 \ 3 \ 4 ← 一直線になる 挿入順によっては木が一直線になり、検索がO(n)に劣化する。これを解決するのが自己平衡二分探索木で、挿入・削除のたびに自動でバランスを取り直す。AVL木と赤黒木はどちらもこのカテゴリに属する。 AVL木 1962年にソ連の数学者Adelson-VelskyとLandis（AVLの名前の由来）が考案した世界初の自己平衡二分探索木。 バランスの管理方法 各ノードに高さ（height）を持たせ、左右の高さの差（バランス係数）が常に1以内になるよう管理する。 def _balance_factor(self, node): return self._height(node.left) - self._height(node.right) 差が2以上になったら回転で修正する。 回転 回転は「親子関係を1段入れ替えるだけ」の操作。二分探索木の順序を壊さずに形だけ変える。 rotate_right(y): y x / \ / \ x C → A y / \ / \ A t2 t2 C t2 は回転で行き場を失う孫ノード。二分探索木の順序的に x < t2 < y が保証されているので、yの左に付け替えるだけでよい。 バランス崩れのパターンは4つ（LL, RR, LR, RL）で、それぞれ1〜2回の回転で解消できる。 挿入・削除 挿入・削除のたびに _rebalance が呼ばれ、高さの更新とバランスチェックが走る。 ...

はじめに 動かしながらゼロから学ぶLinuxカーネルの教科書 第2版 上記の技術書を読んでいてスケジューラ周りの理解が曖昧だったので、生成AIや公式ドキュメントを使って整理した。 CFS (Completely Fair Scheduler) とは Linux 2.6.23から導入されたプロセススケジューラ。「全プロセスに公平にCPU時間を与える」という思想で設計されている。 vruntime（仮想実行時間） vruntimeは「実際の実行時間をNICE値で補正した値」で、CFSの核心となる指標。 vruntime += 実際のCPU時間 × (1024 / プロセスの重み) NICE値が低い（優先度高）→ 重みが大きい → vruntimeの増加が遅い → より長くCPUを使える NICE値が高い（優先度低）→ 重みが小さい → vruntimeの増加が速い → すぐ交代させられる CFSは「vruntimeが最も小さいプロセスを次に実行する」というルールで動く。後ろ向きの指標（過去の使用量の累積）であることがEEVDFとの本質的な差になる。 NICE値と重み NICE値は -20（最高優先度）〜 +19（最低優先度）の範囲で、内部的に重みに変換される。 NICE 0 → weight 1024 NICE -1 → weight 1277（約1.25倍） NICE +1 → weight 820（約0.8倍） NICE -20 → weight 88761 NICE +19 → weight 15 1段階変わるごとに約10%のCPU時間が変化する設計になっている。 タイムスライスとスケジューリングレイテンシ スケジューリングレイテンシは「全プロセスが最低1回実行されるべき目標周期」。デフォルト約6〜24ms（プロセス数による）。 タイムスライスはその比例配分： タイムスライス = スケジューリングレイテンシ × (タスクの重み / キュー内の全タスクの重みの合計) 具体例： ...