2005/12/13

前回のおさらい（１）
前回のおさらい（１）z 排他制御（相互排除）– 複数のプロセス（スレッド）のプログラムコードの中に，共通の資源（例：共有変数など）にアクセスする部分があるとき，その部分を同時に実行できるプロセス（スレッド）がただ一つとなるようにすること．
• 最初のプロセス（スレッド）が上記のような危険区間（critical section）に到達すると，他のプロセス（スレッド）は危険区間の中に入れないように制御する．
z 同期処理– プロセス（スレッド）が，何らかの条件が成り立つまで処理を中断して待つこと．
• ここでいう「条件」とは，自分自身以外のものによって変更される種類のものを指す．

コンピュータシステムII（１０）
情報基盤センター
天野 浩文

12

前回のおさらい（２）
前回のおさらい（２）

前回のおさらい（３）前回のおさらい（３）z セマフォ（semaphore）– もともとは相互排除のための機構– 少し工夫すると，ある種の同期にも使える．
– 最も簡単な相互排除機構
z 以下のような性質を持つ整数型変数– 初期化を別にすれば，次のような P および V と呼ばれる2種類の操作によってのみアクセス可能• P: 危険区間の開始を宣言する．他のプロセス（スレッド）が危険区間に入っているときには，先に進まずにここで待つ．
• V: 危険区間の終了を宣言する．同じセマフォに対するP命令で待っている他のプロセス（スレッド）が先に進めるようになる．

z セマフォを排他制御に使うとき– 初期状態は，危険区間に入れる状態• セマフォの初期値を１または正の整数にセット– 各プロセス（スレッド）は，危険区間の前後をP操作・V操作ではさんでおく．
z セマフォを同期処理に使うとき– 初期状態は，P操作が先に進めない状態• セマフォの初期値は 0 または負の整数– 先行させたいほうにV操作を，後追いさせたいほうにP操作を実行させる．

3

コンピュータシステムII（１０）412005/12/13

前回のおさらい（４）前回のおさらい（４）前回のおさらい（５）前回のおさらい（５）z バリア同期– 待ち状態のプロセス（スレッド）を１つだけ覚醒させるPV操作とは異なり，N 番目にそれを実行したものが他のすべてを覚醒させる．
– バリア同期すべきプロセス（スレッド）の数 N を初期値とする
共有変数を用いる

z P操作の実装に関する注意– 「先に進んでよいかどうか」の条件判断と，それに続くセマ
フォの変更や休眠処理までの間に，他のP操作の条件判断がはさまると，不具合が発生する．
– 複数のプロセッサが共有メモリ上の変数にアクセスできる場
合には，割り込みを禁止するだけでは不可• 単一の機械語命令で実装するとよいz Test-and-Set 命令（機械語命令）を使ったP操作

Barrier(S): Sを1減らす
if S>0 then {自分自身を休眠状態にする} else {他のすべてのプロセス（スレッド）を覚醒させる
Sを再初期化}

while Test-and-Set(lock) do {}– Test-and-Set(lock)• 変数lockの値を返す• lockには trueを書き込む

lockの値が true
なら，TS命令の繰り返し．
lockの値がfalse なら，何も実行せずに終了して次に進む．

5

6

デッドロック（deadlock）
デッドロック（deadlock）
z 「すでに確保した資源がありながら，他のプロセス（スレッド）が先に確保してしまったために待たされている資源がある」という状態にある一群のプロセス（スレッド）が，いずれも先に進めなくなって膠着状態に陥ること．

排他制御機構と同期機構（つづき）
排他制御機構と同期機構（つづき）:
P(S1);
P(S2);
共有資源に対する処理
V(S2);
V(S1);
:

S1

S2

取れる:
P(S2);
P(S1);
共有資源１に対する処理
V(S2);
V(S1);:

取れない
7

コンピュータシステムII（１０）822005/12/13

デッドロックが起きるための必要条件
デッドロックが起きるための必要条件

デッドロックの抑止（prevention）
デッドロックの抑止（prevention）

z デッドロックが起こるためには，以下の条件がすべて成立していなければな
らない．
1. 相互排除（mutual exclusion）
少なくとも１つの資源は，同時にひとつのプロセス（スレッド）にしか利用できない．
2. 確保と待機（hold and wait）
少なくとも１つの資源を確保しているが，他のプロセス（スレッド）が先に確保してしまった資源が利用可能になるのを待っているプロセス（スレッド）が少なくとも１つある．
3. 非プリエンプション（no preemption）
いったん確保された資源は，そのプロセス（スレッド）の処理が終了して解放されるまでは利用可能にならない．
4. 巡回待機（circular wait）「プロセス（スレッド）i はプロセス（スレッド）j の確保している資源が解放されるのを待っている」という関係が，p1→p2→・・・→pn →p1という形式で閉路を形成している．

z デッドロックの必要条件４つのうちのいずれかが成立しないように，プロセス（スレッド）からの資源要求の順序・タイミングに一定の制約を課す．
– 条件１：「相互排除」を取り除くのは，一般には不可能．
– 条件２：「確保と待機」を取り除くには，各プロセス（スレッド）に，たとえば• 実行に先立ってすべての資源を確保するようにさせる．
• 共有資源を何も確保していないときにのみ，資源を要求するようにさせる．
– 条件３：「非プリエンプション」を取り除くには，たとえば：• すでに何かの資源を確保したプロセス（スレッド）がさらに別の資源を要求したとき，それが確保できなければ，先に確保した資源を取り上げてしまう．
– 条件４：「巡回待機」を取り除くには，たとえば• 資源の間にあらかじめ順番を付け，その順にしか資源を要求できないようにさせる．

9

10

デッドロックの回避（avoidance）
デッドロックの回避（avoidance）

デッドロックが起こってしまったらデッドロックが起こってしまったら

z デッドロックの抑止の問題点• （確かに，デッドロックが起きていないか，起きるおそれがないかを監視しておく必要はないのだが…）

z 不幸にもデッドロックが起こってしまったら– そのままにしておいても自然に解消されることは絶対にない．
z デッドロックからの回復（recovery from a deadlock）– デッドロックに関与しているプロセス（スレッド）のいずれかを強制終了させる．
• 終了させられたプロセス（スレッド）が確保していた資源は解放され，巡回待機の条件が（一時的に）消滅する．
• あるいは，デッドロックが解消されるまで，順にプロセス（スレッド）を強制終了して，資源を解放させていく．
– デッドロックに関与しているプロセス（スレッド）のいずれかを，まだ実行開始していなかったことにする．
• やりかけた操作をすべて元の状態に戻して，最初から実行しなおす．

– しかし，資源の利用効率，ひいてはシステム全体の処理効率が低下してしまう．
z デッドロックの回避（avoidance）– システム全体の資源の割り当て状況を監視しながら，デッドロックが発生する可能性のある資源割り当て要求が出されたら，それの処理を遅らせる．
– 資源の割り当て状況やプロセス相互の待機状況を常に監視しておかなければならない．

11

コンピュータシステムII（１０）1232005/12/13

デッドロックの検出（detection）
デッドロックの検出（detection）

待ちグラフの例
待ちグラフの例

z デッドロックの回避やデッドロックからの回復を行うためには，システムがデッドロックに陥っていっているかどうか，あるいは，デッドロックに陥る危険がないかどうか，を知る方法が必要．
z 待ちグラフ（wait-forグラフ）– 「プロセス（スレッド）i はプロセス（スレッド）j の確保している資源が解放されるのを待っている」という関係を，pi→pjという枝（edge）で表したグラフ– これに閉路があることは，デッドロック状態にあることの必要十分条件である．
– 待ちグラフを常時管理しておき，定期的に閉路検出アルゴリズムを走らせる．
z 時間切れ（timeout）方式– ある程度の時間が経過しても終了しない処理は，デッドロックに陥っていると推定する．
– 検知は非常に簡単だが，単に時間がかかっているだけのものをデッドロックと誤判定する危険もある．

p1

p2

p3

p1

p2

p3
実は，この待ちグラフには，全体を含む大きな閉路も存在している．

p4

p4

デッドロックではない状態

デッドロックが発生している状態

z p3が終了すれば，p2も終了できる．
z p2が終了すれば，p1が終了できる．
z p1とp2とp3が終了すれば，p4が終了できる．

z p2とp3とp4は巡回待機の状態にあるため，このままでは終了できない．
z p1は，p2が終了しない限り終了できない．
z p4は，p1とp2とp3が終了しない限り終了できない．

13

14

単一プロセッサ上のデッドロック検出との比較
単一プロセッサ上のデッドロック検出との比較

デッドロックからの回復の有効性（１）
デッドロックからの回復の有効性（１）z 並列処理・分散処理におけるデッドロック検出– 実は，単一プロセッサ上で複数のプロセス（スレッド）を時分割実行している場合と，ほぼ同様の議論となっている．
• 単一プロセッサ上でもデッドロックは発生しうる．
• それを抑止・回避・検出することが必要．
z ただし，並列処理・分散処理においては，単一プロセッサの場合よりも，より複雑で困難な問題になる．
– システム全体の状況を把握しているスケジューラがどこで動作しているか？
• プロセススケジューリングの項で，システム全体のREADYプロセスキューやスケジューラの配置を議論したときと同様の状況

z 並列処理・分散処理には，次の２つの理由で行われるものがある．
1. 複数の演算ノードを同時に必要とするような大規模計算や，広域に分散したデータをまとめて使用するような大規模データ処理のため
2. 個々の計算・処理は単一または少数の演算ノード上で実行可能であるが，たくさんの計算・処理を複数の演算ノード上にばらまいて同時に実行するため（結果として，全体が並列処理・分散処理になっている）
z デッドロックからの回復は，上記のいずれの場合も有効なのだろうか？

15

コンピュータシステムII（１０）1642005/12/13

デッドロックからの回復の有効性（２）デッドロックからの回復の有効性（２）デッドロックからの回復の有効性（３）デッドロックからの回復の有効性（３）z 複数の演算ノードを同時に使用するような大規模計算・処理のとき– デッドロックを起こしたプロセス（スレッド）も，そうでないプロセス（スレッド）も，共通の目的のための大きな仕事の一部分を分担している．
– 内部でバリア同期を行っていることもある．
z この中でデッドロックが発生する場合– プログラム全体を再度先頭から実行しなおしても，また同じプロセス（スレッド）群が同じ場所でデッドロックに陥る可能性が高い．
– デッドロックを発生させたプロセス（スレッド）だけ強制終了させたり再実行させたりすると，正しい結果にならない．

z 複数の演算ノード上にばらまかれて同時に実行される，多数の小さな計算・処理のとき– それらの計算・処理は，全体でひとつの計算・処理を行っているわけではない．全体でバリア同期を取るようなこともない．
– 単体でデッドロックを起こす可能性は低いが，複数集まると，デッドロックに陥ることがある．
• 後で述べるトランザクション処理は，このような処理の好例
z この種のデッドロックが発生した場合– デッドロックを発生させてしまったプロセス（スレッド）だけ強制終了させたり再実行させても，他のプロセス（スレッド）は正しい結果を生成できる．
– 再実行されたプロセス（スレッド）は，再びデッドロックが起こらなければ，正しい結果を生成できる．
z このような状況では，デッドロックからの回復も有効である．
– 実際に，データベースでは，デッドロックに陥ったトランザクション（この用語の意味は後述）のアボートや再実行を行うことがある．

– 前回示した行列積の例を思い出して欲しい．

z このような状況では，デッドロックからの回復はあまり有効ではない．
– むしろ，デッドロックを回避または抑止できるように，プログラムのほうを修正すべき

17

18

トランザクション（Transaction）
トランザクション（Transaction）
z 一つの意味的にまとまった仕事– 「意味的にまとまった」とは，途中まで実行されて中断・中止された状態
では，意味のある（正しい）結果を残せない，ということ．
– データベース（database, DB）の分野で使われることが多く，「ひとまとまりの処理を構成するデータベース操作の集まり」などと定義されることもある．
– ここでは，データベースに議論を限ることにする．
z トランザクションの例– 預金口座Aに，指定された金額を入金する• データベース中の預金口座Aのデータに対する参照（読み出し）と更新（書き込み）– 預金口座Aから，指定された金額を引き出す• データベース中の預金口座Aのデータに対する参照と更新– 預金口座Aから預金口座Bに，指定された金額を送金する．
• データベース中の預金口座Aのデータに対する参照と更新• データベース中の預金口座Bのデータに対する参照と更新

並行処理制御（Concurrency
並行処理制御（Concurrency Control）
Control）
教科書では，これを「同時性制御」と呼んでいる．しかし，concurrent は従来から「並行（の）」と訳されることが多かったし，「同時」という訳語は simultaneous との混同を招く恐れもある．この講義では，あえて「並行処理制御」という用語を用いる．
（なお，「並行制御」，「並行性制御」，「同時実行制御」などと呼ぶ専門家もいる．）

19

コンピュータシステムII（１０）2052005/12/13

トランザクションとデータベース管理システム
トランザクションとデータベース管理システム

古典的なトランザクション処理
古典的なトランザクション処理

z データベース管理システム（database management system,DBMS）

z CPUに比べるとディスク装置ははるかに低速なので，あるトランザクションの処理のためにディスクアクセスが始まると，CPUが遊んでしまう．
– CPUが一つしかない場合でも，その間に他のトランザクションのための演算処理を行えばよいではないか！
z 時間軸の上では，複数のトランザクションのための処理が同時に進行しているように見える．
– このように，一つのCPUの上で複数の処理が（実行権を奪い合いながら／譲り合いながら）同時に進行している状態を並行（concurrent）であるという．

– データベースへの操作（読み出し，書き込み）のすべてを代行する
z トランザクションは，すべてこのDBMSによって処理される．
データベース
管理システムトランザクション1の処理

トランザクション2の処理

データベース
21

22

並行処理制御（Concurrency
並行処理制御（Concurrency Control）の必要性Control）の必要性

並行処理制御の目的
並行処理制御の目的

z 複数のトランザクションを並行に処理する場合に，何の制御もせずに野放図に並行処理すると：– トランザクションの要求した処理が正しく実行されないおそれがある．
– データベースの一貫性が損なわれるおそれがある．
• データベースのデータは長期間保存されることが多いので，誤りが長期間他の処理に影響を与え続けたり，誤りがたくさん蓄積してデータベースの価値が損なわれる．
z 並行処理を行う場合には何らかの制御が必要だ！
⇒並行処理制御– （性能向上のために）並行処理したとしても，あえてそうしなかった場合と同じ結果になっている必要がある．

z 直列可能性（serializability）

23

コンピュータシステムII（１０）– 複数のトランザクションをあるスケジュールで切り替えながら実行した場合には，それと等価な結果を生む何らかの直列スケジュールが存在しなければならない．

このように実行してもよいが...

下のいずれかの順序で直列（逐次）実行したのと同じ結果になっていなければならない．ただし，到着順でなくともよい．
24

6

2005/12/13

トランザクションが隔離性を満たさない例（１）トランザクションが隔離性を満たさない例（１）z 複数のトランザクションを同時に実行してもよいが，その処理内容について，DBMSは以下のような性質を保証しなければならない．
– ACID特性（ACID property）• 原子性（Atomicity）

z 前回の講義でも取り上げた，口座からの出金の例– トランザクションが行う操作はすべてデータベースに反映されるか，あるいは，すべて取り消されるか，のどちらかでなければならない．

時間トランザクション処理に関する最近の議論
トランザクション処理に関する最近の議論

トランザクション2

トランザクション1

READ(A);

100
100
100READ(A);

0A=A-100;
WRITE(A);• 一貫性（Consistency）– 一貫性の取れたデータベースに対してトランザクションを実行した結果は，再び一貫性が取れていなければならない．

A=A+200;• 隔離性（Isolation）…直列可能性と同じことを言っている– 複数のトランザクションを並行処理（同時実行）した場合でも，その結果は，それらのトランザクションを何らかの順序で逐次処理した場合と一致しなければならない．

WRITE(A);300• 耐久性（Durability）– 一旦実行終了したトランザクションの行ったデータ操作は，その後のシステム障害などで消失してはならない．

これらのトランザクションを，1⇒2，2⇒1のどちらの直列スケジュールで実行しても，このような結果になることはない．

300?
2526

トランザクションが隔離性を満たさない例（２）（つづき）
トランザクションが隔離性を満たさない例（２）（つづき）

z 口座Aから口座Bに送金するトランザクションを考える．
– 口座Aのデータと口座Bのデータをそれぞれプロセス p1とプロセス p2が管理している．
– トランザクションT1とトランザクションT2は，口座Aからの出金処理・口座Bへの入金処理を行う．それぞれの金額は100，200とする．

z T1・T2はいずれも，出金を行ってから入金を行うが，以下のようなスケジュー
ル S で実行されたとする．
1. p1：T1のために口座Aの出金処理
2. p2：T2のために口座Aの出金処理
口座A
100
3. p1：T2のために口座Bの入金処理
200
4. p2：T1のために口座Bの入金処理
z T1・T2を直列（逐次）に実行する
場合の順序
時間– T1⇒T2
口座B– T2⇒T1
100z スケジュール S で実行された場合の200
口座Aと口座Bに残る履歴の組み合わせ（右の２枚の図）は，上記のいずれの直列スケジュールとも一致しない．

DBMS
p1

金額

T1

p2

T2

時間

AB

コンピュータシステムII（１０）金額

トランザクションが隔離性を満たさない例（２）トランザクションが隔離性を満たさない例（２）

2728

7

2005/12/13

隔離性を満たすための方策の例
隔離性を満たすための方策の例

z 複数のトランザクションを並行処理（同時実行）した場合でも，その結果は– データベースの，可能なすべての初期状態に対して，– アクセスされるすべてのデータ項目について，– それらのトランザクションを何らかの順序で逐次処理した場合の結果（変化の履歴を含む）と一致しなければならない．
z 特定の初期状態のときだけ等価な直列スケジュールが存在する，というのではダメ– 先ほどの例で，残高不足でどちらのトランザクションも送金できないような場合には，どんなスケジュールで実行しても直列実行の場合と（たまたま）等価な結果になる．
z データ項目Aの上で観測されるトランザクション実行順とデータ項目Bの上で観測されるトランザクション実行順が異なるようなことも，あってはならない．

z 二相ロック（two-phase locking）プロトコル– 各トランザクションは，データベース内のデータ項目に対し，ロック・アンロックによる排他的なアクセスを行う．
• データ項目に対するロック・アンロックは，セマフォに対するP・V操作のような働きをする．
• 共有（読み出し）ロックと専有（書き込み）ロック• 複数の資源をロックする場合，いったん最後のロック
アンロック操作が始まったら，二度とロック操作を行わない．
最初のアンロック– 直列可能性（隔離性）を保証できることが理論的に証明されている．
– しかし，デッドロックに陥る可能性がある．
• やりかけた仕事を最後まで実行できない可能性がある，ということ．
時間29

ロック確保数隔離性に関するより厳密な定義
隔離性に関するより厳密な定義

上記はあくまでも一例．ロック・アンロックの形態が異なる方法や，ロック・アンロックを全く用いない方法などもあるが，それらの詳細はデータベースの講義に譲る．

30

トランザクション処理と並列・分散処理（１）
トランザクション処理と並列・分散処理（１）

トランザクション処理と並列・分散処理（２）トランザクション処理と並列・分散処理（２）z トランザクション処理– DBMSに格納されたデータが大規模であれば，その処理負荷は非常に重い．
– 非常にたくさんのトランザクションがあるときにも，全体の処理負荷が重くなる．
– あるトランザクションが必要とするデータが広域に分散しているかもしれない．
z 複数のトランザクションを単一のプロセスで処理すると（データベース管理システムが単一プロセスで逐次動作すると）– 複数の演算ノードがあっても並列処理・分散処理が行えず，処理効率が上がらない．
– 必要なデータが分散してる状態では処理ができない．

z DBMS自体を，複数の演算ノード上で複数のプロセスまたはスレッドとして処理する．
– トランザクションに含まれる複数の操作を，並行ではなく並列に実行できるようになる．
– しかし，先に述べた隔離性の条件を満たすための制御は，より複雑になる．
• 処理を実行する主体が複数あるため，直列に実行したときと同じ結果になるように保証するのは大変．

31

32コンピュータシステムII（１０）82005/12/13

原子性を満たすために（１）原子性を満たすために（１）原子性を満たすために（２）原子性を満たすために（２）z 隔離性を満たすような並行処理制御が行われている場合でも，トランザクションの処理が最後まで完遂できないことがある．
– デッドロックに陥った場合– （例えば残高不足などの理由で）それ以降の処理が許可されない場合– DBMSに障害があって，トランザクション処理全体が停止してしまうような場合
z トランザクションは，途中まで処理が終わった状態で放置されてはいけない．
– 最後までやり遂げるか– 実行されていない状態（最初の状態）からやり直すか

z いくつものデータ項目にアクセスするトランザクションがデータベースへの書き込みをその都度行っていると...

33

34– 途中で止まったときに，すでに書き込まれた結果を元に戻すのは大変．
z そこで，通常は，以下のような方法が採られる．
– トランザクション実行中の書き込みは，当該データ項目の作業用コピーに対して行う．元のデータベースにはただちに反映させない．
– トランザクションが正常終了できるとわかったときに，初めて，すべての書き込み結果を，元のデータベースに反映させる⇒コミット（commit）操作– トランザクションが正常に終了できないとわかったときは，当該トランザクションを強制終了し，作業用コピーを捨てる．
（実行前の状態に戻ることができる）⇒アボート（abort）操作

分散DBにおけるコミット操作の問題点
分散DBにおけるコミット操作の問題点

二相コミット（Two-Phase
二相コミット（Two-Phase Commit）プロトコルの原理
Commit）プロトコルの原理

z DBMSが広域分散システム上で動作しているような場合– 単一の「管理プロセス」がシステム全体の状態を把握・管理するのは非常に困難• コミットしてもよいのか，アボートすべきなのかの判断を単一のプロセスで行うのが大変．
• 分散システムの性質上，コミット操作（DBへの最終書き込み）そのものを管理プロセスが行うことはできない．
– 各演算ノードでコミット操作が正常終了することを保証するのは非常に困難• 通信路に障害が起きて，通信が届かない可能性がある．
• 演算ノードがシステム障害で動かなくなることすらあり得る．
• こちらの問題を完全に解決することは不可能．

z 仮定– 各演算ノードごとに，そこのデータを管理する「リソースマネージャ」が１つ存在する．
– 個々のデータ項目の監視まではできないがリソースマネージャの「投票」の結果を管理できる「コーディネータ」が，システム全体で１つ存在する．
z １つの分散トランザクションの作業用コピーの上での処理が終了した後のコミット操作を，次の２つの段階に分割する．
– 第一段階• 各演算ノードでコミットの準備ができたかどうかを確認する．
– 第二段階• 各演算ノードのリソースマネージャからの「投票」を受けて，コミット／アボートの判断を行い，各ノードでコミットを行う．

35

36

コンピュータシステムII（１０）「二相コミット」は，コミット操作そのものが２つの段階に分かれているためにそう呼ばれているのであり，トランザクションがコミット操作の前と後に分かれているためと考えるのは誤りである．

92005/12/13

二相コミットプロトコルの詳細（１）
二相コミットプロトコルの詳細（１）

二相コミットプロトコルの詳細（２）二相コミットプロトコルの詳細（２）z 第一段階（Phase 1）

z 第二段階（Phase 2）– コーディネータは，すべてのリソースマネージャから「準備完了」のメッセージを受け取ったら，コミットすることを決定する．
どれかひとつでも「拒否」が混ざっているか，あるいは，あまりに時間がかかり過ぎて「あきらめた」（＝時間切れになった）場合には，アボートすることを決定する．
– コーディネータは，各リソースマネージャに，コミット／アボートの決定を送信する．
– 各リソースマネージャは，実際のコミット操作に必要な書き込
み処理またはアボートに必要な処理を行い，終了すれば「完了（OK）」を返答する．
– コーディネータは，すべてのリソースマネージャから「完了」を受け取ると，初めて，分散トランザクションが正常に終了したか，「なかったことにできた」ことを確信できる．

– コーディネータは，各リソースマネージャに「準備要求（PREPARE）」メッセージを送信– 各リソースマネージャは，以下の処理を行う• コミットの準備ができたら，「準備完了（READY）」を投票する．コミットできないときには，「拒否（REFUSE）」を投票する．
• （処理がまだ終了していない演算ノードは）投票はいくらでも遅らせることができる．
– （もちろん，一定の制限時間をおいて，「時間切れ」と判定することはあり得る．）

37ある分散トランザクションTの『一生』（１）
ある分散トランザクションTの『一生』（１）コーディネータ
Tの開始

プロセス１

ある分散トランザクションTの『一生』（２）
ある分散トランザクションTの『一生』（２）コーディネータ

プロセス2

BEGIN

38

Tの開始

BEGIN

プロセス１

プロセス2

BEGIN

BEGIN

まだ，DBには書き込んでいないTのための処理

まだ，DBには書き込んでいない

Tのための処理

Tのための処理

Tのための処理

コミットの開始
PREPARE

READY

コミットの開始
PREPAREPREPAREREADYCOMMIT

OK

第一段階

READY

ABORT

COMMIT
OK

第二段階

実際にDBに書き込む

OK
39

コンピュータシステムII（１０）

PREPARE
REFUSE

第一段階

ABORT
OK

第二段階

作業用コピーを捨てる40102005/12/13

まとめ
まとめz デッドロック– デッドロックの必要条件– デッドロックの抑止・回避，デッドロックからの回復– デッドロックの検出
z トランザクション処理– データベースに対する操作を，意味のあるまとまり（トランザクション）として処理すること．
– 並行に処理しても，並列に処理してもよい．
– ただし，ACID特性を保証しなければならない．
z 並行処理制御– ACID特性のうちのI（隔離性）を保証するための制御– 一例として，二相ロックがある．
z コミット– ACID特性のうちのA（原子性）を保証するための制御– 並列・分散でなくても，よく用いられる．
z 二相コミット– 分散システムにおいてトランザクションの原子性を保証するためのプロトコル• 二相ロックと混同しないように注意すること！

41

コンピュータシステムII（１０）11