第12回トランザクション処理(2) 同時実行制御 10.2 同時実行制御の必要性 10.3 スケジュールの直列化可能性 10.4 ロック法 (pp.274-297) 10.2 同時実行制御の必要性 • 時間的にオーバラップするトランザクションは上手く制御しないと様々な異常を発生する。 – 遺失更新異常：更新内容が失われる – 不正整合検索異常：一貫性のないデータの検索 – 波及ロールバック異常 – 汚読異常 10.3 スケジュールの直列化可能性 • [1]直列化可能スケジュール • 直列スケジュール – トランザクションの集合を時間的にオーバラップ（並行）せず、ひとつずつ実行する。 – 一貫性を保てるが、非効率。 • 直列化可能スケジュール – トランザクションを並行に実行するが、結果は、ある直列トランザクションと等価なもの。 – 一貫性と効率性を両立できる。 • ビュー等価とは？ 10.3 スケジュールの直列化可能性 • ［４］相反グラフ解析 • ノード：トランザクション • 有効辺：ある項目xを異なるトランザクションで read, writeするとき、有効辺が引かれる • グラフが非巡回（acyclic）なら、直列化可能なスケジュールがある。 10.4 ロック法 • [1]ロック法の目的 – 直列化可能スケジュールを自動的に生成することができる。 • [2]ロッキングプロトコル – トランザクションが項目ｘにロック(鍵)をかける。 – 2重にロックをかけることはできない。 – 直列化可能とは限らない. 10.4 ロック法 • [3]２相ロッキングプロトコル(2PL) – 第１層(成長相、Lock相) – 第２相(縮退相、Unlock相) – 直列化可能スケジュールを保証する。 • [4]デッドロック – トランザクションが互いにロックしあって、処理が進まなくなる。 – そのような状況を監視し、発見したら関係しているトランザクションのいずれかをアボートする。理解チェック(レポート提出不要) 1. 直列化可能スケジュールとは何か？ 2. 相反グラフ解析を説明しなさい。 3. ２層ロックプロトコルを説明しなさい。レポート提出 1. 遺失更新異状となるトランザクションの例(T1,T2) をあげなさい。 2. 直列化可能性のうち「ビュー等価」を説明しなさい。 3. 以下のトランザクションT1とT2について(a)直列スケジュールの例をあげよ。また、非直列スケジュールのうち(b-1)ビュー直列化可能な例と(b-2)ビュー直列化可能でない例を答えよ。 T1: {begin read(x); read(y); x = x-y; write(x) end} T2: {begin read(y); read(x); y = y-x; write(y) end} 4. 2相ロッキングプロトコルを説明しなさい。