カーネル内の時刻/時間関連サブシステム
以下の時刻/時間関連サブシステムについて、詳細を解説します。
時刻/時間の表現
Linuxカーネル内では時刻/時間を表す構造体が必要に応じて色々と定義されています。
- long unsigned int jiffies;
tick を数えたもので、初期値は 32bit プラットフォームでは -5 分相当となります。64bit プラットフォームでは、-5 分相当の 32bit 値を、符合なしで 64bit に拡張したもの (上位 32bit を 0 で埋めたもの) です。 - struct timeval
タイマー値を指定する場合に使用します。この構造体のメンバは、tv_sec (秒) と tv_usec (マイクロ秒)で、主にユーザーランド API として使用されます。 - struct timespec
タイマー値を指定する場合に使用します。この構造体のメンバは、tv_sec (秒) と tv_nsec (ナノ秒) で、ユーザーランド API の他 xtime などで使用されます。 - ktime_t
64 bit 符号付整数によるナノ秒単位での時刻/時間を格納するために使用し、カーネル内部で広範に利用されます。
1. jiffies と timer wheel
jiffies と timer wheel は、Linux にとって伝統的なサービスです。
Jiffies は、tick、すなわち 1/HZ 秒 (RHEL では HZ = 1000で、1 ミリ秒) 毎に 1 ずつ増えるグローバル変数 (符合なし整数) で、カーネル内部で時間を測るのに利用できます。
Timer wheel は、 jiffies が特定値になったときにコールバックを呼ぶ機構です。おなじみの struct timer と、add_timer()/del_timer()/mod_timer() などの関数を使って管理するものです。
timer wheel の実装
Timer wheel は、add_timer / del_timer が頻繁に行なわれ、かつほとんどの timer が expire しないで del_timer される、という性質に基づき実装されています。add_timer / del_timer は、登録されているタイマーの数によらず、 O(1) で実行可能です。
Linux Kernel のメーリングリストの kernel/timer.c design に関する Ingo Molnar 氏の記述が参考になります。
497 日 (49.7 日) 問題
かつて Linux で、システムの連続稼動日数が 497 日を超えた場合に生じる問題、いわゆる 497 日問題あるいは 49.7 日問題がよく発生しました。
この問題の多くは、jiffies が一周してしまう (2^32 に達してしまう) のが理由 (HZ = 100 のとき 497 日、HZ = 1000 のとき 49.7 日) で、誤ったコーディングが原因です。
現在では、この手の問題を早期に発見するため jiffies の初期値を -5 分に相当する値としています。ただし、アプリケーションや、カーネル内の他のタイマ関連変数において、類似の現象は現在でもたまに見られます。
2. Wall clock と monotonic clock
Wall clock は壁時計ですが、現在の Linux では大元の時計を指します。カーネル内の多くのサブシステムが、時間に関する処理をする際に壁を見て、この時計を参照します。
Monotonic clock は、POSIX でも規定されていますが、単調増加が保証されている (つまり、時刻が巻き戻ったり settimeofday などで調整されたりしない) 時計です。
Wall clock、monotonic clock ともにナノ秒の単位の値を持ちますが、実際の精度はハードウェアに依存します。以下のような仕組みで維持されます。
- xtime (カーネル内グローバル変数)
– 現在時刻 (Unix epoch からの時間) を保持する struct timespec
– jiffies の更新と同じタイミングで更新
– 更新のタイムスタンプをあわせて保持 - getnstimeofday()/ktime_get_real() (Wall clock を得る API)
– 時刻参照の際には、計時ハードウェアの現在値も参照して正確な時刻を得る
- ktime_get()/monotonic time (monotonic time を得る API)
– wall_to_monotonic という変数があり、起動時刻から Unix epoch までの時間 (つまり負数) を持つ
– 現在時刻に加えると、起動からの時間を得ることができる
– POSIX clock 拡張の CLOCK_MONOTONIC にも用いられる
xtime は NTP による補正を受けるため、getnstimeofday()、ktime_get()、ktime_get_real() などの結果も NTP による補正のかかった値となります。
3. Tick
Tick は、1/HZ 秒に 1 度呼ばれ、以下のような処理を行ないます。
- jiffies の更新 / xtime の更新
- load average の計算 (10 tick に 1 度)
- timer wheel コールバックの実行 (softirq 利用)
- hrtimer コールバックの実行
- CPU 利用率統計の更新 (sys%, user%, …、per-cpu、per-task)
- タスクスケジューラ呼び出し (プリエンプト)
など
これらのうち、最初の 2 つはシステム全体で 1/HZ 秒に 1 度行えばよい処理なので、いずれか 1 つの CPU でのみ行なわれますが、それ以外は各 CPU で 1/HZ 秒に 1 度実行されます。
4. High-resolution timer
High-resolution timer (hrtimer) は、timer wheel と似たような API ですが、以下のような特徴があります。
- ktime (ナノ秒単位) ベース。Timer wheel は jiffies (tick 単位) がベース
- 時計が指定時刻に達したらコールバック
- 時計は3 (2)種
– CLOCK_REALTIME
– CLOCK_MONOTINIC (単調増加、suspend している間は進まない)
– CLOCK_BOOTTIME (2.6.38-、CLOCK_MONOTONIC とほぼ同じだが、suspend している間にも進む。正確には、復帰時に suspend していた時間が加算される) - 高精細タイマーハードウェアが搭載されていないと low-res モードで動作。Low-res モードでは、API は使えるが、コールバックは tick でのみ呼ばれる
- 通常の IA サーバ / PC は Local APIC タイマーなどを備えるため指定な際は high-res モード
- high-res モード時は、tick も hrtimer から呼ばれる
- 普通の赤黒二分木で実装 (O(logN))
5. スケジューラークロック
スケジューラークロックは、実行中のタスクの直近の実行時間 (前回コンテキストスイッチからの実行時間) の計測などに使われます。ナノ秒を単位とする 64bit 値です。
CPU ローカル (他の CPU とスケジューラークロック値を比較できない)、軽量、排他不要 (スケジューラー内からは安直に排他できない) などの特徴があります。また、printk のタイムスタンプ (カーネル起動時に printk.time=1 をつけた場合) にも利用されます。
208 日問題
ところで、このスケジューラークロックは、x86 アーキテクチャでは本来数百年にわたって溢れないように作られていますが、実際には簡単に溢れる実装になっていたことが、数年前に発覚して問題になりました (現在は修正されています)。
x86 ではスケジューラークロックは TSC を使って計算されています。
#define CYC2NS_SCALE_FACTOR 10
TSC × cyc2ns >> CYC2NS_SCALE_FACTOR + <offset>
アンダーラインを引いた部分が、TSC リセットからの時間をナノ秒単位で表すわけですが、64bit で計算しているため、TSC×cyc2ns の部分は 264 までで溢れます。これを 10bit 右シフトしていますので、アンダーラインの部分は 0 から 254 までの値を取ります。
この 254 というのは、18014398509481984 ですから、254 ÷ 109 ÷ 60 ÷ 60 ÷ 24 ≒ 208.5 と、208 日ほどで達してしまうことが分かります。
ただ、スケジューラークロックがあふれないことを前提とするコードになっていたことも問題であったはずです。実際、x86 や ARM など現在主流のアーキテクチャでは、プラットフォーム固有のタイマーハードウェアを用いて溢れないように作られているようですが、そうではないアーキテクチャでは jiffies をナノ秒単位に変換しているため、32bit アーキテクチャではすぐに溢れます。