死锁的预防检测

数据库中处理死锁（Deadlock）问题的方法主要有两种：预防（Prevention）和检测（Detection）。

1. 死锁检测 (Deadlock Detection):

   • 这种方法是通过构建一个“等待图”（Wait-For graph）来发现死锁。
   • 等待图是利用锁定表结构构建的。
   • 它可以增量地或周期性地构建。
   • 当在等待图中发现环路时，就会选择一个“受害者”（victim）事务并回滚它，以打破死锁。

2. 死锁预防 (Deadlock Prevention):

   • 这种方法旨在阻止死锁的发生。教材中提到了几种预防策略：
     • 资源排序 (Resource Ordering)：对所有数据元素（资源）进行排序（例如 A1, A2, …, An）。一个事务 T 只有在其请求锁定资源 Ai 时，当前持有的所有资源的索引都小于 i 时，才能获得锁定。 然而，教材指出在大多数情况下，事务按顺序请求资源是不现实的。
     • 超时 (Timeout)：如果一个事务等待某个资源的时间超过预设的阈值（L 秒），系统就会回滚这个事务。 这是一种简单的方法，但很难确定一个合适的等待时间 L。
     • 等待 - 死亡 (Wait-die)：为事务分配时间戳（timestamp）。事务 Ti 只有在请求锁定被事务 Tj 持有时，当且仅当 Ti 的时间戳小于 Tj 的时间戳时，Ti 才能等待 Tj。 否则，Ti 必须“死亡”，即被回滚。 教材讨论了如何通过使用事务的原始时间戳重新提交来避免饥饿（starvation）问题。
     • 受伤 - 等待 (Wound-wait)：也为事务分配时间戳。事务 Ti 在请求锁定被事务 Tj 持有时，如果 Ti 的时间戳小于 Tj 的时间戳，则 Ti 会“伤害”（wound）Tj。 这里的“伤害”意味着 Tj 会被回滚，并将锁定释放给 Ti。 否则，Ti 会等待 Tj。