ļĺÇÐ
5.2 システムモデル
process A
process B
message (from A to B)
recovery point
図 5.3: 一貫性が保たれる復元状態
process A
process B
message (from A to B)
recovery point
図 5.4: 矛盾を生じる復元状態
各プロセスにおいて，復元される状態がメッセージを横切る場合を図5.3および 図5.4に示す．横の矢印は，各プロセスの実行を表わしている．斜めの矢印は，プ ロセス間でやり取りされるメッセージを表わしており，両図ともプロセスBがプロ セスAからメッセージを受け取る状況を示している．図中の黒丸はそれぞれのプ ロセスの状態が復元される時点を示している．図5.3はプロセスAについてはメッ セージを送信した後の状態，プロセスBについてはメッセージを受信する前の状 態が復元される場合を表している．図5.4はプロセスA についてはメッセージを送 信する前の状態，プロセスBがメッセージを受信した後の状態が復元される場合 を示している．
これらの図において，図5.3は一貫性を保った復元状態となり，図5.4は矛盾が 生じる(一貫性が保てない)復元状態となる[Elnozahy et al. 99]．図5.4では，プロ セスBについての復元状態がプロセスAが送ったメッセージを反映しているにも かかわらず，プロセスAの復元状態はそのメッセージを送る前の状態となり，これ は，現実には起り得ない状態となるためである．それぞれの図で見られるように，
各プロセスの復元される状態を結んだ線(図中点線)に着目すれば，この線がメッ セージと「X」の形で交差する場合には一貫性が保たれた状態であり，メッセージ を追い越すような形で交差する線は一貫性が保てない状態となる．
なお，図5.3において，復元状態を示す線がメッセージを横切るということは，
「メッセージは送られたが，まだ届いていない状態」が復元されるということを意味 する．このようなメッセージはイン・トランジット・メッセージ(in-transit message) と呼ばれる．イン・トランジット・メッセージは各プロセスの実行状態の復元後，
受信したプロセスに再度渡される必要が生じる．
これらの一貫性の議論をもとに，メッセージパッシングシステムおけるシステム 全体の実行状態復元の実際の方法は，大きく以下の2種類に分類される．
• チェックポインティングベースのロールバックリカバリ
• ログベースのロールバックリカバリ
チェックポインティングベースのリカバリは，各プロセスで行われるチェックポ インティングのみを用いる方法である．図5.5は，チェックポインティングベース のリカバリ手法における実行状態復元の例を示している．前述の例と同様に，各プ ロセスの実行は横の矢印で表し，メッセージは斜めの矢印で表している．各プロセ スのチェックポイントは，図中黒丸で表している．通常実行中，各プロセスはそれ ぞれ自身の状態を保存(チェックポインティング) する．あるプロセスに故障が生 じリカバリが必要になったとき，リカバリ作業では一貫性が保たれる各プロセスの チェックポイントを選びだし，その状態まで各プロセスの実行状態を戻す(ロール バック)．図5.5の例では，前述の議論に基づき(c3A, c2B, c3C)が一貫性が維持された 状態となり，各プロセスについてこれらのチェックポイントの状態が復元されるこ
Recovery line Process
A
Process B
Process C
Message
Recovery point
Rollback
failure Checkpoint
m2
m3
m4
m5
m6
m1
m7
cA1 cA2 cA3 cA4
cB1 cB2
cB3
cC1 cC2 cC3 m8
図 5.5: チェックポインティングベースのロールバックリカバリ
とになる．なお，チェックポインティングベースの手法では，リカバリ作業によっ て各プロセスが復元されるポイントは「リカバリポイント(recovery point)」と呼 ばれる．また，各リカバリポイントを結んだ線は「リカバリライン(recovery line)」
と呼ばれる．
ログベースのロールバックリカバリでは，各プロセスで行われるチェックポイン ティングに加えプロセス間で取り交わされるメッセージの情報をログとして保存す る．リカバリ時には，このログを用いてメッセージを再生することにより，チェッ クポイント後の各プロセスの状態を再構築する．このときやはり再構築される状態 は，一貫性が維持されたシステム状態である必要がある．
5.2.2 デバイスドライバとデバイスの動作
本研究では，デバイスの取り扱いに対し，以下の3つをプロセスとしてみなして 前節で述べたメッセージパッシングシステムでの一貫性の議論を適用する．
• デバイス
• デバイスドライバ(通常実行)
• 割り込み処理
CPUとデバイスの関係を図5.6に示す．横の矢印は，それぞれCPUとデバイス が動作していることを表している．デバイスの横の矢印のうち，細い部分はデバイ スが停止している(idle状態)ことを示す．また，縦の矢印はCPUからデバイスの レジスタへのアクセスを示し，それぞれCPUからデバイスへ向うものはwrite，デ バイスからCPUへ向うものはreadアクセスを示している．割り込みも同様に，デ バイスからCPUへ向う縦の矢印で示している．
CPU
device
read access
write access
interrupt
図 5.6: CPUとデバイスの動作
通常デバイスはCPUからのアクセスによってレジスタが設定された後，その動 作を開始する．多くのデバイスは，CPUとは並列に動作し，その動作の完了は割 り込みによって通知される．つまり，デバイスはCPUからのアクセスによってそ の状態が変化し，また，CPUと並列に動作している最中にも自身でその状態を変 化させる．
図5.6は分散システムの図5.5に非常に良く似ている．CPUとデバイスが並列か つ独立に動作することは，分散システムにおける各プロセスの扱いと同様である．
また，デバイスへのアクセスおよび割り込みによって，それぞれCPUおよびデバ イスの状態が変化することも，分散システムにおけるメッセージの取り扱いと同様 である．
これらのことから，デバイスとデバイスドライバの関係において，分散システム における一貫性の議論を適用する．つまり，デバイスドライバおよびデバイスにつ いて，デバイスアクセス(メッセージ)を横切らないリカバリラインを構築するこ とができれば，それは，一貫性の保たれた復元状態となる，ということである．な お，このことに関する妥当性については6.1節で述べる．
デバイスはデバイス自身でその状態を保存することができない，という点におい て，メッセージパッシングシステムと異なる．このため，2.3.3節で述べたように，
デバイスが停止している状態はCPUからの適切な再初期化処理によって復元可能 とし，リカバリ処理によってその状態が復元されるものとする．また，メッセージ パッシングシステムでは，図5.3のようにメッセージを横切った場合，リカバリ後 に再生する必要があった．これは，メッセージパッシングシステムでは通信チャネ ルによってアプリケーションには透過に行われることが多かった．これは，デバイ スとCPUの関係においては，リカバリ時にCPUが明示的にアクセスを再生する ことによって行うことができる．また，デバイスへのアクセスは即座にデバイスの 状態に反映されるものとし，イン・トランジット・メッセージは考慮しない．
このようにモデル化したとき，デバイスドライバとデバイスの一貫性を保つため には，デバイスについて復元可能な状態と，CPUおよび主記憶(デバイスドライバ の実行)について復元可能な状態とを基準にして各アクセスを横切らないリカバリ
Device driver
Device
P1 P2
L1 L2 L3
図 5.7: 基本的なデバイスアクセス
ラインを発見し，このリカバリラインを構築するために必要なデバイスドライバで の処理について考えれば良いことになる．以下，このモデルを用いて，デバイスお よびデバイスドライバ間での一貫性の維持のための処理について，検討を行う．
なお，デバイスドライバの実行のうち，割り込み処理についても一つのプロセス とみなしてモデル化する．なぜなら，割り込み処理はCPUの通常実行に対して非 同期に起動され，また，そのコンテキストはデバイスドライバとは独立のものとな るためである．