TransactionalInformation Systems まとめ 第四章　（４）

　　　　　③Rules for locking

・well-formed locking

分類

概要

定義

意味

LR1

lockとunlockのタイミング

If ti contains a step of the form ri (x) [wi (x)], then schedule s also contains a step of the form rli (x) [wli (x)] before the data operation (i.e., a lock on x is held at the point of the operation on x). Moreover, s contains a step of the form rui (x) [wui (x)] somewhere after the operation.

operationに対して、lockは先に、unlockはあとに

LR2

lockの回数

For each x accessed by ti , schedule s has at most one rli (x) and at most one wli (x) step; in other words, locks of the same type are set at most once per transaction and per data item.

１つのitemに対して、lockは「１トランザクション中に１回のみ」。readとwrite、それぞれ。

LR3

unlockの回数

No step of the form rui (.) or wui (.) is redundant (i.e., executed per transaction more than once).

１つのitemに対して、lockは「１トランザクション中に１回のみ」。readとwrite、まとめて。

LR4

lockとconflict

if x is held locked by both ti and t j for ti, tj ∈ trans(s), i = j ,

then these locks are not in conflict (i.e., they are compatible).

１つのitemに対して、複数のトランザクションでlockしていた場合、conflictしていない。



・well-formed locking

分類

概要

定義

意味

OS1

lockとopの順序

In a schedule s, for any two operations pi (x) and qj (x), i = j , such that pli (x) →ql j (x) is permitted, if ti acquires pli (x) before
t j acquires ql j (x), then the execution of pi (x) must occur before the execution of qj (x).

複数のトランザクションで同じitemへのoperationが発生した場合、lockの順序とoperationの順序が一致すること。

OS2

lockの保持期間

While a transaction is on hold, it cannot release any of its locks.

※on holdとは

So for a correct protocol, we need a rule for unlocking. If we have a relationship pli (x) →ql j (x) of ordered sharing between two transactions ti and t j ,and ti has not yet released any lock, t j is called order dependent on ti . If ther eexists any such ti , transaction t j is on hold.

先行してlockを取得したトランザクションのunlock待ち（on hold）の間は、自トランザクションもunlockを実行しない。

※on holdの間は、先行したトランザクションが「許容不可となるoperationを実行する（＝not CSRになる）」かもしれない。このため、on hold側のトランザクションも待つ必要がある。

 

 

 

・Altruistic locking

ALは新たなoperationとして「donate」を導入する。unlockをしなくても、他のトランザクションがitemにlockとoperationを実行できるようにする。

「donate」は「lockの使用権限を与える」ことを表す。conflictしているトランザクションにlockの権利を渡すことで、並行実効性を高めるもの。

AL uses a third access control operation, besides lock and unlock, which is called donate. The donate operation is used to inform the scheduler that access to a data item is no longer required by the transaction that has currently locked the item, so that the item can be “donated” for access to another transaction. The donating transaction is free to acquire other locks in the future, so that lock and donate operations do not need to follow a twophase rule; but other than that, the transaction still has to be two-phase with respect to unlock operations.

 

in the wake と indebted

in the wakeはdonateされたitemをlockしていた、先行トランザクションがunlockしていない状態。

indebtedはin the wakeにあるoperationがconflictしていること。直接的か、間接的（他のトランザクションのoperationを介して）か。

★【要確認】in the wakeは「read - read」のケースも含んでいると思われる　→　なので、indebtedを別に設けて区別していると思われる。

intuitively, if transaction t j locks a data item that has been donated and not yet unlocked by transaction ti , i ≠= j , we say that t j isin the wake of ti . More formally, we have the following:

  1. An operation pj (x) from transaction t j is in the wake of transaction ti , i ≠j , in the context of a schedule s if di (x) ∈ op(s) and di (x) <s pj (x) <s oui (x) for some operation oi (x) from ti .

  2. A transaction t j is in the wake of transaction ti if some operation from t j is in the wake of ti . Transaction t j is completely in the wake of ti if all of its operations are in the wake of ti .

  3. A transaction t j is indebted to transaction ti in a schedule s if oi (x), di (x), pj (x) ∈ op(s) such that pj (x) is in the wake of ti and either oi (x) and pj (x) are in conflict or some intervening operation qk(x) such that di (x) <s qk(x) <s pj (x) is in conflict with both oi (x) and pj (x).

 

分類

概要

定義

意味

AL1

donateとopの関係

Items cannot be read or written by ti once it has donated them; that is, if di (x) and oi (x) occur in a schedule s, o ∈ {r, w}, then oi (x) <s di (x).

donateはoperationの後に実行する

AL2

donateとunlockの関係

Donated items are eventually unlocked; that is, if di (x) occurs in a schedule s following an operation oi (x), then oui (x) is also in s and di (x) <s oui (x).

donateはunlockの前に実行する。
※unlockが先にできるのなら、donateはいらない。

AL3

別トランザクションによるlock

Transactions cannot hold conflicting locks simultaneously, unless one has donated the data item in question; that is, if oi (x) and pj (x), i ≠j , are conflicting operations in a schedule s and oi (x) <s pj (x), then either oui (x) <s pl j (x), or di (x) is also in s and di (x) <s pl j (x).

トランザクション間でconflictするoperationが実行されるのは、以下のいずれかとなる。

　①先行するoperationがunlockされた

　②先行するoperationがdonateされた

AL4:

トランザクション間のop順序

When a transaction t j is indebted to another transaction ti , t j must remain completely in the wake of ti until ti begins to unlock items.

That is, for every operation pj (x) occurring in a schedule s, either

pj (x) is in the wake of ti or there exists an unlock operation oui ( y) in s such that oui ( y) <s o j (x).

トランザクションがindebted（in the wakeかつconflict）であるとき、indebtedなトランザクションのopはすべて以下のいずれかとなる。

　①in the wake

　②実行済のoperationに対して、すべてunlockされている