タイマ割り込みとタイマホイールの構造

なぜ「タイマ専用のデータ構造」が要るのか

カーネルは膨大な数のタイマを抱えます。TCP の再送タイムアウト、接続のアイドル切断、I/O の打ち切り、schedule_timeout による短い眠り——サーバー1台でも同時に何万個ものタイマが生きていることは珍しくありません。これらは大半が「期限まで待つが、ほとんどの場合は期限前にキャンセルされる」という性質を持ちます。つまり挿入とキャンセルが圧倒的に多く、実際に満了するものは少数です。

横にスクロール

この性質に対し、素朴に「満了時刻でソートした連結リスト」や「優先度付きキュー」を使うと挿入が O(n) や O(log n) になり、毎秒大量に発生する登録・解除がボトルネックになります。そこで Linux は、精度を犠牲にする代わりに挿入・削除を平均 O(1) にする専用構造として タイマホイール（timer wheel） を採用しています。tick で数える粗い時間軸の上で動く timer_list がこれです。時間軸そのものの話は /os/kernel-timekeeping-timers/ を前提とします。

タイマホイールの基本 ── ハッシュではなくバケット配列

タイマホイールは、満了時刻（jiffies 値）を添字にしたバケットの配列です。各バケットは、その粒度で同じ満了時刻にまとめられたタイマの連結リストを持ちます。概念上は現在時刻を指す「指針（カーソル）」が進み、期限に達したバケットのリストを取り出す——これがホイールという名の由来です。現行Linuxはこの配列を粒度の異なる複数段に重ねています。

バケット配列（例: 256スロット）
  index = expires & (SLOTS - 1)   ← 満了時刻の下位ビットでバケットを選ぶ

  [0][1][2] ... [k] ... [255]
                 ↑
              現在の指針（jiffiesの下位ビット）
  tickごとに指針を1つ進め、そのバケットのリストだけ満了処理する

ここが核心です。挿入は満了時刻から段とバケット添字をビット演算で即決できるので O(1)、削除は連結リストからの取り外しなので O(1)。満了処理も期限に達した各段のバケットだけを回収し、そのバケットで満了するタイマ数に比例した手間で済みます。ソートされた構造のように全体を整列させる必要がありません。

代償は精度です。同じバケットに入ったタイマは同時刻として扱われ、tick 粒度（HZ=250 なら 4 ミリ秒）より細かい区別はできません。さらに後述の階層では、遠い未来のタイマほど粒度が荒くなります。現行実装はバケット境界を切り上げて早期実行を避けるため、期限が粗い粒度ぶん遅れる可能性があります。だからこそ「多少遅れてもよいタイムアウト」に向くのです。

階層化 ── 1段では配列が足りない

問題は配列の長さです。1 tick=1 スロットの単一ホイールで長い期限まで表すと、巨大な配列が必要です。これを解くのが階層型タイマホイール（hierarchical timing wheel）です。

時計の文字盤が秒・分・時の輪を重ねるように、ホイールを複数段重ねます。下位の段ほど粒度が細かく射程が短く、上位の段ほど粒度が荒く射程が長い。Linux の現行実装は概念的にこう構成されます。

現行Linuxでは各段が64バケットを持ち、段が上がるたびに粒度が8倍になります。段数は HZ に応じて8または9です。挿入時は、満了までの残り時間（expires - base->clk）からどの段に置くかを選び、その段の中ではビット演算でバケットを決めます。残りが大きいほど上位の粗い段へ入るため、遠い期限ほど粒度が荒く配置されるのが設計の肝です。

calc_index() は段の粒度でバケット満了時刻を切り上げます。これによりタイマが指定期限より前に発火することを防ぎます。一方で、元の expires より後ろのバケット境界まで遅れる可能性は受け入れます。ホイール上限を超える極端に長い期限は、最上位段の最大期限へ丸められます。

現行Linuxは再カスケードしない ── 登録位置を変えない

古典的な階層型ホイールは、上位段のタイマを期限が近づくたび下位段へ移すカスケードを行いました。これは満了時刻を細かい粒度へ近づけられる反面、境界時刻に多数のタイマをまとめて再配置する負荷を生みます。

現行Linuxは、タイムアウトの大半が満了前に取り消されるという実測上の性質を優先します。登録時に段とバケットを一度だけ決めた後は、満了まで下位段へ降ろしません。各段は固有の粒度で時計を進め、その段のバケット満了時刻に達したらリストを回収して TIMER_SOFTIRQ へ渡します。

timerを登録
  → 期限差からlevelを選ぶ
  → level粒度でbucket満了時刻を切り上げる
  → bucketへ一度だけ連結
  → そのlevelの期限到達時に回収（段間の再配置なし）

登録は段選択とリスト連結、取消はリストからの取り外しで平均 O(1) です。再カスケードの突発負荷はありません。ただし満了処理まで常に定数時間という意味ではなく、同じバケットへ期限が集中すれば処理時間はそのタイマ数に比例します。コールバック実行を TIMER_SOFTIRQ へ分ける理由もここにあります。この二段構えは /os/interrupt-top-bottom-half/ の設計そのものです。

hrtimer との使い分け ── ホイールか赤黒木か

精度が要る用途には、ホイールではなく hrtimer を使います。hrtimer は満了時刻をナノ秒の絶対時刻で持ち、tick の粒度に縛られません。データ構造もホイールではなく赤黒木（red-black tree）で、時刻順に並べます。

なぜ木なのか。hrtimer が必要とするのは「次に満了するのはどれか（=最も早い期限）」の即時参照です。赤黒木なら挿入・削除が O(log n)、最左端（最早期限）はキャッシュしたポインタで O(1) に取れます。カーネルはこの最早期限に合わせてハードウェアタイマへワンショットの割り込みを一発予約し、満了したらコールバックを呼び、次の最早期限へ予約し直します。tick に相乗りしないので、tick 粒度を超える精度が出せます。

判断は用途で割り切れます。「期限前にキャンセルされる前提で、多少ずれても困らない大量のタイムアウト」はホイール。挿入・解除が圧倒的多数を占めるこの種の負荷で、O(1) の安さが効きます。一方、「必ず満了させ、ずれが許されない精密な期限」は hrtimer。nanosleep、オーディオの周期、SCHED_DEADLINE の予算管理などです。後者の精度がプリエンプション設計に左右される話は /os/realtime-scheduling/ や /os/kernel-preemption/ と地続きで、hrtimer がナノ秒を「表現できる」ことと精度が「保証される」ことは別物です。

まとめ

• タイマホイールは満了時刻をバケット添字に変換する配列で、挿入・削除を平均 O(1) にする。代償は精度で、tick 粒度より細かくは扱えない。キャンセル主体・精度不問の大量タイムアウトに最適。
• 現行Linuxは登録時に段とバケットを一度だけ決め、再カスケードしない。遠い期限ほど粗い段へ置き、バケット境界を切り上げて早期実行を防ぐ代わりに遅延を許す。
• 再カスケード費用はないが、同じ期限バケットへ集中したタイマの満了処理は個数に比例する。コールバックは TIMER_SOFTIRQ で実行する。
• 精密な期限は hrtimer が赤黒木で管理し、挿入 O(log n)・最早期限 O(1) 参照・ワンショット割り込みで ns 級精度を出す。タイムアウトはホイール、締め切りは hrtimer と役割が分かれる。