以下は、２０１５年版の perfbook の１５章 Parallel Real-Time Computing の kanda.motohiro@gmail.com による全訳です。perfbook の訳の他の部分は、親文書を参照。
１５章 並列リアルタイムコンピューティング
コンピューティングにおいて重要な現れつつある領域は並列リアルタイムコンピューティングです。１５．１節は、「リアルタイムコンピューティング」の定義をいくつか見ます。通常の通俗的用語を超えて、より意味のある基準へと向かいます。１５．２節は、リアルタイム応答を必要とするアプリケーションの種類を概観します。１５．３節は、並列リアルタイムコンピューティングは我々のもとにあることを示し、並列リアルタイムコンピューティングが有効な時と理由を議論します。１５．４節は並列リアルタイムシステムをどのように実装することができるかについて短い概要を与えます。最後に１５．５節ははあなたのアプリケーションがリアルタイム機能を必要とするかどうかをどうやって判断するかの概要を示します。
１５．１ リアルタイムコンピューティングとは何ですか？
リアルタイムコンピューティングを分類する一つの伝統的な方法は、ハードリアルタイムとソフトリアルタイムというカテゴリーに分けることです。マッチョなハードリアルタイムアプリケーションは決して決してデッドラインを逃しません。しかし、弱虫ソフトリアルタイムアプリケーションは頻繁にしばしばデッドラインを逃すことがあります。
１５．１．１ ソフトリアルタイム
ソフトリアルタイムのこの定義に問題を見つけるのは容易です。一つには、この定義によれば、どんなソフトウェアのかけらもソフトリアルタイムアプリケーションであると言うことができます。「私のアプリケーションは１００万点のフーリエ変換をピコ秒の半分で計算します。」「不可能です！！！このシステムのクロックサイクルは３００ピコ秒以上です！」「ああ、でもこれはソフトリアルタイムアプリケーションです！」もしも「ソフトリアルタイム」という語が何にせよ使われるなら、明らかに何らかの限界が必要です。
なので、あるソフトリアルタイムアプリケーションは少なくてもある回数の割合はその応答時間要件を満たさなくてはいけないと言うことができるでしょう。例えば、それは９９.９％の割合で、２０マイクロ秒以下で実行しなくてはいけないと言えます。
これはもちろん、そのアプリケーションがその応答時間要件を満たすのに失敗したらどうすべきかという問題を提起します。答えはアプリケーションによって違うでしょう。一つの可能性は、制御されているそのシステムはたまの制御アクションの遅れを無害にするだけの十分な安定性と慣性を持つというものです。もう一つの可能性は、アプリケーションが結果を計算する二つの方法を持つというものです。速くて決定論的だが不正確な方法と、計算時間が予測不可能だがとても正確な方法と。一つの妥当なアプローチは、両方の方法を並行して開始し、正確な方法が時間内に終われなかったらそれを止めて、速いけど不正確な方法の出した答えを使います。速いけど不正確な方法の一つの候補は、今の時間周期の間は何も制御アクションをしないことです。別の候補は、一つ前の時間周期でやったのと同じ制御アクションをすることです。
短く言えば、ソフトリアルタイムについて語るときに、正確にそれがどれだけソフトであるかの基準がなくては意味がありません。
１５．１．２ ハードリアルタイム
それに対して、ハードリアルタイムの定義はとても明らかです。結局、あるシステムは常にそのデッドラインを守るかそうでないかのどちらかです。不幸にも、この定義を厳密に適用すると、ハードリアルタイムシステムは決して存在不可能です。その理由は、図１５．１に楽しく描かれています。より頑強なシステムを作るのは可能なのは事実です。冗長さを増すなどして。しかし私が常により大きなハンマーを使うことができるのも事実です。
なので、繰り返しますが、明らかに単なるハードウェアの問題だけでなく、真の大きな鉄の金物の問題であるものについて、ソフトウェアを非難するのはたぶん不公平です。
脚注
あるいは、最近のハンマーなら、大きな鋼鉄問題でしょうか。
この結果、ハードリアルタイムソフトウェアとは、ハードウェア故障がない限り、そのデッドラインを常に守るソフトウェアであると定義するのが良さそうです。不幸にも、図１５．２に楽しく描かれるとおり、失敗が常に許されるとは限りません。その絵の気の毒な男の人に、「安心して下さい。もしもデッドラインに間に合わないことがあなたの悲劇的な死につながるとしても、それは決してソフトウェアの問題のせいではありません！」と言っても、彼が安心するとは単純に期待できないでしょう。ハードリアルタイム応答はシステム全体の属性であって、ソフトウェアだけの属性ではないのです。
でも、完璧は要求できないならば、前述のソフトリアルタイムアプローチと同様に、通知でうまくやれるでしょう。すると、図１５．２の Life-a-Tron がデッドラインを超えそうになったら、病院の職員に警告すればいいでしょう。
不幸にも、このアプローチは、図１５．３に楽しく描かれる自明な解決策があります。自分のデッドラインを守れないだろうと常に直ちに通知を発するシステムは、法律文書には適合するでしょうが全く役に立ちません。システムはそのデッドラインを、ある回数の割合は守るという要件も、明らかに必要です。あるいは、それは決められた数の連続した操作より多く、デッドラインを守れない事はあり得ない、というように。
通俗的用語のアプローチを、ハードリアルタイムにもソフトリアルタイムにも使えないことは明らかです。なので、次の節はもっと実世界のアプローチを取ります。
１５．１．３ 実世界のリアルタイム
「ハードリアルタイムシステムは常にそのデッドラインを守ります！」のような文章はうけやすく、疑いなく覚えやすいですが、実世界のリアルタイムシステムには、何か他のものが必要です。結果となる仕様が覚えにくいものであっても、それは環境とワークロードとリアルタイムアプリケーション自身に対して制約を与えることで、リアルタイムシステムの構築を単純化することができます。
１５．１．３．１ 環境の制約
環境への制約は、「ハードリアルタイム」が意味する、応答時間への無制限の約束への異議を扱います。これらの制約は、許容可能な運転温度、空気の質、電磁放射の強さとタイプ、そして、図１５．１の観点から、衝撃と震動の強さを指定します。
もちろん、ある制約は他のよりも満足しやすいです。コモディティ計算機コンポーネントは、しばしば、零下の温度では動作することを拒否すると厳しい方法で学んだ人は多いです。それは、気候を制御する要件のセットを示唆します。
昔の大学の友人があるとき、かなり侵食性の強い塩素化合物を特徴とする環境でリアルタイムシステムを動作させるという挑戦をしなくてはいけなくなりました。それを彼は、賢明なことにハードウェアを設計している彼の同僚に渡しました。実際には、私の同僚は、その計算機に直に接している環境の空気組成の制約を課しました。その制約を、ハードウェア設計者は、物理的封印を使って満足させました。
もう一人の昔の大学の友人は、真空での工業的強度のアーク放電を使ってチタニウムのインゴットをスパッタする計算機制御されたシステムを研究していました。時々、アークはチタニウムのインゴットを通る自分の道に飽きて、ずっと短くてより楽しい、グラウンドへの道を選びました。物理学の授業で皆、学んだように、電子の流れが突然変わると、電磁波が作られます。より大きな流れのより大きな変化は、より強力な電磁波を作ります。そしてこの場合、結果となる電磁パルスは、４００メートル以上離れたところにある小さな、「ラバーダック」アンテナの導線に、１／４ボルトの電位差を誘導するのに十分でした。これは、近くの導電体は、逆二乗の法則によって、より高い電圧を感じたことを意味します。それには、そのスパッタリング処理を制御している計算機を構成する導電体も含まれます。特に、その計算機のリセット線で誘導された電圧は、実際に計算機をリセットするのに十分でした。関連する人が皆、驚いたことに。この場合、この挑戦は、ハードウェアを使って満足させられました。それは、かなり洗練されたシールドと、私が今まで聞いた中で最も低いビット率である９６００ボーというビット率の光ファイバーネットワークを使いました。とは言え、これほど激しくない電磁的環境は、しばしば、ソフトウェアによって扱うことができます。誤り検出と訂正符号によって。とは言え、誤り検出と訂正符号は失敗の割合を減らすことができますが、通常はそれを全くゼロにはできないことを覚えておくのは重要です。それはハードリアルタイム応答を達成するための、さらにもう一つの障害を作り出すこともあります。
また、例えば、システムの電源線と、監視あるいは制御される外の世界の部分とそのシステムが通信するためのデバイスを、経由するエネルギー強度が最低であることが要求される状況もあります。
クイッククイズ１５．１
しかし、電池で給電されるシステムはどうですか？それは、全体としては、システムに流れこむエネルギーを必要としません。
多くのシステムは、印象的な衝撃と震動の強さのある環境で動作することを意図されています。例えば、エンジン制御システム。より過酷な要件は、連続する震動から離れて、間欠的な衝撃に目を移すと見つかります。例えば、私の大学での研究で、私は古いアテナ弾道ミサイル計算機を見つけました。それは手榴弾が近くで爆発しても運転を続けるように設計されていました。
脚注
何十年も後、ある型の計算機システムの受け入れテストは、巨大な爆発を含みます。そして、ある型の通信ネットワークは、慎重に「弾道ジャミング」と呼ばれることも扱わなくてはいけません。
そして最後に、航空機で使われる「ブラックボックス」は、墜落の前、間、そしてその後も運転を続けなくてはいけません。
もちろん、ハードウェアを環境的な衝撃や侮辱に対してより頑強にすることは可能です。いくつもの巧妙な機械的衝撃吸収デバイスは、衝撃と震動の効果を減らせます。複数レイヤのシールドは高エネルギー電磁放射の影響を減らせます。誤り訂正符号は、低エネルギーの電磁放射の効果を減らせます。
訳注
原文は、 high, low が逆です。
多くのポッティングとシーリングの技術は、空気の質の影響を減らせます。そして多くの加温と冷却システムは温度の効果を無害化できます。極端な場合、三重モジュロ冗長性は、システムの一つの部分の故障が、システム全体の誤った振る舞いにつながる可能性を減らせます。しかし、これらの方法の全ては、一つのことを共通に持ちます。それらは失敗の確率を減らせますが、それをゼロにはできません。
これら厳しい環境的条件は、しばしばより頑強なハードウェアを使うことで対処されます。しかし、次の二つの節で述べるワークロードとアプリケーションの制約は、しばしばソフトウェアで扱われます。
１５．１．３．２ ワークロード制約
人と同じように、リアルタイムシステムは、それを過負荷にすることでデッドラインを守れなくすることがしばしば可能です。例えば、もしシステムがあまりに頻繁に割りこまれたら、そのリアルタイムアプリケーションを扱うための十分なCPUバンド幅が無いかもしれません。この問題へのハードウェア解決策は、割り込みがシステムに送られる率を制限することかもしれません。可能なソフトウェア解決策は、あまりに割り込みがたくさん受信される時にはしばらく割り込みを禁止することや、多すぎる割り込みを発生させているデバイスをリセットすること、あるいはポーリングを使って、割り込みを全く避けることが含まれます。
過負荷は、キューイング効果によって、応答時間を悪化させることもあります。なので、リアルタイムシステムでは、CPUバンド幅をオーバープロビジョンすることはめずらしくありません。実行中のシステムが、（例えば）８０％のアイドル時間を持つように。このアプローチは、記憶域とネットワークデバイスにも適用されます。ある場合には、リアルタイムアプリケーションの高優先度の一部分が使うためだけに、専用の記憶域とネットワーキングハードウェアが用意されていることもあります。なので、このハードウェアがほとんどアイドルなのはめずらしくありません。リアルタイムシステムでは、スループットよりも応答時間がより重要だからです。
クイッククイズ１５．２
でも、待ち行列理論の結果によれば、低使用率はただ平均応答時間を改善するだけで、最悪の場合の応答時間を改善しないのではありませんか？多くのリアルタイムシステムは後者の応答時間だけを気にしているのではないですか？
もちろん、十分に低い使用率を維持するのは、設計と実装全般にわたって、厳格な基準が必要です。忍び寄る小さな機能ほど、デッドラインを破壊するものはありません。
１５．１．３．３ アプリケーション制約
操作によっては、他の操作と比べて、有限の応答時間を得るのが易しいものがあります。例えば、割り込みと起床操作に対して応答時間の指定を見るのはとても一般的です。しかし、(例えば)ファイルシステムアンマウント操作に対してはそれはとてもまれなことです。その一つの理由は、アンマウントはそのファイルシステムの全てのメモリ上データを大容量記憶域にフラッシュしないといけないため、ファイルシステムがしなくてはいけない仕事の量に限界を設けるのはとても難しいからです。
これは、リアルタイムアプリケーションは、合理的に有限の遅延が提供される操作だけに閉じ込められる必要があることを意味します。それ以外の操作は、そのアプリケーションのリアルタイムでない部分に押し出されるか、あるいは完全に止める必要があります。
アプリケーションのリアルタイムでない部分にも制約があるかもしれません。例えば、リアルタイムでないアプリケーションは、リアルタイムの部分が使っているCPUを使うことが許されますか？そのアプリケーションのリアルタイム部分が、特別に忙しいと思われる時間期間がありますか？もしそうならば、そのアプリケーションのリアルタイムでない部分はその期間中、走ることが許されますか？最後に、そのアプリケーションのリアルタイム部分は、リアルタイムでない部分のスループットをどこまで悪化させることが許されますか？
１５．１．３．４ 実世界のリアルタイム仕様
これまでの節でお分かりのように、実世界のリアルタイム仕様は、環境、ワークロード、そしてアプリケーション自身についての制約を含む必要があります。さらに、そのアプリケーションのリアルタイム部分が使うことの許される操作について、その操作を実装するハードウェアとソフトウェアについての制約もなくてはいけません。
そのような操作のそれぞれに、その制約は最大応答時間(そして多分、最小応答時間も)と、その応答時間を満足する確率を含むでしょう。１００%の確率は対応する操作がハードリアルタイムサービスを提供しなくてはいけないことを示します。
場合によっては、応答時間とそれを満足する確率の両方は問題の操作のパラメタによって変わることがあるでしょう。例えば、ローカルLANを経由するネットワーク操作は、同じネットワーク操作を大陸間WANでする時に比べて、(例えば)１００マイクロ秒以内に完了することが多いでしょう。さらに、銅線あるいはファイバーLANを経由するネットワーク操作は時間のかかる再送なしに完了する確率がとても高いでしょう。それに対して損失の多い WiFiネットワークを経由する同じネットワーク操作は、厳しいデッドラインを守れない確率がずっと高いかもしれません。同様に、緊密に結合したソリッドステートディスク(SSD)からのリードは、古い型のUSB接続した回転する赤さび色の円盤からの同じリードと比べるとずっと早く完了することが期待されます。
脚注
重要な安全のための知識。USBデバイスからの最悪の応答時間は、極めて長いことがあります。なので、リアルタイムシステムはクリティカルパスから全てのUSBデバイスを十分に離して置くように注意するべきです。
リアルタイムアプリケーションのあるものは、操作の異なるフェーズを通過します。例えば、回転する丸太から木の薄いシート(「ベニヤ」と呼ばれます)を剥く合板旋盤を制御するリアルタイムシステムは、以下のフェーズを必要とします。
（１）丸太を旋盤に載せます。
（２）丸太に含まれる最大の円筒を刃に向けるように、旋盤のチャックに丸太を位置付けます。
（３）丸太を回転し始めます。
（４）丸太からベニヤを剥くために、連続的に刃の位置を変えます。
（５）剥くのに小さくなりすぎた残りの丸太の芯を除きます。
（６）そして、次の丸太を待ちます。
この６つの操作フェーズのそれぞれは、それ固有のデッドラインと環境的制約を持つでしょう。例えば、フェーズ４のデッドラインは、フェーズ6のそれよりずっと厳しくて、秒でなくミリ秒であることが期待されます。なので、低優先度の作業はフェーズ４でなくフェーズ6で行われると思って良いでしょう。とは言え、フェーズ４のより厳しい要件をサポートするためには、ハードウェア、ドライバ、そしてソフトウェア設定を注意深く選ぶことが必要でしょう。
このフェーズごとのアプローチの鍵となる利点は、遅延予算を分解できることです。そうすることでアプリケーションのいろいろなコンポーネントが独立して開発できます。それぞれは自分自身の遅延予算を持ちます。もちろん、他の種類の予算と同様に、どのコンポーネントが全体の予算のどれだけの部分を得るかについてたまに競合があるのは十分にありえます。そして、他の種類の予算と同様に、その競合を時間をかけずに解決するためには、強いリーダーシップと、共用されるゴールの認識が、助けとなるでしょう。そして繰り返しますが、他の種類の技術的予算と同様に、遅延に対する適切な焦点を保証し、遅延問題に早めの警告を与えるためには、強力な検証作業が必要です。成功する検証作業はほとんど常に良いテストスイートを含むでしょう。それは理論家にとっては不十分かもしれませんが、仕事を無事終わらせるのを助ける恩恵があります。２０１５年初頭の事実としては、実世界のほとんどのリアルタイムシステムは形式的証明ではなくて受け入れテストを使っています。
とは言え、リアルタイムシステムを検証するテストスイートが広く使われていることは実際に欠点を持ちます。つまり、そのリアルタイムソフトウェアは特定のハードウェアとソフトウェア構成に限られたその特定ハードウェアでしか検証されないことです。ハードウェアと構成を追加するには、高価で時間がかかるテストを追加しなくてはいけません。形式的検証の分野はこの状況を変えられるくらいに進歩するかもしれませんが、２０１５年初頭では、それにはかなりの進歩が必要です。
クイッククイズ１５．３
形式的検証は既にとても有能です。それは、何十年にもわたる強力な研究の結果です。これ以上の進歩など本当に必要なのでしょうか？それとも、これは怠慢であり続け、形式的検証のおそるべき力を無視し続ける実務家の言い訳に過ぎないのでしょうか？
アプリケーションのリアルタイム部分の遅延要件に加えて、そのアプリケーションのリアルタイムでない部分に性能とスケーラビリティの要件があることも考えられます。この追加の要件は、究極のリアルタイム遅延は、しばしば、スケーラビリティと平均性能を悪化させることで達成されるという事実を反映します。
ソフトウェア工学的要件も重要なことがあります。特に、大きなチームが開発と維持をする必要のある巨大アプリケーションではそうです。この要件はしばしば、より優れたモジュラリティと故障の孤立化を重要視します。
これは、本番のリアルタイムシステムのためのデッドラインと環境的制約を指定するために必要な作業の概略にすぎません。この概略が、リアルタイムコンピューティングへの、通俗的用語を元にするアプローチが不適切であることを明らかにできることを希望します。
１５．２ 誰がリアルタイムコンピューティングを必要としますか？
全てのコンピューティングは実はリアルタイムコンピューティングであると主張することは可能です。一つのまずまず極端な例として、誕生日の贈り物をオンラインで買う時に、その贈り物は、受け取る人の誕生日の前に届いてほしいでしょう。そして実際、世紀の変わり目のウェブサービスでさえ、一秒以下の応答時間制約がありました [Boh01]。そして、時が経つにつれ要求は弱まることはありませんでした [DHJ+07]。とは言っても、リアルタイムでないシステムとアプリケーションが直裁的には満たすことのできない応答時間制約を持つリアルタイムアプリケーションに焦点を当てることは有益なことです。もちろん、ハードウェア価格が下がって、バンド幅とメモリサイズが大きくなるにつれて、リアルタイムとリアルタイムでないものとの境界は移動し続けるでしょう。しかしそのような進歩はいかなる意味においても悪い事ではありません。
クイッククイズ１５．４
リアルタイムとリアルタイムでないものを、「リアルタイムでないシステムとアプリケーションが直裁的には満たすことのできない」ことによって分類するのは、お笑いです。そのような差別化に絶対的にいかなる理論的根拠もありません！！！もっとましなことはできないのですか？？？
リアルタイムコンピューティングは工業制御アプリケーションで使われます。それは、製造から航空電子工学まで及びます。科学的アプリケーション。たぶん、最もはなばなしいのは、星の光の揺らめきを抑えるために、地上の望遠鏡で使われる補償光学でしょう。軍事アプリケーション。前記航空電子工学を含みます。そして、金融サービスアプリケーション。そこでは、機会を見つけた最初の計算機がその結果となる利益のほとんどを刈り取るでしょう。これらの４つの領域は、「生産の追求」、「生命の追求」、「死の追求」、そして、「お金の追求」に分類できます。
金融サービスアプリケーションは他の３つのカテゴリーのアプリケーションと少し違います。お金は、物質ではありません。ということは、計算以外の遅延がとても小さいことを意味します。それに対して、他の３つのカテゴリーに固有の機械的遅延は、とてもはっきりした収穫逓減の地点を与えます。そこを超えると、アプリケーションのリアルタイム応答のそれ以上の削減が、ほとんどあるいはまるで利益を生まなくなる地点です。ということは、金融サービスアプリケーションは、他のリアルタイム情報処理アプリケーションと同様に、軍拡競争に直面することを意味します。そこでは、最低の遅延のアプリケーションが通常は勝ちます。結果となる遅延要求は、それでも、１５．１．３．４節に書いたように指定することはできますが、その要求の通常とは違う性質のため、金融と情報処理アプリケーションは、「リアルタイム」ではなくて、「低遅延」だと言う人もいます。
それを正確にどう呼ぶことにしても、リアルタイムコンピューティングへの要求は大きいです [Pet06, Inm07]。
１５．３ 誰が並列リアルタイムコンピューティングを必要としますか？
誰が本当に並列リアルタイムコンピューティングを必要とするかはあまり明確ではありません。しかし、それとは無関係に、低価格のマルチコアシステムの到来は、それを前面に押し出してきました。不幸にも、リアルタイムコンピューティングの伝統的な数学的基礎は、単一のCPUシステムを前提としてきました。規則を証明するいくつかの例外を除いてです[Bra11]。とは言え、現代的コンピューティングハードウエアをリアルタイム数学的サークルに適合させる方法はいくつかあります。そして数名のLinuxカーネルハッカーは学会がその転換をするようにはたらきかけてきました [Gle10]。
一つのアプローチは、多くのリアルタイムシステムは生物の神経システムを反映していることを認識することです。応答は、図１５．４に示すように、リアルタイムの反射から、リアルタイムでない戦略策定と計画までの範囲があります。ハードリアルタイムの反射は、センサーを読んでアクチュエータを制御しますが、それは単一のCPUでリアルタイムで走り、一方、リアルタイムでない戦略と計画の部分は残りの複数のCPUで走ります。戦略と計画のアクティビティは、統計解析、周期的なキャリブレーション、ユーザインタフェース、サプライチェーンアクティビティ、そして準備を含むかもしれません。計算負荷が高い準備アクティビティの例としては、１５．１．３．４節で議論した、ベニア剥きのアプリケーションを思い出して下さい。一つのCPUが一つの丸太を剥くために必要な高速リアルタイム計算に参加している一方、他のCPUは次の丸太の長さと形を解析して、高品質のベニアを最大可能な量だけ採取するために、次の丸太をどのように配置するかを決めようとしているかもしれません。多くのアプリケーションは、リアルタイムでないコンポーネントと、リアルタイムのコンポーネントを持つことがわかってきました [BMP08]。なので、このアプローチは、伝統的なリアルタイム解析を現代的なマルチコアハードウエアと組み合わせるためにしばしば使われます。
もう一つの自明なアプローチは、一つを除いて全てのハードウエアスレッドを停止して、ユニプロセッサリアルタイムコンピューティングの解明済みの数学に戻ることです。しかし、このアプローチは、潜在的なコストとエネルギー効率の利点をあきらめます。とは言え、これらの利点を得るためには、３章で扱った並列性能障害を克服する必要があります。そしてそれは、平均においてだけでなく、最悪ケースにおいてです。
なので、並列リアルタイムシステムを実装するのはとても挑戦的です。この挑戦に応えるための方法を、以下の節で概説します。
１５．４ 並列リアルタイムシステムを実装する
リアルタイムシステムの二つの主なスタイルを見ます。イベントドリブンと、ポーリングです。イベントドリブンリアルタイムシステムはほとんどの時間、アイドルのままです。オペレーティングシステムからアプリケーションに渡されたイベントに対して、リアルタイムに応答します。あるいは、そのシステムは、ほとんどアイドルのままでいる代わりに、バックグラウンドのリアルタイムでないワークロードを走らせることもできます。ポーリングリアルタイムシステムは、リアルタイムスレッドを特徴とします。それはCPUバウンドで、ループのそれぞれのパスで入力をポールして、出力を更新するタイトなループを回っています。このタイトなポーリングループはしばしば完全にユーザモードで実行します。そのユーザモードのアプリケーションのアドレス空間にマップされたハードウエアレジスタから読み、そこに書きます。あるいは、アプリケーションによっては、ポーリングループをカーネル内に置きます。例えば、ローダブルカーネルモジュールを使って。
選ばれたスタイルに関係なく、リアルタイムシステムを実装するのに使われるアプローチはデッドラインに依存します。例えば、図１５．５に示すとおり。この図の一番上から見ると、もしあなたが１秒以上の応答時間でもかまわないなら、あなたのリアルタイムアプリケーションを実装するのにスクリプト言語を使っても十分良いです。そして、実際にスクリプト言語は驚くほどしばしば使われています。私がその実践をお勧めするわけではないですが。もし必要な遅延が、数十ミリ秒を越えるなら、古い２．４バージョンのLinuxカーネルを使うことができます。同様に、私がその実践をお勧めするわけではないですが。特別な、リアルタイム Java 実装は、数ミリ秒のリアルタイム応答遅延を提供できます。ガーベジコレクタを使ってもです。Linux 2.6.x と 3.x は、数百マイクロ秒のリアルタイム遅延を提供できます。注意深く設定、チューニングされ、リアルタイムに優しいハードウエアで走らせればです。特別な、リアルタイム Java 実装は、１００マイクロ秒以下のリアルタイム応答遅延を提供できます。ガーベジコレクタの使用を、注意深く避ければです。（しかし、ガーベジコレクタを避けるということは、Java の巨大な標準ライブラリを避けることも意味し、それは Java の生産性の利点を失うことも意味することに注意下さい。）-rt パッチセットを取り入れたLinuxカーネルは、２０マイクロ秒以下の遅延を提供できます。そして、専用のリアルタイムオペレーティングシステム（RTOS)で、メモリ変換なしに動くものは、１０マイクロ秒以下の遅延を提供できます。マイクロ秒以下の遅延を達成するには、典型的には手でコーディングしたアセンブリか、特定用途向けのハードウエアが必要なこともあります。
もちろん、スタックの上から下まで全部に渡って、注意深い設定とチューニングが必要です。特に、もしもハードウエアあるいはファームウェアがリアルタイム遅延を提供することができないならば、失われた時間を取り戻すためにソフトウェアができることはありません。そして、高性能ハードウエアはときには、より良いスループットを得るために、最悪ケースの振る舞いを犠牲にすることがあります。実際、割り込みを禁止したタイトループの実行で得られるタイミングは、高品質の乱数発生器の基礎を提供することがあります [MOZ09]。さらに、ファームウェアによっては、いろいろなハウスキーピング作業を実行するために、サイクルを盗むことがあります。ある場合には、犠牲となったCPUのハードウエアクロックを再プログラムすることで自分の痕跡を消そうとします。もちろん、サイクルを盗むのは、仮想化環境では予期される振る舞いです。しかし人々はそれでも、仮想化環境でのリアルタイム応答にむけて努力をしています [Gle12, Kis14]。なので、あなたのハードウエアとファームウェアのリアルタイム能力を評価するのは致命的に重要です。そのような評価をする組織があります。それには、Open Source Automation Development Lab (OSADL) が含まれます。
しかし、能力のあるリアルタイムハードウエアとファームウェアがあるならば、スタックの一つ上の層は、オペレーティングシステムです。それについては、次の節で。
１５．４．１ 並列リアルタイムオペレーティング・システムを実装する
リアルタイムシステムを実装するときに使うことのできる戦略がいくつかあります。一つのアプローチは、図１５．6に示すように、汎用のリアルタイムでないOSを特定用途向けのリアルタイムOS(RTOS)の上に移植することです。緑の、「Linuxプロセス」の箱は、Linuxカーネルの上で走っているリアルタイムでないプロセスを表します。そして黄色い「RTOSプロセス」の箱は、RTOSの上で走っているリアルタイムプロセスを表します。
これは、Linuxカーネルがリアルタイム能力を獲得するまではとても一般的なアプローチでした。それは今でも使われています [xen14, Yod04b]。しかしこのアプローチは、アプリケーションが、RTOSの上で走る部分と、Linuxの上で走る部分に分けられることを要求します。二つの環境を似たように見せることは可能です。例えば、RTOSからPOSIXシステムコールを、Linux上で走っている補助スレッドに転送するなどして。しかし、いつもうまくいくとは限りません。
さらに、RTOSはハードウェアとLinuxカーネルの両方にインタフェースしないといけません。これはハードウェアとカーネルの両方が変化するにつれて、多大なメンテナンスが必要です。さらに、そのようなRTOSはしばしば固有のシステムコールインタフェースとシステムライブラリのセットを持ちます。これはエコシステムと開発者の両方を孤立細分断することがあります。実際、RTOSとLinuxの組み合わせを促進したのは、この問題だったようです。なぜならばこのアプローチは、RTOSのリアルタイム能力への完全なアクセスを許す一方、アプリケーションのリアルタイムでないコードからLinuxの豊富で活気あるオープンソースエコシステムへの完全なアクセスを許すからです。
RTOSとLinuxカーネルを組みにするのは、Linuxカーネルが最低限のリアルタイム能力しか持たない期間の、狡猾で便利な短期間の答えでした。しかしそれは、リアルタイム能力をLinuxカーネルに加えることを動機付けました。このゴールへの進化を図１５．７に示します。上の行はプリエンプションを無効にしたLinuxカーネルの図です。それは実質的にリアルタイム能力は持ちません。真ん中の行は、プリエンプションを有効にしたメインラインLinuxカーネルの増加していくリアルタイム能力を示した図のセットです。最後に、一番下の行は -rt パッチセットを適用したLinuxカーネルの図です。リアルタイム能力は最大です。-rt パッチセットからの機能は、メインラインに加えられ、時とともにメインラインLinuxカーネルの能力を増していきます。しかし、最も要求の高いリアルタイムアプリケーションは -rt パッチセットを使い続けます。
図１５．７の一番上にあるプリエンプト不可能カーネルは、CONFIG_ PREEMPT=n でビルドされます。なので、Linuxカーネル内の実行はプリエンプトされることはできません。ということは、カーネルのリアルタイム応答遅延は、Linuxカーネル内の最長のコードパスによって上限が決まるということです。それはとても長いです。しかし、ユーザモードの実行はプリエンプト可能です。なので、右上に示すリアルタイムLinuxプロセスの一つは、左上に示すリアルタイムでないLinuxプロセスをどれでも、それがユーザモードで実行している時にはいつでもプリエンプトすることができます。
図１５．７の真ん中にあるプリエンプト可能カーネルは、CONFIG_PREEMPT=y でビルドされます。なので、Linuxカーネルのほとんどのプロセスレベルのコードはプリエンプト可能です。これはもちろん、リアルタイム応答遅延を大いに改善しますが、RCUリード側クリティカルセクション、スピンロッククリティカルセクション、割り込みハンドラ、割り込み禁止コード領域、そしてプリエンプト禁止コード領域では、プリエンプションはいまだに不可能です。それは、図の真ん中の行の、左端の図の赤い箱で示されます。プリエンプト可能RCUの到来は、RCUリード側クリティカルセクションをプリエンプト可能としました。それは、中心の図で示されます。そして、スレッド化された割り込みハンドラの到来は、デバイス割り込みハンドラをプリエンプト可能としました。右端の図に示すとおりです。もちろん、この間に、とても多くのこれ以外のリアルタイム機能が追加されました。しかしそれはこの図ではうまく表せません。その代わり、１５．４．１．１節で議論します。
最後のアプローチは、単純に、リアルタイムプロセスの通る道にあるものを全てどけることです。そのプロセスが必要とする全てのCPUから、それ以外の処理を除きます。これは、３．１０ Linuxカーネルで、 CONFIG_NO_HZ_FULL Kconfig パラメタ [Wei12] によって実装されました。このアプローチは少なくても一つのハウスキーピングCPUを必要とすることに注意するのは重要です。それは例えばカーネルデーモンを走らせるなどのバックグラウンド処理を行います。しかし、あるハウスキーピングでないCPUの上で実行可能なタスクが一つしかない場合、そのCPUではスケジューリングクロック割り込みは止められます。それは、干渉とOSジッターの重要な源を除きます。
脚注
プロセス課金の要求のため、１秒に１回のスケジューリングクロック割り込みは残ります。この問題を解決して残りの割り込みを除くのは将来の課題です。
いくつかの例外を除いては、カーネルはハウスキーピングでないCPUからそれ以外の処理を強制的にどけることはありません。その代わり、あるCPUに実行可能なタスクが一つしかない場合、単純により良い性能を提供します。適切に設定すれば、それはかなりな作業ですが、CONFIG_NO_HZ_FULL はベアメタルシステムの性能とほとんど競うことのできるほどのリアルタイムスレッドレベルの性能を提供します。
リアルタイムシステムにとってこれらのどのアプローチが一番良いかについて、もちろん、多くの論争がありました。そしてこの論争は、かなり長いこと続いています[Cor04a,Cor04c]。よくあるように、答えは、「場合による」のようです。これは以下の節で議論します。１５．４．１．１節はイベントドリブンリアルタイムシステムを考えます。１５．４．１．２節は、CPUバウンドのポーリングループを使うリアルタイムシステムを考えます。
１５．４．１．１ イベントドリブンリアルタイムサポート
イベントドリブンのリアルタイムアプリケーションに必要なオペレーティングシステムのサポートはとても広範に渡ります。しかし、この節はいくつかの要素だけに焦点を当てます。つまり、タイマー、スレッド化した割り込み、優先度継承、プリエンプト可能RCU、そして、プリエンプト可能スピンロックです。
タイマー
は、明らかにリアルタイム操作にとって致命的に重要です。結局、もしあなたがあることが指定した時間に終わるように指定できないならば、その時までにどうやって応答できるでしょう？リアルタイムでないシステムにおいても、多数のタイマーが生成されます。このため、それは極端に効率よく扱わないといけません。例となる用途には、TCPコネクションの再送タイマー（それは、ほとんど常に、発火する機会を得る前にキャンセルされます）、
脚注
少なくても、パケット損失率が合理的に低いという前提のもとで！
時間指定の遅延（sleep(1) のような。それはほとんどキャンセルされることはありません）、そして、poll() システムコールのタイムアウト（それは、しばしば、発火する機会を得る前にキャンセルされます）があります。そのようなタイマーのための良いデータ構造は、そうすると、優先度付きのキューであり、追加と削除のプリミティブは高速で、ポストされたタイマーの数に対して O(1) のものでしょう。
このための古典的なデータ構造は、calendar queue です。それは、Linuxカーネルでは、timer wheel と呼ばれます。この大昔からのデータ構造は、離散イベントシミュレーションでも大いに使われています。概念は、時間は量子化されるということです。例えば、Linuxカーネルでは、時間量子の長さは、スケジューリングクロック割り込みの周期です。指定された時刻は、整数で表され、何らかの整数でない時刻へのタイマーのポストをしようとする全ての試みは、手近な整数の時間量子に丸められます。
一つの直裁的な実装は、時刻の低オーダーのビットをインデックスとする単一の配列を確保することでしょう。これは理論的にはうまく行きますが、実際のシステムでは、ほとんど常にキャンセルされる長く続くタイムアウト（例えば、TCPセッションの４５秒のキープアライブタイムアウト）を多数、作ります。
訳注
45 seconds
これらの長く続くタイムアウトは、小さな配列では問題を起こします。なぜならば、まだ満了していないタイムアウトをスキップするために多くの時間が費やされるからです。一方、多数の長く続くタイムアウトを優雅に収めることのできるほど、十分大きな配列は、多くのメモリを使い過ぎます。特に、性能とスケーラビリティへの関心が、そのような配列をそれぞれ全てのCPUに一つづつ必要とする場合にはそうです。
この競合を解決する一般的なアプローチは、複数の配列を階層を構成して提供することです。この階層の最も低いレベルでは、それぞれの配列要素は時間の一つの単位を示します。二つ目のレベルでは、それぞれの配列要素は時間のN単位を示します。Nは、それぞれの配列の要素数です。三つ目のレベルでは、それぞれの配列要素は時間のN＾２単位を示します。というように、階層を上がっていきます。このアプローチは、それぞれの配列を、異なるビットでインデックスすることを許します。図１５．９は非現実的に小さな８ビットのクロックについてこれを示したものです。ここでは、それぞれの配列は１６要素を持ちます。なので、時刻の４つの低オーダーのビット（現在は 0xf）が、低オーダーの（右端の）配列をインデックスして、次の４ビット（現在は 0x1）が次の上のレベルをインデックスします。なので、私達は、それぞれ１６要素の２つの配列を持ちます。全部で、３２要素で、それは、全部合わせても、単一の配列で必要となる２５６要素の配列よりもずっと小さいです。
このアプローチは、スループットをベースとするシステムでは、極めてうまくいきます。それぞれのタイマー操作は、 O(1) に小さな定数を加えたもので、それぞれのタイマー要素は最大でも、m+1 回、触られます。m は、レベルの数です。
不幸にも、timer wheel は、リアルタイムシステムではうまくいきません。それは、二つの理由があります。最初の理由は、タイマーの正確さとタイマーのオーバーヘッドには、厳しいトレードオフがあることです。それは、図１５．１０と１５．１１に楽しく描かれています。図１５．１０では、タイマー処理は１ミリ秒に一度しか起きません。それは、多くの（ただし、全てではないです！！）ワークロードにとって、オーバーヘッドを許容できるほど小さく保ちます。しかしそれは、タイムアウトが１ミリ秒以下の粒度では設定できないことも意味します。一方、図１５．１１では、タイマー処理は１０マイクロ秒ごとに起きます。それは、ほとんどの（ただし、全てではないです！！）ワークロードにとって、タイマー粒度を許容できるほど小さく保ちます。しかしそれは、タイマーをあまりに頻繁に処理するために、そのシステムは何か他のことをする時間がないかもしれません。
二つ目の理由は、高いレベルから低いレベルへとタイマーをカスケードする必要があることです。図１５．９に戻ると、上の（左端の）配列の要素 1x にエンキューされた全てのタイマーは、その時刻になったときに呼ばれることができるために、低い（右端の）配列にカスケードダウンされなくてはいけないことがわかります。不幸にも、多数のタイムアウトがカスケードされるのを待っていることがあります。特に、レベルの多い timer wheel ではそうです。スループットに重点を置くシステムではこのカスケーディングは、統計学の力によって問題とはなりません。しかし、リアルタイムシステムでは、カスケーディングは問題となるほどの遅延の悪化になることがあります。
もちろん、リアルタイムシステムは単純に異なるデータ構造を選択することができます。例えば、ある種のヒープあるいはツリーは、挿入と削除操作に O(1)上限をあきらめる代わりに、データ構造メンテナンス操作に、O(logn) 上限を達成します。これは、特別用途の RTOS には良い選択かもしれませんが、Linuxのような汎用システムでは非効率的です。それは、日常的に、極めて多数のタイマーをサポートしています。
Linuxカーネルの -rt パッチセットが選んだ解決策は、後のアクティビティをスケジュールするタイマーと、TCPパケット損失のような確率の低いエラー処理をスケジュールするタイムアウトを区別することです。一つの鍵となる発見は、エラー処理は通常は特に時間が致命的ではないため、timer wheel のミリ秒レベルの粒度が十分だということです。もう一つの鍵となる発見は、エラー処理のタイムアウトは通常はとても早い時期にキャンセルされることです。それは、しばしば、カスケードできるようになる前です。最後の発見は、システムは一般的に、タイマーイベントに比べてずっと多くのエラー処理タイムアウトを持つということです。このため、O(logn)データ構造は、タイマーイベントに対して、許容できる性能を提供できるだろうということです。
短く言えば、Linuxカーネルの -rt パッチセットは、エラー処理のタイムアウトに対しては、timer wheel を使い、タイマーイベントに対しては、ツリーを使います。それはそれぞれのカテゴリーに対して、必要なサービスの質を提供します。
スレッド化した割り込み
は、リアルタイム遅延を悪化させる重要な源を対策するために使われます。それは、図１５．１２に描かれる長く走る割り込みハンドラです。この遅延は特に、一つの割り込みで多数のイベントを配布するデバイスでは問題になります。それは、割り込みハンドラがこれら全てのイベントを処理するために長い間走ることを意味します。さらに悪いのは、まだ走っている割り込みハンドラに新しいイベントを配布することのあるデバイスです。そうすると、割り込みハンドラは無限に走るかもしれず、リアルタイム遅延を無限に悪化させます。
この問題を対策する一つの方法は、図１５．１３に示すスレッド化された割り込みを使うことです。割り込みハンドラは、プリエンプト可能なIRQスレッドのコンテキスト内で走ります。そのスレッドは、設定可能な優先度で走ります。するとデバイスの割り込みハンドラは、IRQスレッドが新しいイベントに気がつくようにするために十分な、ごく短い時間だけ走ります。図に示すように、スレッド化された割り込みは、リアルタイム遅延を大きく改善することができます。それは一つには、IRQスレッドのコンテキストで走っている割り込みハンドラが、高優先度のリアルタイムスレッドによってプリエンプトされることができるからです。
しかし、タダのお昼ごはんというものは無いように、スレッド化割り込みには欠点もあります。一つの欠点は、割り込み遅延が大きくなることです。割り込みハンドラをすぐに走らせる代わりに、ハンドラの実行は、IRQスレッドがそれを実行することができるようになるまで後回しにされます。もちろん、これは、割り込みを発生するデバイスが、リアルタイムアプリケーションのクリティカルパスにあるのでない限り問題とはなりません。
もう一つの欠点は、下手に書かれた高優先度のリアルタイムコードは割り込みハンドラを飢えさせることがあることです。例えば、ネットワーキングのコードが走れなくします。その結果、問題をデバッグするのがとても難しくなります。なので開発者は、高優先度のリアルタイムコードを書くときには十分な注意をはらわなくてはいけません。これはスパイダーマンの原則と呼ばれます。大きな力は大きな責任を伴う。
優先度継承
は、優先度逆転を防ぐために使われます。それは、特に、プリエンプト可能な割り込みハンドラが確保するロックによって起こることがあります[SRL90b]。低優先度のスレッドがロックを持っているとします。しかしそれは中間優先度のスレッドグループによってプリエンプトされます。CPUごとに、そのようなスレッドが少なくても一つあるとします。割り込みが起き、高優先度のIRQスレッドが中間優先度のスレッドの一つをプリエンプトします。しかしそれが低優先度のスレッドが持っているロックを取ろうとする時までです。不幸にも、低優先度のスレッドは実行を開始するまでロックを放すことはできません。中間優先度のスレッドはそれを許しません。なので高優先度のIRQスレッドは、中間優先度のスレッドの一つがCPUを放すまでロックを取れません。短く言えば、中間優先度のスレッドは間接的に高優先度のスレッドをブロックしています。これは優先度逆転の古典的な状況です。
この優先度逆転は、スレッド化されない割り込みでは起きないことに注意下さい。なぜならば、その場合、低優先度のスレッドはロックを持っている間、割り込みを禁止する必要があるでしょうから。その結果、中間優先度のスレッドはそれをプリエンプトできません。
優先度継承の解決策では、ロックを取ろうとする高優先度のスレッドは、そのロックを持っている低優先度のスレッドに、そのロックが放されるまで、自分の優先度を与えます。こうして、長期間の優先度逆転を防ぎます。
もちろん、優先度継承はその限界を確かに持ちます。例えば、もしあなたがご自分のアプリケーションを、優先度逆転を完全に避けることができるように設計したならば、より優れた遅延が得られるでしょう[Yod04b]。これは驚きではありません。優先度継承は、最悪の場合の遅延に、コンテキストスイッチの対を加えるからです。とは言え、優先度継承は、無限の延期を、遅延の有限の増加に変換することができます。そして、優先度継承のソフトウェア工学的な利益は、多くのアプリケーションにおいて、その遅延コストを上回るかもしれません。
もう一つの限界は、それが、あるオペレーティングシステムのコンテキスト内でのロックベースの優先度逆転だけを対策することです。それが対策できない一つの優先度逆転シナリオは、高優先度のスレッドがネットワークソケットにおいて、メッセージを待っている場合です。そのメッセージは低優先度のスレッドが書くはずなのですが、それはCPUバウンドの中間優先度のスレッドのセットによってプリエンプトされています。
訳注
原文はスレッドとプロセスを混同して使っています。
さらに、ユーザ入力に対して優先度継承を適用することの潜在的不利益が、図１５．１４に楽しく描かれています。
最後の限界は、リーダーライターロッキングに関係します。とてもたくさんの低優先度のスレッドがあるとします。たぶん、何千もです。それらが全て、特定のリーダーライターロックを、リード確保しています。
これらのスレッドが全部、中間優先度のスレッドのセットによってプリエンプトされたとします。少なくても、CPUごとに一つの中間優先度のスレッドがあります。最後に、高優先度のスレッドが起こされて、この同じリーダーライターロックをライト確保しようとします。このロックをリード保持しているスレッドの優先度をいかに強力にブーストしても、高優先度のスレッドがそのライト確保を完了できるまでにはかなり長い時間がかかることが有り得るでしょう。
このリーダーライターロックの優先度逆転の難問には、いくつかの可能な解決策があります。
１ あるリーダーライターロックには、一度に、一つのリード確保だけを許します。（これは、Linuxカーネルの -rt パッチセットが伝統的に採用しているアプローチです。）
２ あるリーダーライターロックには、一度に、N 個のリード確保だけを許します。NはCPUの数です。
３ あるリーダーライターロックには、一度に、N 個のリード確保だけを許します。N は、開発者が何らかの手段で指定する数です。
Linux カーネルの -rt パッチセットがいつかこのアプローチを取る可能性は大いにあります。
４ より低い優先度で走っているスレッドがリード確保したことのあるリーダーライターロックを、高優先度のスレッドは決してライト確保しないようにします。（これは、優先度シーリングプロトコル [SRL90b]の変種です。）
クイッククイズ１５．５
でももし、リーダーライターロックを、一度に一つのリーダーだけがリード確保することを許されるならば、それは排他ロックと同じではありませんか？？？
ある場合には、リーダーライターロックの優先度逆転は、リーダーライターロックをRCUに変換することで避けることができます。それについては、次の節で簡単に議論します。
プリエンプト可能RCU
は、９．３節で議論したように、リーダーライターロックの代わりとして使うことができることがあります [MW07, MBWW12, McK14]。それを使うことができる時は、それは、リーダーと更新者を同時に走らせることを許します。それは、低優先度のリーダーが、高優先度の更新者に対して、いかなる種類の優先度逆転シナリオも起こすことを防ぎます。しかし、これが便利に使えるためには、長く走るRCUリード側クリティカルセクションをプリエンプトできることが必要です [GMTW08]。そうでないと、長いRCUリード側クリティカルセクションは過剰なリアルタイム遅延を起こします。
このため、プリエンプト可能RCU実装が、Linuxカーネルに追加されました。この実装は、現在のRCUリード側クリティカルセクション内でプリエンプトされたタスクの一覧を保持することによって、カーネル内の全てのそれぞれのタスクの状態を個別に追跡する必要を避けています。グレースピリオドは以下の時に終わることができます。
（１）全てのCPUが、現在のグレースピリオドの開始の前に有効であった全てのリード側クリティカルセクションを完了した時。
（２）前記の既存のクリティカルセクション内にいた時にプリエンプトされた全てのタスクが、その一覧から除かれた時。
この実装の単純化したバージョンを図１５．１５に示します。 __rcu_read_lock()関数は、１から５行目にあり、__rcu_read_unlock()関数は７から２２行目にあります。
__rcu_read_lock()の３行目は、ネストした rcu_read_lock()呼び出しのタスクごとのカウントを加算します。そして４行は以下のRCUリード側クリティカルセクション内のコードが、rcu_read_lock()の前になるようにコンパイラがリオーダーするのを防ぎます。
__rcu_read_unlock()の１１行目は、ネストレベルカウントが１か、言葉を代えて言えば、これがネストしたセットの一番外側の rcu_read_unlock() に対応するかを判定します。そうでないなら、１２行目はこのカウントを減算して、制御はコール元に戻ります。そうでない場合、これは一番外側のrcu_read_unlock()です。それは、１４から２０行目で実行される、クリティカルセクションの終わりの処理が必要です。
１４行目はコンパイラが、クリティカルセクションにあるコードを、rcu_read_unlock() を構成するコードとリオーダーするのを防ぎます。１５行目はネストのカウンタを大きな負数に設定して、割り込みハンドラに含まれるRCUリード側クリティカルセクションとの破壊的な競合を防ぎます [McK11a]。そして、１６行目はコンパイラがこの代入を１７行目の特別処理のチェックとリオーダーするのを防ぎます。もし１７行目が特別処理が必要だと判断したら、１８行目で rcu_read_unlock_special() を呼んでその特別処理をします。
必要となる特別処理はいくつかの型がありますが、RCUリード側クリティカルセクションがプリエンプトされた時に必要なものに焦点を当てましょう。この場合、タスクは、自分がRCUリード側クリティカルセクションにいた時に最初にプリエンプトされた時に入ったリストから、自分を除かなくてはいけません。しかし、このリストはロックで守られることに注意するのは重要です。ということは、rcu_read_unlock() はもはやロック無しではありません。しかし、最も優先度の高いスレッドはプリエンプトされることはありません。なので、これら最も優先度の高いスレッドにとっては、rcu_read_unlock() は決していかなるロックも取ろうとすることはありません。さらに、もし注意深く実装すれば、ロックはリアルタイムソフトウェアを同期するために使うこともできます [Bra11]。
特別処理が必要でもそうでなくても、１９行目は、コンパイラが１７行目のチェックを２０行目でネストのカウントをゼロすることとリオーダーするのを防ぎます。
クイッククイズ１５．６
図１５．１５の１７行目の t->rcu_read_unlock_special.s のロードのすぐ後にプリエンプションが起きたとします。するとタスクは、rcu_read_unlock_special() を呼ぶことがないのではありませんか？すると、タスクは、現在のグレースピリオドをブロックしているタスクのリストから自分を抜くことができず、その結果、グレースピリオドは無限に延長されませんか？
このプリエンプト可能RCU実装は、多数のリーダーへの優先度ブーストに伴う遅延を起こすことなく、リードがほとんどのデータ構造に対して、リアルタイム応答を可能とします。
プリエンプト可能スピンロック
は、Linuxカーネルにある長く続くスピンロックベースのクリティカルセクションのため、 -rt パッチセットの重要な部分です。この機能はまだ、メインラインに届いていません。これは概念的には、単純にスピンロックをスリープロックに置換することなのですが、比較的議論の余地があることがわかってきました。
脚注
さらに、-rt パッチセットの開発は、近年は遅くなってきました。たぶん既にメインラインLinuxカーネルにあるリアルタイム機能が、とても多くのユースケースにとって十分であるためでしょう[Edg13, Edg14]。しかし、OSADL (http://osadl.org/)は、残りのコードを -rt パッチセットからメインラインに移すための基金を集めようとしています。
しかしそれは、数十マイクロ秒以下のリアルタイム遅延を達成する作業のためにはとても必要です。
もちろん、これ以外のLinuxカーネルのコンポーネントでも、世界クラスのリアルタイム遅延を達成するために致命的に重要なものはいくつもあります。最も最近のものは、デッドラインスケジューラです。しかし、この節で一覧にしたものは、-rt パッチセットによって強化されたLinuxカーネルの動作について良い感触を与えるでしょう。
１５．４．１．２ ポーリングループ リアルタイムサポート
最初にちらりと見た時は、ポーリングループを使うことは全ての可能なオペレーティングシステム干渉問題を避けるように思えるかもしれません。結局、もしあるCPUが決してカーネルに入らないならば、カーネルは全く絵の外にいます。そして、カーネルを横にどける伝統的アプローチは、単純にカーネルを持たないことです。多くのリアルタイムアプリケーションは実際に、ベアメタルの上で走ります。特に、８ビットマイクロコントローラで走るものはそうです。
現代的なオペレーティングシステムカーネルにおいて、単純に、あるCPUにおいて単一のCPUバウンドのユーザモードのスレッドを走らせ、干渉の全ての原因を避けることで、ベアメタル性能を得られると期待するかもしれません。現実はもちろんより複雑ですが、Frederic Weisbecker [Cor13]が率いる NO_HZ_FULL 実装のおかげで、単純にそれを行うことができるようになってきました。それは、Linuxカーネルのバージョン３．１０に採用されました。とは言っても、そのような環境を正しく設定するには十分な注意が必要です。多くのOSジッターの可能な源を制御する必要があるからです。以下の議論は、いくつかのOSジッターの源の制御を取り上げます。それには、デバイス割り込み、カーネルスレッドとデーモン、スケジューラのリアルタイムスロットリング（これは機能です。バグではありません！）、タイマー、リアルタイムでないデバイスドライバ、カーネル内のグローバル同期、スケジューリングクロック割り込み、ページフォルト、そして最後に、リアルタイムでないハードウェアとファームウェアが含まれます。
割り込みは、大量のOSジッターの素晴らしい源です。不幸にも、ほとんどの場合、割り込みはシステムが外の世界と通信するために絶対に必要です。OSジッターと外の世界との接触を維持することのこの競合を解決する一つの方法は、少数のハウスキーピングCPUを保持して、全ての割り込みをこれらのCPUに強制することです。LinuxソースツリーのDocumentation/IRQ-affinity.txtファイルは、デバイス割り込みを指定したCPUに向かわせる方法を説明します。それは２０１５年初頭時点では、こんな感じです。
echo 0f > /proc/irq/44/smp_affinity
このコマンドは割り込み #44 を、CPU０から３に閉じ込めます。スケジューリングクロック割り込みは特別の扱いが必要なことに注意下さい。この節の後のほうで議論します。
OSジッターの二つ目の源は、カーネルスレッドとデーモンのためです。個々のカーネルスレッド、RCUのグレースピリオド kthread (rcu_bh, rcu_preempt, そして rcu_sched)など、は、taskset コマンド、sched_setaffinity() システムコール、 cgroups を使えば、希望する任意のCPUに強制することができます。
CPUごとの kthread はしばしばもっと面倒です。ハードウェア構成とワークロードレイアウトを制限することもあります。これらの kthread からのOSジッターを防ぐには、以下のどれかが必要です。ある種のハードウェアはリアルタイムシステムに接続しないこと。全ての割り込みとI/O開始はハウスキーピングCPUで行われること。ワーカーCPUに作業を向けないように、特殊なカーネル Kconfig あるいはブートパラメタを選択すること。あるいは、ワーカーCPUは決してカーネルに入らないこと。特定の kthread ごとの忠告は、Linuxカーネルソースの Documentation ディレクトリの kernel-per-CPU-kthreads.txt に見つかるでしょう。
リアルタイム優先度で走っているCPUバウンドなスレッドへのLinuxカーネル内のOSジッターの３つ目の源は、スケジューラ自身です。これは、意図したデバッグ機能です。もしあなたのリアルタイムアプリケーションに無限ループバグがあっても、１秒あたり少なくても５０ミリ秒が重要なリアルタイムでない作業に割り当てられるのを保証するために設計されました。しかし、あなたがポーリングループスタイルのリアルタイムアプリケーションを実行している時には、このデバッグ機能を無効にする必要があるでしょう。これは、以下のようにすればできます。
echo -1 > /proc/sys/kernel/sched_rt_runtime_us
もちろんこのコマンドを実行するにはルートとして実行している必要があります。そして、あなたはスパイダーマンの原則を注意深く考える必要もあるでしょう。危険を避ける一つの方法は、前のパラグラフで述べたように、CPUバウンドなリアルタイムスレッドを実行している全てのCPUから、割り込みとカーネルスレッド、デーモンをオフロードすることです。さらに、あなたはDocumentation/schedulerディレクトリにある文書を注意深く読むべきです。sched-rt-group.txtファイルにあるものは特に重要です。特に、もしあなたが CONFIG_RT_GROUP_SCHED Kconfig パラメタで有効になる cgroups リアルタイム機能を使っているならばそうです。その場合あなたは、Documentation/cgroups ディレクトリにある文書も読むべきです。
OSジッターの４つ目の源は、タイマーから来ます。ほとんどの場合、あるCPUをカーネルから遠ざけておけば、タイマーがそのCPUでスケジュールされることは防げます。一つの重要な例外は、再出するタイマーです。その場合、あるタイマーハンドラはその同じタイマーの後の以降の出現をポストします。そのようなタイマーがどんな理由にせよあるCPUで開始したら、そのタイマーは周期的にそのCPUで走り続けます。それはOSジッターを無限に起こします。再出するタイマーをオフロードする野蛮ですが効果的な一つの方法は、CPUホットプラグを使って、CPUバウンドのリアルタイムアプリケーションスレッドを走らせる予定の全てのワーカーCPUをオフラインとして、次にこの同じCPUをオンラインにして、あなたのリアルタイムアプリケーションを開始することです。
OSジッターの5つ目の源は、リアルタイム使用が意図されていないデバイスドライバから来ます。古い有名な例として、２００５年には、VGAドライバは画面を消去するために、割り込みを禁止してフレームバッファをゼロにしました。それは、何十ミリ秒ものOSジッターを起こしました。デバイスドライバが引き起こすOSジッターを避ける一つの方法は、リアルタイムシステムで今まで数多く使われてきたデバイスを注意深く選ぶことです。そうすれば、そのリアルタイムバグは直っているはずです。もう一つの方法は、デバイス割り込みとそのデバイスを使う全てのコードを専用のハウスキーピングCPUに閉じ込めることです。三つ目の方法はそのデバイスがリアルタイムワークロードをサポートする能力をテストし、全てのリアルタイムバグを直すことです。
脚注
もしあなたがこのアプローチを取るなら、どうぞあなたの修正をアップストリームにサブミットして、他の人が利益を得られるようにして下さい。あなたがご自分のアプリケーションをLinuxカーネルの後のバージョンに移植する必要が生じた時には、あなたもその「他の人」の一人となることを覚えておいて下さい。
OSジッターの六つ目の源は、カーネル内のある種のシステム全体にわたる同期アルゴリズムから来ます。多分、最も顕著なのは、グローバルな TLB フラッシュアルゴリズムです。これは、メモリアンマップ操作を避けることで避けることができます。特に、カーネル内のメモリアンマップ操作を避けることです。２０１５年初頭では、カーネル内のアンマップ操作を避ける方法は、カーネルモジュールをアンロードしないことです。
OSジッターの７つ目の源は、スケジューリングクロック割り込みと、RCUコールバック呼び出しから来ます。これらは、あなたのカーネルを、NO_HZ_FULL Kconfig パラメタを有効にしてビルドし、nohz_full=パラメタに、リアルタイムスレッドを実行するワーカーCPUの一覧を指定してブートすることで避けられます。例えば、nohz_full=2-7 は、CPU２，３，４，５，６と７をワーカーCPUとして割り当てます。そして、CPU０と１をハウスキーピングCPUとして残します。ワーカーCPUは、それぞれのワーカーCPUに、実行可能タスクが一つしかいない時にはスケジューリングクロック割り込みを発生させません。そして、それぞれのワーカーCPUのRCUコールバックは、ハウスキーピングCPUの一つの上で呼ばれます。そのCPUに実行可能タスクが一つしかないためにスケジューリングクロック割り込みを抑止しているCPUを、adaptive ticks モードにいると言います。
nohz_full= ブートパラメタの代わりに、あなたのカーネルを NO_HZ_FULL_ALL をつけてビルドすることもできます。それは、CPU０をハウスキーピングCPUとして割り当て、全ての他のCPUをワーカーCPUとします。いずれにしても、システムの残りの部分によって引き起こされるハウスキーピング負荷を処理するために、十分な数のハウスキーピングCPUを割り当てることを保証するのは重要です。それには、注意深いベンチマークとチューニングが必要です。
もちろん、タダのお昼ごはんというものはありません。NO_HZ_FULL も例外ではありません。以前に述べたように、NO_HZ_FULL はカーネルとユーザの遷移をより高価にします。それは、差分処理の課金の必要性と、カーネルサブシステム（RCUのような）に、遷移を伝える必要性のためです。それはまた、POSIX CPU タイマーが有効なプロセスを実行しているCPUが adaptive-ticks モードに入ることを許しません。これ以外の制限、トレードオフ、そして設定上の助言は、Documentation/timers/NO_HZ.txt に見つかるでしょう。
OSジッターの８つ目の源は、ページフォールトです。ほとんどのLinux実装は、メモリ保護のためにMMUを使っていますから、これらシステムの上で動くリアルタイムアプリケーションは、ページフォールトすることがあります。あなたのアプリケーションのページをメモリに固定するために、mlock() と mlockall() システムコールを使って下さい。そうすれば、メジャーページフォールトを避けられます。もちろん、スパイダーマンの原則が適用されます。なぜならば、あまりに多くのメモリをロックダウンすることは、システムが他の仕事をすることを妨げるからです。
OSジッターの９つ目の源は、不幸にも、ハードウェアとファームウェアです。なので、リアルタイム用途のために設計されたシステムを使うことが重要です。OSADL は長期間に渡るシステムのテストを実行しています。なので、そのウェブサイト ((http://osadl.org/) を参照することは役に立つでしょう。
不幸にも、OSジッターの源のこの一覧は決して完成しません。カーネルの新しいバージョンごとに変わるだろうからです。このため、OSジッターの源の増加分を追跡することができることが必要です。CPU N が、CPUバウンドのユーザモードのスレッドを走らせているとすると図１５．１６に示したコマンドはこのCPUがカーネルに入った全ての契機の一覧を作成します。もちろん、５行目の N は問題のCPUの番号に変えないといけません。そして、２行目の 1 は、カーネル内の関数呼び出しの追加のレベルを見るために増やすこともできます。結果となるトレースは、OSジッターの源を追跡する助けになるでしょう。
お分かりのように、CPUバウンドのリアルタイムスレッドをLinuxのような汎用OSの上で走らせてベアメタル性能を得るのは、詳細にわたって大変な注意が必要です。もちろん自動化は助けになり、ある程度の自動化は適用されてきました。しかし、比較的使用者数が少ないために、自動化は比較的ゆっくりと現れることが予測されます。しかし、汎用のオペレーティングシステムを実行しながらベアメタルに近い性能を得る能力は、ある種類のリアルタイムシステムを構築することを容易にすることが約束されます。
１５．４．２ 並列リアルタイムアプリケーションを実装する
リアルタイムアプリケーションを開発することは、幅広い題材です。この節は、いくつかの点に触れることができるだけです。それについて、１５．４．２．１節はリアルタイムアプリケーションで一般的に使われるいくつかのソフトウェアコンポーネントを見ます。１５．４．２．２節はポーリングループをベースとするアプリケーションをどのように実装するかについての簡単な概略を示します。１５．４．２．３節は、ストリーミングアプリケーションについて同様の概略を与えます。そして１５．４．２．４節はイベントベースのアプリケーションを簡単に取り上げます。
１５．４．２．１ リアルタイムコンポーネント
工学の全ての領域においてそうであるように、コンポーネントの頑強なセットは生産性と信頼性にとって必須です。この節は、リアルタイムソフトウェアコンポーネントの完全なカタログではありません。そのようなカタログは一冊の本全体を埋めるでしょう。そうでなく、これは利用可能なコンポーネントの型の簡単な概略です。
リアルタイムソフトウェアコンポーネントを探す自然な場所は、ウェイト無しの同期 [Her91]を提供するアルゴリズムでしょう。そしてロック無しのアルゴリズムはリアルタイムコンピューティングにとって実際にとても重要です。しかし、ウェイト無しの同期は有限時間内の前方進行を保証するだけです。そしてリアルタイムコンピューティングはずっと厳しい、指定時間内の前方進行保証に適するアルゴリズムを必要とします。結局、一世紀は有限ですが、あなたのデッドラインがミリ秒で測定されるならば役には立ちません。
しかし、実際に指定時間内の応答時間を提供する重要なウェイト無しのアルゴリズムがいくつかあります。それには、アトミックtest and set、アトミックexchange、アトミックfetch-and-add、循環配列をベースとする単一生産者／単一消費者のFIFOキュー、そして、多くのスレッドごとに分割されたアルゴリズムがあります。さらに、最近の研究は、ロック無しの保証を持つアルゴリズムは、統計的に公平なスケジューラと、フェイルストップなバグが無いことを前提とすれば、現実的には同じ遅延を提供するという観察を確認しました [ACHS13]。
脚注
ウェイト無しのアルゴリズムは、全てのスレッドが有限時間内に進行することを保証します。一方、ロック無しのアルゴリズムは、少なくても一つのスレッドが有限時間内に進行することを保証するだけです。
脚注
この論文は、同時に、bounded minimal progress の概念を導入しました。それは、理論の世界から、リアルタイム実践への歓迎すべき一歩です。
これは、ロック無しのスタックとキューが、リアルタイム用途に適切であることを意味します。
クイッククイズ１５．７
でも、フェイルストップなバグがあっても正しい動作をすることは、価値あるフォールトトレランスな性質ではありませんか？
理論的心配にもかかわらず、現実には、リアルタイムプログラムでロックはしばしば使われます。しかし、より厳しい制約のもとでは、ロックベースのアルゴリズムも指定時間内の遅延を提供することができます [Bra11]。その制約は以下を含みます。
１ 公平なスケジューラ。固定優先度という一般的な場合には、最も高い優先度のスレッドにだけ、指定時間内の遅延が提供されます。
２ ワークロードをサポートできる十分なバンド幅。この制約をサポートする実装規則は、「通常の運転中は、全てのCPUには少なくても５０％のアイドル時間がある」あるいは、もっと形式的には、「提供される負荷は、ワークロードが全ての時刻においてスケジュール可能であることに十分なほどに低い」でしょう。
３ フェールストップバグがないこと。
４ 有限の確保、転送、そして解放遅延を持つ、FIFOのロックプリミティブ。繰り返しますが、それぞれの優先度内でFIFOであるロックプリミティブという一般的な場合には、最も高い優先度のスレッドにだけ、指定時間内の遅延が提供されます。
５ 無限時間の優先度逆転を防ぐ何らかの方法。この章で以前に述べた、優先度シーリングと優先度継承規則ならば十分です。
６ ロック確保のネストが有限であること。ロックの数は無限にあっても構いません。ただし、あるスレッドが一度に決してそれらのうちのいくつか（理想的にはただひとつだけ）以上を確保しない限りにおいて。
７ スレッド数が有限であること。前の制約と組み合わせると、この制約は、どのロックでも、それを待っているスレッドの数は有限であることを意味します。
８ 全てのクリティカルセクションで費やされる時間は有限であること。どのロックでも、それを待っているスレッドの数は有限であることと、クリティカルセクションの長さが有限であることより、待ち時間は有限となります。
クイッククイズ１５．８
この一覧の前に、「これを含む」と書いてあるのが気になります。他にも制約があるのですか？
この結果は、多くのアルゴリズムとデータ構造をリアルタイムソフトウェアで使うことができることを示します。そして、昔からあるリアルタイム実践を正当化します。
もちろん、注意深くそして単純なアプリケーション設計も極めて重要です。世界で最高のリアルタイムコンポーネントでも、貧弱に考えられた設計の埋め合わせはできません。並列リアルタイムアプリケーションにとって、同期オーバーヘッドは明らかに設計上の鍵となるコンポーネントでなくてはいけません。
１５．４．２．２ ポーリングループアプリケーション
リアルタイムアプリケーションの多くは、センサーデータを読んで、制御法則を計算して、制御出力を書く、単一のCPUバウンドのループから構成されます。もし、センサーデータを提供し、制御出力を受け付けるハードウエアレジスタがそのアプリケーションのアドレス空間にマップされているならば、このループは完全にシステムコールが要りません。しかし、スパイダーマンの原則に注意下さい。大きな力は大きな責任を伴う。この場合、ハードウエアレジスタに不適当な参照をして、そのハードウエアを文鎮化するのを避けるという責任です。
この構成はしばしば、ベアメタルの上で走ります。オペレーティングシステムの恩恵（あるいは干渉）なしにです。しかし、ハードウエア能力が向上し、自動化のレベルが上がるに連れて、より多くのソフトウェア機能が求められるようになってきました。例えば、ユーザインタフェース、ロギング、そして報告、それらは全てオペレーティングシステムの恩恵を受けることができます。
ベアメタルの上で走ることのほとんどの利益を得ながら、汎用オペレーティングシステムの完全な機能と能力へのアクセスを得る一つの方法は、１５．４．１．２節で述べた Linuxカーネルの NO_HZ_FULL 機能を使うことです。このサポートは、最初に、Linuxカーネルのバージョン３．１０で可能となりました。
１５．４．２．３ ストリーミングアプリケーション
人気のある、ある種ビッグデータのリアルタイムアプリケーションは、入力を多くの源から得て、それを内部的に処理し、そして警告とまとめを出力します。このストリーミングアプリケーションはしばしば高度に並列で、源からの異なる情報を並列に処理します。
ストリーミングアプリケーションを実装する一つのアプローチは、稠密な配列の循環FIFOを使って、異なる処理手順をつなぐことです [Sut13]。そのようなそれぞれのFIFOはそれへと生産する単一のスレッドと、それから消費をする（たぶん別の）単一のスレッドを持ちます。ファンインとファンアウトポイントは、データ構造ではなくてスレッドを使います。なので、もし複数のFIFOの出力をマージする必要がある時は、独立したスレッドがそれらから入力して、別の、この独立のスレッドだけが唯一の生産者である別のFIFOに出力します。同様に、もしあるFIFOの出力を分割する必要がある時は、独立したスレッドがこのFIFOから入力して、必要に応じて複数のFIFOに出力します。
この規則は、制限が多いように見えるかもしれません。しかしそればスレッド間の通信を最低限の同期オーバーヘッドで可能とします。そして、厳しい遅延制約を満たそうとするには、最低限の同期オーバーヘッドは重要です。これは特に、それぞれの手順での処理量が小さい時に当てはまります。その場合、同期オーバーヘッドは処理オーバーヘッドに比べて重要になります。
個々のスレッドはCPUバウンドかもしれません。その場合、１５，４，２，２の助言が適用できます。一方、個々のスレッドがそれぞれの入力FIFOからのデータを待ってブロックするならば、次の節の助言が適用できます。
１５．４．２．４ イベントドリブンのアプリケーション
イベントドリブンのアプリケーションの楽しい例として、中間的な大きさの工業エンジンへの燃料の噴射を使いましょう。通常の運転条件では、このエンジンは頂上のデッドな中心の周りの、角度一度の範囲内で、燃料が噴射されることを要求します。回転数を1,500-RPMとするならば、１秒に２５回、あるいは１秒に約９０００度の回転があります。それを変換すると、１度あたり、１１１マイクロ秒になります。なので、燃料噴射は約１００マイクロ秒の時間間隔内にスケジュールする必要があります。
時間指定のウェイトを燃料噴射を開始するために使うとします。ただ、あなたがエンジンを作っているなら、回転センサーをつける方が良いでしょう。時間指定のウェイトの機能をテストする必要があります。たぶん、図１５．１７に示すテストプログラムを使って。不幸にも、このプログラムを走らせると、-rt カーネルにおいても、許されない時間ジッターが起きることがあります。
一つの問題は、POSIX CLOCK_REALTIME は、奇妙なことに、リアルタイム用途には意図されていないことです。そうでなく、それはプロセスあるいはスレッドが消費したCPU時間の総計に対して、「リアルタイム」であることを意味します。リアルタイム用途には、その代わりに、CLOCK_MONOTONIC を使うべきです。しかしこの修正をしても、結果は未だに許容できないものです。
もう一つの問題は、スレッドは sched_setscheduler() システムコールを使って、リアルタイム優先度に上げられなくてはいけないことです。しかし、この修正でも不十分です。なぜならば、まだページフォールトがあるからです。mlockall() システムコールを使って、このアプリケーションのメモリを固定し、ページフォールトを防ぐ必要もあります。これらの修正を全部入れると、最後に結果は許容できるものとなるかもしれません。
他の状況では、さらに調整が必要かもしれません。時間に致命的なスレッドをそれ固有のCPUにアフィニティ設定する必要があるかもしれません。そのCPUから割り込みをアフィニティ設定して除く必要もあるかもしれません。ハードウェアとドライバを注意深く選ぶ必要があるでしょう。カーネル設定を注意深く選ぶ必要があるというのはとてもあり得ます。
この例でわかるように、リアルタイムコンピューティングはとても容赦無いことがあります。
１５．５ リアルタイム 対 真に高速：どのようにして選びますか？
リアルタイムと、真に高速なコンピューティングの間の選択は、難しいことがあります。リアルタイムシステムはしばしば、リアルタイムでないコンピューティングに対して、スループットのペナルティを科しますから、必要が無いのにリアルタイムを使うことは、図１５．１８に楽しく描かれるように問題になることがあります。一方、リアルタイムが必要なときにそれを使わないことも、図１５．１９に楽しく描かれるように問題になることがあります。あなたに上司を気の毒に思わせるには、ほとんど十分です！
一つの大まかな法則は、選択するために以下の４つの質問を使います。
１ 長期間に渡るスループットの平均だけが、ゴールですか？
２ 高負荷が応答時間を劣化させるのは許されますか？
３ mlockall() システムコールの使用を禁止するような、厳しいメモリの使用量制限がありますか？
４ あなたのアプリケーションの基本的な仕事の要素は、完了するのに１００ミリ秒以上かかりますか？
この質問の答えが一つでも「はい」ならば、あなたは、リアルタイムよりは、真に高速、を選ぶべきです。そうでないなら、リアルタイムがあなたに向いているかもしれません。
賢く選択下さい。そしてもしあなたが本当にリアルタイムを選ぶなら、あなたのハードウェア、ファームウェア、そしてオペレーティングシステムがその仕事に耐えるかをよく確かめて下さい！
以上