長期証券投資の方法の一つを紹介
10年以上証券投資をしてきて今の方法にたどり着いた自分なりの投資方法を書きます。おそらくは少なからない人が推測している「株をやる」とは大きく違っていると思います。もう一点、タイトルについて「株式取引じゃないの？」と思われるかもしれませんが、株式だけではなく投資信託も買ってるので両方を含む証券投資としています。
文書化するのはめんどくさいので列挙で。
- 目的
- 60歳になったころから悠々自適に暮らせるようになること
- 自分のはじき出した適正株価の計算(後述)が妥当かどうかを確かめたいという趣味。あともちろん資産も増やしたい。
- 投資の原資
- 生活費やとっさの入院など、まぁまぁの確率で入り用になりそうな金額を決めて、それだけは現金で持つ。それ以外は全て証券投資の原資。
- 買うもの
- 個別株を買う基準
- その他の考え方
- 底値で買おうということは考えない。無理*3。これは「頭と尻尾はくれてやれ」という言葉もある。あくまで買いたい株を探しているそのときに割安かどうかが問題。
- 買った後はよほどのことがなければ資産の増減は確認しない。株価というものはそもそもフラフラ変動するものなので日々の変化を気にしてもしょうがない*4。また、60歳あたりまでに資産が増えていればいいので途中経過はどうでもいい。むしろ途中で暴落してくれれば買い増せるチャンスが増えるので好ましい*5。
- 海外株は買わない。株価そのものの変動と為替レートの変動を考えると予測が極めて困難と判断しているため
- チャートや板は一切見ない。上記の考え方に基づくと見る理由が無い
- 短期投資をしない理由
- コロケーションをはじめとするなかばインチキな大技を使える巨人たちに負け続けるのはわかっているので納得がいかないから
- なるべく精度が高そうな数値ベースで判断したいという性格とは相いれないから
- なんとなくストレスがたまりそう。長期投資をしている場合に対して日々の株価が気になってしまいそう
こんなところです。
Linuxカーネル4.1のプロセススケジューラ(ドラフト)
はじめに
本記事は昔書いたlinuxカーネル4.1のプロセススケジューラの実装について途中まで書いたけど諸事情により二年くらい放置していたドラフトです。死蔵するのももったいないので公開しておきます。今現在のカーネルに比べてずいぶんと変わっていること、未稿の部分がかなりあること、誤字脱字や「てにをは」は気にしていないこと、などにご注意ください。
このドキュメントを積極的に更新する予定は(少なくともこの場では)いまのところありません。
プロセススケジューラ
ある瞬間にCPU1で動作できる処理は1つだけです。この限りあるCPU資源をシステムに存在する プロセス間で分配するのがプロセススケジューラです。プロセススケジューラは大きく分けて 次のことをします。
個々のコアのことであり、かつ、ハイパースレッドが有効化されていれば個々のハイパースレッドの ことです。
まずは簡単のため、1CPUの場合に絞って記載します。その後マルチプロセッサの場合について記載します。
1CPUの場合
プロセススケジューラはユーザに対して複数のプロセスが同時並列的に動作しているように見せかけます。 それには、複数の動作可能なプロセッサを交互に動かす時分割(タイムシェアリング)という仕組みを用います。 たとえば2つの実行可能なプロセスp0, p1が同時に存在している場合、CPUの上で動作するプロセスは次の ように遷移します。
とくにnice値によって優先度に差をつけていない場合はp0, p1に対してCPU時間を均等に割り当てます2。 このp0, p1を順番に動作させることをラウンドロビン形式と呼びます。
具体的にはそれぞれのプロセスは、たとえば 10 ms というレイテンシと呼ばれる期間を 2 等分した 10/2 = 5 ms という期間だけ 一度に動作できます。動作中の全てのプロセスがレイテンシに定められた期間に一度は必ず CPU 時間を使える ためにこの名前がついています。
実行可能なプロセスが3つ以上になっても話は同じです。
この場合は各プロセスは1回あたり 10 / 3 ~= 3.3 ms という期間 CPU を使えます。
ここで min_guranurarity について書く
プロセスは常にCPU時間を使おうとしているわけではありません。write(2)の延長でストレージのI/O待ちを している時や、sleep(3)によって自ら待ちに入るような場合もあります。次に示すのはCPU上で唯一動作可能な p0というプロセスが1秒間動作した後にスリープした後に再び起床して動き出すという図です。
p0 -> アイドルプロセス ... というような図
p0が動作していない間は、より正確に言うと、CPU上に動作可能プロセスが存在していない場合は、スケジューラが CPU上でアイドルプロセスという特殊なプロセスを動作させます。アイドルプロセスの最も単純な実装は、無限ループに よってCPU資源を消費し続けるというものです。しかし、通常は1つ以上のプロセスが動作可能になるまでCPUの電力消費を 極力抑えた状態待つような動作をします。
スリープしていたプロセスが起床した場合はどうなるでしょうか。次に示すのはp0, p1がCPU上で動作している ときに、p2が新たに起床して動作可能になった図です。
ここではp2の起床タイミングがわかりやすかったですが、もちろん、より複雑な場合もあります。 そのようなパターンについては後述します。起床してきたプロセスは通常早く動きたいので、 優先的に動作させる仕組みがあります。これについても詳細は後述します。
これまでは、時系列に沿ってCPU上でどのような処理が動作しているかという観点で見てきましたが、それに加えて 各プロセスが時系列に沿ってどのような状態になるかを見てみましょう。
複数CPUの場合
複数CPUの場合、ある瞬間にCPU上で同時に動作できるプロセスの数がCPU数に応じて増えます。 2CPUなら2個、10CPUなら10のプロセスが同時に動作できます。例えば2CPUシステムで動作可能プロセスが 2つ存在する場合は次のようになります。
2CPUで4プロセスp0〜p3が同時に実行可能であれば、図
では、どのプロセスがどのCPU上で動作するかはどのように決まるのでしょうか。実はこれもプロセス スケジューラの役割です。プロセススケジューラは、上述のように1CPU内で複数プロセスにCPU時間を 平等に割り当てる機能に加えて、CPU間で均等にプロセスの負荷を分散する機能もあります。この機能の ことをロードバランサやグローバルスケジューラと呼びます(本書では前者の表記をします)。
次に示すのは、2CPUシステムにおいてCPU0上で唯一のプロセスp0が動作している状態から、スリープしていたp1, p2, p3 がそれぞれ時間差で起床する図です。
複数CPUの場合はレイテンシの値が次の式に従って増加します。
レイテンシ = 1 + <1CPU時のレイテンシ * log2(<CPU数>)>
のちほどロードバランサの節で詳しく述べますが、あるCPU上でプロセスが実行待ちのときに他にアイドルCPUがあれば、そのプロセスはアイドルCPU上に移動して即座に実行開始できます。それに加えて、CPU数が多いほどアイドルCPUが存在する可能性も高まります。このため、CPU数が増加するとユーザの体感レイテンシはスケジューラが定めた体感レイテンシよりも短くなります。このため、上記の式によってレイテンシの値を決めることによって、CPU数が多いときにユーザの体感レイテンシを損なうことなくスループット性能を向上させられます。
nice値と優先度
これまでプロセススケジューラは動作可能なプロセスに平等にCPU時間を割り当てると言ってきましたが、 それには例外があります。ユーザから見て重要なプロセスには優先的にCPU時間を割当てたいときがあります。 このようなときには nice システムコールやnice コマンド、renice コマンドなどを使います。 nice 値は-19から20の値が存在し、ややこしいのですが-19が最高優先度でデフォルトが0,最低優先度が20です3。
nice値が変化することによってレイテンシは変化しませんが、nice値の低い(優先度の高い)プロセスは nice値の高い(優先度が低い)プロセスよりもCPU時間を多くの比率だけもらえます。
スケジューリングポリシー
スケジュールするにあたって、優先度以外にももう一つ、プロセススケジューリングの挙動を変更する スケジューリングポリシーという要因があります。これには主に次のような種類があります。
- SCHED_OTHER(デフォルト)
- SCHED_FIFO
- SCHED_RR
SCHED_OTHERは本章でこれまでに述べてきたような動きをします。
SCHED_FIFO はリアルタイム性の強いプロセス、たとえば定期的に起床してシステムの生存確認を するようなハートビート用プロセスなどに用います4。1つでも実行可能なSCHED_FIFO プロセス が 存在すると、当該プロセスがブロックするまで SCHED_OTHER プロセスは動作できません。実行可能な SCHED_FIFOプロセスが複数存在する場合は、ブロックするか、あるいはsched_yield()によって自発的に CPUを明け渡さなければ次のプロセスにCPU時間を明け渡しません。
ことを保証できるわけではないのでロボット制御のような処理には適しません。
SCHED_RR は、ほとんどSCHED_FIFOと同じですが、1 つだけ違いがあります。SCHED_RR プロセスが 複数存在する場合は 100 ms ごとにラウンドロビン形式でCPU実行権がプロセス間で遷移します。
スケジューリングポリシーは他にも次のようなものがありますが、これらについては重要度が低いため、本書では触れません。
- SCHED_BATCH
- SCHED_DEADLINE
- SCHED_IDLE
コアスケジューラの実装
モジュール構造
プロセススケジューラには前述のスケジューリングポリシーに対応する様々なスケジューリングアルゴリズムが存在します。具体的には次のように、1つないし複数のスケジューリングポリシーに対して、スケジューリングクラスと呼ばれるstruct sched_class構造体によってアルゴリズムが分かれています。
| スケジューリングポリシー | スケジューリングクラス |
|---|---|
| SCHED_OTHER, SCHED_BATCH, SCHED_IDLE | fair_sched_class |
| SCHED_FIFO, SCHED_RR | rt_sched_class |
| SCHED_DEADLINE | dl_sched_class |
これ以外に、例外的にアイドルプロセスに対してはidle_sched_classという特別なスケジューリングクラスが割り当てられています。
プロセススケジューラは、あらゆるスケジューリングクラスに共通するコア部分のコードが、それぞれ別コードに まとめられているスケジューリングクラスを呼び出すようなモジュール構造なっています。これによって、コア部分の コードにif文やswitch文などによって各スケジューリングポリシーのコードを書く場合に比べて、ソースの見通しが よくなると共に、将来的に新しいスケジューリングクラスの追加が楽になっています。
プロセススケジューラのコードのうち、ソース上では次のような構成になっています。
kernel/sched +--- core.c: プロセススケジューリングのコア部分コード。ここを起点に他のファイル内のコードを呼び出す +--- fair.c: スケジューリングポリシー SCHED_OTHER, SCHED_BATCH, SCHED_IDLE に関するコード +--- rt.c: スケジューリングポリシー SCHED_FIFO, SCHED_RR に関するコード +--- idle.c: アイドルプロセス用の特殊なスケジューリングクラス(SCHED_IDLEとは無関係)に関するコード +--- idle.c: アイドルプロセスに関するコード +--- wait.c: プロセスの実行待ちに関するコード
データ構造
代表的なデータ構造は次の通りです。
struct task_struct: 個々のプロセス、スレッドを表します。
| フィールド名 | 意味 |
|---|---|
| state | プロセス管理の章で述べたスレッドの実行状態 |
| policy | スケジューリングポリシー |
| prio | 優先度(後述) |
| on_rq | スレッドがランキューに乗っていれば1以上(詳細は後述)。乗っていなければ0 |
| on_cpu | スレッドがCPU上で実行中なら1(このときstateは必ずTASK_RUNNING)、そうでなければ0 |
Linuxカーネルにおいてはプロセス内の個々のスレッドに対して1つの struct task_struct を持ちます。 Linuxのプロセススケジューラのスケジューリング単位はプロセスではなくスレッドです。例えば あるプロセスが5個のスレッドを持つ場合、Linuxカーネル内では5つのスレッドそれぞれに対して1つづつ、task_structが存在します。
struct rq: 各CPU上で実行可能になっているスレッドの一覧を管理するデータ構造。現在CPU上で実行中のカレントスレッドの次以降にスケジュールされる順に並んでいる優先度付きキュー構造をしている。CPU毎に存在する。
| フィールド名 | 意味 |
|---|---|
| nr_running | CPU上で動作中、あるいは動作待ちのスレッドの数 |
| clock | スケジューラの処理で現在時刻として使用する値。単位はナノ秒。現在時刻を知るために毎回ハードアクセスするとコストがかかりすぎるので、ここにキャッシュしている |
| dl | dl_sched_classに属するタスクが繋がるランキュー |
| rt | rt_sched_classに属するタスクが繋がるランキュー |
| cfs | fair_sched_classに属するタスクが繋がるランキュー |
struct sched_class: 各スケジューリングクラスに対応。プロセススケジューラの処理中に呼び出されるスケジューリングクラス固有のコールバックのリスト
| フィールド名 | 意味 |
|---|---|
| enqueue_task | スレッドがTASK_RUNNINGになったときに、スレッドをランキューに挿入する |
| dequeue_task | スレッドがTASK_RUNNINGでなくなったときに、スレッドをランキューから外す |
| check_preempt_curr | 指定したタスクが現在実行中のスレッドにプリエンプションできるかどうかを判定する。内部でプリエンプションが成功すれば後述のresched_curr()を呼ぶ必要がある |
| pick_next_task | ランキューから次にCPU上で実行するスレッドを選択する。内部で必ずput_prev_taskハンドラを呼ぶ必要がある |
| put_prev_task | 現在CPU上で実行中のスレッドをランキューに戻す |
| task_tick | タイムスライス切れを監視するために定期的に発生するタイマー割り込みの処理中に必要な処理 |
| task_waking | スレッドが起床中に必要な処理 |
| task_woken | スレッドが起床し終えた時に必要な処理 |
| select_task_rq | 後述のロードバランス用あるスレッドについて、所属しているCPUより負荷の高いCPUを探す |
| migrate_task_rq | 後述のロードバランス用。スレッドが現在所属するCPUから別のCPUに移動する直前に呼ばれる |
タイムスライス切れの監視
スケジューラはcurrentのタイムスライス切れを次のようなタイミングで監視しています。
- タイマーサブシステム定期的5に発生させるタイマー割り込みの延長。精度はカーネルビルドの設定によるが最高でも1ミリ秒。処理の入り口はscheduler_tick()
- プロセススケジューラが必要に応じて(後述)発生させる高精度タイマーの延長。 精度はナノ秒。処理の入り口はhrtick()。
これ以外にもスケジューラのコードの中では、ランキュー操作など、随所でupdate_rq_clock()を呼び出すことによって、currentのタイムスライス切れを細かく監視しています。
上記2つの関数は次のようなことをします。
- update_rq_clock(): rq->clockを更新
- current->sched_class->task_tick()ハンドラを呼ぶ。このハンドラは、タイムスライスが切れていたら、currentを切り替えるようにスケジューラに通知する
- (scheduler_tick()のみ) trigger_load_balance(): 必要ならばロードバランサを起動(後述)
プロセス切り替え
カーネルの中でスケジューリングが必要になったときにはschedule()が呼ばれます。この関数は次のような契機で呼ばれます。
- 現在CPUで実行中のスレッドが、IO待ちやカーネル内の資源待ちによってブロックされた
- タスク生成時/起床時のpreemptionやタイムスライス切れなどの理由によって、起床時のカーネル内の別の処理からスケジューリング要求があった(need_resched()がtrueになった)
この関数の中では、スケジューリング要求がある限り(need_resched()がtrueである限り)、スケジューリング処理の本体であるschedule()を呼び出し続けます。なぜこういうことをするかというと、schedule()の実行中にカーネル内の別の処理から再度スケジューリング要求が来ることがあるからです。再度のスケジュール要求を後回しにせずに、ここで処理することによって、スケジュール処理の実行タイミングが遅れないようにしています。
スケジューリング処理の本体である__schedule()について述べます。
__schedule():
rcu_note_context_switch: RCUサブシステムに、pが所属するCPUコンテキストスイッチ処理に入ったことを知らせる(RCUについては別の章で述べる)
sched_feat(HRTICK)は通常falseを返すのでhrtick_clear()は気にしなくて良い
if カレントスレッドはスリープ状態?(prev->stateがTASK_RUNNING(=0)以外)
if シグナルがpending?
カレントスレッドを再度実行可能状態にする -> 4に進む
else
deactivate_task(): カレントスレッドをランキューから外す
dequeue_task() -> カレントスレッド->sched_class->dequeue_task()を(登録されていれば)
pick_next_task(): 次に動作するスレッド(next)を選ぶ
clear_tsk_need_resched(): スケジューリングの必要が必要なNEED_RESCHEDフラグを落とす
if 次に動作するタスクがカレントスレッドと同じ(prev == nextが同じ)?
context_switch(): カレントスレッドprevからnextに切り返る => 終わり
スケジューリングクラスごとにキューを持つことを図示する
pick_next_task(): 次に動作するスレッド(next)を選ぶ
通常ほぼ全てのスレッドのスケジューリングクラスはデフォルトのfair_sched_classであることを利用した最適化処理。次に動かすスレッドの候補となる、現在ランキューに存在する全スレッドのスケジューリングクラスがfair_sched_classなら、fair_sched_class->pick_next_taskを呼び出して次に動かすスレッドを決める
if 次に動かすスレッドが見つかった? 当該タスクを次に動かすスレッドとして返して、終了 idle_sched_class.pick_next_task()を呼び出して、アイドルプロセスを次に動かすスレッドとして返して、終了 優先度の高いスケジューリングクラスのキューから順番にclass->pick_next_task()を呼び出して、次に動作させるスレッドを決める。pick_next_taskは、当該クラス用のランキューが空ならば、NULLを返す。この場合は次に優先度が高いスケジューリングクラスのpick_next_task()を呼ぶ。最低優先度であるidle_sched_classのpick_next_task()は、このスケジューリングクラスに属する唯一のスレッドであるアイドルプロセスを必ず返します
スケジューリングクラスの優先度 1. stop_sched_class: カーネル内の 2. dl_sched_class: SCHED_DEADLINE用 3. rt_sched_class: SCHED_RR|SCHED_FIFO用 4. fair_sched_class: SCHED_OTHER|SCHED_IDLE|SCHED_BATCHに対応 5. idle_sched_class: アイドルプロセス用
context_switch()
parepare_task_switch(): コンテキストスイッチ前に必要な各種サブシステム用、及びアーキテクチャ用の処理 arch_start_context_switch(): 準仮想化環境においてコンテキストスイッチ前に必要な処理 メモリ空間(mm)の切り替え。次に動くスレッドがカーネルスレッドなら(mm == NULL)、カレントスレッドのメモリ空間をそのまま使う switch_to(): アーキテクチャ固有の、実際にコンテキストスイッチをする処理。
switch_to()
このマクロそのものと内部で呼び出す__switch_to()関数を用いて、CPUのレジスタの値を現在のprevのものから、以前にnextのthread_infoに退避しておいた next のものに順次入れ替えます。その過程で、現在のレジスタの値をprevのthread_info に退避します。この関数から復帰するときには、nextが動作中のプロセスに切り替わります。
レジスタの値が入れ替わる様子の概念図
スレッドを待ち状態にする処理
スレッドを待ち状態にするには待ちキューという仕組みを使います。待ちキューを使用する流れは次の通りです。
prepare_to_wait(): 実行中のスレッドを待ちキューに登録した上で、当該スレッドを待ち状態にする(対応するstruct task_structのstateをTASK_INTERRUPTIBLE|TASK_UNINTERRUPTIBLEにする)。 schedule()によって、スレッドからCPUを手放させて、ランキューから外す。ここで一旦スレッドは待ち状態になる。 (別のスレッドから非同期に呼び出される) wake_up(): 別のスレッドによって待ちキューから外され、実行可能状態になる finish_wait()によって、待ち状態終了後の後処理をする。
データ構造
wait_queue_head_t: 所定のイベントを待つスレッドを繋げるためのキュー
| フィールド名 | 意味 |
|---|---|
| task_list | キューに繋がっているスレッドのリスト。後述のwait_queue_tを介してスレッドを繋げる |
wait_queue_t: 待ちキューに繋がるスレッドを表す
| フィールド名 | 意味 |
|---|---|
| task_list | wait_queue_head_t->task_listに繋がる |
| func | 待ちが状態解けた際に呼ばれる。デフォルトはautoremove_wake_function() |
| private | func()を呼び出す時に引数として渡される。デフォルトはcurrent |
prepare_to_wait()
void prepare_to_wait(wait_queue_head_t *q, wait_queue_t *wait, int state)
待ちキューqに、currentに対応するwaitを繋ぎ、current->stateをstateに設定します。
wake_up(q)
待ちキューqで待っているスレッドのうち、キューの先頭に繋がっているスレッドに対応するwait_queue_tのfunc()ハンドラを呼び出して、qから当該スレッドを登録解除します。
wake_up()には、指定した数のスレッドを起床させるwake_up_nr()やwake_up_all()などの多くの変種があります。
autoremove_wake_function()
int autoremove_wake_function(wait_queue_t *wait, unsigned mode, int sync, void *key)
default_wake_function(): 後述するtry_to_wake_up()を呼び出して、スレッドを起床させる waitを待ちキューから外す
finish_wait()
void finish_wait(wait_queue_head_t *q, wait_queue_t *wait)
current->stateをTASK_RUNNINGする。デフォルトではここに来る前にtry_to_wake_up()の延長で既にTASK_RUNNINGになっている。 waitを待ちキューqから外す。デフォルトではここに来る前にautoremove_wake_functionの中で既にqから外れているので何もしない。
スレッドを起床させる処理
待ち状態のスレッドを起床させる処理の本体がtry_to_wake_up()です。
static int try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
この関数は、スレッドがスリープしていれば、起床させてランキューに挿入します。成功すれば1を、失敗すれば0を返します。引数の意味は次の通りです。
- p: 起床させようとするスレッド
- state: p->stateがこの引数で指定したマスクに入っていたときのみ起床させる
- wake_flags: この関数の挙動を制御するための種々のフラグ。後述
処理の流れは次の通りです。
1. p->state & stateが真なら先に進む。そうでなければ終了
if pはスリープ状態だがまだランキュー上にいるか?
ttwu_remote(): pを実行可能状態にする。失敗すれば2.2へ
ttwu_do_wakeup(): pを実行可能状態にする
pのCPU上で実行中のスレッドへのpreemptを試行(check_preempt_curr())
pを実行可能状態にする(p->stateをTASK_RUNNINGにする)
p->sched_class->task_woken()ハンドラを(登録されていれば)呼ぶ
else
p->stateをTASK_WAKINGにする
p->sched_class->task_waking()ハンドラを(登録されていれば)呼ぶ
必要ならばロードバランスによってpを別のCPUに移動させる
ttwu_queue()を呼んでタスクを起床させる
ttwu_do_active(): 内部でp>sched_class->enqueue_task()ハンドラを呼ぶことによって、pが所属するcpuのランキューに挿入して実行可能状態にする。
ttwu_activate: pを、pが所属するcpuのランキューに挿入する
ttwu_do_wakeup():
プリエンプション
スレッドがfork()によって生成されたときや、スリープ状態から起床した際などには、実際にCPUを使えるようになるまでランキュー内で待機します。ただし、所定の条件を満たせば、CPU上で現在動作中のスレッドに取って代わって、当該スレッドが即座に動作開始できることがあります。これをプリエンプションと呼びます。
check_preempt_curr()
この関数は、指定したスレッドから、当該スレッドが所属するCPU上で現在実行中のスレッドへのプリエンプショを試行します。この関数の挙動は次の通りです。
| 条件 | 挙動 |
|---|---|
| pのスケジューリングクラスとpが所属するCPU上のカレントスレッドのそれが同じ | 当該スケジューリングクラスのcheck_preempt_curr()ハンドラを呼び出す。ハンドラ内ではプリエンプションが成功すればresched_curr()を呼ぶ |
| 前者よりも後者のほうが優先度が高い | 必ずプリエンプションしない |
| 前者のほうが後者よりも優先度が高い | 必ずプリエンプションする。resched_curr()を呼び出す |
resched_curr()
if 処理を実行中のCPUは、プリエンプションするスレッドが属するCPUと同じか?
NEED_RESCHEDを立てる
else
NEED_RESCHEDを立てる
if アイドルプロセスがNEED_RESCHEDを監視しているか?
exit
else
プリエンプションしたスレッドにIPIを飛ばしてNEED_RESCHEDが立ったことを通知
プリエンプトした後にコンテキストスイッチが起きるタイミング
次のようなタイミングで発生します。
cond_resched()は、NEED_RESCHEDが立っている場合のみschedule()を呼びます
fairクラスの実装
データ構造
ランキュー(struct cfs_rq)
| フィールド名 | 意味 |
|---|---|
| load | ロードバランスに使用する、このランキューの負荷 |
| nr_running | このランキュー上のTASK_RUNNINGなスレッドの数 |
| tasks_timeline | fair_sched_classを使ってスケジューリングする実行可能スレッドが繋がるランキュー本体(データ構造は赤黒木) |
| rb_leftmost | ランキュー内から次回選択されるスレッドに対応するノード |
| curr | 当該ランキューが担当するCPUで現在実行中のスレッド |
| min_vruntime | このランキューに属する全スレッドの中での最小のvruntime |
スケジューリング対象(sched_entitry)
CFSにおけるスケジューリング対象です。別の章で説明するcgropuについて考えなければtask_structと1対1対応していると考えてもらっていいです。
| フィールド名 | 意味 |
|---|---|
| load | ロードバランスに使用する、entityが持つ負荷(後述) |
| vruntime | ナノ秒単位の仮想的な実行時間(後述) |
| cfs_rq | 自分が所属するCFSランキュー |
vruntime
CFSで管理されるスレッド(正確にはそれに対応するsched_entity)は、上記のように各自vruntimeという値を持っています。この値は、スレッドの仮想的な累計実行時間を指しており、次のような特徴があります。
- 各スレッドのvruntimeは、レイテンシターゲットの間にスレッドが与えられたタイムスライスだけ動作すると、レイテンシの長さだけ動作したように増加する値である。
- 上記の理由により、レイテンシの倍数の実時間において、ランキュー上の全てのスレッドのvruntimeは等しい
- vruntimeは、当該スレッドがCPU上で動作している間に、スケジューラ処理の各所において、随時現在時刻に更新される
- CFSはvruntimeが小さいスレッドから順番にCPUを割り当てる
以下に具体例を出します。
- latencyは20ミリ秒
- T0,T1という2つのスレッドが存在する(つまりタイムスライスは"20/2=10"ミリ秒)
- T0,T1は常に実行可能状態(スリープしない)
- T0,T1の実行時間はt0,t1
- T0,T1のvruntimeはv0,v1。初期値はそれぞれ0ミリ秒
この場合、実時間の経過と共に、2つのスレッドの実実行時間及びvruntimeは以下の表のように変化します。表の中の数値の単位はすべてミリ秒です。 v0,v1が同じ値の場合はどちらが先に動いてもいいのですが、ここでは仮にt0が先に動くものとします。
| 実時間 | t0 | t1 | v0 | v1 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 10 | 10 | 0 | 20 | 0 |
| 20 | 10 | 10 | 20 | 20 |
| 30 | 20 | 10 | 40 | 20 |
| 40 | 20 | 20 | 40 | 40 |
ここで、latencyの倍数の時間において(0,20,40ミリ秒時点)は次のことが言えます。
- それぞれのタスクが平等に動作している(t0,t1が等しい)
- vruntime(v0,v1)は現在時刻に等しい
- vruntimeはタイムスライスを使い切った段階で、latencyの倍数になるように調整されている。言い方を変えると、与えられたタイムスライスだけ動作すると、latencyだけ動いたように調整される。
t1が実時間でいう0ミリ秒から20ミリ秒まで待ち状態だった、あるいは20ミリ秒時点で新規生成された場合はどうなるでしょうか。この場合は、当該スレッドがランキューに挿入された時点で、スレッドのvruntimeがランキューのmin_vruntimeまで切り上げられます。こうしておかないと、このようなスレッドが起床/生成直後に大量にCPUを独占してしまいます。具体的には次のような挙動になります。
| 実時間 | v0 | v1 |
|---|---|---|
| 0 | 0 | 0|0|0 |
| 10 | 10 | 0|10|0 |
| 20 | 20 | 0|20|20| <- ここでT1が起床 |
| 30 | 30 | 00|40|20 |
| 40 | 30 | 10|40|40 |
この場合も、latencyの倍数の時間において(0,20,40ミリ秒時点)、次のことが言えます。
- 1回のレイテンシの範囲では全スレッドが実時間的に平等に動作している、および、
- vruntimeが全て実時間に等しい値になっている
上述したCFSのスケジューリングの仕組みをそのまま使うと、実行可能なタスクが大量に存在する場合に、コンテキスト スイッチによるオーバーヘッドが無制限に大きくなってしまいます。例えば latencyが100ミリ秒でスレッドが1,000個あった場合、各スレッドは一度に"100/1,000=0.1"ミリ秒、つまり100マイクロ秒しか 動けません。仮にコンテキストスイッチのコストを10マイクロ秒とすると(もちろん実際の値はシステムによって異なります)、 コンテキストスイッチだけでCPUリソースの10%を食い潰してしまいます。これを防ぐためにmin_granularityという値が存在します。 "latency/実行可能タスク数 < min_granularity"の場合、実際のlatencyも"min_granularity*スレッド数"になる(sysctlパラメタの値は変わらない)と共に、 各スレッドのタイムスライスはmin_granularityになります。
スリープ状態から起床したスレッドは、動作直後に短時間だけCPUを使ってまたスリープするという傾向にあります。それが顕著なのが shellなどの対話型のスレッドです。システムの応答性を上げるためには、これらスレッドの応答性を上げる必要があります。そのためにCFSは、 スリープ状態から起床したスレッドのvruntimeが現在実行中のスレッドのそれより少なければ、前者は後者をpreemptできるという仕組みになっています。
ただし、この仕組みをそのまま使ってしまうと、スリープと起床を繰り返すようなスレッドが大量に存在する場合に、preemptによるコンテキストスイッチが 大量に発生すると共に、そのオーバーヘッドも大きくなってしまいます。本パラメタはそれを防ぐために存在します。latencyで定められた期間の中で、 起床したスレッドの実行時間が現在実行中のタスクのそれよりもwakeup_granularityだけ少ない場合のみpreemptできるようになっています。
vruntimeの型は符号なし64ビット型(u64)かつ単位がナノ秒なので、(264)/(109)/60/60/24/365~=586年後にオーバーフローします。これだけあればまず問題ありません、かつ、vruntimeの各種計算はオーバーフローを考慮したものになっています。
fair_sched_classのハンドラ
スケジューラのコアコードから呼び出されるfair_sched_classのハンドラの定義を次に述べます。
enqueue_task_fair(fair_sched_class.enqueue_task)
static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
cgroupが無い場合は、2つあるfor_each_sched_entity()のループは、一つ目のループが冒頭で"&p->se"に設定したseに対して一回呼び出されるだけで、2つ目のループは実行しません。
enqueue_entity():
update_curr():
currentが最後にCPU時間を得てから現在までの時間をvruntimeの単位に変換したもの(calc_delta_fair(delta_exec,curr))をcurrentのvruntimeに加算する
update_min_vruntime(): cfs_rq->min_vruntimeを、currentおよびcfs_rqに入っているスレッドすべての中の最小値に設定
if (スレッド起床時のenqueueか)
place_entity: pのvruntimeを更新。
if (スレッドがカレントスレッドではない)
__enqueue_entity: p->seをcfs_rq->tasks_timelineキューに挿入
- hrtick_update(): currentのスケジューリングクラスがfair_sched_classであれば、スレッドpのランキューrqへの更新に伴うcurrentのタイムスライス変化に応じて、高精度タイマーの起動時期を早める。
dequeue_task_fair(fair_sched_class.dequeue_task)
check_preempt_wakeup(fair_sched_class.chech_preempt_curr)
update_curr() if (wakeup_preempt_entity: current->se->vruntime > sched_wakeup_granularityをvruntimeに変換した値(calc_delta_fair(sysctl_sched_wakeup_granularity))) プリエンプション成功。resched_curr()を呼ぶ
pick_next_task_fair(fair_sched_class.pick_next_task)
update_curr(): pick_next_entity(): ランキューから次に動作させるスレッドを選択する put_prev_entity(): prevをランキューに戻す set_next_entity(): pick_next_entity()で選択したタスクをcurrentにする hrtick_start_fair(): currentのタイムスライスを計算して、その時刻に高精度タイマーが動作させるよう設定する put_prev_task(): 内部でprev->sched_class->put_prev_task()ハンドラを呼び出す
put_prev_task_fair(fair_sched_class.put_prev_task)
if (prevは実行可能状態) update_curr() __enqueue_entity(): ランキューにprevを挿入 update_entity_load_avg: ロードバランスに用いるprevの負荷の再計算
task_tick_fair(fair_sched_class.task_tick
entity_tick()
update_curr()
update_entity_load_avg()
if (hrtick()から呼ばれた)
resched_curr()
exit
if current以外にRUNNABLEなタスクがいる)
check_preempt_tick: タイムスライス切れによるプリエンプションを試行
if (currentのタイムスライスが切れた || currentのタイムスライスがmin_guranularity以上、かつ、vruntimeがランキュー先頭のタスクのvruntime以上)
resched_curr()
select_task_rq_fair(fair_sched_class.select_task_rq)
migrate_task_rq_fair(fair_sched_class.migrate_task_rq)
rtクラスの実装
データ構造
ランキュー(struct rt_rq)
エンティティ(sched_rt_entitry)
クラス関数
idle_sched_classのハンドラ
dequeue_task_idle(idle_sched_class,dequeue_task)
アイドルプロセスが待ち状態になることはありえないので、警告メッセージ及びスタックトレースを出す。
check_preempt_curr_idle(idle_sched_class.check_preempt_curr)
resched_curr()
アイドルプロセスは他のあらゆるスレッドより優先度が低いので、必ずプリエンプションが成功する
pick_next_task_idle(idle_sched_class.pick_next_task)
put_prev_task()
仕様に定められていることをするだけ
task_tick_idle(idle_sched_class.task_tick)
アイドルプロセスにはタイムスライスの概念が無いため、何もしない
select_task_rq_idle(idle_sched_class.select_task_rq)
アイドルプロセスの処理
cpu_idle_loop():
while (true)
__current_set_polling(): スケジュール要求をidleがポーリングする設定にする
while (!need_resched())
if (アイドルプロセスがポーリングモードか(上記のスケジュール要求についてのポーリングとは別物)
cpu_idle_poll()
else
cpuidle_idle_call()
__current_clr_polling(): スケジュール要求をidleがポーリングする設定を解除する
大きく分けて2つの処理のどちらかを実行している。どちらを呼ぶかは設定可能
cpuidle_idle_call(): スリープ状態で他のタスクが起床するのを待つ。消費電力小
ocpuidle_get_cpu_driver(): 目的別に定義されているアイドル処理のドライバを選択する if (スケジュール要求がある(NEED_RESCHEDが立っている) exit CPUをどのようなstateに落とすか設定する(x86でいうとCステート) if (current_clr_poloing_and_test() スケジュール要求をpollingする設定になっており、かつ、スケジュール要求が来ていれば、 cpuidle_enter(): CPUを、上記処理で設定したstateに設定してスリープさせる __current_set_polling():
cpu_idle_poll(): スリープ状態に入らないまま他のタスクが起床するのを待つ。消費電力大
while (!need_resched()) cpu_relax();
概要
CPU間の負荷が偏っていると、同じ優先度のスレッドが動作できる量が減って不平等が発生します。 これを避けるために、後述する様々な契機でタスクをCPU間移動させることによって、CPU間の 負荷分散をします。
どのような契機でどこのCPUに移動できるかは struct sched_domain という構造体の ツリーによって表現されます。
| フィールド名 | 意味 |
|---|---|
| parent | 親ドメイン |
| child | 子ドメイン |
| groups | ドメイン内に所属するグループ(後述)のリスト |
| flags | どの契機でタスクをCPU間移動させるかを示す |
| balance_interval | 定期てきに動作するロードバランス処理の動作周期(可変) |
| min_interval | 上記処理の最短動作周期 |
| max_interval | 上記処理の最長動作周期 |
sched_domainには次のような種類があります。
- NUMAノード間のロードバランスをするもの
- NUMAノード内のCPUソケット間でロードバランスするもの
- CPUソケット内のコア間でロードバランスするもの
- コア内のスレッド間でロードバランスするもの
例えば非NUMA環境で2ソケット、2コア,ハイパースレッド無しの場合は次のような構造になります。
それぞれのドメインについて、flagsフィールド内の各フラグに示される契機でロードバランスが 発生します。
| フラグ | 意味 |
|---|---|
| SD_LOAD_BALANCE | 定期的なロードバランス処理を動かす |
| SD_BALANCE_NEWIDLE | CPUがアイドルになる瞬間 |
| SD_BALANCE_EXEC | プロセスのexec時 |
| SD_BALANCE_FORK | プロセスのfork時 |
| SD_BALANCE_WAKE | プロセスの起床時 |
同一コア内のハイパースレッド間のスレッドの移動はコストが小さいため、フラグはたくさん立っています。 その一方NUMA ノード間のスレッドの移動は、移動後にスレッドはリモートメモリを使わなくてはならなくなるなど、 コストが高いので、少ししかフラグが立っていません。 # 後でもっと具体的に書く
各CPUのスケジューラドメインを管理するために、struct rqには次のようなフィールドがあります。
struct rq:
| フィールド名 | 意味 |
|---|---|
| rd | rootスケジューラドメイン |
| sd | このランキューが属するスケジューラドメイン(後述) |
定期的に動作するロードバランサ
softirq処理の延長で、定期的にドメイン内のロードバランスをする処理が動作します。 基本的には下層のドメインのロードバランス処理のほうが、上層のドメインのロードバランス処理より 頻繁に動作します。
ここでドメイン内のグループ(struct sched_group)という概念が登場します。
| フィールド名 | 意味 |
|---|---|
| next | 同じドメイン内のグループを接続する単方向循環リスト |
| cpumask | グループに属するCPUの一覧を示すビットマスク |
たとえば、最近のPCやスマートフォンでよくある、非NUMA, 1CPU、4コア、1スレッドの環境で、4つのCPU(0-3)という構成では、次のようなドメイン/グループの構造ができます。
2ノード、ノードあたり2CPU、2コア、2スレッドというような高価サーバマシンでは次のようになります(最近の実際のサーバマシン用CPUは通常もっとコア数が多いですが)。
このドメイン内をバランスする処理は、
ここでいう負荷とは、nice値などによって色々修正されますが、基本的にはタスクの数だと思って下さい。 なお、グループ間の負荷が 1 スレッド分程度であれば、移動はさせません。なぜかというと、この程度の 負荷の差で移動させると、負荷の差が小さいような場合は頻繁にスレッドがCPU間を移動してコストが高く なってしまうからです。このため、ある程度のしきい値を超える負荷の差が無いと移動はさせません。
deadlineクラスの実装
データ構造
ランキュー(struct dl_rq)
エンティティ(sched_dl_entitry)
クラス関数
スケジューリング関連システムコール
sched_getattr, sched_setattr
nice
（affinityの概念も） sched_getaffinity, sched_setaffinity
sched_yield
sched_rr_get_interval
謎のコンテナランタイムlinuxd
はじめに
本記事はLinux Advent Calenda 2018の最終日、25日目の記事です。
ここ数年、一つないし複数のプロセスから成るアプリをコンテナと呼ばれるサンドボックス上で動かすのが流行っています。このときアプリを動かす実行環境のことをコンテナランタイムと呼びます。このコンテナランタイムには例えば次のようなものがあります。
- runC: アプリをそれぞれ別々のnamespace上で実行。カーネルは全アプリで共有。世間的に「コンテナ」というと今はだいたいこれを指す
- Kata Containers: アプリを個々のアプリ専用VM上で実行
- gVisor: アプリをユーザ空間で独自実装されたLinuxカーネルのサブセット上で実行
本記事は最近筆者が気になっているlinuxdというコンテナランタイムについて簡単に紹介したいと思います。
何がどう"謎"なのか
タイトルに「謎の」と書いているのは、後述の通り世の中に情報がほとんど出回っていないからです。私の知る限り、linuxdが初めて表に出たのは2018年のLinuxCon Chinaであり、そのあとOpen Source Summit 2018 North Americaでも発表があったようです。スライドはこちら。で、いまのところ世に出ている情報は悲しいことにこれだけです。
スライドにも細かい実装の話は載っていないので、本記事は「たぶんこうではなかろうか」という推測をもとに書いていることをあらかじめお断りしておきます。「いやその解釈はおかしいだろう」「たぶんほんとはこうなっているはず」などの突っ込みお待ちしています。
概要
linuxdとはユーザ空間で動作するlinuxカーネル上でアプリを動かすコンテナランタイムです。将来的にはOCIやCRIに準拠したランタイムになる予定だそうです。
上記のさまざまなコンテナランタイムのうち、ユーザ空間で動作するカーネル上で実行するという意味で、linuxdはgVisorに似ています。これ以降は主にgVisorとの比較という形でlinuxdがどのようなものなのかについて述べます。
linuxdはgViorとは異なりカーネルは独自実装のものではなく、linuxそのものに少し手を加えたものです。どのような手を加えているかについては次節で述べます。
linuxdの作者はユーザ空間カーネルを独自実装ではなくlinuxベースにする利点として、次のようなものを挙げています。
- 成熟したlinuxのコードベースを利用できる
- 現在はupstreamのlinuxに独自パッチを当てているが、将来的にupstreamに取り込まれれば以後のカーネルアップデートに自動的に追従できる
- アプリを一切改変せずに動作させられる。gVisorはlinuxの全機能をサポートしているわけではないのでアプリを動作させるためには改変が必要なことがある
linuxカーネルの変更点
linuxdにおいて動かすユーザ空間カーネルはupstreamのlinuxカーネルそのものではなく、それに3つの変更を加えたものです。以下それぞれについて説明します。
アドレス空間操作処理
ユーザ空間カーネル上でアプリを動かすためには、ユーザ空間カーネルがアプリ内の個々のプロセスのためにアドレス空間を作る必要があります。かつ、その後アドレス空間に変更があったときにもユーザ空間カーネルが処理してやる必要があります。詳細は省略しますが、gVisorのようにupstreamカーネルの機能を使ってこれを実現しようとすると、これらの処理のためにユーザ空間カーネルからカーネルに対して大量のシステムコールを発行する必要があります。
これに対してlinuxdにおいては、上記のようなアドレス空間の操作専用システムコールをupstreamカーネルに追加しました。これによってアドレス空間の操作にかかるコストを削減しました
システムコールや例外の横取り処理
ユーザ空間カーネル上でプロセスを動かすためには、アプリ内の各プロセスの動作中にシステムコールの発行や例外が発生したことをユーザ空間カーネルが認識し、処理してやる必要があります。gVisorではこれをptraceシステムコールを使ったカーネル処理の横取りによって実現しています1。ところがこれには複雑な処理が必要なため、非常に低速です。
注意: 本節のここからの部分は冒頭にリンクを張った"Containerize Linux Kernel"というスライドの中の以下の部分から推測しました。
update code on the path for syscalls and exceptions for the new ASes
これに対してlinuxdにおいては、ホストカーネルのシステムコールの入り口部分に変更を加えていると考えられます。ホストカーネル上で直接動作しているプロセスがシステムコールを発行したときは従来通りの動作をします。その一方でlinuxdから立ち上げられたプロセスの場合は、linuxdのユーザ空間カーネルにシステムコールの処理を委託します。linuxdは委託されたシステムコールを実行した上でプロセスに制御を戻します。
この一連の処理はptraceを使う場合に比べて少ない手番で済むので高速、ということでしょう。
ユーザ空間カーネルとホストカーネル間のインターフェース
ユーザ空間カーネルはシステムコールを処理する必要ができたときに、処理が自分自身の中で完結できればそうするのですが、そうではないとき、たとえば物理ハードウェアにアクセスしなければいけないときなどにはホストカーネルに処理を委託します。
本節のここからの部分は元スライドの以下の部分を元に推測しました。
Reduced Attack Surface to Host Kernel - No Hardware ABIs - Limited linux ABI with host kernel, less than 30 sysalls or even less - Limited usage of host kernel functionalities
linuxdにおいてはホストカーネルのうち、ハードウェアを操作する部分はホストカーネルに処理を委託するシステムコール発行に置き換えていると考えられます。このとき使用するシステムコールは必要最小限にしておき、かつ、使っていないシステムコールはseccompによって実行不能にしておくことによって堅牢性を高めているはずです。
おわりに
ユーザ空間でlinuxカーネルを動かすというlinuxdのアプローチはなかなかアツいアイデアに見えます。ただし、Linuxには遥か昔からこれとかなり似たUser Mode Linux(UML)という機能がありました。UMLについてはスライドの中でも次のように言及がありました。
Its experimental stage has started for about 1 year, spawning PoC product based on UML showed the approach workable.
個人的にはUMLの性能向上および拡張ではなくlinuxdという新規のプロジェクトにしている理由がよくわかりませんでしたが、これまでに述べた通り謎が多いので実際のところはよくわかりません。近いうちに上記のような私の理解を発表者にして確認してみようと思っています。回答をもらえて、かつ、公開可能であれば本記事を更新する予定です。
OSSの継続性を推測する基準の例
はじめに
みなさんは自分が欲しい機能を持ったOSSを見つけたものの「使っているうちに開発が止まったりしないだろうか」と思ったことはないでしょうか。あるいは似たような複数のOSSのうちのどれを採用するかという選択を迫られて悩んだ経験はないでしょうか。筆者はどちらもよくあります。本記事はこのようなときOSSの継続性が高いかどうか(言い方を変えると今後も開発が続きそうかどうか)を推測するための筆者の基準についていくつか紹介します。題材とするのはgolangのデバッガとして知られる二つのソフトウェア、delveとgodebugです。
delveとgodebugはそれぞれ2014年5月と2015年という比較的近い時期に誕生した(initial commitされた)、golangで作られたプログラムのデバッガです。ソースコードの規模も数千行と、それほど違いはありません。現在前者は勢いよく開発中、後者はREADMEに「非推奨。今後開発は続かないからかわりにdelveを使ってね(意訳)」と書いてあるという違いがあります。これから両者のgitリポジトリから得られる情報をもとに、それぞれが誕生してから現在までにどのように変化してきたのかを紹介しつつ、上記の基準を紹介いたします。
コミット数の推移
OSSの勢いを測る指標のひとつにコミット数の推移があります。単に絶対数というわけではなく推移というのがポイントです。
delveがinitial commitされた2014年5月から2018年8月までの2つのプロジェクトのコミット数の推移を次に示します。
delveは誕生時から現在にかけて開発が絶え間なく続いていることがわかります。このようなOSSは継続性が高いと期待できるため、採用しやすいと筆者は考えています。
godebugについては誕生から数か月間は一時的にdelveよりもコミット数が多いことがありましたが、すぐ順番が入れ替わってからその後は勢いを取り戻すことはなく2015年の後半以降はほぼ開店休業状態になってしまいました。このようなOSSを選ぶのは今後の機能追加もバグ修正も期待できないため、採用するリスクが高いです。実際に、久しぶりにコミットした2017年には上記のREADMEの「delveを使ってね」という文言を追加しています。
なおコミット数はあくまで目安なので、複数のOSSから1つを選択する場合にコミット数の多少の違いを気にして「このOSSが一番コミット数多いので採用！」とするのは早急です。とくに2つのソフトウェアのソース規模が違う場合はコミット数を単純比較しても意味がないです。
コミッタ数の推移
コミット数だけではなくOSSの開発にかかわっているコミッタ数の推移も重要な指標です。以下にコミット数の推移と同期間におけるそれぞれのOSSについてのコミッタ数を示します。
delveは定期的に複数人がコミットしているのに対してgodebugはオリジナル作者がほとんど一人で頑張っているということがわかります。一人での開発はどうしても多人数開発の場合に比べて人的資源の問題で開発速度が遅くなりがちです。さらに作者が飽きたり、あるいは他のことで忙しくなるなどの理由によって開発を継続できなくなると、そのOSSの開発そのものが止まる可能性もあります。仮にコミット数が多くてもコミッタ数が少ないOSSは相対的に将来開発を継続できなくなるリスクが高いと筆者は考えます。
その他の観点
delveやgodebugは該当しませんが、大手の会社が資本を投入しているか、開発に参加しているか(コミッタのメールアドレスを見ればわかる)」というのも継続性を推測するのに重要な要素です。他にもいろいろあるのですが、全部書いていたらきりがないのでこのあたりでやめておきます。
おわりに
本記事を通じて「OSSの継続性を推測するにはこういう観点があるのか」ということがなんとなくわかっていただければ幸いです。
なお、ここまで主にユーザからの視点で記載してきましたが、自分が使いたいOSSの開発を継続するためにはみなさん自身ができる範囲でいいのでそのOSSのコミュニティになんらかの貢献(issueの発行、コードやドキュメントの提供)をするのがとても重要です。実際に、重要かつユーザが多いものの資金難や開発者が少ないことによって継続の危機にあるOSSはいくつもあります。
Linuxカーネルに関する独自コードをメンテナンスするコスト
はじめに
Linuxカーネル(以下カーネル)に機能を追加する、あるいはバグを修正する自作コードには次の2つの種類があります。
これらの変更を長期間メンテナンスするには次の方法があります。
- Linux開発コミュニティに働きかけて独自コードを公式のmainlineと呼ばれるツリーにコードをマージする
- 独自コードを自分自身で管理して、mainlineカーネルの新バージョンが出るたびに追従する(後述)
本記事は前者の方法に比べて後者の方法をとった場合に必要なメンテナンスコストについて述べます。本記事の表題にはlinuxと書いていますが、linuxと似たようなドラスティックな変更(後述)を是とするソフトウェアすべてに当てはまる話なのでlinuxの開発には関係ないかたにも役立つ話かと思います。
独自カーネルモジュールを作る場合の追従コスト
昨日書いたエントリで述べたように、カーネルは外部インターフェース(ユーザ空間とのインターフェース)は基本的には変えませんが、内部インターフェースは変わることがままあります。インターフェースを変更するときはmainlineにマージされれているコードについては、インターフェースを変更した人やサブシステムメンテナなど1が責任を持って新しいインターフェースに置き換えます。
このときmainlineにマージされていないコードに対する配慮はありません。したがって、ある時点のカーネルバージョンに対応する独自カーネルモジュールを作っており、それが問題なくビルドできていたとしても、そのモジュールが使っているインターフェースがその後に変更された場合、それはビルドできなくなります。このため独自カーネルモジュールを新しいバージョンに追従するためのコストがかかります。さらに独自モジュールのコード量は時を経るほど増えていくので、一回の追従に必要なコストは増える一方です。
複数バージョンに対してモジュールをメンテナンスしなければいけない場合は、古いバージョンのモジュールに対して新しいバージョンの変更をバックポートしないといけないので、どんどん追従が困難になっていきます。
これを続けると、自作コードの量(ここではパッチの数)が増えるにつれて、および、追従すべきカーネルの数が増えるごとに追従コストが爆発的に増えていくことがわかっていただけると思います。
カーネル本体を変更する場合の追従コスト
カーネル本体を変更する場合は前節において説明した独自カーネルモジュールのメンテナンスにかかるコストに加えて、別のコストもかかります。カーネル内インターフェースが変わらなくても、関数内の処理論理が書き換えられることがあります。このときは既存カーネルに対する変更を新しい処理論理に合わせて変更する必要があります*1。
複数のmainlineカーネルバージョンに対して変更部分を管理しなくていけない場合、上記のコストに加えて、古いバージョンに対して新しいカーネルに入っている重大バグの修正パッチもバックポートし続ける必要があります。これらの修正はパッチ数でいうと1バージョンごとに数百、数千個にも及びますので、大量の人的資源が無いと現実的ではありません。
バックポートのコストはstableカーネルというものを使えば減らせます。linuxには各バージョンのmainlineカーネルに対して、より新しいカーネルからの重大なバグ修正パッチをバックポートしたstableカーネルがしばらくの間提供されます。これを利用すれば、古いカーネルについては新しいstableカーネルが出るたびに、その上に独自コードのパッチを(必要であれば変更した上で)当てたものを使えば、相当バックポートコストが減らせます((stableカーネルに似たような長期間サポートされるカーネルは他にも色々ありますが、それらについての説明は省略します)。ただしそれもstableカーネルが出る期間が終わるまでです。それ以降は自分でなんとかする必要があります。
上記の図の中では、見やすさのために新しいカーネルからのバックポートのためのコード量を少な目に表現していますが、実際には独自コードよりもはるかに大きいことにご注意ください。
バックポートコストを減らすためには、stableカーネル以外にも、ある時点でのstableカーネルをもとにディストリビューション独自の変更をしたディストリビューションカーネルをベースにするという方法もあります。ただしここで一点注意があります。ディストリビューションが提供するカーネルは独自パッチを当てるとサポート対象にならなくなります。商用ディストリビューションのサポートを受けているかたは、独自コードを使いたければmainlineに取り込んだ上でディストリビュータに取り込み依頼をしなければなりません。
mainlineにマージすべきか否か
これまでの記述によって「では必ずmainlineにマージすべきなの？」と思うかもしれませんが、必ずしもそうとも限りません。前述の追従コストに比べてmainline化のコストが高くなるような場合は、あえて独自管理をすることもありえます。その他にも、コードを一般公開したくないなどの理由によってmainline化をしない選択をする場合もあります。
おわりに
本記事で書いたことは一度体験してみないとなかなかわからないため、これまでに様々な組織が独自管理を選択した後に収集がつかない状態になった結果、独自コードのmainline化を基本方針にするようになりました。本記事を読むことによって、みなさまが先人達の轍を踏むことなく独自コードの将来的な管理コストについて学んでいただければ幸いです。
-
サブシステムメンテナがみなさん自身なら自分で書き換えなければいけないこともありますが…↩
*1:場合によっては当該パッチが不要になることもあります
Linuxのプロセススケジューラから見たSocionext SC2A11
はじめに
本記事はSocionext SC2A11のキャッシュメモリ構成の続きです。今回はLinuxのプロセススケジューラにはこのCPUがどのように見えているかについて調べました。
まずは前提知識としてLinuxカーネルのプロセススケジューラに存在するロードバランサという機能について説明します。その後に、ロードバランサからSC2A11がどのように見えているのかについて記載します。
ロードバランサ
システムに複数の論理CPU(1つのコア、あるいはSMT(1)が有効なら1つのスレッド)が存在する場合、Linuxのプロセススケジューラの中のロードバランサという機能がそれぞれの論理CPU上のプロセス数を平均化しようとします2。
たとえば1ソケット4コア、つまり4論理CPUのシステムにおいて実行可能プロセスが4つ存在する場合、1つの論理CPUに4つのプロセスが偏るようなことはなく、それぞれの論理CPUにプロセスが1つづつ割り振られます。一時的にそのようなことになる可能性はありますが、すぐに解消されます。
ロードバランサが単純に全論理CPUを平等に扱って負荷分散すると問題が発生します。たとえば2コア2プロセスの4論理CPUシステムについて考えてみましょう。論理CPU0,1と2と3がそれぞれ同じコア内の2スレッドとします。このとき実行可能プロセスが2つあるとすると、論理CPU0と1にプロセスが割り振られて、2と3がアイドルという状況が考えられます。
ペアになっているスレッドはほとんどのハードウェア資源を共有するため、現実的なワークロードの場合、2つのスレッド上に両方プロセスが動作している場合の性能は片方のスレッドにだけプロセスが存在する場合の高々1.5倍程度です。したがって、この場合は論理CPU0と1のいずれかに1つのプロセスを、論理CPU1と2のいずれかに1つのプロセスを割り振るほうがCPU資源を有効に使えます。
ロードバランサはCPU資源を有効に使うためにハードウェアから与えられた情報をもとにして論理CPUの階層構造を作り出し、上の階層から下の階層に順番に負荷分散します。それぞれの階層のことをスケジューラドメインと呼びます。たとえば前述の2コア2スレッドのシステムの場合は
という処理論理になっています。スケジューラドメインの階層構造は/proc/schedstatを見ればわかります。詳細については次節において述べます。
SC2A11の場合
SC2A11の/proc/schedstatの中身は次のようになっていました。
$ cat /proc/schedstat cpu0 0 0 0 0 0 0 40778266780070 212490834550 257123 domain0 000003 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 cpu1 0 0 0 0 0 0 6518877752440 6168684830 155606 domain0 000003 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 cpu2 0 0 0 0 0 0 2042515035170 7070977990 189374 domain0 00000c 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 cpu22 0 0 0 0 0 0 777618304410 8670056290 155964 domain0 c00000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 cpu23 0 0 0 0 0 0 803551513420 8844408870 165495 domain0 c00000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 $
ここでは論理CPUごとに自身が属するスケジューラドメインについての情報が出力されます。各ドメインはdomain<階層番号>で表現されます。階層番号が大きいほど上の階層であることを示します。domain
上記の出力によって次のことがわかります。
続いてこの階層はどこから得られたものなのかを調査しました。arm64アーキテクチャにおけるスケジューラドメインの階層構造は最大3階層です。
この階層構造を作っているのがarch/arm64/kernel/topology.c内のコードです。ここで作成した情報は/sys/firmware/devicetree/base/cpus/cpu-map以下を見ればわかります。SC2A11の場合はcpu-mapディレクトリの下に12個のcluster<クラスタ番号>ファイル、そのまた下にcore<クラスタ内のコア番号>というディレクトリが存在します。つまりSC2A11は24個のコアが2個づつのコアから成る12個のクラスタによって構成されていることがわかりました。ちなみに1つのクラスタを構成する2つのコアは前回の記事においてL2キャッシュを共有していることがわかっています。
なお、このマシンは該当しませんが、SMT機能があるCPUの場合はcore
おわりに
次の記事はSocionext SC0FQAA-BはNUMAか否かです。
Socionext SC2A11のキャッシュメモリ構成の推測
はじめに
本記事はARM v8 アーキテクチャのネイティブな開発環境を提供するSC0FQAA-Bに搭載されているSocionext SC2A11 (24コア)のキャッシュメモリがそれぞれどのコア間で共有されているかを調べた結果をまとめた記事です。
なぜそんなことをしたかというと、SC2A11のカタログにはL1dが32KB, L2が256KB, L3が4MBということは書いてあったのですが、それぞれの共有関係については記載がなかったからです。公式サイトからたどれるその他ドキュメントにも同様に記載がありませんでした。
資料請求のフォームがあったのでそこから仕様書をもらって確認するという方法がありましたが
- 個人ユーザが「キャッシュメモリの情報を知りたかったから」という理由で資料をもらえる気がしない
- できたとしても面倒そうだし、時間もかかりそう
という理由により、実験によって情報を得ることにしました。
ちなみに実験に使ったマシンは自分で買ったわけではなく、東大PFLabが買ったもの同研究室のご厚意によって借りたものです。某SNSでこのキャッシュの疑問についてブツブツつぶやいていたら、PFLabでこのマシンをセットアップしたlivaさんがよきに計らってくれました。livaさんとPFLabには厚く御礼申し上げます。
調査結果
キャッシュメモリは恐らく次のような構成になっていることがわかりました。
| 名前 | 合計サイズ[KB] | 共有関係 | サイズ/コア[KB] |
|---|---|---|---|
| L1d | 32 | 全コア独立 | 32 |
| L2 | 256 | 2コアごとに共有 | 128 |
| l3 | 4096 | 全コアで共有 | 約170 |
(2018/3/16追記) 数日前、このマシン用のDevice Treeにキャッシュメモリ構成に関する情報を追加するパッチが投稿されていることをMasami Hiramatsuさんに教えていただきました。パッチの内容によると筆者の推測は正しかったようです。なお、このパッチはすでにマージされたので、いずれファームウェアのバージョンアップによってキャッシュメモリの情報が正しくlinuxから取得できるようになりそうです。
sysfsからの情報採取
カーネルが初期化時にハードウェアからキャッシュメモリの構成を得ている場合は/sys/devices/system/cpu/cpu
dmesgを見たところ、起動中に次のようなメッセージが出力されていました。
# dmesg ... [ 2.582856] cacheinfo: Unable to detect cache hierarchy for CPU 0 ...
これはlinuxカーネルのソースコードでいうと以下の部分に該当します。
...
static int detect_cache_attributes(unsigned int cpu)
{
int ret;
if (init_cache_level(cpu) || !cache_leaves(cpu))
return -ENOENT;
per_cpu_cacheinfo(cpu) = kcalloc(cache_leaves(cpu),
sizeof(struct cacheinfo), GFP_KERNEL);
if (per_cpu_cacheinfo(cpu) == NULL)
return -ENOMEM;
ret = populate_cache_leaves(cpu);
if (ret)
goto free_ci;
/* * For systems using DT for cache hierarchy, of_node and shared_cpu_map * will be set up here only if they are not populated already */
ret = cache_shared_cpu_map_setup(cpu);
if (ret) {
pr_warn("Unable to detect cache hierarchy for CPU %d\n", cpu); ... ★
goto free_ci;
}
cache_override_properties(cpu);
return 0;
free_ci:
free_cache_attributes(cpu);
return ret;
}
...
どうやらcache_shared_cpu_map_setup()が失敗したようです。この原因が次のうちどれなのかはわかっていません。
- 全アーキテクチャ共有コード(drivers/base/cacheinfo.cあたり)
- arm64のコード(arch/arm64/kernel/cacheinfo.cあたり)
- このマシン用のDevice Tree(/sys/firmware/devicetree以下にマップされている)
- その他
ここでこれ以上深堀りはしたくなかったので、次に示す実験によるアプローチによってキャッシュメモリ構成を推測することにしました。
実験
実験のコンセプトは次の通りです。
- コア0上で所定サイズのバッファにアクセスし続けるプログラム(memory_loadプログラム)を動かす
- コア0~23のいずれかの上で、所定サイズのバッファ(memory_loadプログラムのものとは別)に所定の回数アクセスすることによってアクセス速度を計測するプログラム(cacheプログラム)を動かす
- memory_loadプログラムのバッファサイズを(a) L1よりやや小さな値(30[KB])、(b) L2よりやや小さな値(500[KB])、(c) L3 よりやや小さな値(4000[KB])にする。これによって次のことが言える
- a) cacheプログラムのバッファサイズL1以下における性能が劣化した場合、2つのプログラムが動作しているコア間ではL1キャッシュを共有している
- b) 同バッファサイズがL2以下における性能が劣化した場合、2つのプログラムが動作しているコア間ではL2キャッシュを共有している
- c) 同バッファサイズがL3以下における性能が劣化した場合、2つのプログラムが動作しているコア間ではL3キャッシュを共有している
2つのプログラムのソースを示します。
#include <unistd.h>
#include <sys/mman.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <err.h>
#define CACHE_LINE_SIZE 64
int main(int argc, char *argv[])
{
char *progname;
progname = argv[0];
if (argc != 2) {
fprintf(stderr, "usage: %s <size[KB]>\n", progname);
exit(EXIT_FAILURE);
}
register int size;
size = atoi(argv[1]) * 1024;
if (!size) {
fprintf(stderr, "size should be >= 1: %d\n", size);
exit(EXIT_FAILURE);
}
char *buffer;
buffer = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (buffer == (void *) -1)
err(EXIT_FAILURE, "mmap() failed");
struct timespec before, after;
clock_gettime(CLOCK_MONOTONIC, &before);
int i;
for (;;) {
long j;
for (j = 0; j < size; j += CACHE_LINE_SIZE)
buffer[j] = 0;
}
if (munmap(buffer, size) == -1)
err(EXIT_FAILURE, "munmap() failed");
exit(EXIT_SUCCESS);
}
#include <unistd.h>
#include <sys/mman.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <err.h>
#define CACHE_LINE_SIZE 64
#define NLOOP (64*1024*1024)
#define NSECS_PER_SEC 1000000000UL
static inline long diff_nsec(struct timespec before, struct timespec after)
{
return ((after.tv_sec * NSECS_PER_SEC + after.tv_nsec)
- (before.tv_sec * NSECS_PER_SEC + before.tv_nsec));
}
int main(int argc, char *argv[])
{
char *progname;
progname = argv[0];
if (argc != 2) {
fprintf(stderr, "usage: %s <size[KB]>\n", progname);
exit(EXIT_FAILURE);
}
register int size;
size = atoi(argv[1]) * 1024;
if (!size) {
fprintf(stderr, "size should be >= 1: %d\n", size);
exit(EXIT_FAILURE);
}
char *buffer;
buffer = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (buffer == (void *) -1)
err(EXIT_FAILURE, "mmap() failed");
struct timespec before, after;
clock_gettime(CLOCK_MONOTONIC, &before);
int i;
for (i = 0; i < NLOOP / (size / CACHE_LINE_SIZE); i++) {
long j;
for (j = 0; j < size; j += CACHE_LINE_SIZE)
buffer[j] = 0;
}
clock_gettime(CLOCK_MONOTONIC, &after);
printf("%f\n", (double)diff_nsec(before, after) / NLOOP);
if (munmap(buffer, size) == -1)
err(EXIT_FAILURE, "munmap() failed");
exit(EXIT_SUCCESS);
}
それぞれ次のようにビルドします。
$ cc -O3 -o memory_load memory_load.c $ cc -O3 -o cache cache.c
memory_loadプログラムを所定のCPU上で動かすときは次のようにします。
$ taskset -c <CPU番号> ./memory_load <バッファサイズ [KB]>
cacheプログラムを所定のCPU上で動かすときは次のようにします。
$ taskset -c <CPU番号> ./cache <バッファサイズ [KB]>
リファレンスとなるデータの採取
まずはすべてのデータの比較対象となる、負荷をまったくかけない状態の性能を計りました。その結果を以下に示します。
$ for i in 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 ; do taskset -c 0 ./cache $i ; done 0.494395338 0.4878244995 0.7931622984 0.849168839 0.8938277609 0.9555984775 1.041136652 1.064321914 1.069313969 1.158684927 1.505872599 1.577874511 $
コマンド実行結果の数値の単位はナノ秒です。これをグラフにすると次のようになります。x軸もy軸も対数なので見かたに注意してください。
おおよそL1(25 [KB]), L2(28 [KB]), L3(212 [KB])を境界として性能が悪くなってゆくことがわかります。
実験結果
L1の共有範囲
memory_loadのバッファサイズがL1よりやや小さな値(30KB)場合のデータをもとにしたグラフを以下に示します。
memory_loadプログラムとcacheプログラムを同じコア(コア0)上で動かした場合のみ性能が悪く、その他は同程度の性能となりました。ごちゃごちゃしていて見づらいので、
- memory_loadプログラムを動かさない場合(リファレンス性能)
- cacheプログラムをコア0上で動かした場合,
- 同、コア1上で動かした場合
というデータのみを抽出したグラフを以下に示します。
コア0上でmemory_loadプログラムによってL1キャッシュをほとんど使っても他のコアにおける性能がほぼ変わらないことから、コア0とコア1~23はキャッシュを共有していないことがわかりました。
なお、cacheプログラムをコア0上で動かした場合の性能が悪いのは、2つのプログラムがCPU時間を分け合っているせいでしょう。
L2の共有範囲
memory_loadのバッファサイズがL2よりやや小さな値(500KB)にした場合のデータをもとにしたグラフを以下に示します。ここでcacheプログラムをコア2~23で動かした場合のデータはほぼ同じだったので、
- memory_loadプログラムを動かさない場合(リファレンス性能)
- cacheプログラムをコア0上で動かした場合,
- 同、コア1上で動かした場合
- 同、コア2上で動かした場合
というデータのみを抽出しています。
cacheプログラムをコア1上で動かした場合にバッファサイズがL1のサイズ~L2のサイズあたりで性能劣化していることから、コア0とコア1はL2キャッシュを共有していると考えられます。
L3の共有範囲
memory_loadのバッファサイズがL3よりやや小さな値(4000 KB)にした場合のデータをもとにしたグラフを以下に示します。ここでcacheプログラムをコア2~23で動かした場合のデータはほぼ同じだったので、
- memory_loadプログラムを動かさない場合(リファレンス性能)
- cacheプログラムをコア0上で動かした場合,
- 同、コア1上で動かした場合
- 同、コア2上で動かした場合
というデータのみを抽出しています。
cacheプログラムをコア2上で動かした場合にバッファサイズがL2のサイズ~L3のサイズあたりで性能劣化していることから、コア0とコア2(および3~23)はL3キャッシュを共有していると考えられます。
おわりに
今後も本マシンの色々なデータをとっていきたいと思います。バッファサイズをL3のサイズを超える16MBにしてmemory_loadプログラムを動かしたところ、コア0とL2を共有するコア1上でcacheプログラムを動かした場合の性能が上がったという謎現象(L2を共有していないかのような振舞いをする)が発生しました。
これが気になっているので最初に調査するかもしれませんし、気が変わってI/O性能測定などの全然違うことをするかもしれません。
(2018/3/13追記) 結局はさらに気が変わってSC2A11がプロセススケジューラからどう見えるかという観点で調査しました。
