私の書いたいくつかの並列プログラムは、最初から動きました。しかし、それは私がこの二十年の間、多数の並列プログラムを書いてきたからという以外の理由はありません。そして、私の書いたより多くの並列プログラムは、最初、正しく動いているように見えるだけで、実は、正しく動いているように私をあざむいていただけだったのです。
このため私は、自分の並列プログラムのために検証をとても必要としてきました。並列検証の裏にある基本的なトリックは、他のソフトウエア検証と同じですが、計算機は何が間違っているかを知っていると自覚することです。なので、計算機があなたにそれを伝えるように強いるのはあなたの仕事です。この章は、機械尋問の短期課程と考えることができます。
脚注
でも、親指をはさむネジと、水責め用の布は、お家に置いてきても良いですよ。この章はよりずっと洗練され、効果的な方法を扱います。特に、ほとんどの計算機システムは痛みを感じたり、溺れるのを恐れたりしませんから。
より長い課程は、検証についての最近の多くの本にあります。あるいは、少し古いけどとても役に立つ本もあります。検証は、ソフトウエアのあらゆる形に関係するとても重要な題材です。なのでそれは、それ自体で、熱心に学習する価値があります。しかしこの本は、主に並列性についての本なので、必然的にこの章は、この致命的に重要な題材の表面をひっかく程度のことしかできません。
11.1節は、デバッグの哲学を紹介します。11.2節は、トレースを、11.3節はアサーションを、11.4節は統計解析を議論します。11.5節は少し普通ではないコードレビューのアプローチを述べます。それは、神話的な10000個の目があなたのコードを見てないとわかった時には役に立つかもしれません。11.6節は並列ソフトウエアの検証に確率論を使うことの概要です。性能とスケーラビリティは並列プログラミングの1級の要求ですから、11.7節はそれを扱います。最後に、11.8節は楽しいまとめと、避けるべき統計のわなの短い一覧です。
11.1 まえがき
11.1.1節はバグの源を議論します。11.1.2節はソフトウェアを検証する時に必要な心がまえの概要を見ます。11.1.3はいつ検証を始めるべきかを述べます。11.1.4節は驚くほど効果的なオープンソース方式のコードレビューとコミュニティーテストを述べます。
11.1.1 バグはどこから来るか
バグは開発者から来ます。基本的な問題は、人の頭脳は計算機ソフトウエアを念頭に置いて進化したのではないということです。人の頭脳は、他の人の頭脳や、動物の頭脳に合わせて進化しました。この歴史のゆえに、以下の3つの計算機の特性は、しばしば人の直感にとって衝撃的なものとしてうつります。
1.計算機は典型的には常識を欠きます。数十年に渡って、人工知能の祭壇に捧げた研究にもかかわらず。
2.計算機は一般的にユーザの意図を理解できません。あるいは、より形式的に言うと、計算機は一般的に心の理論を持ちません。
3.計算機は普通は、断片的な計画からは、何一つ役に立つことはできません。そうでなく、それぞれすべての可能なシナリオのそれぞれすべての詳細が完全に明記されることを求めます。
最初の2点は議論の余地はないでしょう。多くの失敗した製品、多分有名なのは、Clippy と Microsoft Bob でしょう、で明らかにされました。ユーザに対して、人として対することを試みた結果、これら2つの製品は、自分では対処できないことがはっきりする程に、常識と心の理論の期待値を引き上げてしまったのです。もしかすると、最近、スマートフォンで現れ始めたソフトウェアアシスタントの多くは、よりうまくできるのかもしれません。とはいえ、それらの開発者はみんな、いまだに古いやり方で開発をしています。アシスタントはエンドユーザーのためになるかもしれませんが、自分の開発者を助けることはあまりないでしょう。
人間のこの断片的な計画への愛は、もっと説明の必要があります。特に、これが古典的な両刃の剣であることを思うとそうです。この、断片的な計画への愛は、その計画を実行する人が、(1)常識を持っていて、(2)その計画の背後の意図をよく理解できるという前提に明らかに基づいています。後の前提は特に、計画をする人と実行する人が同じ一人であるという一般的な場合には正しいです。この場合、計画は、障害が現れるとほとんど無意識に改定されます。このため、断片的な計画への愛は人類にとってうまくはたらいてきました。ある意味で、計画不可能なことを計画しようとして飢えて死ぬよりは、食べ物を見つける可能性のあることを手当たり次第にやってみることの方がましだったからです。しかし、過去の日常生活での断片的な計画の有効性はプログラム格納式計算機の将来においての有効性を保証しません。
さらに、断片的な計画に従うという必要性は、人の心理に重要な影響を与えてきました。人類の歴史のほとんどにおいて、人生はしばしば困難で危険だったという事実のためです。鋭い歯と爪との暴力的な遭遇の確率が高い断片的な計画を実行するのは、ほとんど正気といえないレベルの楽観性を必要とするというのはもっともなことです。その楽観性のレベルは実は人類のほとんどが持っています。この正気といえないレベルの楽観性は、プログラミング能力の自己評価にまで現れます。これは、自明なプログラムをコードすることに関する技術に関するインタビューの有効性と(それにそれに対しての反論)によって証拠付けられました。実際、正気とはいえないレベルの楽観性を持たない人のための医学用語は、「医学的に抑圧されている」です。そのような人々は、通常、日々の暮らしを送ることにとても困難があります。それは、正気とはいえないレベルの楽観性が、通常の健康な人生にとって重要であるという、もしかすると直感に反した事実を裏付けるものです。もしあなたが、正気と言えないほど楽観的でないなら、あなたは困難だけど価値のあるプロジェクトを始めようとすることは無いでしょう。
脚注
この大まかな規則には、いくつかの有名な例外があります。例外の一つのセットは、抑圧からの少なくても一時的な脱出を得るために、困難あるいは危険なプロジェクトを引き受ける人たちです。もう一つのセットは、失うもののない人たちです。そのプロジェクトは文字通り、生と死の問題です。
クイッククイズ11.1:
計算機の世界で、断片的計画に従おうとする傾向が、致命的に重要である時はいつですか?
重要な特別なケースは、価値があるけれども、それを実装するために必要な時間を正当化するほど十分な価値はないプロジェクトです。この特別ケースはとてもよくあることで、1つの初期的な現象は、意思決定者たちが、実際にプロジェクトを実装するために十分な投資をしたがらないことです。これへの自然な対応は、開発者が、プロジェクトの開始を認めてもらうために、非現実的な楽観的見積もりをすることです。もし組織(オープンソースであれ、プロプライエタリであれ)が十分に強力ならば、結果起こるスケジュールの遅延と予算超過をのりきれるかもしれません。そして、プロジェクトは日の光を見られるでしょう。しかし、組織が十分に強くなく、見積もりがゴミだったと明らかになって直ちに、意思決定者たちがプロジェクトをキャンセルできなかった場合、そのプロジェクトはその組織を殺すこともあります。さらに別の組織がそのプログラムを取り上げて、それを完成させるか、キャンセルするか、あるいはそれによって殺されるか、するかもしれません。あるプロジェクトは、いくつかの組織を殺した後でないと、成功しないかもしれません。連続組織殺害犯プロジェクトを最後に完成させる組織は、多大なレベルの謙虚さを持ち続けることができるように祈ることができるだけです。次のプロジェクトでその組織は殺されるかもしれないとしても。
正気と言えないほどの楽観性は重要かもしれませんが、それがバグの鍵となる源です(そして、たぶん、組織の失敗の)。なので、問題は、「巨大プロジェクトを始めるのに必要な楽観性を維持しながら、同時に、バグを低い唸り声を上げるだけの状態にとどまらせるための十分な現実性を注入し続けるにはどうしたらいいか?」ということです。次の節はこの難問を調べます。
11.1.2 必要なマインドセット
検証作業をするときはいつでも、あなたは以下の定義を心に留めるべきです。
1 唯一のバグの無いプログラムは自明なプログラムです。
2 信頼できるプログラムは既知のバグがありません。
これらの定義から、論理的に、すべての信頼できる自明でないプログラムはあなたが知らないバグを少なくても1つ持っているということです。なので、自明でないプログラムに対して行われる検証作業で、バグを見つけられないものは、それ自体が失敗です。このため、良い検証は、破壊の練習です。これはつまり、あなたがものをこわすのが好きなタイプの人なら、検証はあなたにとって正しいタイプの仕事と言えます。
クイッククイズ11.2:
あなたは、 time コマンドの出力を処理するスクリプトを書いているとします。出力は、こんなふうです。
real 0m0.132s
user 0m0.040s
sys 0m0.008s
スクリプトは、その入力のエラーをチェックする必要があります。そして、おかしな time 出力を受け取ったら、適切な診断メッセージを出す必要があります。シングルスレッドのプログラムが生成した time 出力で使うためにこのプログラムをテストするとしたら、あなたはどんなテスト入力を提供したらいいでしょう?
でもあなたはスーパープログラマーで、あなたのコードは常に毎回、最初から完璧でしょう。そうならば、おめでとう!どうぞこの章はとばして下さい。でも、私が疑り深いのを許して下さいね。まあ、わたしはこれまで、最初から完璧なコードが書けると主張する人にたくさん会ってきましたがその多くは、実際にはそんな芸当はできない人ばかりでした。それは、前述の、楽観性と自信過剰の議論を考えれば、それほど驚くことではないでしょう。そしてもしあなたが本物のスーパープログラマであっても、誰か他の人の仕事をデバッグしているかもしれませんね。 そうでない私達のためのアプローチの1つは、私達の通常の正気と言えないほどの楽観性の状態(もちろん、私はそれをプログラムできますよ!)と、厳しい悲観主義(動いているみたいだけど、どこかにもっとバグが隠れているのはわかっています。)の間を行き来することです。あなたがものをこわすのが好きなら、助けになります。そうでないか、あるいはあなたが好きなのは、他の人のものをこわすことだけなら、誰か、あなたのコードをこわすのが本当に好きな人を探して、あなたがそれをテストするのを手伝ってもらいましょう。 もう一つの、役に立つ心の枠組みは、他の人があなたのコードでバグを見つけることへの嫌悪です。この嫌悪は、他の人でなくあなたがバグを見つける確率を高めるために、あなたが理性を越えてあなたのコードを拷問する動機付けとなるでしょう。 最後の1つの心の枠組みは、あなたのコードが正しいことに誰かの命がかかっている可能性を考えることです。これも、あなたにコードを拷問してバグのありかを明らかにしようとする動機付けとなるでしょう。 この多様な心の枠組みは、異なる心の枠組みを持ち、異なるレベルの楽観性を持った複数の人々がプロジェクトに貢献するという可能性に扉を開きます。これは、適切に組織化されたなら、うまく働くでしょう。 活発な検証を、図11.1に示すように拷問の一種と考える人もいるかもしれません。
脚注
もっと皮肉的な人は、その人たちは代わりに、検証が、その人たちが直さないといけないバグを見つけるのを恐れているだけだと疑問に思うかもしれません。
そのような人は、ペンギンの漫画は忘れて、図11.2に示すように、拷問しているのは実際は無生物のものであることを思い出すと楽になるかもしれません。さらに、安心して下さい。自分のコードを拷問できない人は、コードによって拷問される運命にありますから。 しかし、これは、プロジェクトの生涯のうち、実際いつ、検証を始めるのがいいか、という問題を未解決とします。これについては、次の節で。
11.1.3 検証はいつ始めるべきですか?
検証はプロジェクトが始まったその同じ時に始めるべきです。 その理由ですが、バグを突き止めるのは、大きいプログラムの場合、小さいプログラムの時よりずっと大変です。なので、バグを突き止める時間と労力を最小にするには、コードの小さい単位をテストするのが良いです。このようにして見つけられるバグは全部ではないかもしれませんが、結構な割合が見つかるはずです。そして、見つけるのも、直すのもずっと簡単です。このレベルでのテストにより、設計全体の大きな欠陥が明らかになることもあります。そうすれば、そもそも設計からして文字通りこわれたコードを書いて時間をムダにすることも最小にできます。 でも、なぜ設計を検証するために、コードを書くまで待つのですか?
脚注
ことわざにあるにもかかわらず。「まず、コードを書かないといけません。そうすれば、考える意欲が出ます。」
3章と4章を読んでもらえば、いくつかの残念なよくある設計の欠陥を避けるための情報をあなたに提供できるかもしれません。また、あなたの設計を同僚と議論したり、単に書きあらわすだけでも、それ以外のバグを除く助けになるでしょう。 しかし、設計ができるまで検証を始めるのを待つというのは、待ちすぎであるというのはとてもあり得ることです。あなたの普通のレベルの楽観性は、あなたが要件を完全に理解する前に設計を始めるようにさせていませんか?この質問への答えはほとんど常に、「はい」です。欠陥のある要件を避ける1つの良い方法は、あなたのユーザを知ることです。本当にその人たちのためになりたいなら、その人たちと一緒に暮らさないといけません。
クイッククイズ11.3: あなたは私に、コーディングを始めるよりずっと前から、このアホな検証を全部やれと言っているのですか???それは、決して始められないための素晴らしい方法に聞こえます!!!
初めてのプロジェクトは異なる検証アプローチを必要とします。例えば、ラピッドプロトタイピング。ここでは、最初のいくつかのプロトタイプの主なゴールは、プロジェクトがどのように実装されるべきかを学ぶことであり、最初の試みから正しい実装を作ることではあまりありません。しかし、検証を省くべきではないことを心に留めるのは重要です。ただ、それへのラディカルに異なるアプローチを取るのです。 さて、あなたがプロジェクトを始めた時から検証を始めるべきだと分かったところで、以下の節は、これまで有効性が確認されてきた多くの検証テクニックと方法を述べます。
11.1.4 オープンソースのやり方
オープンソースプログラミング方法論はとても効果的であることが証明されてきていて、強力なコードレビューとテストの領域も含んでいます。
私は個人的に、オープンソースコミュニティの強力なコードレビューの効果を証言することができます。私が最初にLinuxカーネルに対して用意したパッチの1つは、分散ファイルシステムに関するもので、あるノードのユーザが他のノードのユーザがメモリにマップしているファイルのその位置に書き込むことが出来ました。この場合、ファイルシステムがライトの間、コヒーレンスを保つために、影響するページをマップから無効にする必要があります。私は最初の試みをパッチにして、オープンソースの金言、「速く投稿して、こまめに投稿しなさい。」に従って、パッチを投稿しました。そして私は、どうやってテストしようか考えました。
しかし、私がテスト戦略の概要を決めることができるより前に、私は私の投稿に対して、いくつかのバグを指摘する応答を受けました。私はバグを直して、パッチを再度投稿しました。そして、テスト戦略を考えることに戻りました。しかし、私がなんらかのテストコードを書く機会を持つ前に、私は再投稿したパッチに対してよりたくさんのバグを指摘した応答を受けました。このプロセスは何度も繰り返され、私は自分が実際にパッチをテストする機会があるのか、わからなくなりました。
この経験は、オープンソースのことわざが真実であることを示します。目玉が十分あれば、すべてのバグは洗い出される。
しかし、あなたがいくらかのコードあるいはパッチを投稿する時は、いくつかの質問に答えるのは意味があることです。
1 目玉のいくつが、実際にあなたのコードを見ますか?
2 いくつが、実際にあなたのバグを見つけるくらいに経験豊かで賢いですか?
3 彼らは正確にいつ、見てくれますか?
私は幸運でした。そこには、私のパッチが提供する機能を欲しがっている人がいました。その人は分散ファイルシステムで長い経験を持ち、私のパッチをほとんど直ちに見てくれました。私のパッチを見る人がいなければ、レビューもなく、バグも見つかることはなかったでしょう。もし私のパッチを見る人が分散ファイルシステムの経験不足なら、すべてのバグを見つけることはできなかったでしょう。その人達が見るまでに1ヶ月、あるいは1年かかったなら、私はパッチがどのように動くはずだったかを忘れてしまって、直すのがよりずっと難しくなっていたでしょう。
しかし私達は、オープンソース開発の2つめの主義を忘れてはいけません。つまり、強力なテストです。例えば、とてもたくさんの人がLinuxカーネルをテストします。サブミットされたパッチをテストする人もいます。もしかするとあなたのかもしれません。他の人は、-next ツリーをテストします。それは助けになりますが、あなたがパッチを書いてから、それが -next ツリーに現れるまで、何週間、あるいは何ヶ月もかかることがあります。その頃には、パッチはあなたの頭のなかでそれほど新鮮ではなくなっています。さらに他の人は、メンテナーツリーをテストします。それもしばしば似たような時間の遅れがあります。
メインラインあるいはマスターソースツリー(Linuxカーネルの場合、Linus のツリー)にコミットされるまで、コードをテストしない人もかなりいます。もしあなたのメンテナーが、テストされるまであなたのパッチを受け付けようとしないならば、あなたはデッドロック状態になります。あなたのパッチはテストされるまで受け付けられません。しかし、それは、受け付けられるまでテストされません。そうはいっても、メインラインコードをテストする人たちはまだ比較的アグレッシブです。多くの人と組織は、コードがLinuxディストリビューションにプルされるまでコードをテストしないことを思えば。
そして、もし誰かが本当にあなたのパッチをテストするとしても、その人があなたのバグを見つけるのに必要なハードウエアとソフトウエア構成、それにワークロードを使うかは何も保証がありません。
なので、オープンソースプロジェクトにコードを書くときであっても、あなたは自分のテストスイートを開発して、実行する準備をする必要があります。テスト開発は、評価されることが少なくてとても貴重なスキルです。なので、あなたが使える既存のテストスイートは何でも、十分に活用するように注意下さい。テスト開発は重要ですが、これ以上の議論は、その題材に特化した本に譲りましょう。なので、以下の節は、あなたが既に良いテストスイートを持っているという前提で、あなたのコードでバグを見つけることを議論しましょう。
11.2 トレース
他が全部ダメな時は、printk() を入れましょう!あるいは、あなたがユーザモードの C 言語アプリケーションの作業をしているなら、 printf() です。
理由は簡単です。もしあなたが、どのようにコード実行がある点に到達したかをわからないなら、コードの前の方に printf 文をちりばめて、何が起きたのかを調べましょう。gdb (ユーザアプリケーションのとき)あるいは、 kgdb (Linux カーネルをデバッグするとき)のようなデバッガを使えば、同様の効果と、さらに便利さと柔軟性を得ることができます。さらにずっと洗練されたツールはあって、ごく最近の製品は、失敗の時点から時間をさかのぼる能力があるものもあります。
これらのブルートフォーステストツールは、すべて貴重です。特に、最近は典型的なシステムは64K 以上のメインメモリと、4MHzより速いCPU を持っていますから。これらのツールについては書かれたものが多いので、この章ではもうあまり触れません。
しかし、これらのツールはすべて深刻な欠点があります。やりたいことが、高性能な並列アルゴリズムの高速パスにおいて、何か変なことが起きているのを調べることだとすると、それはしばしば多大なオーバヘッドをともないます。この目的のために特別のトレース技術があります。それは、典型的には、データ所有技術(8章を参照)を駆使して、実行時のデータ採取オーバヘッドを最小にします。Linux カーネルでの1つの例は、「トレースイベント」です。ユーザ空間を扱う別の例(しかし、Linux カーネルにはまだ受け入れられていません。訳注。今は?)は、LTTng です。これらはそれぞれ、CPU ごとのバッファを使い、データが極端に低いオーバヘッドで採取できるようにしています。そうとはいえ、トレースを有効にすると、バグを隠すのに十分なくらいタイミングを変え、ハイゼンバグになることがあります。それについては、11.6節、特に11.6.4節で述べます。
もしあなたがハイゼンバグを避ける事ができても、他の落とし穴が待っています。例えば、マシンは本当にすべてを知っていますが、それが知っていることはほとんど常にあなたの頭に入る量をはるかに超えています。このため、高品質のテストスイートは普通は、洗練されたスクリプトがついてきて、大量の出力を解析できるようにしています。しかし、注意して下さい。スクリプトは驚くべきことに気がつくことはあまりありません。私の rcutorture スクリプトは、良い例です。これらのスクリプトの初期のバージョンは、RCU グレースピリオドが無限にストールするテスト実行で完全に満足していました。もちろん、この結果、スクリプトは直されて、RCU グレースピリオドのストールを検出するようになりました。しかしこれは、スクリプトは、私が検出させようと考えた問題だけを検出できるという事実を変えることはありません。スクリプトは便利ですが、時々、手作業で rcutorture 出力をスキャンすることの代わりにはなりません。
トレースと、特に printk() 呼び出しのもう一つの問題は、それらのオーバヘッドがしばしば本番使用には大きすぎることです。そういう場合のいくらかでは、アサーションが便利です。
11.3 アサーション
アサーションは、通常、以下のように実装されます。
1 if (something_bad_is_happening())
2 complain();
このパターンは、しばしば、C プリプロセッサマクロあるいは、言語のイントリンシックにカプセル化されています。例えば、 Linxu カーネルでは、これは、WARN_ON(something_bad_is_happening()) と表現されるかもしれません。もちろん、もし、something_bad_is_happening() がとてもたくさん起きると、結果のレポートは他の問題をわからなくすることがあります。その時は、WARN_ON_ONCE(something_bad_is_happening()) の方がより適切です。
クイッククイズ11.4:
WARN_ON_ONCE を、どう実装しますか?
並列コードでは、起きる可能性のある1つの特別に困ったサムシングは特定のロックのもとで呼ばれることが期待される関数が、そのロックが確保されないで呼ばれるかもしれないことです。そういう関数は、ときには、ヘッダコメントに、「コール元はこの関数を呼ぶときには、 foo_lock を持っていないといけません」などと書いてあることがあります。しかし、そのようなコメントは誰かが実際にそれを読まないと役に立ちません。lock_is_held(&foo_lock) のような実行される文の方が、ずっと強制力があります。
Linux カーネルの lockdep 機能は、このステップをさらに進めて、潜在的なデッドロックを報告したり、関数が適切なロックが取られているかを検証することができるようにします。もちろん、この追加の機能は大きなオーバヘッドをもたらしますから、 lockdep は本番使用にはあまり適切ではありません。
なので、チェックが必要だけれど実行時のチェックオーバヘッドが許容されない場合は、どうしましょう?1つのアプローチは、静的解析で、次の節でお話しします。
11.4 静的解析
静的解析はあるプログラムが別のプログラムを入力にして、そこにある誤りや脆弱性を報告する検証技術です。面白いことに、ほぼすべてのプログラムはコンパイラやインタプリタによって静的解析されます。これらのツールはもちろん完全ではありませんが、それが誤りを位置づける能力はこの数十年でとても改善しました。これはひとつには、解析のためのメモリが64Kバイト以上使えるようになったことによります。
元の UNIX lint ツールはとても便利でした。ただ、そのほとんどの機能はそれ以降、C コンパイラに取り込まれてきました。それでも、今でも多くの lint のようなツールが開発され、使われています。
Sparse static analyzer は、 Linux カーネルの、以下のような高レベルの問題を探します。
1.ユーザ空間の構造体に対して、ポインタを誤って使う。
2.長すぎる定数を代入する。
3.switch 文が空
4.ロック確保と解放プリミティブが対応していない。
5.per-CPU プリミティブの使い方の誤り
6.RCU プリミティブを、RCU でないポインタに使う。あるいはその逆。
コンパイラは、これからもその静的解析能力を向上させていくでしょうが、Sparse static analyzer は、コンパイラの外での静的解析の利点を示しました。特に、アプリケーション固有のバグを見つけることにおいて。
11.5 コードレビュー
いろいろなコードレビュー活動は、静的解析の特殊ケースです。ただ、人が解析をします。この節は、インスペクション、ウオークスルー、そして自己インスペクションについて述べます。
11.5.1 インスペクション
伝統的に、正式なコードインスペクションは、対面の会合で行われ、役割も正式に決まっています。モデレーター、開発者、そして、それ以外の1人か2人の参加者。開発者はコードを順に読んでいき、それが何をしていて、なぜそれがうまくいくかを説明します。1人か2人の参加者は質問をして、問題を指摘します。モデレーターの仕事は、矛盾を解決することと、記録を取ることです。このプロセスは、バグを見つけるのにとても効率的なことがあります。特に、参加者のすべてがそこにあるコードをよく知っている場合。
しかし、この対面の正式な手続きは、グローバルな Linux コミュニティでは必然的にうまくいきません。ただ、IRC セッションごしにならうまくいくかもしれませんが。その代わりに、個人がそれぞれコードをレビューして、電子メールあるいは IRC でコメントを提供します。この記録は、電子メールアーカイブあるいは IRC ログで提供されます。そして、モデレーターは適切に自分の仕事をします。時々、フレームウォーがあるものの、このプロセスはそれなりにうまくいきます。特に、参加者のすべてがそこにあるコードをよく知っている場合。
脚注
とは言え、伝統的な形式的インスペクションに比べて、Linux カーネルコミュニティのアプローチの一つの優位点は、コードに詳しくない人からのより多くの貢献の可能性です。その人たちは、そのため、コードに詳しい人が抱いている誤った前提によって視界を塞がれることがありません。
Linux カーネルコミュニティのレビュープロセスは、改善の余地が十分にあります。
1 効率的なレビューを行うのに必要な、時間と経験を持つ人が得られないことがあります。
2 すべてのレビュー議論はアーカイブされているとはいえ、しばしばそれは「失われます」。つまり、知見は忘れられ、人々は議論を見つけることができません。これは、同じ古いバグを再度入れることになることがあります。
3 いったんフレームウォーが起きると、鎮めるのが難しいことがあります。特に、対立する人々が異なるゴール、経験、そして語彙を持っている時には。
このため、レビューをするときは、関連するコミットログ、バグレポート、あるいは、LWN の記事などの文書を見るのは良いことです。
11.5.2 ウオークスルー
伝統的なコードウオークスルーは、正式なインスペクションに似ています。ただ、あるテストケースにしたがって、そのグループがコードについて「計算機のふりをする」ところが違います。典型的なウオークスルーのチームは、モデレーター、書記(見つかったバグを記録します。)テストのエキスパート(テストケースを生成します。)そして、たぶん、それ以外に1人か2人。これはとても効率的なこともありますが、同様にとても時間がかかります。
私が正式なウオークスルーに参加してから、何十年になりますが、いまどきのウオークスルーはデバッガによるシングルステップを使ったらどうかと思います。以下のような、特別にサディスティックな手続きを想像することができるでしょう。
1 テスタがテストケースを示します。
2 モデレーターが、そのテストケースを入力にして、コードをデバッガのもとで開始します。
3 それぞれの行が実行される前に、開発者はその行の結果を予言し、なぜその結果が正しいかを説明するように求められます。
4 もし出力が、開発者の予言と異なるなら、これは潜在的なバグの証拠とみなされます。
5 並列コードの場合、「並列サメ」がそのコードと同時実行するコードにはどのようなものがあるか、そしてなぜその同時実行が無害であるかを問います。
サディスティック?確かに。効果的?うーん、多分。もし、参加者が要件と、ソフトウエアツールと、データ構造と、そしてアルゴリズムを良く理解しているならば、ウオークスルーはとても効果的になることができるでしょう。そうでない場合、ウオークスルーはしばしば、時間のむだです。
11.5.3 自己インスペクション
開発者は通常、自分自身のコードをインスペクトするのはあまり効果的にできません。しかし、それ以外に合理的な方法がない状況があります。例えば、その開発者がそのコードを見る権限のある唯一の人である場合、他の候補となることのできる開発者がみんな、忙しすぎる場合、あるいは、問題のコードがあまりにも珍奇なので、開発者が他の人にそれをまじめに受け取ってもらえず、まずはプロトタイプをデモするよりない場合などです。こういう場合、以下の手続きは、とても便利です。特に、複雑な並列コードのとき。
1 要件、データ構造の図、そして設計上の選択の根拠を含む設計文書を書きます。
2 エキスパートに相談し、必要なら設計文書を改訂します。
3 紙にペンでコードを書きます。進むにつれて誤りを直します。既存のほとんど同じコードシーケンスを参照する誘惑に抵抗します。そうでなくて、をれをコピーします。
4 誤りがあったら、新しい紙にコードを複写し、誤りを直します。最後の2つのコピーが等しくなるまで繰り返します。
5 自明でないコードに対して、正確さの証明を作成します。
6 可能なら、ボトムアップにコード断片をテストします。
7 すべてのコードが統合されたら、完全な機能と負荷テストをします。
8 コードがすべてのテストをパスしたら、コードレベルの文書を書きます。多分、前述の設計文書の補足とします。
私が、新しい RCU コードのために、この手続きに忠実に従ったとき、最後には、通常、2,3個のバグが残るだけでした。いくつかの顕著で(同時に困った)例外を除けば、私はこれらのバグを他の人より先に見つけることができました。とはいえ、時がたち、Linux カーネルのユーザの数が増え、多様になるに従って、このようなことはより一層難しくなって来ています。
クイッククイズ11.5:
なんで、既存のコードをペンで紙にコピーしないといけないんです???そんなことをすれば、写し間違いの確率が増えるだけでしょう?
クイッククイズ11.6:
この手続は、ばかげてオーバーエンジニアリングです。こんな方法で、合理的な量のソフトウエアが書けると、とうてい期待はできないでしょう???
前記手続きは、新しいコードに対してはうまくいきます。しかし、もしあなたが、既に自分で書いたコードをインスペクトしなければいけないとしたらどうでしょう?もちろんこの手続きは、あなたがコードを捨てるために書いたような特別な場合でも、古いコードに対して適用できます。しかし、以下のアプローチはそれよりはましな環境で便利かもしれません。
1 あなたのお好きな文書ツール(LATEX, HTML, OpenOffice, あるいはストレートな ASCII)を使って、問題のコードの高レベル設計を記述します。データ構造と、それらの構造がどのように更新されるかを示すために、たくさんの図を使います。
2 コードのコピーを作ります。すべてのコメントを取り去ります。
3 そのコードが何をするか、1文ずつ文書にします。
4 バグを見つけたら直します。
コードを詳細に説明することは、バグを見つけるのに優れた方法なので、これはうまくいきます。この2つ目の手続きは、誰か他の人の書いたコードに対して、あなたが考えるためにも良い方法です。しかし多くの場合、最初のステップだけで十分です。
他の人にレビューやインスペクションをしてもらうのは、たぶんより効率的で効果的でしょうが、前記手続きは、どんな理由にせよ、他の人を巻き込むことのできない場合には、とても便利です。
この時点で、あなたは、この退屈なペーパーワークをすることなしに並列コードを書くことはできないのか、疑問に思っているでしょう。以下は、それをするための、時の検証を経た方法です。
1 使用可能な並列ライブラリ関数を使うことでスケールするシーケンシャルプログラムを書きます。
2 マップリデュース、BOINC、ウェブアプリケーションサーバなどの並列フレームワークのための、シーケンシャルプラグインを書きます。
3 問題が完全に分割される、すばらしい並列設計をします。そして、通信なしに並列に動作する、シーケンシャルプログラムを単に実装します。
4 ツールが自動的に問題を分解して並列化してくれるアプリケーション領域(線形代数のような)のひとつにとどまります。
5 並列プログラミングプリミティブの、極端に規律化された使い方をして、結果となるコードが正しいことが容易にわかるようにします。
でも、注意して下さい。より良い性能あるいはスケーラビリティを得るために、「ちょっとだけ」規則を破る誘惑がいつもあります。規則を破るのはしばしば一般的な破綻につながります。つまり、あなたがこの節で説明したペーパーワークを注意深くやらない限り。 しかし、もしあなたがペーパーワークをやるか、前述の方法を使って、なんとか安全にペーパーワークを回避したとしても、バグは存在するだろうというのは悲しい現実です。より多くのより多様なユーザは、それだけで、より多くのバグをより素早く明らかにします。特に、ユーザが元の開発者が思ってもみないことをするときには。次の節は、並列ソフトウエアを検証するときにはあまりにもよく見かける、確率的なバグをどう扱ったらいいかを述べます。
11.6 確率とハイゼンバグ
さて、あなたの並列プログラムは失敗します。時々。
しかしあなたは、これまでの節のテクニックを使って、問題を見つけて、今やその手に修正があります!おめでとう!!! さて、問題は、どれだけテストをしたら、あなたが本当にバグを直したと確信できるかです。起きる確率を減らしただけでないですか?関連するいくつかのバグの1つを直しただけでないですか?まるで関係ない、むだな変更をしただけでないですか?つまり、図11.3で示される無限の質問への答えはなんでしょう? 不幸にも、正直な答えは、絶対の確信を得るためには、無限の量のテストが必要だということです。
クイッククイズ11.7: あなたがとてもたくさんのシステムを自由に使えるとします。例えば、現在のクラウド価格で、あなたはかなりの量のCPU時間を、比較的低コストで買うことができます。このアプローチを使って、すべての現実的な目的のために十分に確実といえるというところまで近づくというのはどうでしょう?
しかし、私達は、高い確率であれば、絶対に確かなことでなくても、喜んでそれで受け入れることがしばしばあります。なので、この問題に対するのに、強力な統計ツールを使うことができます。この節は、単純な統計ツールに焦点を当てます。これらのツールはとても便利ですが、この節を読むだけでは、ちゃんとした統計学の課程を取ることの代わりにはならないことに注意下さい。
脚注
それを私はとてもお勧めします。私が取ったいくつかの統計学の課程は、私がそれを学ぶのに使った時間をはるかに越える価値を与えてくれました。 単純な統計ツールの始めとして、私達が離散テストをしているのか連続テストをしているのかを決める必要があります。離散テストは、きちんと定義された個別のテスト実行を特徴とします。例えば、Linuxカーネルパッチのブートアップテストは離散テストの例です。あなたはカーネルをブートして、上がってくるかこないかです。あなたが、1時間、カーネルのブートテストをしたとしても、あなたがカーネルをブートしようと試みた回数と、ブートが成功した回数が、しばしば、あなたがテストに使った時間よりも重要です。機能テストは離散であることが多いです。 それに対して、もし私のパッチがRCUに関するものなら、私は、rcutorture を流します。それは、カーネルモジュールで、なんと驚くことに、RCU をテストします。カーネルをブートするときには、ログインプロンプトが現れるのが離散テストの成功を示しますが、rcutorture は、あなたがそれに止まれというか、カーネルがクラッシュするかのどちらかがあるまで喜んで RCU を拷問し続けます。rcutorture テストの継続時間が、(普通は、)あなたがそれを開始、停止した回数よりも重要です。なので、rcutorture は、連続テストの例です。このカテゴリには、多くのストレステストを含みます。 離散テストを扱う統計は、連続テストのそれとは少し違います。しかし、離散テストの統計の方が、単純でより近づきやすいです。さらに、離散テストのための統計は、しばしば、(少し正確さは落ちますが)連続テストにも適用できます。なので、離散テストから始めましょう。
11.6.1 離散テストのための統計学
ある実行でバグが起きる確率は10%で、5回の実行をするとします。少なくても一つの実行が失敗する確率をどのように計算しますか?一つの方法は、以下の通りです。
1 ある実行が成功する確率を計算します。それは90%です。
2 全ての5回の実行が成功する確率を計算します。それは、0.9の5乗で、約59%です。
3 二つの可能性しかありません。全ての5回の実行が成功するか、少なくても一つが失敗するか。なので、少なくても一つが失敗する確率は、100%引く59%で、41%です。
しかし多くの人々は手順を繰り返すよりは公式で計算する方が簡単だと感じます。もしあなたが、前記の手順の繰り返しがお好きなら、それをお使いください!公式がお好きな人には、単一の失敗の確率を f と呼びます。すると単一の成功の確率は 1 - f です。そして、n 回の実行全てが成功する確率は以下です。
失敗の確率は、 1 - Sn あるいは、以下です。
クイッククイズ11.8
なんですって???前記の、5回のテストでそれぞれが10%の失敗確率の例をこの公式に入れたら、59,050% でした。これは全く意味をなしません!!!
さて、テストが10%の割合で失敗しているとします。あなたが直したはずの修正が実際に改善効果があったと、99%確信するためには、あなたは何回このテストを実行する必要があるでしょう?
この質問を別の方法で問うなら、「失敗の確率を99%以上に上げるためには、このテストを何回実行する必要があるでしょう?」結局、テストを十分な回数実行して、少なくても一つの失敗を見る確率が99%になれば、その時に失敗がないということは、これが偶然だという確率はたった1%です。そして、 f= 0.1 を式11.2に代入して、 n を変えると、元のテストごとの10%の失敗の割合のもとでは、43回の実行で、少なくても一つのテストが失敗する確率が98.92%であることがわかります。そして、44回の実行で、少なくても一つのテストが失敗する確率は99.03%です。なので、もしも私たちの修正に対するテストを44回実行して、失敗しなければ、その修正が実際に本物の改善である可能性は99%です。
しかし、式11.2に繰り返し数字を代入するのは面倒かもしれません。なので、n について解きましょう。
最終的に、必要なテストの回数は、以下で与えられます。
f= 0.1 と Fn = 0.99 を等式11.6に代入すると、43.7 です。これは、私たちの修正が本物の改善であると99% 確信するためには、連続して44回の成功するテスト実行が必要なことを意味します。これは前の方法で求めた数字と一致し、それは安心できることです。
クイッククイズ11.9
等式11.6で、ログは、ベース10、ベース2、それともベース e ですか?
図11.4は、この関数を描きます。驚くことではないですが、それぞれのテスト実行が失敗する頻度が小さいほど、バグがなおったと99%確信するためにはより多くのテスト実行が必要です。もしバグが、テストがたった1%の割合で失敗するだけとするならば、心が折れる458回のテスト実行が必要です。失敗の確率が減るほど、必要なテスト実行回数は増えます。失敗の確率がゼロに近づくと、それは無限大になります。
この物語の教訓は、あなたがめったに起きないバグを見つけた時は、あなたが注意深く標的を定めたより大きな失敗率を持つテストを思いつくことができたならば、あなたのテスト作業はずっと簡単になるということです。例えば、あなたの標的を定めたテストが失敗率を1%から30%に引き上げたなら、99%の確信に必要な実行回数は458テスト実行からたった13テスト実行に下がります。
しかし、この13テスト実行は、あなたの修正が「何らかの改善」をもたらしたと99%確信できるだけです。
あなたがその代わりに、あなたの修正が失敗率を一桁小さくしたと99%確信したいとします。失敗のないテスト実行は、いくつ必要でしょう?
30%の失敗率からの一桁の改善は、3%の失敗率です。この数字を等式11.6に入れると、こうです。
なので、一桁の改善は、大まかに、一桁多いテストを必要とします。確信は不可能で、高確率はとても高価です。高信頼ソフトウェアの開発において、テストをより迅速に実行し、失敗をより確実に起こすことは、明らかに必須の技能です。11.6.4節はこの技能について述べます。
11.6.2 離散テストのための統計学を乱用する
さて、あなたが、約十時間に3回失敗する連続テストを持ち、あなたはその失敗を起こすとあなたが信じるバグをなおしたとします。あなたが、失敗の確率を下げたと99%確信できるためには、このテストを失敗なしにどれだけ長く流す必要があるでしょう?
統計学に過度の暴力をはたらくことなく、単純に、一時間の実行を30%の失敗率を持つ離散テストであると再定義することができます。すると、前節の結果により、このテストが十三時間、失敗なしに実行したら、私たちの修正が実際にプログラムの信頼性を改善した確率は99%でしょう。
教条主義の統計学家は、このアプローチを認めないかもしれません。しかし、悲しい事実は、この手の統計的方法論の乱用によって引き起こされる誤差は通常は、あなたがあなたのプログラムの失敗率を測定するときに避けられない誤差に比べて、とても小さいということです。とは言え、次の節はより怪しさの少ないアプローチを説明します。
11.6.3 連続テストのための統計学
この節はより攻撃的な数学を含みます。もしあなたが数学の攻撃を受ける気分でなければ、どうぞ前節の結果を使うか、11.6.3.2節まで飛ばしてください。たぶん、282ページの等式11.30を、後の参照のために覚えておいて下さい。
11.6.3.1 ポアソン分布を導く
テスト回数 n が増加し、テストごとの失敗 f が減るにつれて、数学を連続な領域に移動することは意味のあることになります。λ を nf と定義するのが便利です。n を増やして f を減らしても、λ は変わりません。直感的には、λは、単位時間当たりの失敗回数の期待値です。
さて、すると、全ての n テストが成功する確率は何でしょう?これは、以下で与えられます。
しかし、λ は nf に等しいので、これを f について解いて、f = λ / n です。前記等式にこれを代入して:
賢明でかつ数学好きの読者は、これは n が無限に大きくなると、 e ^ -λ に近づくことがわかるでしょう。言葉を代えて言えば、ある長さのテストでλ の失敗が期待されるなら、そのテストのゼロ失敗の確率 F0 は、以下で与えられます。
次の手順は、一つを除いて全てのテストが成功する確率を計算することです。それは:
階乗のある分数は、テスト結果の異なる置換の寄与のためです。f は単一の失敗確率で、(1 - f) ^ n - 1 は、残りのテストが成功する確率です。分子の n! は、n 回のテストの全ての置換を表し、分母の二つの階乗は、片方で一つの失敗と、もう片方で n - 1 の成功が区別できないことを表します。
階乗を相殺して上と下に 1 - f をかけると:
f は任意に小さいと仮定しますから、1 - f は任意に値 1 に等しいです。すると、分母を無くせます。
以前のように、f = λ / n を代入すると:
大きな n に対して、以前のように、後ろの項は、 e ^ -λ で近似できます。なので、λ の失敗が期待されるテストにおいて、単一の失敗の確率は、以下で与えられます。
三つ目の手順は、n 回のうち、二つを除いて全てのテストが成功する確率を計算することです。それは:
階乗を相殺して上と下に (1 - f) ^2 をかけると:
今回も、f は任意に小さいと仮定しますから、 (1 - f) ^2 は任意に値 1 に等しいです。すると、分母のその部分を無くせます。
また、f = λ / n を代入すると:
n は大きいと仮定しますから、n - 1 は任意に n に近いため、分子の n(n - 1) を分母の n^2 と相殺できます。またもや、最後の項は、 e ^ -λ で近似できますから、λ の失敗が期待されるテストにおいて、二つの失敗の確率は、以下で与えられます。
さて、より一般的な結論を試みる準備ができました。m 個の失敗があるとします。m は n に比べてとても小さいです。すると:
階乗を相殺して上と下に (1 - f) ^m をかけると:
お気づきと思いますが、f は任意に小さいので、 (1 - f) ^m は任意に値 1 に近く、落とすことができます。
もう一度、f = λ / n を代入すると:
m は n に比べて小さいので、分子の階乗は最後のもの以外全て、分母の n^m と相殺でき、この結果:
いつものように、大きな n に対して、最後の項は、 e ^ -λ で近似できます。なので、λ の失敗が期待されるテストにおいて、m 回の失敗の確率は、以下で与えられます。
これが、祝福されるべきポアソン分布です。より厳密な導出は、例えば、 Feller の古典的な “An Introduction to Probability Theory and Its Applications” [Fel50]
などの、高度な確率論の教科書ならどれにでも見つけられるでしょう。
11.6.3.2 ポアソン分布を使う
ポアソン分布を使って、11.6.2節の例を再実行してみましょう。この例には、時間あたり30%の失敗率を持つテストがあったのを思い出して下さい。質問は、修正と主張されるものが実際に失敗率を下げたと99%確信できるためには、このテストをその修正に対してどれだけ長く流す必要があるか、でした。これを解くには、F0 である e ^ -λ が0.01 である必要があります。λ について解くと、こうなります:
時間あたり 0.3 失敗ですから、必要な時間は、 4.6/0.3 = 14.3 です。それは、11.6.2節の方法で計算した十三時間と、10%内です。通常はあなたは自分の失敗率を10%以内の正確さで知ることはできないので、これは、11.6.2節の方法が、とても多くの状況でポアソン分布の良好で十分な代わりとなることを示します。
より一般的には、もし単位時間に n 失敗があり、修正が失敗率を下げたとP% 確信したいならば、以下の公式が使えます。
クイッククイズ11.10
平均で、バグが一時間に3回のテスト失敗を起こすとします。修正が失敗の確率を優位に下げたと99.9% 確信するためには、テストはエラーなしにどれだけ長く走らないといけないでしょう?
以前と同様、バグがより稀に起きて、要求される確信レベルがより大きいほど、エラーなしに走らないといけないテスト実行はより長くなります。
あるテストが、ほぼ一時間に一度失敗するとします。しかし、バグ修正の後、24時間のテスト実行は二回だけ失敗しました。これが、ランダムな運のためである確率はいくつでしょう?言葉を代えて言えば、この修正が統計的効果を何も持たない確率はいくつでしょう?この確率は、等式11.26を以下のように合計すると計算できます。
これは、ポアソン累積分布関数です。より短く、こう書くこともできます。
ここで m は、長いテスト実行での誤りの数(今の場合2)です。λ は、長いテスト実行での期待される誤りの数(今は24)です。この式に、 m= 2, λ = 24 を入れると、2以下の失敗の数の確率は約、 1.2 * 10^-8 で、この修正が統計的に有意な効果を持つという確率は極めて良いことを示します。
脚注
もちろん、この結果は、あなたが残りの二つの失敗の原因となるバグ(達)を見つけてなおさなくても良いことの言い訳にはいかなる意味でもなりません!
クイッククイズ11.11
全ての階乗と指数関数の合計をするのは真の苦痛です。もっと簡単な方法はありませんか?
クイッククイズ11.12
でも待って!!!何らかの失敗の数が(ゼロ回の失敗の可能性も含めて)なくてはいけないということは、等式 11.30にある合計は、m が無限大になるにつれて値 1 に近づくのではないですか?
ポアソン分布はテスト結果を解析するための強力な道具です。しかし、この最後の例で、24時間のテスト実行においてまだ二つのテスト失敗が残っているのは事実です。そのような低い失敗率はとても長いテスト実行につながります。次の節は、この状況を改善する直感に反する方法を議論します。
11.6.4 ハイゼンバグを捕らえる
このような考察は、ハイゼンバグを説明するのにも役に立ちます。トレースとアサーションを追加すると、バグが起きる確率を容易に減らすことになります。そして、これが、とても軽量のトレースとアサーション機構が致命的に重要である理由です。 「ハイゼンバグ」という名前は、量子力学の、ハイゼンベルクの不確定性原理からきています。それは、ある粒子の位置と速度を正確に測定するのは、どの時間上の点においても不可能だと主張します。粒子の位置をより正確に測定しようとするすべての試みはその速度の不確定さを増すことになります。ハイゼンバグについても同じようなことが起きます。ハイゼンバグの原因を突き止めようとする試みは、バグの現象を全く変えてしまったり、完全に消したりすることがあります。 物理学がこの問題の名前の由来であるなら、物理学に解決策を求めるのが論理的でしょう。幸い、素粒子物理学がその仕事にぴったりです。ハイゼンバグを消滅させる、反ハイゼンバグを作ったらどうでしょう? この節は、それをするいくつかの方法を述べます。
1 競合しやすいところに遅延を入れる。
2 ワークロードの負荷を強める。
3 怪しいサブシステムを孤立させてテストする。
4 普通でないイベントをシミュレートする。
あるハイゼンバグの反ハイゼンバグを作るのは、科学というよりは魔術のようなものですが、以下の節は、対応する反ハイゼンバグの種族を生成するヒントを与えます。
11.6.4.1 遅延を入れる
5.1節のカウントを失うコードを考えましょう。printf 文を入れると、カウントを失うのはとてもまれになるか、あるいは起きなくなるでしょう。しかし、ロード、加算、ストアシーケンスを、ロード、加算、遅延、ストアシーケンスにすると、カウントを失うことがとても増えます。(やってみて!)あなたが競合条件に関係するバグを見つけたら、このように遅延を入れて、反ハイゼンバグを作ることがしばしば可能です。
もちろんこれは、そもそも、競合条件をどうやって見つけたらいいかという問題を提起します。これはある意味、黒魔術のようなものですが、それを見つけるためにできることはいくつかあります。
1つのアプローチは、競合条件はしばしば、競合に関わるデータをこわすことになることが多いことに注意することです。なので、こわれたデータがあったら、その同期を2重にチェックするのは良い習慣です。すぐには競合がわからなくても、こわれたデータのアクセスの前と後に遅延を入れることで、失敗の確率が変わるかもしれません。遅延を、組織化された方法(例えば、2分探索)で追加、削除すれば、あなたは競合条件の動作についてより良く調べることができるかもしれません。
クイッククイズ11.13:
もし、どこかの関係ないポインタがこわされて、その結果、あるデータがこわれたような場合、このアプローチは本当に助けになるのですか???
もうひとつの重要なアプローチは、ソフトウエアとハードウエアの構成を変えて、失敗の確率の統計的に重要な違いを見ることです。そして、最も失敗の確率を大きく変えるソフトウエアあるいはハードウエアの構成の変化に関係するコードをより重点的に調べることができます。例えば、そのコードを孤立させてテストするのも有効でしょう。
ソフトウエア構成の1つの重要な側面は、変更履歴です。それが、git bisect がとても便利な理由です。変更履歴を2分探索することで、ハイゼンバグの性質についてとても貴重な鍵を得られることがあります。
クイッククイズ11.14:
でも、私が2分探索をやったら、巨大なコミットに当たって終わりました。さて、どうしたらいいでしょう?
怪しいコード部分をどのように見つけたにせよ、次は失敗の確率を上げるために遅延を入れることができます。これまで見てきたように、失敗の確率を上げることは、対応する修正の確信度を上げるのをずっと簡単にします。
しかし、時には、通常のデバッグ技術を使って問題を追跡するのはとても難しいことがあります。次の節は、その他の方法を紹介します。
11.6.4.2 ワークロードの負荷を上げる
あるテストスイートが、そのサブシステムに比較的低い負荷を与えるために、タイミングの少しの変化がハイゼンバグを消すというのはよくあることです。この場合に反ハイゼンバグを作る1つの方法は、ワークロードの負荷を上げることです。そうすれば、バグの現れる確率を上げることができることが十分あります。もし、確率が十分に上がったら、バグが消えることなく、トレースのような軽量の診断を追加できるかもしれません。 ワークロードの負荷を上げるにはどうしたらいいでしょう?これはプログラムによりますが、以下にやると良いことをあげます。
1 CPU をもっと増やす。
2 プログラムがネットワークを使うなら、ネットワークアダプタを増やす。リモートシステムを増やす、あるいは高速にする。
3 問題が起きるときに、プログラムが大量の I/O をしているなら、(1)記憶域デバイスをもっと増やす。(2)より高速の記憶域デバイスを使う。例えば、ディスクを SSD にする。(3)大容量記憶域をメインメモリに変えて、RAM ベースのファイルシステムを使う。
4 問題の大きさを変える。例えば、並列の行列乗算をしているなら、行列の大きさを変える。
より大きい問題は、より複雑性を増すでしょうし、より小さい問題は、しばしば競合のレベルを増します。大きいのと小さいのと、どっちに進むかわからないときは、単に両方やってみましょう。 しかし、バグはある特定のサブシステムに存在し、プログラムの構造上、そのサブシステムにかけられる負荷は限界があるというのはよくあることです。次の節は、この状況を扱います。
11.6.4.3 怪しいサブシステムを孤立させる
もしプログラムが、怪しいサブシステムに多大な負荷をかけることが難しいあるいは不可能な構造を持っている場合、便利な反ハイゼンバグは、そのサブシステムを孤立させてテストする負荷テストです。Linux カーネルの rcutorture モジュールは、まさに、RCU についてのこのアプローチを取ります。本番環境で可能な負荷より多くを RCU にかけることで、RCU バグが rcutorture テストの間に見つかる確率は、本番使用の間よりも大きくなります。
脚注
しかし悲しいことに、確率1には大きくなりません。 実際、並列プログラムを作るときは、コンポーネントを別々に負荷テストするのが賢明です。そのようなコンポーネントレベルの負荷テストを作るのは時間のむだに見えるかもしれませんが、わずかなコンポーネントレベルのテストのおかげて、膨大なシステムレベルデバッグをしなくてよいかもしれません。
11.6.4.4 普通でないイベントをシミュレートする
ハイゼンバグは時には、普通でないイベントが原因です。例えば、メモリ確保の失敗、条件ロック確保の失敗、CPU ホットプラグ操作、タイムアウト、パケット喪失、など。この種のハイゼンバグに対する反ハイゼンバグを作る方法は、余分な失敗を導入することです。 例えば、malloc() を直接呼ぶ代わりに、ラッパー関数を呼びます。それは、乱数を使って、ある時は無条件に NULL を返し、あるときは、実際に malloc() を呼んで結果のポインタを返します。余分の失敗を入れるのは、シーケンシャルプログラムにとっても、並列プログラムにとっても、堅牢さを焼きこむのに優れた方法です。
クイッククイズ11.15: なぜ、既存の条件ロックプリミティブはこの余分な失敗機能を提供しないのですか?
これまで、私達は並列プログラムの機能の中のバグだけに焦点を当ててきました。しかし、性能は並列プログラムの1級の要件です(そうでないなら、シーケンシャルプログラムを書けばいいです。)から、次の節は、性能のバグを見つけることについて述べます。
11.7 性能見積もり
並列プログラムは普通、性能とスケーラビリティの要件があります。結局、性能がどうでもいいなら、シーケンシャルプログラムを使えばいいでしょう?究極の性能と線形スケーラビリティは必要ないかもしれませんが、対応する最適なシーケンシャルプログラムよりも遅い並列プログラムは価値がありません。そして、世の中には実際に、すべてのマイクロ秒が問題で、すべてのナノ秒が必要な場合があります。なので、並列プログラムにとって、不十分な性能は、不正確さと同じくらい、バグなのです。
クイッククイズ11.16: これはばかげています!!!結局、間違った答えを得るよりは、予定より遅れて正しい答えを得るほうがましでしょう??? クイッククイズ11.17:
でももし、あなたが、アプリケーションを並列化するというすべての大変な仕事をやる気ならば、なぜ、ちゃんとやらないのです?なぜ、最高の性能と線形スケーラビリティ以下のもので妥協するのです? このため、並列プログラムの検証は、その性能の検証も含む必要があります。しかし、性能の検証は、実行するべきワークロードがあり、手元のプログラムを評価する性能基準があることを意味します。これらの要求は、しばしば、性能ベンチマークによって満足されます。これについては次の節で。
11.7.1 ベンチマーク
古いことわざにあります。「嘘、大嘘、統計、そしてベンチマーク」しかし、ベンチマークはしばしば使われるので、あまりに悲観的になるのはよくありません。
ベンチマークは、アドホックなテストの踊りから、世界標準まで広い範囲のものがあります。しかし、その形式化のレベルを別にすれば、それらは4つの大きな目的のためにあります。
1 競合する実装を比べるための公平なフレームワークを提供します。
2 競合するエネルギーを、ユーザーのためになる方向に実装を改善することに焦点を当てます。
3 ベンチマーク対象の実装の使用例となります。
4 あなたのソフトウエアがあなたの競合の製品に比べて優れている点を強調するためのマーケティングの道具となります。
もちろん、本物のアプリケーションを動かすことができるなら、それが実際は最善のアプローチです。不幸にも、それはしばしば現実的ではありません。理由は以下です。
1 アプリケーションはプロプライエタリであり、あなたはそれを動かす権利がありません。
2 アプリケーションは、あなたがアクセス可能なハードウェア以上のものを必要とします。
3 アプリケーションは、あなたが合法的にアクセスできない、例えば、プライバシー規制のために、データを使います。
これらの場合、そのアプリケーションを近似するベンチマークを作ることは、前記障害を克服する助けになるでしょう。注意深く構成されたベンチマークは、性能、スケーラビリティ、エネルギー効率、そしてその他いろいろ、を改善する助けになります。
11.7.2 プロファイリング
多くの場合、あなたのソフトウェアのごく小さな部分が性能とスケーラビリティの低下のほとんどの責任を負っていることがあります。しかし、開発者が実際のボトルネックを手作業で見つけることができないのはよく知られたことです。例えば、カーネルのバッファ確保の場合、稠密な配列の検索にすべての注意が集中されましたが、それはアロケータの実行時間のたった数パーセントしか使わないことが判明しました。ロジックアナライザーを使って収集された実行プロファイルは、キャッシュミスに注意をうながし、それが実際には問題のほとんどの原因でした。
gprof, perf などの多くのツールがあり、それを使えば、あなたの注意を最も効果があるところに集中することができるでしょう。
11.7.3 差分プロファイリング
スケーラビリティ問題は、あなたがとても大きなシステムで動かさない限り、明らかにならないことが多いです。しかし、来たるべきスケーラビリティ問題を、ずっと小さいシステムで動かしていても検出することができることがあります。そのための1つの技術は、差分プロファイリングと呼ばれます。
アイディアは、あなたのワークロードを2つの異なる条件の元で動かすことです。例えば、2つのCPUで動かして、次にもう一度、4つのCPUで動かします。あるいはその代わりに、システムに加える負荷を変えたり、ネットワークアダプターの数を変えたり、大容量記憶域の数を変えたりします。そして、2つの実行でプロファイルを取り、対応するプロファイル結果を数学的に結合します。例えば、あなたが主にスケーラビリティが気になるなら、対応する測定結果の比率を取って、次にその比率を数字が小さくなる順に並べます。すると、スケーラビリティ問題の主な犯人と思われるものが一覧の最初に並んでいるはずです。
Perf のように、組み込みの差分プロファイリングサポートを持つツールもあります。
11.7.4 マイクロベンチマーク
マイクロベンチマークは、より詳細な評価をするために、どのアルゴリズムあるいはデータ構造をより大きなソフトウェア母体に取り込むのが良いかを決めるときに便利です。マイクロベンチマークの一つの一般的なアプローチは、時刻を測って、テスト対象のコードを何回か繰り返して実行して、また時刻を測ることです。二つの時刻の差を繰り返しで割れば、テスト対象のコードを実行するのに必要な時間が測れます。
不幸にして、この測定アプローチは、多くの誤りが忍び込むことがあります。それは、
1 測定には、時刻計測のオーバーヘッドがいくらか含まれます。この誤り要因は、繰り返しを増やせばいくらでも小さくできます。
2 テストの最初の何回かの実行は、キャッシュミスあるいは(もっと悪いことに)ページフォルトを起こすかもしれません。それは、測定値を大きくします。この誤り要因も、繰り返しを増やせば小さくできます。あるいは、測定期間を始める前に、いくらかのウォームアップの繰り返しを動かせば、しばしば、完全に消すことができます。
3 例えばランダムなメモリエラーのようなある種の干渉は、ごくまれなので、テストの繰り返しのセットを何回か実行することで対処できます。もし、干渉のレベルが統計的に有意なら、規格外値は、統計的に除くことができます。
4 どんなテストの繰り返しも、システムの他のアクティビティーの干渉を受けます。
干渉の原因は、他のアプリケーション、システムユティリティとデーモン、デバイス割り込み、ファームウェア割り込み(システム管理割り込み、SMI を含みます)、仮想化、メモリエラー、その他たくさん、です。これらの干渉の原因はランダムに起きることを考えると、これらの効果は、繰り返しを少なくすることで最小化できます。 1つめと4つめの干渉の原因は、矛盾するアドバイスを与えますが、これは私たちが本当の世界に生きている1つのしるしです。この節の残りでは、この矛盾を解決する方法を考えます。
クイッククイズ11.18: 他の誤り要因はどうなりますか?例えばキャッシュとメモリレイアウトの干渉によるものとか。
以下の節は、これらの測定誤りに対処する方法を議論します。11.7.5節は孤立化テクニックで、ある種の干渉を防ぐのに使えます。11.7.6節は、干渉を検出する方法で、干渉のためにこわれた測定データを除くことができます。
11.7.5 孤立化
Linux カーネルは、CPUのグループを外の干渉から孤立させるいくつかの方法を持ちます。
まず、他のプロセス、スレッド、タスクからの干渉を考えましょう。POSIX sched_setaffinity() システムコールは、あるCPUの集合からほとんどのタスクを移動させて、あなたのタスクをその同じグループ内に閉じ込めるために使えます。Linux 固有のユーザレベルの tasksetコマンドでも同じ目的のために使えます。なお、sched_setaffinity() も、 taskset も、強い権限が必要です。Linux固有の、コントロールグループ (cgroups) も、同じ目的のために使えます。このアプローチは、干渉を減らすのにとても効果的で、多くの場合、これだけで十分です。しかし、確かに限界もあります。例えば、ハウスキーピングの仕事によく使われる、CPUごとのカーネルスレッドについては、何もできません。
CPUごとのカーネルスレッドの干渉を防ぐ1つの方法は、あなたのテストを、高実時間優先度で動かすことです。例えば、 POSIX sched_setscheduler() システムコールが使えます。しかし、これをやるときは、あなたは無限ループを避ける暗黙の責任を負うことに注意下さい。なぜなら、そうなると、あなたのテストのためにカーネルの部分が機能しなくなることがあります。
脚注。これはスパイダーマン原則の例です。「大きな力は大きな責任を伴う。」
これらのアプローチは、プロセス、スレッド、そしてタスクからの干渉を大いに減らすかあるいはもしかすれば除くことさえできるかもしれません。しかし、それは、デバイス割り込みからの干渉を防ぐには何もしてくれません。少なくても、スレッド化された割り込みが使われていない時は。Linuxは、/proc/irq ディレクトリ経由で、割り込みに関して、いくらかの制御を許します。
訳注。/proc/irq が threaded interrupt というのは誤りと思います。
そこには、割り込みベクトルごとに、数字のディレクトリがあります。それぞれの数字のディレクトリには、smp_affinity と smp_affinity_list があります。十分な権限があるなら、これらのファイルに値を書き込んで、割り込みを、指定されたCPU集合に限定することができます。例えば、“sudo echo 3 > /proc/irq/23/smp_affinity” すると、ベクトル23の割り込みを、CPU 0と1に限定します。“sudo echo 0-1 > /proc/irq/23/smp_affinity_list”としても、同じ効果が得られます。“cat /proc/interrupts”を使うと、あなたのシステムの割り込みの一覧と、それぞれのCPUがいくつを処理したか、そしてどんなデバイスがそれぞれの割り込みベクトルを使っているかを知ることができます。
同様のコマンドを、あなたのシステムのすべての割り込みベクトルに対して使えば、割り込みをCPU0と1だけに閉じ込めて、残りのCPUを干渉なしにできます。あるいは、ほとんど干渉なし、です。ユーザモードで実行しているCPUでは、スケジューリングクロック割り込みが発生することがわかっています。
脚注
Frederic Weisbecker は、adaptive-ticks プロジェクトを研究しています。それは、実行可能タスクが一つしか無いCPUでは、スケジューリングクロック割り込みを止めることができます。しかし、2013年初頭では、残念ですがこれは未だ、研究中です。
また、あなたは割り込みを閉じ込めたCPUが、その負荷を処理する能力を持つか、注意して確認しないといけません。
しかしこれは、テストと同じオペレーティングシステムインスタンス上で動いているプロセスと割り込みを処理出来るだけです。あなたが、テストをゲストOSで動かしていると考えて下さい。ゲストOS自身は、KVM を動かしているLinuxのような、ハイパーバイザ上で動いています。理論的には、ハイパーバイザのレベルで、ゲストOSのレベルでやったように同じテクニックを適用することはできます。しかし、ハイパーバイザレベルの操作は、権限のある人に限られているのがとても一般的です。さらに、これらテクニックのどれも、ファームウェアレベルの干渉に対しては働きません。
クイッククイズ11.19:
ここで推奨された、テスト中のコードを孤立化されるテクニックは、同時にコードの性能に影響しませんか?特に、それがより大きなアプリケーションの中で動いている時は。
もしあなたがこの困った状況にあることに気がついたなら、干渉を防ぐのではなく、干渉を検出する必要があるかもしれません。これについては次の節で。
11.7.6 干渉を検出する
もしあなたが、干渉を防げなくても、事が起きた後で干渉を検出して、その干渉に影響されたテスト実行を棄却することはできるかもしれません。11.7.6.1は、追加の測定をして棄却をする方法を、11.7.6.2は統計を元とする棄却を説明します。
11.7.6.1 干渉を測定によって検出する
Linux を含む多くのシステムは、事が起きた後である種の干渉が起きたかどうかを判定する方法を提供します。例えば、あなたのテストがプロセスを元とする干渉に当たったならば、テスト期間中にコンテキストスイッチが起きたはずです。Linux を元とするシステムでは、このコンテキストスイッチは、/proc/<PID>/sched にある、nr_switches フィールドで見ることができます。同様に、割り込みを元とする干渉は、 /proc/interrupts ファイルで検出できます。
ファイルを開いて読むのは、低オーバーヘッドの方法ではありません。あるスレッドのコンテキストスイッチの回数は、図11.5に示すように、getrusage() システムコールで得ることができます。同じシステムコールで、マイナーページフォルト (ru_minflt) と、メジャーページフォルト (ru_majflt) を検出することもできます。
不幸にも、メモリ誤りとファームウェアインタフェースはとてもシステム固有です。仮想化のための干渉の検出も同じです。回避は検出より優れ、検出は統計より優れますが、統計を使わなくてはいけない時もあります。これについては次の節で。
11.7.6.2 干渉を統計によって検出する
統計解析は必ずデータに対する前提を元とし、性能マイクロベンチマークは、しばしば以下を前提とします。
1 小さい測定値は、大きい測定値よりも正確であることが多いです。
2 良いデータの、測定不確定性は、既知です。
3 テスト実行のある程度の部分は良いデータを持つはずです。
小さい測定値は、大きい測定値よりも正確であることが多いという事実は、測定結果を昇順にソートするのは生産的であることを意味します。
脚注
ことわざを言い換えれば、「まずは探して、それから質問しなさい」
測定不確定性は、既知であるという事実は、互いにこの不確定性の内にある測定値を受け入れることを可能とします。干渉の効果が、この不確定性に対して大きいならば、悪いデータを棄却するのは簡単になります。最後に、ある程度の部分(例えば、1/3)は良いと考えることができるという事実は、ソートしたリストの最初の部分を無条件に受け入れることを許します。このデータは次に、予想される測定誤差を越える測定データの自然偏差の目安を得るために使えます。
アプローチは、ソートされたリストの始めから先頭につながっている指定個数の要素を取ることです。そしてそれらを要素間の典型的なデルタを見積もるのに使います。それを次にリストにある要素数とかければ、許される値の上限値が得られます。アルゴリズムは次に、リストの次の要素を繰り返し考察します。もしそれが上限値より小さいところに収まり、次の要素と前の要素の間の距離が、これまで受け入れられてきたリスト部分の平均要素間の距離と比べて大きすぎることがなければ、その場合次の要素は受け入れられ、処理は繰り返されます。そうでない場合、リストの残りは棄却されます。
図11.6は、これを実装する単純な sh/awk スクリプトです。入力は、x 値と、それに続く y 値の任意の長さのリストから構成されます。そして出力は入力行一行あたり、一行で、以下のフィールドを持ちます。
1 x 値。
2 選択されたデータの平均値。
3 選択されたデータの最小値。
4 選択されたデータの最大値。
5 選択されたデータ要素の数。
6 入力データ要素の数。
このスクリプトは、以下の三つのオプショナルな引数を取ります。
・ --divisor: リストを分割するセグメント数。例えば、divisor 4 は、データ要素の最初の1/4が良いと仮定します。デフォルトは3です。
・ --relerr: 相対的測定誤差。スクリプトは、この誤差以内の値は全て、全ての意図と目的にとって等しいと仮定します。デフォルトは 0.01 つまり 1%です。
・ --trendbreak: データの傾向に断絶が認められる要素間の間隔の比率。例えば、もしも今まで受け入れられてきたデータの間の間隔の平均が1.5なら、trend-break 、傾向の断絶比率が2.0の時、もしも次のデータ値が最後のものと比べて3.0以上違うならば、これは傾向の断絶を構成します。(もちろん、相対的誤差が3.0以上でない限り。その場合には、「断絶」は無視されます。)
図11.6の1から3行目は、パラメータのデフォルト値を設定します。そして4から21行目はこれらのパラメータのコマンドラインでの再設定を解析します。23と24行目の awk 呼び出しは、divisor, relerr, そして trendbreak 変数を、それらの対応する sh 変数の値にします。awk の慣例に従い、25から52行目はそれぞれの入力行ごとに実行されます。24から26行目にあるループは、入力の y 値を d 配列に複写し、27行目はそれを昇順にソートします。28行目は、divisor を適用して、丸めることで、絶対的に信用できる y 値の数を計算します。
29から33行目は maxdelta 値を計算します。これは、y 値の上限の最小値として使われます。このため、29と30行目はデータの信用できる領域の値の間の差に、divisor をかけます。それは、信用できる領域の値の間の差を、y 値の全体のセットに射影します。しかし、この値は、相対的誤差よりもずっと小さいかもしれないので、31行目で絶対誤差 (d[i] * relerr) を計算して、それを、データの信用できる部分にわたって、差 delta に加えます。そして32と33行目はこれら二つの値の最大値を計算します。
34から43行目にあるループのそれぞれのパスは、良いデータのセットにさらに別のデータ値を加えようとします。35から39行目はtrend-break デルタを計算します。36行目は、傾向を計算するために十分の数の値をまだ持たない時は、この制限を無効にします。そして、38と39行目は良いセットにあるデータの対の間の平均の差異に trendbreak をかけます。もし40行目で、候補となるデータ値が上限値の下限 (maxdelta) を超えると判定し、かつ41行目で候補となるデータ値とその前の値の差が trend-break 差 (maxdiff) を超えると判定したならば、42行目でループを抜けます。良いデータの完全なセットが得られました。
次に44から52行目はデータセットの統計を計算して、表示します。
クイッククイズ11.20
このアプローチはただ単純に変です!なぜ、統計学の授業で学んだ平均と標準偏差を使わないのですか?
クイッククイズ11.21
でももし信用できるデータのグループの全ての y 値が正確にゼロだったらどうしますか?するとスクリプトはゼロ以外の全ての値を棄却しませんか?
統計的干渉の検出はとても便利なことがあります。しかしそれは最後の方法として使われるべきです。最初から干渉を避ける(11.7.5節)、あるいはそれができないときは、測定によって干渉を検出する(11.7.6.1節)の方が、ずっと良いです。
11.8 まとめ
検証は正確な科学にはなれませんが、それに組織的なアプローチを取れば、多くを得ることができます。なぜなら、組織的なアプローチは、あなたが自分の仕事にとって正しい検証ツールを選ぶのを助け、図11.7に面白く書かれたような状況を避けてくれるでしょうから。
鍵となる選択は、統計です。この章で述べた方法は、ほとんどの場合にとてもうまくいくでしょうが、その限界も確かにあります。この限界は本質的なものです。なぜならば、私達は一般的には、 Halting Problem によって不可能だとされていることをしようとしているからです。私達にとってありがたいことに、与えられたプログラムが停止するかどうかだけでなく、11.7節で述べたように、そのプログラムが停止する前にどれだけ走るかを見積もることも可能であるような、多くの特殊ケースが存在します。さらに、与えられたプログラムが正しく動くか動かないかわからないという状況で、11.6節で述べたように、それが正しく動く時間の割合を見積もることのできることがしばしばあります。
とはいえ、考えもなしにこれらの見積もりに頼るのは、勇敢というより無謀です。結局、私達は、コードとデータ構造中のぼうだいな複雑さを、1つのただの数字に要約しているからです。もしもそのような無謀さを驚くほど長い時間、続けることができたとしても、抽象化され忘れられたコードとデータが、たまに深刻な問題を起こすこともあると考えるのは、合理的なことです。
1つのありえる問題は変動性です。繰り返す実行が、ワイルドに異なる結果を与えるというものです。これはしばしば、平均に加えて、標準偏差も維持することで対処されます。しかし、巨大で複雑なプログラムの振る舞いを、2つの数字で要約しようという試みは、その振る舞いを1つの数字で要約しようという試みと無謀さの点ではほぼ同じだというのは事実です。計算機プログラミングでは、平均あるいは平均と標準偏差を使うことがしばしば十分であるということは驚きです。しかし、保証はありません。
変動性の1つの原因は、混乱させるファクターの存在です。例えば、連結リスト検索で消費されるCPU時間は、リストの長さに依存します。ワイルドに異なる長さのリストを使った実行の平均は、たぶん、あまり役には立たず、平均に標準偏差を加えても、あまり改善しません。するべき正しいことは、リストの長さを制御することです。長さを一定にするか、あるいはCPU時間をリスト長の関数として測定するかです。
もちろん、この忠告はあなたが混乱させるファクターに気づいていることを前提とします。そして、マーフィーによれば、あなたはたぶん気がつくことはないはずです。私は混乱させるファクターのあるプロジェクトにいくつも関わってきました。それには、エアコン(開始の時にかなりの電力を使い、計算機に供給される電圧を一時的に低すぎる状態にし、ときには障害を起こしました。)、キャッシュ状態(性能におかしな変動をもたらしました。)I/O エラー(ディスクエラー、パケット損失、そしてイーサネットMAC アドレスの重複)、なんと、いるか(トランスポンダの行列で遊びたくて仕方ありませんでした。いるかがいなければ、トランスポンダは高精度のアコースティック位置検出とナビゲーションに使えるはずでした。)もありました。
つまり、検証は常にシステムの振る舞いのなんらかの測定を必要とします。この測定が、システムの厳しい要約でなくてはいけないために、それは人を誤らせることがあります。なので、ことわざにあるように、「気をつけて。外にあるのは本当の世界だよ。」
しかし、あなたがLinuxカーネルの作業をしているとしましょう。それは、2013年時点で、世界で約10億インスタンスがあります。その場合、100万年に一度現れるバグは、すべてのインストールベースでは一日にほぼ3回現れることになります。1時間の実行でこのバグを見つける確率が50%のテストは、そのバグの発生確率を9桁以上上げないといけません。それは、現在のテスト方法論にとって、厳しい挑戦を課します。そのような状況において、適用でき、ときには良い結果を得られる1つの重要なツールが、形式的検証であり、次の章の題材です。
以上