火星でいったい何が起きたのか? - Glenn Reeves

(Risks ダイジェスト、"What really happened on Mars ?" 翻訳)

(はじめに)

1997年に火星に到着した NASA の火星探査機マーズ・パスファインダー (Mars Pathfinder) 号は、 火星地表で探査機のコンピュータシステムが再起動してしまうという問題にみまわれた。 これは OS のスケジューリングにおいて出てくる priority inversion (優先度逆転) という 現象が、現実のシステムに深刻な影響を引きおこした例である。

現在のたいていの OS では複数の処理が並列して行われているが、 各処理 (プロセス) には優先度 (priority) という属性が与えられている。 実時間で何かを制御するさいには、コンピュータが決められた時間内で 正しく応答する必要があるため、プロセスを正しい優先度で動かすことは非常に重要である。 ところが、ある状況下では優先度の低いプロセスが優先度の高いプロセスよりも 速く走ってしまうという現象が起こる。これが優先度逆転である。 優先度逆転はそれまで大した問題ではないと思われてきたが、 マーズ・パスファインダー号の場合はこれがシステムの再起動という深刻な問題につながった。 NASA ジェット推進研究所 (JPL) のソフトウエアチームはこの問題の原因が 優先度逆転であることをつきとめ、火星地表の探査機上のソフトウエアを 修正することにより問題を解決した。

以下は Risks ダイジェスト Vol 19.54 から抜粋した記事の日本語訳である。 URL: http://catless.ncl.ac.uk/Risks/19.54.html#subj6

(なお、記事中の vxWorks という OS は Wind River社 による組み込み用オペレーティングシステムの製品名をさす)


Mike Jones <mbj@MICROSOFT.com>
Fri, 9 Jan 1998 14:13:58 -0800
> Date: Monday, December 15, 1997 10:28 AM
> From: Glenn E Reeves <Glenn.E.Reeves@jpl.nasa.gov>
> Subject:   Re: [Fwd: FW: What really happened on Mars?]
> 
> 
> 火星でいったい何が起きたのか?
> (What really happened on Mars ?)
> 
> 
> これまでのところ、ほとんどの人は IEEE の実時間システムシンポジウムにおける
> Dave Wilner のトークの、Mike (mbj@microsoft.com) による要約に目を
> 通しているものと思う。ぼくは Mike のことは知らないし、ぼく自身は
> このシンポジウムには出席しなかったし (今になって思うと、ぜひとも
> 出席したかったと思うが)、このトークより前に Dave Wilner と話したこともなかった。
> でも、ぼくが宇宙船マーズ・パスファインダー号のソフトウエアチームを率いていたんだ。
> なので、あそこでどんなことを言ったのかを苦労して思いだすよりも、
> ここではただ何が起きたのかを書く。あとはあなたが判断してほしい。
> 
> ぼくはこのメールを、Mike が元の文章を送った人で、ぼくが電子メールアドレスを
> もっているすべての人に送った。最初のやつを転送した人にはどうかこれも
> 転送してほしい。Mike、きみが元の文章を投稿したところ全部にこれも
> 投稿してくれることを願っているよ。
> 
> ぼくはこの問題がはっきりと理解されることを望んでいるので、この問題に
> かかわった領域をひとつひとつたどっていくことにする。
> 
> 
> ハードウエア
> 
> マーズ・パスファインダー号の簡単なハードウエア・アーキテクチャのしくみは
> 次のようになっている。宇宙船はひとつの CPU によって制御されている。
> これは VME バスの上に乗っていて、ここには無線や、カメラや、
> 1553 バスへの中継をおこなうインターフェイスカードも含まれている。
> 1553 バスは 2つの場所をつなぐ。ひとつは宇宙船の「巡航」部分であり、
> もうひとつは宇宙船の「着陸機」部分だ。巡航部分のハードウエアは
> 推進器や、バルブや、太陽光センサやスタースキャナー (a star scanner) を制御する。
> 着陸機部分のハードウエアは加速計や、レーダー高度計や、気象科学用の
> ASI/MET といった機器を制御する。この 1553バスとの間をつないでいた
> ハードウエアは (どちらの終端も) ぼくたちが探査機カッシーニから
> 引き継いだものだ。このハードウエアには特定の使用方法が定められている。
> それは、ソフトウエアが 8ヘルツの速度でこれをスケジュールすることだ。
> 1553 バスと、それに取り付けられたデバイスの両方を制御する
> ソフトウエアのアーキテクチャは、この“機能”によって支配されている。
> 
> 
> ソフトウエア・アーキテクチャ
> 
> この 1553 バスを制御するソフトウエアと、それにとりつけられた機器は
> 2つのタスクとして実装されていた。1番目のタスクは、1553 バス上の
> トランザクションの準備 (バス・スケジューラ、あるいは bc_sched タスクと呼ばれる)
> を制御しており、2番目のタスクはトランザクションの結果 (つまりデータ) を
> 収集するはたらきをしていた。この 2番目のタスクは、bc_dist と呼ばれる
> (分配用なのでこう呼ばれた)。このバス上の、ある一回のサイクルにおける
> 典型的な動きの時系列は次のようになっている。これの長さは変わらない。
> つねに一定のサイクルが繰り返される。
> 
> 
>      |<------------------- .125 秒 ------------------------>|
> 
>      |<***************|                    |********|   |**>|
> 
>                       |<- bc_dist 活性化 ->|    bc_sched 活性化
>      |<- バス活性化 ->|                             |<->|
> 
>  ----|----------------|--------------------|--------|---|---|-------
>      t1               t2                   t3       t4  t5  t1
> 
> 
>  *** で表された部分は上にあげた以外のタスクが実行している時間だ。
>  上の図でわかるように、ここにはいくらかの空き時間が存在する。
> 
>  t1 - バスのハードウエアは 8ヘルツ境界のハードウエア制御からはじまる。
>       このサイクルのトランザクションは、前回の bc_sched タスクの実行により
>       準備されている。
>  t2 - 1553 の通信が終了し、bc_dist タスクが目ざめる。
>  t3 - bc_dist タスクがすべてのデータ分配を完了する。
>  t4 - bc_sched タスクが次のサイクルのトランザクションを準備するために目ざめる。
>  t5 - bc_sched タスクの仕事が完了する。
> 
> タスク bc_sched と bc_dist は各サイクルで、お互いがその実行を終了したかどうかを
> チェックするようになっている。bc_sched タスクはシステムの中で
> (vxWorks の "tExec" タスクを除いて) もっとも優先度が高いタスクだ。bc_dist は
> 3番目に優先度が高い (突入と着陸を制御するタスクが 2番目の優先度である)。
> これ以外の宇宙船の機能を担当するタスクはすべてこれより下の優先度をもつ。
> サイエンスのための機能、たとえば撮影とか、画像圧縮とか、ASI/MET の
> タスクなどはさらに下だ。
> 
> 1553 バスに接続された機器からデータが収集できるのは、これらの機器に
> 電源が供給されている時だけである。このシステムではほとんどのタスクが
> 二重バッファ化された共有メモリを経由して 1553 上で収集された情報に
> アクセスしており、bc_dist タスクはここに最新のデータを書きこんでいた。
> 例外は ASI/MET タスクで、これはプロセス間通信 (IPC) 機構によって
> 情報を伝達している。IPC には vxWorks の pipe() 関数を使った。タスクは
> ひとつあるいは複数の IPC「キュー」上でメッセージが到着するのを待つ。
> タスクはメッセージの到着を待つのに select() を使っていた。
> 優先度の高いメッセージと低いメッセージが両方要求されたときには
> 複数のキューが使用された。このシステムにおける、ほとんどの IPC
> トラフィックは実時間データを配送するためのものではなかった。
> ところが、繰り返すけどこれには例外があって、ASI/MET タスクでは IPC が
> 使われていた。火星上での再起動の原因は、この IPC メカニズムの使い方に
> あったんだ。
> 
> 
> 機能不全 (FAILURE)
> 
> 宇宙船の機能不全は、bc_sched タスクが開始するまでに bc_dist タスクが
> 完了できなかったことにより認識された。これに対する宇宙船の反応は、
> コンピュータを再起動するというものだった。この再起動はすべての
> ハードウエアおよびソフトウエアを初期化する。また、これは現在までに
> コマンドが発行されている動きをすべて終了させる。すでに収集された
> サイエンス用および工学用のデータは消えない (RAM 上のデータは
> 電力が続くかぎり復帰する) が、その日の残りの活動は翌日になるまで
> 完了しなかった。
> 
> この機能不全は priority inversion (優先度逆転) と呼ばれる現象であることが
> わかった (ぼくたちがこれをどうやって発見し、どうやって修復したかについては
> 後で述べる)。優先度の高い bc_dist タスクが、ある共有リソースを握っていた、
> それよりもずっと優先度の低い ASI/MET タスク によってブロックされてしまったんだ。
> ASI/MET タスクはこのリソースを獲得したあと、中くらいの優先度をもつタスクの
> いくつかに制御を横取りされた (preempted)。 bc_sched タスクが次の
> 1553 バスサイクルのトランザクションを準備するために目ざめたとき、
> これは bc_dist タスクがまだその実行を終えていないことに気がついた。
> この問題をひき起こしたリソースとは select() 関数内で使われていた
> 排他制御用のセマフォで、select() が待っているファイル記述子のリストに
> アクセスするのを制御するためのものだった。
> 
> select 関数は、select をサポートするデバイス用のファイル記述子の
> 「待ち行列」を保護するために排他制御用のセマフォを作成する。
> vxWorks の pipe() 関数はそのようなデバイスのひとつで、ぼくたちが
> 使っていた IPC はこの pipe の使用に頼っていた。ASI/MET タスクは select を
> 呼びだし、これが pipeIoctl() を呼びだし、これが selNodeAdd() を呼ぶ。
> これが排他制御セマフォを得るさいのプロセスである。ASI/MET タスクは
> 制御を横取りされ、semGive() は完了していなかった。中程度の優先度をもつ
> いくつかのタスクが、bc_dist タスクが活性化するまで走りつづけた。
> bc_dist タスクは ASI/MET のデータを送ろうとしたが、IPC 機構を経由しており、
> これはその中で pipeWrite() を呼んでいる。pipeWrite() は排他制御セマフォを
> 取ろうとしてブロックされた。中程度の優先度をもつタスクがさらに走り、
> ASI/MET タスクはまだ走れなかった。そのうちに bc_sched タスクが目ざめた。
> この時点で、bc_sched タスクは bc_dist がまだそのサイクルを
> 完了していないと思い (これはシステムが絶対に守らなければならない期限だ)、
> エラーを宣言して再起動に入った。
> 
> 
> どうやって発見したか
> 
> マーズ・パスファインダーで飛ばされたソフトウエアには、中にいくつかの
> デバッグ機能が入っていた。これらの機能はラボでは使われていたが、実際に飛ぶ
> 宇宙船では使われていなかった (なぜならそのうちのいくつかは、地球に送り返せる
> 量を超える情報を吐くからだ)。これらの機能は「運よく」残されていたのではなくて、
> デザイン上の決定としてソフトウエアの中に残しておいたのだ。ぼくたちは「飛ばすものを
> テストし、テストしたものを飛ばせ (test what you fly and fly what you test)」の
> 哲学を強固に信じている。
> 
> これらのツールのうちひとつはトレース/ログ機能で、これはもともとは移植された
> vxWorks の初期のバージョンにあったバグをみつけるために開発されたものだった
> (Wind River 社はこのミッションのために、vxWorks を我々のために RS6000 プロセッサ用に
> 移植してくれた)。このトレース/ログ機能はプロジェクトのソフトウエアエンジニアの
> ひとりである David Cummings が作った。Wind River 社の Lisa Stanley は
> この機能をとってきて、それを pipe サービス、メッセージキューサービス、
> 割り込み処理、select サービス、そして tExec タスクに組み込んだ。この機能は
> 起動時に初期化され、停止が命令されるまでデータを (リングバッファ中に)
> ためつづける。命令されると、この機構はおびただしい量の情報をダンプする。
> 
> 火星での問題が起きたあと、ぼくたちはラボで同じ操作を何度も何度もくり返し実行した。
> bc_sched はすでに命令されるとトレース/ログ収集を中止し、得られていたデータを
> ダンプするようにコーディングされていた (たとえ飛行中にダンプをとることは
> できないとわかっていたとしても)。なので、これをテストするためラボに行ってからも
> ぼくたちはそのソフトウエアを変更する必要はなかった。
> 
> 18時間以内のうちに、ぼくたちはこの問題が起こる状況をつくりだせるようになった。
> いったん機能不全が再現できてしまうと、優先度逆転が問題なのは明らかだった。
> 
> 
> どうやって問題を修復したか
> 
> 問題が理解されると、解決方法は明らかに見えた: セマフォを作成するときの
> フラグを、優先度継承 (priority inheritance) が可能になるように変更するのだ。
> Wind River 社の人々は、彼らのサービスの多くにグローバルな設定用の変数を
> 用意している。たとえば select サービスで使われる semMCreate のための
> 「オプション」パラメータなどがそうだ (これは文書化されておらず、
> vxWorks のソースコードを持っていなかったり、ソースを詳しく
> 研究していない人々はこの機能に気づかないかもしれないのだが)。
> しかし、この方法はいくつかの理由からそう簡単ではなかった。
> 
>  1) このコードは selectLib() の中にあり、これはすべてのデバイス生成に
>     共通していた。このグローバル変数を変更すると、これ以降に作られる
>     すべての select 用セマフォがこの新しいオプションで生成されることになる。
>     ぼくたちの初期化用ロジックには、bc_dist タスクと ASI/MET タスクとの
>     通信用 pipe に関連づけられたセマフォのみを修正する、簡単な方法はなかった。
> 
>  2) もしぼくたちがこれを変えて、その変化がグローバルに適用されたとすると、
>     この変化は残りのシステムの挙動をどのように変えるのか?
> 
>  3) この優先度逆転用のオプションは、Wind River 社によって実行速度を
>     最高にするため意図的にオフにされていた。もしこれをオンにしたとすると、
>     それによって生じるパフォーマンスの低下はどれくらいなのか?
> 
>  4) もし優先度逆転用のオプションをオンにした場合、select 関数それ自体の
>     本質的なふるまいが変わることがありうるか?
> 
> 最終的にぼくたちはグローバル変数を修正して優先度逆転用のオプションを
> 含めることにした。これで問題は解決された。ぼくたちは Wind River 社に、
> (3) と (4) がもつ潜在的な影響を分析してくれるよう依頼した。かれらは
> パフォーマンス上の影響は最小限であり、select() のふるまいは、
> 特定のファイル記述子を待っているタスクがつねにひとつだけであるときには
> 変化しないと結論づけた。これはぼくたちのシステムでは正しかった。
> 優先度逆転用オプションをデフォルトでオンにするかどうかについては、
> Wind River ではまだ議論が続いているものと思う。(1) と (2) については、
> この変更はたしかにすべての select 用セマフォのふるまいを変えた。
> 分析とテストの両方から、ぼくたちはこの変化が悪さをすることはないと結論した。
> 宇宙船のソフトウエアを変更する前に、ぼくたちは広範囲にわたって
> システムをテストした。
> 
> 
> どうやって宇宙船のソフトウエアを変更したか
> 
> いや、ぼくたちはソフトウエアを変えるのに vxWorks のシェルは使わなかった
> (これは宇宙船の上で使用可能ではあったにせよ)。宇宙船のソフトウエアに
> 「パッチをあてる」プロセスは特別なもので、これはいまオンボードにある
> ものと自分が欲しい状態のもの (そして地球上にあるもの) との間の差分を
> 宇宙船に送る。宇宙船の上にあるカスタムソフトウエアは (さまざまな
> 確認行為のあと) オンボードのコピーを修正する。より詳しい情報が欲しい場合は
> ぼくにメールしてほしい。
> 
> 
> なぜ打ちあげ前にわからなかったのか?
> 
> この問題は ASI/MET データが収集されている最中で、中間的なタスクに
> 非常な負荷がかかっているときでなければ現れなかった。ぼくたちの
> 打ちあげ事前テストでは、データ転送速度とサイエンス活動は「最適な場合」のみに
> 制限していた。火星地表からのデータ転送速度は予期されていたよりも速く、
> サイエンス活動の量はそれに比例して大きくなっていたことが問題を悪化させた。
> ぼくたちは「それまで想像していたのよりもいい」場合については
> 予期していなかったし、テストもしていなかったのだ。
> 
> 
> 人間の本質、期限による圧迫
> 
> この問題については、ぼくたちは着陸の前にも目にしていたが、それを追求しようとしても
> 再現できなかった。それは忘れられていたのでも、重要でないと見なされていたからでもない。
> 
> そう、ぼくたちは突入と着陸用のソフトウエアにフル集中していたのだ。
> そう、ぼくたちはこの問題を優先度の低いものとみなしていた。
> そう、ぼくたちは着陸の前にすべてを完璧なものにしておきたかった。
> でも、優先度の低い問題を完璧にしようとして時間切れになってしまうことをのぞけば、
> ここにはどんな問題もないのだ。
> 
> ぼくたちの側にはもうひとつ別のこともあった。ぼくたちは、自分たちのシステムが
> どれくらい堅牢かを知っていた。なぜって、ぼくたちはそれがそうあるように
> デザインしたのだから。
> 
> ぼくたちは、この問題が起こったときに再起動してしまうことは知っていた。
> ぼくたちは現在の活動を復帰して、サイエンス用のデータに支障がないようにする
> 機構を組み込んでいた (たとえそれがあとの着陸後のミッションまで
> 使われないとしても)。ぼくたちは火星の大気に突入しているあいだに
> 複数回の再起動ができる機能も組み込んでいた (し、テストもしていた)。
> ぼくたちはメモリやプロセッサに当たった放射線によって引き起こされる
> エラーからも復帰できるようにソフトウエアをデザインした。着陸後に
> 無線が故障した場合でも、宇宙船はローバーの配置を含む 60日間のミッションを
> 自力でこなすことさえできただろう。たくさんのセーフガード機構が
> システムに組み込まれており、この種のエラーが起きたときでも堅牢で継続した
> 作業ができるようになっていた。このセーフガード機構のためぼくたちは
> この種の問題にあたる優先度を低くできたのだ。
> 
> ぼくたちは自分たちの優先度を守ったのである。
> 
> 
> 分析と教訓
> 
> ぼくたち (JPL チーム) は select/pipe 機能の動き方について、誤った仮定を
> していたのだろうか? おそらくはそうだろう。でも優先度逆転用の機能を使わないという
> 意識的な決定があったわけではない。ぼくたちは単にそれを見落としたのだ。
> この航行用ソフトウエアには、ほかにもクリティカルなデータ構造に
> 同様の保護が必要で、そのためのセマフォに優先度逆転用の機能が必要なところが
> 何箇所かあった。COTS 類を飛ばすときのひとつのよき教訓は − それがどう動くか
> 確実にわかっているようにしろ、ということだ。
> 
> もしぼくたちが解法をひらめくのに使えるこうしたツールを持っていなかったら、
> ぼくらはおそらく **永遠に** この問題を理解できなかっただろう、という点で、
> Mike が言ったことはまったく正しい。まさにこの手の問題のために、ぼくらはたくさんの
> ツールをソフトウエアの中に組み込んでおいた。ぼくたちはつねにそれを
> 残しておくことにした。実際のところ、シェル (と標準出力ストリーム) は
> ミッション全体をとおして非常に役に立った。より詳しいことが知りたい場合は
> ぼくにメモをおくれ。
> 
> 
> 記録を正しく
> 
> まず、みんなにぼくが Wind River 社についてどう感じているかをわかってもらいたい。
> 彼らはぼくたちのために、まったく素晴らしい仕事をしてくれた。彼らは熱意にあふれており、
> ぼくらが出せる値段で vxWorks の移植をしてほしいとたのみこんだときに
> サポートしてくれた。彼らはアルファ・バージョンを 3ヵ月でもってきてくれた。
> 問題がもちあがると、その問題に対してはぼくが今まで働いてきた中でも
> 一番すぐれたエンジニアの数人をよこしてくれた。彼らとのコミュニケーションは、
> 完璧だったよ。もし彼らがこれほどのプロフェッショナルな仕事をしてくれなかったら、
> マーズ・パスファインダー号のミッションはこれほどの成功はおさめなかっただろう。
> 
> つぎに、Dave Wilner はこの問題について、彼のトークの前にぼくに
> 話してくれたということ。ぼくはこの問題について詳しく記述した
> ノートを見つけることができなかったので、ぶっつけ本番でしゃべったが、
> これは明らかに間違いだった。ごめんよ Dave。
> 
> 
> 謝辞
> 
> まず最初に、このトークのとてもよくできた記述を書いてくれたことに対して
> Mike に感謝したい。たぶん 400人ばかりの人々がぼくにコピーをくれたと思うよ。
> きみは マーズ・パスファインダーのミッション終了レポートの一部を書くのに、
> ずっとぐずぐずしていたぼくをひと押ししてくれた。
> 
> とりわけ Steve Stolper にはこれを手伝ってもらって感謝している。
> 最大の感謝は、ぼくが率いる名誉にあずかれて、その卓越した技術力で
> ぼくたちを成功に導いてくれたソフトウエアチームに贈られるべきだろう:
> Pam Yoshioka, Dave Cummings, Don Meyer, Karl Schneider, 
> Greg Welz, Rick Achatz, Kim Gostelow, Dave Smyth, Steve Stolper。
> それから、Miguel San Martin, Sam Sirlin, Brian Lazara (WRS), 
> Mike Deliman (WRS), Lisa Stanley (WRS)。
> 
> 
> Glenn Reeves, マーズ・パスファインダー号 航行ソフトウエア統轄エンジニア
> glenn.e.reeves@jpl.nasa.gov

日本語訳: Yusuke Shinyama