LEC 10-12

Conflict

>> 当两条指令是不同事务在相同数据项上的操作，并且其中至少有一个是write指令时，则称这两条指令是冲突的（不用想其他的东西，单纯满足这三个条件就可以了）例：

①Ii = read(Q), Ij = read(Q);

②Ii = read(Q), Ij = write(Q);

③Ii = write(Q), Ij = read(Q);

④Ii = write(Q), Ij = write(Q);

比如这四个操作中 ②、③、④就是li和lj冲突的

Precedence Graph

>> 是一个有向图（directed graph）G = （V，E），V是顶点集，E是边集

当满足以下任意一个条件时，T1指向T2:

①在T2执行read(Q)之前，T1执行write(Q)

②在T2执行write(Q)之前，T1执行read(Q)

③在T2执行write(Q)之前，T1执行write(Q)

（其实为了好记的话，除了“rr”，其他的只要后面字母一样都可以当作边的条件）

Testing Conflict-Serializability 判断是否有冲突可串行性

>> 有如上图的“圈”的话就不是conflict-serializability，没有圈就是conflict-serializability，唯一判断标准

Enforcing Conflict-Serializability Using Locks 使用locks强制...

>> Operations

$l_{i}$ (x) : lock

$u_{i}$ (x) : unlock

>> Rules

1. 每一个r(x)/ w(x)前面都要有一个li(x)，并且li(x)和ui(x)不能挨着

2. li(x)在 lj(x)前面那么 ui(x) 就要在uj(x)前面

Two-Phase Locking (2PL) :

>> Simple modification of the simple locking mechanism that guarantees conflict-serializability

>> 2PL分为phase 1和phase 2， phase 1 是从第一个lock到第一个unlock之前，phase 2 是从第一个unlock到最后。如果phase 2 里还有lock，那么这就不是一个2PL

>> If S is a schedule containing only 2PL transactions, then S is conflict-serializable

>> 2PL可能会引起一些问题，例如死锁 : deadlocks whick leads to wait forever

>> How can we make 2PL more flexible? By using different lock modes

1. Share lock Operation : s-lock(X) Shorthand notation : sli(X)

>> 可能会造成死锁例如：

T1：

begin Transaction t1

select * from table with (holdlock) （holdlock的意思是加共享锁，直到事务结束（提交或回滚）才会释放）

update table set column1=‘hello’

T2：

begin Transaction t2

select * from table with (holdlock)

update table set column1=‘world’
假设T1和T2同时到达select语句，都为table加上了共享锁（hold lock），那么当T1、T2要执行update时，根据锁机制，共享锁需要升级为排他锁，但是排他锁与共享锁不能共存，要给table加排他锁，必须等待table上的共享锁全部释放才可以，可是holdlock的共享锁必须等待事务结束才能释放，因此T1和T2都在等待对方释放共享锁，形成循环等待，造成死锁

2. Exclusive lock Operation : x-lock(X) Shorthand notation : xli(X)

3. Update lock Operation : u-lock(X) uli(X)

作用和s-lock()是类似的，但更新锁与共享锁兼容（shared lock和exclusive lock不兼容)，所以更新锁可以防止里那种一般情况的死锁发生，update lock不必等共享锁全部释放成才能变成exclusive lock，可以直接变成

更新锁会阻塞其他的更新锁和排他锁，因此更新锁和更新锁是不兼容的

New upgrading policy :

4. Intention lock : If a transaction wants to lock an item X, it must first put an intention lock on the super-items of X （就是在在lock item X前，需要先有一个intention lock）

Intention shared : IS Intention to request a shared lock on a sub-item

Intention exclusive : IX Intention to request an exclusive lock on a sub-item

>> Policy for Granting Locks