TECHNOLOGY LINUX KERNEL

【第9回】元東大教員から学ぶLinuxカーネル「タイマと時間管理」

2022年9月28日

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOS(Linuxカーネル)の授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校(UNC)コンピュータサイエンス学部で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発.
  • プログラミング歴15年以上,習得している言語: C/C++PythonSolidity/Vyper,Java,Ruby,Go,Rust,D,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開
  • 2020年1月~現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務.2022年6月~現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO.
  • 最近は自然言語処理AIイーサリアムに関する有益な情報発信に従事.
    • (AI全般を含む)自然言語処理AIの論文の日本語訳や,AIチャットボット(ChatGPT,Auto-GPT,Gemini(旧Bard)など)の記事を50本以上執筆.アメリカのサンフランシスコ(広義のシリコンバレー)の会社でプロンプトエンジニア・マネージャー・Quality Assurance(QA)の業務委託の経験あり.
    • (スマートコントラクトのプログラミングを含む)イーサリアムや仮想通貨全般の記事を200本以上執筆.イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり.

こういった私から学べます.

前回を読んでいない方はこちらからどうぞ.

Linuxカーネルの記事一覧はこちらからどうぞ.

LinuxカーネルはC言語で書かれています.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

今回のテーマはタイマと時間管理です.

Linuxカーネルの時間の概念がわかります!

カーネルの時間経過の概念

カーネルに時間経過の概念を持たせることは,以下のケースで必須です.

  • 定期的なタスクを実行する(例:CFSの時間計算)
  • ある処理を将来の相対的な時間に遅延させる
  • 一日の時間を示す

System Timerの中心的役割は以下になります.

  • 定期的な割り込み,System Timerの割り込み
  • システムの稼働時間,時刻の更新,ランキューのバランス,統計情報の記録等
  • あらかじめプログラムされた頻度,タイマのティックレート(tick rate):tick = 1/(tickレート)秒

また,将来の相対的な時間のイベントをスケジュールする動的なタイマがあります.

tick rateとjiffies

tick rate

tick rate(System Timerの周波数)は,HZ変数で定義します.

linux/include/asm-generic/param.hで,HZはCONFIG_HZと定義されています.

CONFIG_HZの値は,カーネルコンパイル時の設定オプションとなります.

HZのデフォルトはアーキテクチャ依存となり,x86-64とARM64は以下になります.

  • x86-64:1,000HZ(1ms)
  • ARM64:100HZ(10ms)

タイマの周波数(HZ)が高いと高精度になり,以下の特徴があります.

  • 分解能が細かいカーネルタイマを実現できる.
  • タイムアウト値を持つシステムコール(例:poll)は,アプリケーションによっては大幅な性能改善が見込める.
  • 時間測定の精度が向上する.
  • プロセスのプリエンプションがより正確に行われるため,低周波数ではタイムスライス終了後にプロセスがより多くのCPU時間を得る可能性がある.

しかし,タイマ周波数が高いことは,タイマ割り込みの頻度が多くなり,結果としてオーバーヘッドが大きくなってしまいます.

また,最近のハードウェアではタイマの周波数を高くすることはあまり意味がありません.

Linuxカーネルではtickless kernelというカーネルのtickを一時的に停止することができるコンパイル時のオプションがあります.

具体的には,以下のNO_HZファミリーのオプションを利用します.

  • CONFIG_NO_HZ:tickless kernelの古い設定項目で,古い設定ファイルとの後方互換性を確保するために,しばらくの間は残すとのこと(将来的には削除予定).
  • CONFIG_NO_HZ_COMMON:tickless kernelを利用する時の共通のオプションで,以下のどちらかを選択する.
    • CONFIG_NO_HZ_IDLE:CPUがアイドル状態の場合,tickは必要に応じてのみトリガーする.
    • CONFIG_NO_HZ_FULL:CPUがタスクを実行しているときでも,可能な限りtickを停止するように試みます.通常,CPU上で1つのタスクを実行する必要があります.

カーネルは現在のタイマの状態に応じて動的にSystem Timerを再プログラムします.

一時的にSystem Timerを停止するため,数百ミリ秒の間,イベントがない状況が発生します.

tickless kernelにより,オーバーヘッドの削減や省エネルギーが期待できます.

また,CPUが低消費電力のアイドル状態の時間が長くなります.

jiffies

jiffiesは,システムが起動してからのタイマのtick数を保持するunsigned long型のグローバル変数です.

jiffiesとseconds(秒数)の変換は以下になります.

  • jiffies = seconds * HZ;
  • seconds = jiffies / HZ;

jiffiesとsecondsの変換例は以下になります.

jiffiesの内部表現を紹介します.

「sizeof(jiffies)」は,32ビットアーキテクチャでは32ビット(4バイト),64ビットアーキテクチャでは64ビット(8バイト)です.

HZ == 100の32ビット変数では497日,HZ == 1000の32ビット変数では50日でオーバーフローします.

しかし,64ビットの変数では,非常に長い間オーバーフローが発生しません.

jiffies

上図のようにリンカマジックを利用することで,32ビットと64ビット両アーキテクチャでunsigned long型を維持したまま64ビット変数にアクセスできます.

つまり,アーキテクチャ毎のjiffiesの変数名と型は以下のようになります.

  • 64ビットアーキテクチャ:jiffies_64(unsigned long long型),jiffies(unsigned long型)
  • 32ビットアーキテクチャ:jiffies(unsigned long型)

jiffiesのラップアラウンドについて解説します.

ここで,ラップアラウンドとは,unsigned long型(符号なし整数型)が最大値を超えると0に折り返されることです.

32ビットでは,0xffffffff + 0x1 == 0x0になることです.

以下のコードの5行目のようにif文で「timeout > jiffies」と比較するとjiffiesがラップアラウンドして0になった時に正常に動作しなくなります.

そこで,linux/include/linux/jiffies.hにある以下のマクロを利用することで,ラップアラウンドの問題を解決します.

  • time_after(a, b)マクロ:時刻aが時刻bより後の場合に真を返す.
  • time_before(a, b)マクロ:時刻bが時刻aより後の場合に真を返す.
  • time_after_eq(a, b)マクロ:時刻aが時刻bより同じか後の場合に真を返す.
  • time_before_eq(a, b)マクロ:時刻bが時刻aより同じか後の場合に真を返す.

先述したコードをtime_beforeマクロで書き換えた場合は以下になります.

アーキテクチャ固有のjiffiesとユーザ空間のclock tickを変換するために,linux/include/linux/jiffies.hにあるjiffies_to_clock/jiffies_64_to_clock_t関数を利用します.

linux/inlcude/asm-generic/param.hでマクロとして定義されているユーザ空間のclock tickとしてUSER_HZがあります.

上記の関数は,ユーザ空間のAPIであるclock関数から呼ばれます.

ハードウェアのクロックとタイマ

ハードウェアのクロックとタイマは以下になります.

  • Real-Time Clock(RTC)
  • System Timer
  • CPU's Time Stamp Counter(TSC)

RTCは,wall clockの時刻を保存するものです.

マザーボード上の小さなバッテリでバックアップされているため,RTCはコンピュータの電源が切れても増分されます.

Linuxはブート時にデータ構造にwall clockの時刻を保存します.

Linuxカーネルでは,xtimeという変数でwall clockを管理します.

System Timerは,アーキテクチャ共通の一定の周期で割り込みを駆動する機構を提供します.

x86のSystem Timerは,ローカルAPICタイマ(現在のプライマリタイマ)です.

Linuxカーネルのバージョン2.6.17まではProgrammable Interval Timer(PIT)がプライマリタイマでした.

ARM64はGeneric Timerを利用します.

CPU's Time Stamp Counter(TSC)は,最も正確な(CPUクロック分解能の)カウンタです.

x86-64ではクロック周波数に不変で,秒数 = クロック / 最大CPUクロック Hzになります.

x86-64ではTSCをrdtsc命令またはrdtscp命令で読み出します.

ARM64ではTSCをPerformance Monitors Cycle Count Register(PMCCNTR_EL0)で読み出します.

タイマ割り込み

タイマ割り込み処理は,アーキテクチャ依存部,アーキテクチャ共通部の2つから構成されます.

アーキテクチャ依存部はタイマ割込みのハンドラ(Top Half)として登録されます.

  1. System Timer割り込みを認識する(必要に応じてリセットする).
  2. wall clockの時刻をRTCに保存する.
  3. アーキテクチャ共通関数を呼び出す(Top Halfの一部としてまだ実行される).

アーキテクチャ共通部では,linux/kernel/time/tick-common.cにあるtick_handle_periodic関数を呼び出します.

  1. tick_periodic関数を呼び出す.
  2. do_timer関数でjiffies_64をインクリメントする.
  3. update_wall_time関数でwall timeを更新する.
  4. update_process_times関数を呼び出す(必要に応じてロードバランサーを実行する).
  5. account_process_tick関数で現在実行中のプロセスとシステム全体の統計情報を更新する.
  6. run_local_timers関数でdynamic timerを実行する.
  7. scheduler_tick関数を呼び出す.

linux/kernel/time/tick-common.cにあるtick_periodic/tick_handle_periodic関数は以下になります.

linux/kernel/time/timekeeping.cにあるdo_timer関数は以下になります.

linux/kernel/time/timer.cにあるrun_local_timers/update_process_times関数は以下になります.

update_process_times関数は以下の関数を呼び出します.

  • account_process_tick関数:ユーザ空間やカーネル空間のプロセスやアイドルタスクの経過時間に1 tick加算する.
  • run_local_timers関数:期限切れのタイマを実行し,TIMER_SOFTIRQ softirqを発生させる.
  • scheduler_tick関数:現在実行中のプロセスのスケジューラクラスのtask_tick関数を呼び出す.タイムスリック情報の更新し,必要に応じてneed_reschedを設定する.CPUランキューのロードバランサーを実行する(SCHED_SOFTIRQ softirqを発生させる).

タイマ

タイマは,あるコードの実行を一定時間遅らせるために使用します.

「timer == dynamic timer == kernel timer」という意味になります.

linux/include/linux/timer.hにタイマを管理するtimer_list構造体と,タイマの操作マクロ・関数があります.

  • timer_setupマクロ:タイマをセットアップする.
  • add_timer関数:タイマを追加する.
  • del_timer関数:タイマを削除する.

タイマを利用するカーネルモジュールのコード一式はこちらからダウンロードして下さい.

タイマのコードtimer_kernel_module.cは以下になります.

実行結果は以下になります.

16行目の「[17171.765538] Timer started!」が呼ばれた約2秒後に,17行目の「[17173.773958] myhandler() is called!」が表示されていることがわかります.

※正確には17173.773958 - 17171.765538 = 2.00842秒になります.

実行の遅延

カーネルはタイマ(Bottom Half)を使わず,ある程度の時間を待つ(実行を遅延する)必要がある場合があります.

例えば,ハードウェアと通信するドライバです.

必要な遅延は非常に短く,タイマのtick周期よりも短いことがあります.

解決策は以下になります.

  • ビジーループ(Busy Loop)
  • 短い遅延とBogoMIPS
  • schedule_timeout関数

ビジーループ(Busy Loop)

ビジーループ(Busy Loop)は,与えられたtick数が経過するまでループで回転させます.

jiffies,HZ,rdtscが使用可能です.

ビジーループは非常に短い時間を遅らせるには良いが,一般的にはCPUサイクルを浪費するので最適とは言えません.

より良い解決策は,cond_resched関数を利用して待ち時間にCPUサイクルを残しておくことです.

cond_resched関数はneed_reschedフラグが設定されている場合のみスケジューラを起動します.

ただし,割り込みコンテキストから使用することはできません(スケジューラではありません).

割り込みハンドラは高速であるべきなので,純粋なビジーループはおそらく良いアイデアではありません.

ビジーループは,ロック中や割込み禁止中に性能に重大な影響を与える可能性があります.

短い遅延とBogoMIPS

クロックの1 tickより短い時間だけ遅延させたい場合はどうすればよいでしょうか?

  • HZが100の場合,1 tickは10msです.
  • HZが1000の場合,1 tickは1msです.

上記より短い遅延を実現したい場合,mdelay/udelay/ndelay関数を利用します.

これらの関数は,ビジーループとして実装しています.

udelay/ndelay関数は,オーバーフローの危険性があるため,1ms未満の遅延の場合のみ呼び出す必要があります.

linux/include/linux/delay.hにmdelay/ndelay関数の定義があります.(正確にはmdelayはマクロです.)

※udelay関数はアーキテクチャ依存部にあります.(現状はコードが綺麗に整理されていないです.)

上記のコードは少しわかりにくいので,mdelay/udelay/ndelay関数は以下のようなプロトタイプ宣言だと考えるとわかりやすいです.

BogoMIPSは,Linuxカーネルのブート時にCPU速度をビジーループを使って非科学的に測定した結果です.

BogoMIPSの単位はiteration/jiffyで,ブート時にキャリブレーションします.

私のPCのBogoMIPSは,/proc/cpuinfoで確認すると4799.99になります(23行目).

9行目のCPUの周波数「2399.999」(約2.4GHz)の約2倍になっていることがわかります.

schedule_timeout関数

schedule_timeout関数は,呼び出したタスクを少なくともn tickの間スリープさせます.

タスクの状態をTASK_INTERRUPTIBLEまたはTASK_UNINTERRUPTIBLEに変更する必要があります.

また,ロックせずにプロセスコンテキストから呼び出さなければなりません.

タイムアウトを伴う待ち行列でのスリーピングでは,タスクは特定のイベントを待つために待ち行列に入れることができます.

このようなイベントをタイムアウトで待つには,schedule関数の代わりにschedule_timeout関数を呼び出します.

linux/kernel/time/timer.cにschedule_timeout関数があります.

時刻

Linuxには時刻を取得,設定する機能が豊富にあります.

また,ある時点の時刻を表現するためのデータ構造は以下になります.

  • timespec構造体:linux/include/uapi/linux/time.hで定義
  • timespec64構造体:linux/include/linux/time64.hで定義
  • ktime_t:linux/include/linux/ktime.hで定義

ktimeの関連関数はこちらが詳しいです.

現在時刻を取得するカーネルモジュールのコード一式はこちらからダウンロードして下さい.

現在時刻を取得するコードtime_of_day_kernel_module.cは以下になります.

実行結果は以下になります.

以下の処理を実行しています.

  • ktime_get_real_ts64/ktime_get_real関数:1970年1月1日からの経過時間
  • ktime_get_boottime_ts64/ktime_get関数:ブートからの経過時間
  • ktime_get_boottime_ts64/ktime_get_ts64/timespec64_sub関数:経過時間の測定
  • ktime_get/udelay関数:マイクロ秒単位の短い遅延時間の測定

まとめ

今回はタイマと時間管理を紹介しました.

Linuxカーネルで時間を計測したい場合は参考にして下さい.

タイマと時間管理を深掘りしたいあなたは,以下の記事を読みましょう!

LinuxカーネルはC言語で書かれています.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

次回はこちらからどうぞ.

-TECHNOLOGY, LINUX KERNEL
-, , , , , , , ,