DeepLは2020年5月4日現在、日本から課金できない

DeepLをいたく気に入ったので課金しようとしたらアカウント作成中にエラー発生。よくわかんなかったのでサポートに問い合わせたら「税制上の理由で日本からはまだ課金できない。でも、できるようにいま頑張ってるよ(意訳)」とのこと。

以下サポートから届いたメールの抜粋。

Unfortunately, due to tax reasons, it is currently only possible to book DeepL Pro within the European Union, United Kingdom, Switzerland the United States and Canada. We are working hard to make it possible to order DeepL Pro in Japan soon.

If you wish to keep updated with the news from our company (including when it will be possible to book DeepL Pro from outside of the EU), you can visit our Blog (https://www.deepl.com/blog.html) or follow our social media pages on Facebook and on Twitter.

はやく課金したい。

30分で論文流し読みシリーズ ９「Cntr: Lightweight OS Containers」

www.usenix.org

• 実際の所要時間

  • 1時間

• 課題

  • コンテナの実行において、コンテナイメージサイズを最小化しつつ、稀にしか使わないデバッガなどのその他ツールも使いたい
  • アプリもその他ツールもすべて入ったイメージは無駄に大きすぎる
  • アプリが通常使わないその他ツールをイメージから削除してしまうと、いざというときにその他機能が使えない、使うとしてもコンテナに外からツールを流し込まなくてはいけないので面倒
  • コンテナイメージのベースイメージを小さくする*1のはlibcの入れ替えなどによる互換性の問題が避けられない

• 解決方法概要 -コンテナイメージをslimイメージとfatイメージの二種類に分ける

   - slimイメージ: アプリ実行に必要なものだけが入っている
   - fatイメージ: その他ツールが入っている。slimイメージにその他ツールを足した拡張版、というわけではない。コンテンツはなんでもいい。CNTRはfatイメージを使わずホスト環境を直接使う方法もあるが、説明は割愛
  

  • これ以降slimイメージから作られたコンテナをslimコンテナ、fatイメージから作られたコンテナをfatコンテナと記載
  • アプリの実行にはslimイメージを使う。その他ツールが使いたくなったらアプリのコンテナにfatイメージから作ったコンテナをアタッチ(詳細は後述)
  • 上記環境からはユーザはslimコンテナ、およびfatコンテナの両方にアクセス可能。つまりfatコンテナ内のデバッガを使ってslimコンテナ内のアプリをデバッグ、といったことができる

• 解決方法詳細

  1. ユーザがCNTRを呼び出す。このときCNTRにslimコンテナの名前*2とfatイメージをパラメタとして指定する
  2. コンテナの名前をもとに、カーネルから動作中のコンテナのnamespaceや環境変数、cgroupsの一覧といったコンテナのコンテキストを得る
     • コンテナ名をもとにコンテキストを得る方法はコンテナランタイム依存なので、CNTRがランタイムごとにこの処理を実装する必要がある
  3. fatイメージを使ってコンテナを立ち上げて、CNTRFSサーバ(後述)を動かす
  4. 前述のコンテナのコンテキストをもとに、アプリのコンテナ上にネストしたnamespaceを作る
     • CNTRFSというCNTR専用ファイルシステムをマウントする。このCNTRFSはユーザからのファイルアクセスをslimコンテナおよびfatコンテナにforwardするproxyとなる
     • このときにユーザが指定したfatコンテナをパラメタとして渡す。これによってCNTRFSからのファイルアクセスフォワード先が、ユーザの指定したfatコンテナになる。フォワードにおいてはCNTRFSクライアントとサーバが連携
  5. 上記namespaceの中にCNTRのユーザがアクセスできる環境(ここではCNTR環境と呼ぶ)を用意して、その上で動作するシェルをユーザに提供する
  6. ユーザがファイルシステムにアクセスすると、CNTRFSは次のように実際のアクセス先を分ける
     • "/var/lib/cntr"以下にアクセスするとslimコンテナのデータにアクセス
     • "/proc"や"/sys"以下はslimコンテナのものを直接見せる
     • それ以外の場所へのアクセスするはfatコンテナのデータにアクセス

• 効果

  • xfstestsをほとんどパスするほどの高い互換性がある
  • コンテナ実装に依存する部分が少ないこともあって、DockerやLXC,systemd-spawnなどの有名どころのコンテナランタイムで使える
  • Dockerhub上の有名どころのコンテナイメージのサイズを平均で2/3程度に小さくできる
  • 性能オーバーヘッドは少ない

• 感想

  • かっこいい。言われてみるとなるほどだけど、うまくやるなあと思った
  • たくさんfatコンテナを付けると面白そう
  • Kubernetesのephemeral containerをほうふつとさせる。なにか関係があるんだろうか。

*1:たとえばUbuntuからAlpineなど

*2:コンテナランタイムが個々のコンテナを識別するもの

swapは無効化されぬ、何度でも蘇るさ！

めも

Rookのintegration testを動かそうとしたら、テスト用のK8sクラスタを作るスクリプトにおいて、K8sクラスタが立ち上がらない、および、「kubeletはswaponだと動かないよ」というエラーメッセージが出ていることがわかった。しかし上記スクリプトはクラスタ構築前にswapoff -aを実行していた。どういうことかと思って調査すると、たとえswapoff -aしていてもsystemdが定期的にシステムに存在するswap領域の状態を監視しており、無効になっていた場合は再度有効にしているらしいことがわかった。というわけで次のようなパッチで解決。

github.com

寝室からスマホを追放した話

以前から寝る前にスマホをぼさーっと見るのをやめたいなと思ってたんですが、寝室にそもそもスマホを置かないという方法でそれを達成しました。その結果、今朝はえらく頭がすっきりしていて、なんだか睡眠の質が改善したような気がします。たった一日なので因果関係はまだわかりませんが、寝る前にディスプレイを見るのはよくないとかいうし、しばらく続けてみようかと思います。

寝室にスマホを置かないというのは別に珍しい方法ではなくて、スマホを見ないと死ぬというほどスマホ中毒というわけでもないんですが、ここに至るまでにはけっこう時間がかかりました。その理由は、「スマホはなくてもいいけど目覚ましアラームは欲しいなあ、でもかっこいい目覚まし時計はなかなか見当たらないなあ、でも気合い入れて探すのもめんどくさいなあ」、という完全なる怠け根性から来るものでした。で、そんなときに前から気になっていたGoogle Nest Miniを買ってみてアラーム機能を使ってみたら、幸いにも「ああ、これでいいや」と思えました。昨晩からスマホはアラームをすべて解除して書斎の机の上にほったらかしにしています。

store.google.com

ところでGoogle Nest Miniで音楽を流してみると、どんどんYoutube Music Premium(ないしYoutube Premium)を契約する気がわいてきます。ああ怖い。

Ergo Proxyを見た

https://amzn.to/3aZpFC9

ストーリーは難しくて何言ってるのか最初は全然わからなかったものの…といいたいところですが結局最後まで全く理解できないまま終わりました。しかし世界観、とくに主人公のデザインがすばらしかったです。最初から最後まで映像の綺麗さと格好いい雰囲気を楽しんでいました。こういう楽しみかたをしたアニメは初めてかもしれない。

同僚に「Lainが好きならErgo Proxyはきっと気に入るとおもう」と言われて見始めたやつなんですが、なんと見始めたのが去年の二月末。一年以上かけて見ていたことになります。アニメを見る精神力がなくなっていますね。

長期証券投資の方法の一つを紹介

10年以上証券投資をしてきて今の方法にたどり着いた自分なりの投資方法を書きます。おそらくは少なからない人が推測している「株をやる」とは大きく違っていると思います。もう一点、タイトルについて「株式取引じゃないの？」と思われるかもしれませんが、株式だけではなく投資信託も買ってるので両方を含む証券投資としています。

文書化するのはめんどくさいので列挙で。

• 目的
  • 60歳になったころから悠々自適に暮らせるようになること
  • 自分のはじき出した適正株価の計算(後述)が妥当かどうかを確かめたいという趣味。あともちろん資産も増やしたい。
• 投資の原資
  • 生活費やとっさの入院など、まぁまぁの確率で入り用になりそうな金額を決めて、それだけは現金で持つ。それ以外は全て証券投資の原資。
• 買うもの
  • 世界の株価インデックスと連動するインデックスファンドと呼ばれる投資信託ないしETFと呼ばれる上場投資信託を定額買い続ける。なぜインデックスと連動するかというと市場平均を上回るパフォーマンスを出すのは困難という説を信じているから。このへんは敗者のゲームという本に詳しい。
  • 日本株で暴落が起きるなり市場全体が割安になったときに次の条件を満たす株があればインデックスファンドを買った後に残る原資を使って買う*1
• 個別株を買う基準
  • まずはPERやPBRなどの指標に基づいて適当にフィルタリングする。全部調べてなんかいられない
  • 数年にわたって順調に利益を出している会社、今後も出せそうな会社を選ぶ。このへんは勘。
  • 手元ではじき出した適正株価より現在価格が半額以下なものを選ぶ。適正価格をはじき出す方法についてはDCF法の考え方を使う。このとき証券分析をはじめとする現在企業が持っている資産の価値も考慮する。適正価格の半額以下とする理由は、どうせ計算結果は正確ではないので*2安全を考えてこうしている。物を作るときの安全率と同じ考え方。
• その他の考え方
  • 底値で買おうということは考えない。無理*3。これは「頭と尻尾はくれてやれ」という言葉もある。あくまで買いたい株を探しているそのときに割安かどうかが問題。
  • 買った後はよほどのことがなければ資産の増減は確認しない。株価というものはそもそもフラフラ変動するものなので日々の変化を気にしてもしょうがない*4。また、60歳あたりまでに資産が増えていればいいので途中経過はどうでもいい。むしろ途中で暴落してくれれば買い増せるチャンスが増えるので好ましい*5。
  • 海外株は買わない。株価そのものの変動と為替レートの変動を考えると予測が極めて困難と判断しているため
  • チャートや板は一切見ない。上記の考え方に基づくと見る理由が無い
• 短期投資をしない理由
  • コロケーションをはじめとするなかばインチキな大技を使える巨人たちに負け続けるのはわかっているので納得がいかないから
  • なるべく精度が高そうな数値ベースで判断したいという性格とは相いれないから
  • なんとなくストレスがたまりそう。長期投資をしている場合に対して日々の株価が気になってしまいそう

こんなところです。

*1:上記インデックスを買う理由と矛盾するようだが、こちらは半ば趣味なので気にしない

*2:もし正確なら世界一の大金持ちになれる

*3:そんなのができたら世界一の大金持ちになれる

*4:たとえば一週間のうちに倍や半分になるのは当然

*5:さすがに60歳のころに減っていたら泣くと思うけど

Linuxカーネル4.1のプロセススケジューラ(ドラフト)

はじめに

本記事は昔書いたlinuxカーネル4.1のプロセススケジューラの実装について途中まで書いたけど諸事情により二年くらい放置していたドラフトです。死蔵するのももったいないので公開しておきます。今現在のカーネルに比べてずいぶんと変わっていること、未稿の部分がかなりあること、誤字脱字や「てにをは」は気にしていないこと、などにご注意ください。

このドキュメントを積極的に更新する予定は(少なくともこの場では)いまのところありません。

プロセススケジューラ

ある瞬間にCPU¹で動作できる処理は1つだけです。この限りあるCPU資源をシステムに存在する プロセス間で分配するのがプロセススケジューラです。プロセススケジューラは大きく分けて 次のことをします。

• 全プロセスの間で平等にCPUを分配する
• スループットの最大化
• レイテンシ(応答時間、ターンアラウンドタイム)の最短化

個々のコアのことであり、かつ、ハイパースレッドが有効化されていれば個々のハイパースレッドの ことです。

まずは簡単のため、1CPUの場合に絞って記載します。その後マルチプロセッサの場合について記載します。

1CPUの場合

プロセススケジューラはユーザに対して複数のプロセスが同時並列的に動作しているように見せかけます。 それには、複数の動作可能なプロセッサを交互に動かす時分割(タイムシェアリング)という仕組みを用います。 たとえば2つの実行可能なプロセスp0, p1が同時に存在している場合、CPUの上で動作するプロセスは次の ように遷移します。

とくにnice値によって優先度に差をつけていない場合はp0, p1に対してCPU時間を均等に割り当てます²。 この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です³。

nice値が変化することによってレイテンシは変化しませんが、nice値の低い(優先度の高い)プロセスは nice値の高い(優先度が低い)プロセスよりもCPU時間を多くの比率だけもらえます。

スケジューリングポリシー

スケジュールするにあたって、優先度以外にももう一つ、プロセススケジューリングの挙動を変更する スケジューリングポリシーという要因があります。これには主に次のような種類があります。

• SCHED_OTHER(デフォルト)
• SCHED_FIFO
• SCHED_RR

SCHED_OTHERは本章でこれまでに述べてきたような動きをします。

SCHED_FIFO はリアルタイム性の強いプロセス、たとえば定期的に起床してシステムの生存確認を するようなハートビート用プロセスなどに用います⁴。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のタイムスライス切れを次のようなタイミングで監視しています。

• タイマーサブシステム定期的⁵に発生させるタイマー割り込みの延長。精度はカーネルビルドの設定によるが最高でも1ミリ秒。処理の入り口はscheduler_tick()
• プロセススケジューラが必要に応じて(後述)発生させる高精度タイマーの延長。 精度はナノ秒。処理の入り口はhrtick()。

これ以外にもスケジューラのコードの中では、ランキュー操作など、随所でupdate_rq_clock()を呼び出すことによって、currentのタイムスライス切れを細かく監視しています。

上記2つの関数は次のようなことをします。

1. update_rq_clock(): rq->clockを更新
2. current->sched_class->task_tick()ハンドラを呼ぶ。このハンドラは、タイムスライスが切れていたら、currentを切り替えるようにスケジューラに通知する
3. (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が立ったことを通知

プリエンプトした後にコンテキストスイッチが起きるタイミング

次のようなタイミングで発生します。

• システムコールや割り込みからの復帰時
• カーネル処理の中でschedule()やcond_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キューに挿入

1. 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)

TBD

アイドルプロセスの処理

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は通常もっとコア数が多いですが)。

このドメイン内をバランスする処理は、

1. ドメイン内の一番負荷が高いグループを見つける
2. ドメイン内の一番負荷が低いグループを見つける
3. 一番負荷が高いグループから一番低いグループに1つないし複数のスレッドを移動させる

ここでいう負荷とは、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

---

1. ここでいうCPUとは論理CPUのことですマルチコアであれば(最近はほとんどそうですが)↩

2. 正確にはこの間に定期的にカーネルが動作しますが、煩雑になるのでここでは省略します。詳細は後述。↩

3. 遠慮して人にCPU時間を譲ってくれる「良い奴」だからniceという名前が付いているようです↩

4. リアルタイムという名前がついていますが確実に期待した時刻に動作して、デッドライン内に処理が完了する↩

5. 現在は省電力の観点から、時刻の更新が必要無いとわかっている時はタイマー割り込みを一時的に停止します↩