論文紹介: Hive: Fault Containment for Shared-Memory MPs
紹介者: 久野∗1996.4.26

1• 論理レベル: ファイルやメモリ空間。

Introduction• 物理レベル: あるセルのメモリが不足→他のセルのメモリを借りる• SMP はサーバとして多く使われるようになった←動的なマルチプログラミング負荷に強い

どちらも、障害隔離のための考慮必要。たとえば他のセルの• しかし SMP OS は (登場し始めた) 大規模 SMP にはいまいち。

メモリを読もうとして読めない→タイムアウト→障害処理。

Hive は SGI IRIX 5.2 に基づき、これと互換。テスト/評
Hive: 大規模 SMP 用 OS。根本的な違い→複数の分散 OS(セ 価は SimOS と呼ばれる FLASH シミュレータによる。現在ルと呼ぶ) の集合体だということ。利点:得られている結果:• 障害に強い: クラッシュは 1 つのセルに限定される。

• 各種のメモリ障害が隔離可能。

• スケーラブル: 単一カーネルのボトルネックがない。

• カーネルの障害も隔離可能。
• 4 セル版で、IRIX5.2 と比べて 0%〜11%の性能低下。

課題:

ゆえに、大規模 SMP の OS として有望 (だがまだ研究途上)。

• 障害隔離 (fault containment): いかに障害を 1 セルに限定するか。とくに野蛮書 (wiled write) 対策。

• 資源共有: セルの境界を越えて CPU、メモリ等を融通

SMP における障害隔離

2したい。

• 単一システムイメージ: ユーザには 1 つの OS に見える。

• 障害隔離: 多くの分散 OS で実装。耐障害 (fault tolerance) とは違う←部分的な障害は起きてよい。だから二重系は不要。

本論文は、障害隔離に焦点。プラットフォームは Stanford

FLASH(障害隔離のためのハードウェア機構を持つ)。具体• SMP をサーバに使う場合、障害隔離は魅力的←複数の的な方策は:独立したプロセスが動いているから• ただし、OS が賢くないとだめ。プロセスのメモリがそこら中のセルに入ってしまえば、1 セルがダウンした• 防火壁 (firewall): 他のセルからの書き込みを捕捉するハードの利用。

らそのプロセスも死ぬ。

• 障害を起こしたセルが書き込めるページを破棄。

要求:• 迅速な障害検出。

アプリケーションが死ぬ確率はアプリケーションセル間のメモリ共有は 2 レベル:が占有するシステム資源に比例すること。cf. シ∗ Proc. 15th ACM Symp. on Operating Systems Prinsiples, ACM

ステム全体の資源に比例…通常の SMP

SIGOPS vol. 29, No. 5, 1995

1

大規模なアプリケーションはどのみちシステムを全部使う• Hive の機能→障害隔離のためのものと、資源共有のためのもの。

ので助からない (あたりまえ)。チェックポイント等を使うべし。
障害隔離は分散 OS でもやっているが、SMP だとより大3.1

変。ハード的には:Fault Containment Architecture• ハード的には前述の通り。OS レベルでは他のセルに悪• CC-NUMA (fig 2.1) →障害の単位はノード→ノードのい影響を及ぼすのは次のもの。

メモリがアクセスできなくなる/そのノード上のキャッ• 悪いメッセージを送る。

シュが失われる。

• 間違ったデータを作成し、それを他のセルが読む。

• OS としては: 障害のあと何を保証すべきか: 影響されなかったメモリはこれまで通り。影響のあったメモリ• リモート書き込み。

をアクセスしようとした CPU にはエラーが返される• なお、重要なデータを読めなくするというのもあるが、これは別の問題として取り上げない。

(無限遅延はこまる)。エラーのあったメモリの範囲が切り分けられる。

• つまりメモリ障害モデルが必要。FLASH では、(1) プ 悪いメッセージ:ロセサ間通信は途絶しない、(2) 影響を受けるメモリ• RPC での消毒 (sanity check) を行う。普通の分散 OS
は障害のあったセルが書き込み可能であった部分のみと同じ。
(防火壁の機能)。
間違ったデータを読ませる:
ソフト的には:• 読む側のセルで注意深くする。そのため用心参照 (care• 共有メモリの弱点: 野蛮書。文献 7 →ハード障害よりソful reference) プロトコルを用意。読んだ後はもちろんフト障害の方が多い。文献 20 → 5 年間にわたる 3000消毒。の障害調査で、15〜25%は野蛮書を伴った。
リモート書き込み:• 既存の SMP: 野蛮書には無防備。メモリ保護は仮想記
憶機構のみで、それは野蛮書を行う CPU が管理して• 各セルは他のセルのカーネル内部データを直接書くこいる。とはしない。もちろん、ユーザレベルページは共有され書くことができる。なので:• 対策: ハード的またはソフト的。ハード→キャッシュコントローラに入れるのが自然。ソフト→他のセルの信• 保護するページの選択: セルローカルなプロセス

頼できるソフトウェア機構によって野蛮書を防止。このページは他のセルには書かせないし、セルにまこでは信頼性、簡潔さからハードを選択。

たがるものでも最小限にする。ただし許可を落と• 各メモリページごとに、書き込み許可ビットベクタをす方向に設定するのは相手セルとの通信を伴う持たせる。

(向うのキャッシュをフラッシュしてもらう) ため高価。

3• 野蛮書対策: ユーザページへの野蛮書→メモリ故障と同等程度にまで減らしたい (でないと使ってHive Architectureもらえない) →障害を検出して、壊された可能性• セルの集合体 (図 3.1)。各セルの範囲はブート時に決定。各セルは自分の CPU、メモリ、I/O を管理。セル群のあるものはすべて破棄…悲観的アプローチ

は協調して 1 つのシステムであるかのようにふるまう。

2• ただし、検出される前に使われたり、書き込み権 資源共有のポリシー:を放棄する可能性→完全に防止するのは書き込み• ポリシーは全セルにまたがったプロセス Wax が決定
共有の放棄→それは受け入れ難い (SMP の利点の(図 3.3)。何についてのポリシーか→図 3.4。
放棄だから) →放棄せずにどこまで行けるか、普• 過去の分散システムでは次の 2 通りの方法
通の SMP OS 程度にまでなるかが課題。
• 各カーネルが通信しながらポリシー決定→全体像• 検出: 分散 OS で研究されて来た課題。停止したセルはすぐわかるが、狂ったまま動いているセルはわかりは見えないままにくい。他のセルから「あいつは狂ってるから止める」と言えることにすると、狂ったセルが他のセルを止めまくれることになってしまう。

• そこで、各セルは常に他人を観察し、あやしいと「怪しい!」とだけ言う→ユーザプロセスはすべて停止して、合意アルゴリズムの実行→合意された場合にそのセルをリブートする→ユーザプロセスの再開。

• 1 箇所で集中管理→ボトルネック• Wax ではまたがりタスクの共有メモリにすべての情報を保持できる。その各スレッドは個々のセルで動作しそのセルの情報を調べる。

• Wax はふつうのユーザレベルプロセス。セルが死んだ
ら Wax は一旦終了し、再度起動しなおし、情報を収集する (情報のリカバリが簡単)。

• 危険期間 (window of vulnerability): 障害発生から最• Wax から OS に渡すデータは各セルで消毒され、また初のチェックで誰かが「怪しい!」というまで。チェック

各セルの動作の整合性自体は Wax ではなく各セルの間隔と性能のトレードオフ。

カーネルが保証→ Wax によってシステムの信頼性が損なわれることはない。

3.2

Resource Sharing Architecture• 課題: SMP の密な通信の利点と障害隔離の両立。メカ

3.3

ニズム→カーネル、ポリシー→ Wax と呼ばれるユーザ

Implementaiton Status• とりあえず、障害隔離機構に焦点をあてて実装中。セル、用心参照プロトコル、野蛮書対策、障害検出、リレベルプロセス。

• セルはリソースの配分について判断しない←グローバ

カバリ、論理共有、物理共有、セル間高速 RPC など

ルな情報が必要だから。Wax はこの情報を持つがセル稼働。

は持たない。セルは自分の持ち分の整合性と性能にの• 単一システムイメージは途中。セル間 fork、分散プロみ責任を持つ。

セスグループ/シグナル、共有ファイルなど稼働。また資源共有のメカニズム:

がりタスク、Wax、合意プロトコル、耐故障ファイルシステムなど実装中。

• 資源: メモリと CPU• 現在のプロトタイプでも、障害隔離が実装可能なこと、• メモリ共有は 2 レベル (図 3.2)。論理レベル→ファイル (共有バッファキャッシュ) や仮想空間。物理レベル

それでいてオーバヘッドは小さいことは示せている。
しかしフル実装による実証はこれから。

→メモリ資源の有効利用と、アクセスの起きる箇所にデータを置ける (CC-NUMA の特性活用)。

• 性能評価は SimOS による。SGI Challenge クラスのマ• プロセスはセル境界にまたがれる (またがりタスク、spanning task)。各セルはそのうちローカルな持ち分

シン (R4000 200MHz 4CPU、700nsec メモリアクセスを管理するとともに、セルにまたがった共有情報も管ocean(シミュレーション)、raytrace。詳細は 7 節。

理。プロセスのセル間移送も可能。

3時間) をモデル化。実行例としては pmake(並列 make)、

4

Fault Containment Implementa- 4.2 Wild Write Defense
野蛮書対策→ 2 部構成。(1)FLASH ハードウェアの firewalltion
機構で、他のセルに書けるページを最小限に。(2) セルが fail• あるセルが別のセルに危害を与えるケース: (1) 悪いメッ
したらそのセルに書ける状態のページを全部捨てる。
セージ、(2) 悪いデータを他のセルに読ませる、(3) 他のセルへの書き込み。

• (1) については、分散システム (e.g. NFS) で実績が 4.2.1 Firewallある。
• 4KB page 毎の 64bit vector で CPU ごとに書き込み可• (2) と (3) が Hive の新しい点。
否を設定 (64CPU より多い場合はグループ化して map)

4.1

• bit が off なら書き込みは bus error に。bit の変更はlocal CPU のみ可能。

Careful Refrence Protocol• 各ノードのキャッシュコントローラ→そのノード用の• 他のセルのデータを直接読む← RPC では遅すぎる、最新情報がほしい、多数のセルから参照など。

ビット状態を追跡。キャッシュラインの所有者が誰か/書き戻し時点も追跡。

• 読み出したデータはメッセージの場合同様消毒すれば• 他のセルの I/O エリアのアクセスは bus error。DMAによる read/write は DMA を持っているセルの CPUよいが、読み出しそのものに問題。

• ノードが fail すると、メモリ参照は bus error に。

による read/write と同じ。

• 普通の OS →カーネル実行中のメモリ参照 fail →• 4KB というのは OS のページサイズに合わせた。これより大きくてもメモリ割り当てがやりにくい。小さくpanic(自分から shut down)。しかし他のセルの場合はこれでは困る。

するといいかどうかは?

• Hive では、注意参照 (careful reference) プロトコル。

• bit vector の代案: 1bit の書き込み保護ビット (エラー

1. careful on() を呼ぶ (スタックフレームの保管、buserror が起きたらハンドラにより復帰)

隔離にならない)、1 バイトで書き込み可能 CPU を指2. リモート参照の前に必ず境界揃えとメモリ範囲の検査• firewall のコストは小さい← remote write cache miss の3. 消毒の前にすべてのデータをローカルメモリにコピー

ocean で 4.4%増加。write cache miss 自体の比率はか定 (セルの内部での付加バランスができない) 1
平均処理時間は firewall check が入ると pmake で 6.3%、なり小さい。

4. データ構造ごとに構造識別子 (malloc が設定) を検査

4.2.2

5. すべて済んだら careful off() で元に戻る

Firewall management policy• エラー隔離と性能のトレードオフ。

• 例: クロックモニタアルゴリズム: 各セルのクロックハンドラが他のセルのクロック値をチェック。

• remote write が必要なのはある CPU の TLB に書き込み可能なリモートページがある場合。しかしこの状態• 200MHz CPU で careful on() から careful off() まで

は TLB miss ごとに変わるので、そのたびに RPC で1.16us(232cycles)、うち 0.7us(140cycles) はリモート元のセルに許可を求めていられない。2

セル参照のキャッシュミス。

1 書き込み可能セルを指定したら?

• RPC だと最低でも 7.2us。

2 MIPS R は TLB のみでマッピングを行い、TLB miss は OS で扱う

4• では firewall をどうやって管理? 当面は単純で比較的writable の少なくてすむ方法。

める、ということに。だからエラーを通知されるのは• ページに write fault が起きたら、そのセルの CPU す• 実装は世代番号。dirty なページを破棄したら世代が進べてにまとめて書き込み許可ビットを立てる→セル内

み、古い世代番号の記録された file descriptor やアドでの仕事の配分は自由。

レスマッピングから参照しようとするとエラー。

fail の前にファイルを open していたプロセスのみ。

• そのセルのどれかの CPU がページを write map している間は許可ビットは立ったまま。

4.3• ページが writable で map されるのは、ファイルを書Failure Detection and Recovery• 野蛮書き込みによる影響を少なくするため、できるだ

き込み可能モードでマップした場合→そのセルのプロ

け迅速に fail を検出←定期的な整合チェックによる←セスが要求した場合のみ。

チェックが失敗したら分散合意アルゴリズムで合意• pmake(共有 write 少) → 5.0 秒の実行中を 20msec 間隔• RPC timeout ← fail の可能性 (分散 OS と同じ)。それ以外に (1) メモリアクセスが bus error、(2) クロックでサンプル→ 15 remote writable pages/cell。max 42— /tmp のファイルサーバとなったセル。独立プロセ

モニタチェックが失敗、(3) 読み出したデータの整合性

スの集合に対してはうまく働く。

チェックが失敗。

• ocean(共 有 write 多) →〃→ 550 remote writable• 一定時間内に同じ警告を出して 2 回とも合意アルゴリ

pages/cell。どのみち全セルが共同で仕事をしているから、隔離は無理。

ズムでウソだと言われたノードも fail したとみなす。

• 合意アルゴリズムは標準的なもの (未実装)。
4.2.3

Preemptive discard
4.3.1• cell failure の後どのページを破棄するか調べるのは大変→全 TLB をフラッシュし、全 mapping を remove

Recovery algorithm• 生きているセルがどれとどれか決まったら、回復アルゴリズムを実行。その最初には、ページフォルト処理→後に再度 page fault が起きたときチェックする。

や他のセルからのリモートメモリアクセスがまだ残っ• ページを破棄→ファイルシステムのセマンティクスがているかも。

変わってしまう可能性。

• というのは、回復中はユーザプロセスは凍結されるがカーネルレベルのプロセスは凍結されない (回復アル• dirty なページを破棄した場合、後にそのページをアクセスしようとしたプロセスはエラー通知を受けるべ

ゴリズムのためにも必要)。

き…だが、ずーっと後でアクセスするかも知れないの• そこで、まず TLB をフラッシュしてマッピングを削除したら最初のバリアに入る。ここを通過した後のペーでむずかしい。

• ほとんどの UNIX ではクラッシュ時の dirty なページジフォルトはクライアント側で保留しておく。

を調べたりせず、reboot 時に単にディスクにあるものを読み出す←クラッシュしたらローカルなプロセスも• そこで、以後は正当なページフォルトもリモートアク死ぬので、dirty なページをアクセスしたプロセスが不セスも残っていないので、firewall の書き込み許可ビッ整合を観測するということがない。3

トを落として VM cleanup(fail したセルが書けるページを破棄したりそれをファイルシステムに通知したり• そこで Hive でもセルが fail した後そのセルのディスクから読み出すプロセスは単にディスクにあるものが読世代番号を進めたりといった処理をする)。

3 でもその情報を別のページに書いてそれはディスクに入ったら…

5

• VM cleanup が終わったら 2 番目のバリアに入り、それを抜けたら通常動作に復帰 (保留していたページフォ

5.2• Hive では、あるセルが別のセルのページをアクセスしルトも処理)。

たい場合、新しい pfdat(extended pfdat) を割り当てる• ページフォルト RPC のサーバ側は回復のためにブロックする必要がなく、割り込みレベルのみで動作でき効→残りのシステムはリモートメモリアクセスだと知らないまま動作率的。

• 回復の最後にマスタを決め、マスタは fail したセルのハードウェアチェックを行い、正常なら reboot させる。

• export/import — あるセルのページを別のセルの extended pfdat と対応づける操作。
• ページフォルトハンドラ→ないページ→ vonde に読み込み依頼→リモートノードを現す vnode →データホー
ムに RPC →サーバ側はまだページがメモリになけれ共有メモリの実装

5

Logical-Level Sharing of File Pages

ば読み込む→データホームは export を実行→そのこと• エラー隔離を実装しながらいかにうまく共有も許すか?

はデータホームの pfdat に記録 (解放されないように/• 論理レベル共有と物理レベル共有がある。

回復時に参照) →クライアントにそのページのアドレスを変えす→クライアントは import を実行→ extended• セルの役割り→ 3 種類

pfdat が割り当てられハッシュ表に入る。

• Client: データを参照するプロセスが動いている• 以上が一度起これば、あとはハッシュ表を見ればあるのでページフォルトは迅速に処理できる。

セル• Memory Home: 物理ページを持っているセル• クライアントがページを解放→ release を実行→ ex-• Data Home: そのページの中身を持っているセル

tended pfdat を解放してデータホームに RPC →デー
タホームは (他に使われていなければ) ページをフリー• データホームは各種の管理をする。現在の実装ではデーリストに→再度必要になったら取り返せる

タホームは常にそのページのバッキングストアを持つ。

• ローカルページフォルト: 6.9us、リモートページフォル

以下ではまず Hive の基にした IRIX の説明から。

ト: 50.7us (table 5.2)。リモートのうち 17.3us は PRC
コスト、14.2us は IRIX の遅いデータ構造アクセス。

5.1

IRIX Page Cache Design• 各ブロック (物理ページ) は pfdats データ構造が対応。

• 実際には完全に割り込みレベルで処理できない場合も。
全体の効果を見るため pmake で計測。6 秒の実行→8935 faults → 4946 が remote →平均 455msec/fault (cf.
117msec on 1-cell system)。pmake の 1cell から 4cell

pfdats には論理ページ id を格納。論理ページ id は tagと offset から成る。tag はその論理ページが所属するになって遅くなった部分のうち 13%を占める。

object を示し、offset はその中の位置を示す。ハッシュ表で論理 id から pfdats が引ける。

5.3• ページフォルト→ pfdats を検索し、なければ vnode 経
由でファイルシステムに頼んで物理ページを割り当て内容を読み込んでもらう。

Logical-level sharing of anonymouspages• 無名ページ (swap エリア) もほぼ同様。

• read/write システムコールもほぼ同様。

• 無名ページは copy-on-write tree で管理 e.g. Mach
• ただし parent と child が別のセルにあるかも。これを分散カーネル構造で実装してみた。
6• copy-on-write tree の構造は同様→ポインタがリモートポインタ。ローカルプロセスに対応する leaf は必ず• たとえば、クライアントがページを貸してデータホームがそこにデータを入れれば効率が良い。CC-NUMA

ローカルメモリにあるが、他のノードはどこにあってを生かしている。

もよい。

• これをサポートするため、VM は貸したページが importされる時には元の extended pfdat を再利用する。

• 参照のみで変更は不要なので野蛮書の問題はない。
• 共有ページの fault は注意プロトコルしながらポインタをたどっていって該当ノードをみつけ、RPC で ex-5.6

port/import をたのむ。
• この方法で安定して動いている (fault injection もパス) ので、安全な分散データ構造ができることは示せ• 共有により、他のセルの fail が自分のセルのユーザプロセスにダメージを与え得る。そこで:た。が、速くもない。普通に RPC でいきなり頼むの• ページ割り当て/移動時に、なるべく同じところのを使う。

でもいいかも。

5.4

Memory Sharing and Fault Containment• 世代番号方式なので、cell fail で失われるデータの単位

Physical-level sharing

はファイル。だからファイルのメモリホームも絞る。

• ここまでのところ、すべてのページはデータホームの• むずかしいところ。

キャッシュにあることになっていたが…データホームのメモリに、ということなら CC-NUMA の利点がな

5.7

い→物理レベル共有が回答• メモリホームは extended pfdat を利用して物理ページを他のセルに貸し出せる (fig 5.3b)。貸し出したページ

Summary of Memory Sharing Implementation• 論理レベルと物理レベルの分離が重要。

は覚えておき自分では使わない。

• extended pfdat による位置透明性。

• データホームは extended pfdat を割り当ててこのペー• 貸したページを返せとは今はいえない (むずかしい)。

ジを普通に利用 (ただし firewall の設定を変えるときは• 将来は Wax で。

RPC でメモリホームに頼む)。
• とりあえず demand driven で。将来は Wax でポリシーを。

6• 借りたページは一部の目的には使えない。メモリホー

RPC Performance Optimization• RPC の高速化は性能上重要→専用ハード

ムの野蛮書に無防備だから、カーネルには使えない。

• 借りたフレームはいらなくなったらすぐ返しているが、もっとよい方法を探求。

• 専用ハードなしでは、プロセサ間割り込み (IPI)+ス
キャン→遅いし壊されやすい。
• Short InterProcessor Send 機能 (SIPS) →キャッシュラ

5.5

イン (128bytes) と同じ大きさのメッセージを特定プロ

Logical/Physical intereactions

セッサのキューに投げられる。速度はキャッシュミスと同じ。

• 物理レベル共有と論理レベル共有は独立に動作。

• 信頼できるメッセージ→分散システムにくらべて実装が楽。
7

• null RPC → 7.2us (1440cycles)、うち 2us が SIPS。な
ので、返事待ちは spin wait (50usec したら timeout)。
• null でない実際には平均 9.6us (1920cycles)。おもにスタブ実行のオーバヘッド。

• この上にキュー機能を持つ RPC。null RPC で 34us。
• この落差→できるだけ割り込みレベル RPC でできるように設計。また、割り込みレベルで処理できない (ブロックする必要のある) 場合だけキュー機能に移行するように設計。

7

Experimental Results

7.1

SimOS Environment

7.2

Simulated Machine

7.3Performance Tests

7.4

Fault Injection Tests

8

Discussion

9

Related Work

10

Concluding Remarks

8