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

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

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

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

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

タイマホイールは、満了時刻（jiffies 値）を添字にしたバケットの配列です。各バケットは、その時刻に満了するタイマの連結リストを持ちます。現在時刻を指す「指針（カーソル）」があり、tick のたびに 1 つ進みます。指針が指したバケットのリストを取り出し、中のタイマを満了させる——これがホイールという名の由来です。

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

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

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

代償は精度です。同じバケットに入ったタイマは同時刻として扱われ、tick 粒度（HZ=250 なら 4 ミリ秒）より細かい区別はできません。さらに後述の階層では、遠い未来のタイマほど粒度が荒くなります。だからこそこの構造は「タイムアウト」のように多少早い／遅いが許される用途に向くのです。

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

問題は配列の長さです。1 tick=1 スロットの単一ホイールで「数十秒先」まで表すには、HZ=250 で数千〜数万スロットが要り、tick ごとに大量の空バケットを舐めることになりかねません。これを解くのが**階層型タイマホイール（hierarchical timing wheel）**です。

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

挿入時は、満了までの残り時間（expires - now）の大きさを見てどの段に置くかを選び、その段の中ではビット演算でスロットを決めます。残りが大きいほど上位の粗い段に入るため、遠い未来のタイマほど粒度が荒く配置されるのがこの設計の肝です。近いものだけ細かく、遠いものはざっくり——これにより、どの段も現実的なスロット数（各段 64 程度の小さな配列）で全時間域をカバーできます。

カスケードとO(1)償却 ── 上位から下位へ「降ろす」

階層型では、tick で進めるのは最下位の段だけです。では上位の段のタイマはいつ処理されるのか。ここで カスケード（cascade） が登場します。最下位の指針が一周して 0 に戻る瞬間、1 つ上の段の指針を 1 つ進め、そのスロットに溜まっていたタイマたちを取り出して下位の段へ入れ直すのです。

最下位ホイールが一周（指針が0に戻る）
   → 中位ホイールの指針を+1
       → そのスロットのタイマ群を取り出し
          残り時間に応じて下位ホイールへ再配置（cascade）

中位が一周すれば、同様に上位 → 中位へ降ろす

降りてきたタイマは、より近づいた満了時刻に応じて細かい段へ再配置されます。こうして「遠いうちは粗い段で安く保持し、近づいたら細かい段へ移す」段階的な絞り込みが起きます。

償却計算量が O(1) になる理由はここにあります。1 つのタイマが一生のうちにカスケードで段を降りる回数は、段の数（時間域に対し対数的で、定数とみなせる小さな値）に限られます。各カスケードは連結リストの付け替えだけ。N 個のタイマを処理する総コストを N で割れば、1 タイマあたり定数回の再配置に収まります。tick ごとに見るのは原則「最下位の1スロット」だけで、空でも極小コストです。これが「ならし O(1)」の正体です。

なお、近年の Linux はこの素朴なカスケードを見直し、満了時刻ではなくバケット単位でまとめて遅延を許す方式に変えています。キャンセルが多い性質を踏まえ「満了するまで動かさない（再配置を減らす）」ことで、登録・解除のさらなる軽量化を図っています。設計思想——粒度を距離で変え、頻繁な挿入・解除を最優先で安くする——は一貫しています。

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 粒度より細かくは扱えない。キャンセル主体・精度不問の大量タイムアウトに最適。
• 階層化で遠い未来のタイマを粗い上位段に置き、tick では最下位だけを見る。カスケードで上位から下位へ段階的に降ろし、1 タイマの段降り回数が定数に収まることから償却 O(1) が成り立つ。
• 償却 O(1) は平均であり、カスケードが走る tick は処理が跳ねる。だから満了は softirq（割り込みの下半分）へ逃がす。
• 精密な期限は hrtimer が赤黒木で管理し、挿入 O(log n)・最早期限 O(1) 参照・ワンショット割り込みで ns 級精度を出す。タイムアウトはホイール、締め切りは hrtimer と役割が分かれる。