TransactionalInformation Systems まとめ 第四章 （６）

　　　　　④Deadlock Handling

デッドロックは、ふたつのシチュエーションから発生しうる。

　　・複数のitemに対して、複数のトランザクションが「相互に入り繰った順序」でロックした場合

　・複数のitemに対して、複数のトランザクションが「lock conversion」を伴ってロックした場合

　　（t1がr(x)を実行し、t2もr((x)を実行する。これはOK。このあとにt1がw(x)を実行し、t2もw((x)を実行する。

　　　このとき、どちらもlock conversionが発生し、お互いに相手のread lockの解除を待ち合う）。

dead lock detectionは複数の手法がある。おおまかにはperiodicかcontinuous。

分類	概要	名称	定義	方式
victim selection	1	Last blocked	Pick the transaction that blocked most recently, that is, the one that just blocked in the case of continuous detection.
	2	Random	From those involved in a deadlock cycle, pick one transaction randomly.
	3	Youngest:	Pick the transaction with the most recent start-up time, that is, the one that began running most recently.
	4	Minimum locks:	Pick the transaction that holds the fewest locks.
	5	Minimum work:	Pick the transaction that has consumed the least amount of resources (e.g., CPU time) so far.
	6	Most cycles:	Pick the transaction that breaks the largest number of cycles
	7	Most edges:	Pick the transaction that eliminates as many edges as possible.
prevention	1	Wait-die:	If a lock request from transaction ti leads to a conflict with t j , resolve as follows: if ti started before t j , it is blocked (ti “waits for”t j ); otherwise, it is restarted (ti “dies”). In other words, a transaction can only be blocked by a younger transaction.
	2	Wound-wait:	If a lock request from transaction ti leads to a conflict with another transaction t j , resolve as follows: if ti started before t j , then t jis restarted (ti “wounds” t j ); otherwise, ti is blocked (ti “waits for” t j ). Thus, a transaction can only be blocked by an older transaction, and a transaction can kill any younger one it conflicts with.
	3	Immediate restart:	If a lock request from ti leads to a conflict with another transaction t j , simply restart ti . Thus, no transaction is ever blocked.
	4	Running priority:	If a lock request from ti results in a conflict with t j , resolve as follows: if t j is currently waiting due to another conflict, then restart t j and grant ti ’s lock request; otherwise, block ti . Thus, blocked transactions are not allowed to impede the progress of active ones.
timeout		timeout strategy:	For each transaction t the scheduler maintains a timer that is activated as soon as a step of t is blocked. If the timer times out, t is aborted　under the assumption that it has been involved in a deadlock. Clearly, this decision may be wrong, so the choice of the time period for which the timer runs is crucial. Again observe that an aborted transaction has not necessarily been involved in a deadlock.

（４） Hybrid Protocols

①conflictベース

concurrency controlはふたつの問題にわけることができる。

1. rw (and wr) synchronization: read operations are synchronized against write operations, or vice versa;

2. ww synchronization: write operations are synchronized against otherwrite operations, but not against reads.

このふたつの問題への対処それぞれを組合せることを、Hybrid protocolと呼ぶ。

If these synchronization tasks are distinguished, a scheduler can be thought of as consisting of two components, one for each of the respective synchronization tasks.

Since the two components need proper integration (as demonstrated by way of examples shortly), such a scheduler is called ahybrid scheduler.

それぞれについて、以下のように定める。

For rw (and wr) synchronization: two operations are in conflict if theyaccess the same data item, and one is an r step, the other a w step.

For ww synchronization: two operations are in conflict if they access the same data item, and both are write operations.

例	rw synchronization へのprotocol	ww synchronization へのprotocol	補足
１	2PL	SGT
２	SS2PL	TO
３	SS2PL	Thomas’ Write Rule (TWR)	Let t j be the Thomas’ Write transaction that has written x and that has the largest timestamp prior to the Rule (TWR) arrival of wi (x). If ts(ti ) > ts(t j ), then wi (x) is processed as usual; otherwise, it is ignored, and the execution of ti continues. Notice that TWR applies to pairs of write steps only.

②partitionベース

データの分類によって適用するprotocolを分けることもできる。

D, into disjoint subsets D1, D2, . . . , Dn (with n≥ 2, Di ∩ Dj = ∅ for i = j , and Ui=1 to nDi = D).

③specific access characteristicsベース

データのアクセス内容や頻度に応じて分けることもできる。

For example, a data server may manage a small set of very frequently modified data items—so-called hot spots—that constitute subset D1, a large set of less frequently modified data items that form subset D2, and a remaining subset D3 of data items that are never updated online.

例	D1	D2	補足
１	SGT	FOCC	However, we need to ensure that this combination preserves the acyclicity of the global conflict graph that is formed by the union of the two conflict graphs for D1 and D2. This is all but trivial for the two considered protocols, and may in fact require some additional cycle testing across both partitions. Such global overhead may, however, render the use of the “lightweight” FOCC protocol pointless, as the overhead of cycle testing would eventually be incurred for all of D1 ∪ D2.
2	SS2PL	FOCC	In this case, the fact that both protocols are commit order preserving conflict serializable (COCSR) eliminates the need for global checks.