活锁和死锁

饥饿

由于不同锁的类型导致的。有希望获得排他锁，但由于不断获得共享锁，可能永远等待。

解决方法：事务T申请对数据项R加M型锁，允许加锁的条件

1. 在R上不存在与M冲突的锁的其他事务

2. 不存在等待对R加锁，且先于T申请加锁的事务（按先后来）

死锁和活锁

活锁有希望获得锁，但是由于调度顺序的选择，可能永远等待，解决方法：先来先服务

死锁的诊断

DBMS常用方法，有超时法和事务等待图法

• 超时法：如果一个事务等待的时间超过了规定的时间，就认为发生了死锁

  缺点：可能误诊，规定时间不好设 优点：简单

• 等待图法：有向图G=(T, U)。节点表示正在执行的事务，边表示等待情况。T1→T2表示T1等待T2。

  死锁诊断：如果图中存在回路，系统中发生死锁

死锁的预防

一次封锁法：要求事务必须一次将所有要使用的数据全部加锁，否则不能执行。例如，一次性对R1和R2进行加锁。

缺点：

• 扩大封锁范围就会降低并发度

• 当事务需要访问大量数据项时，该事务就会永久等待，因为需要少量数据项的事务会优先执行，这个事务会很久拿不到锁

顺序封锁法：预先对数据对象规定一个封锁顺序，所有事务都会按这个顺序实行封锁，例如：B树上的逐级封锁

缺点：

• 封锁的数据对象多，插入、删除频繁，会导致很难保序，代价大

• 动态封锁请求，使得难以预料要封锁哪些对象（没法先规划一个加锁顺序出来），进一步导致很难保序

基于时间戳的抢占与事务撤销技术（有效的方法）

等待-死亡（wait-die）机制，基于非抢占技术

1. 越老的（时间戳小的）事务要等待大时间戳的事务释放锁，等待越长

2. Tk在获得lock R之前可能重启、死亡并rollback多次

受伤-等待（wound-wait）机制，基于抢占技术

1. 越老的（时间戳小的）事务从不等待具有大时间戳的事务；

2. Tj重启并rollback，重新申请锁。

总的来说，

• 等待-死亡机制（基于非抢占）

  老登要拿小登的锁，老登得等小登用完；小登要拿老登的锁，小登直接死。

• 受伤-等待机制（基于抢占）

  老登要拿小登的锁，直接抢，然后小登死；小登要拿老登的锁，得等老登用完。

死锁恢复

• 选择一个处理死锁代价最小的事务，将其撤销，释放锁。代价为该事务计算的时间、使用多少数据项、完成事务还需多少数据项、撤销该事务需要牵涉多少其他事务。

• 决定rollback多远：彻底撤销或者rollback到可以解决死锁为止

• 避免饥饿

  避免由于某个事物rollback的代价最小，而总是rollback此事务。常用的方法，在代价因素中包含rollback的次数。