“等待-死亡”和“撞击-等待”死锁预防算法有什么区别？

Question

“等待-死亡”和“撞击-等待”死锁预防算法有什么区别？

databasedeadlockdatabase-deadlocks

59

等待-死亡算法和伤害-等待算法有何区别？

这两种死锁预防技术似乎在做同样的事情：回滚旧进程。

它们之间的区别是什么？

请提供一个适当的示例来对比这两个算法。

- Nadeem Bhati

7个回答

22

Parth已经给出了详细的答案。这里我用不同的方式进行总结。

假设T_n请求由T_k持有的锁。以下表格总结了等待死和伤害等待方案的操作：

                           wait-die         wound-wait
Tn is younger than Tk      Tn dies          Tn waits
Tn is older than Tk        Tn waits         Tk aborts

这两种方案都更喜欢时间戳较早的旧交易。

- Jingguo Yao

1

很棒的回答，但是 die 和 abort/rollback 是一样的吗？ - P_95

3

是的，die和abort/rollback是相同的意思。 - Jingguo Yao

如果Tn比Tk年轻并且处于“伤口等待”状态，那么它不应该是Tn在等待吗？@JingguoYao - hakiki_makato

@hakiki_makato 是的，你说得对。我已经修正了打字错误。 - Jingguo Yao

10

wait-die: 当一个年长的事务试图锁定被年轻的事务锁定的数据库元素时，它会等待。当一个年轻的事务试图锁定被年长的事务锁定的数据库元素时，它会终止。

wound-wait: 当一个年长的事务试图锁定被年轻的事务锁定的数据库元素时，它会伤害年轻的事务。当一个年轻的事务试图锁定被年长的事务锁定的数据库元素时，它会等待。

参考资料：

- Jason Law

3

通过比较两个相关主题可以更好地理解它们，因此，等待死亡（wait-die）和伤口等待（wound-wait）之间的相似之处包括：

旧事务将“赢得”比新事务更高的优先级。
当事务重新启动时，它们会保留它们的时间戳。
最终，已中止（更年轻的）事务将成为系统中最老的事务。

等待死亡（wait-die）和伤口等待（wound-wait）之间的差异包括：

在wait-die中，当新事务请求由旧事务持有的锁时，新事务被杀死。
在wound-wait中，当旧事务请求由新事务持有的锁时，新事务被杀死。

- techPirate99

2

当两个交易同时请求锁时，就会像上图一样形成死锁。年轻的事务向老的事务请求锁，而老的事务向年轻的事务请求锁。
这两种技术仅防止其中一条边被形成，而允许另一条边，从而预防循环形成。
如果你注意到，在这两个策略中，年轻的事务都会被中止。只有锁请求的发起者不同。中止的事务会在以后重新开始。

- Pranaya Tomar

图形解释得非常好，谢谢。 - Splines

2

我会稍微调整@JingguoYao的总结，因为对我（和其他人）来说，这样阅读起来更容易。

假设T_n请求由T_k持有的锁。以下表格总结了等待死锁和伤害等待方案所采取的行动：

                Tn is older than Tk     Tn is younger than Tk
wait-die        Tn waits                Tn dies
wound-wait      Tk aborts               Tn waits

两种方案都更喜欢时间戳较旧的旧交易。

- 18446744073709551615

对于“Tn比Tk年轻”的情况下的伤口等待条件，应该是Tk等待而不是_Tn等待_。 - satvik.t

@satvik.t 不，当“Tn比Tk年轻”处于“伤口等待”状态时，Tn必须等待，它的写法是正确的。与被接受的答案进行比较。请注意，所有动词（“等待，死亡，伤口”）都是指Tn而不是Tk。（“Tn伤害Tk”在这里只是重述为“Tk中止”，这在语义上是相同的）。 - Splines

1

在这两种情况下，“老”总是获胜的，即将生存。区别在于从年轻人的交易角度看。如果年轻人请求由老事物持有的资源，在“等待/死亡”中，他可以等待并尊重老事务。如果年轻人请求由老事务持有的资源，在“受伤/死亡”中，他将被迫回滚为旧事务。在这两种方案中，“老”永远不会受到损失。

Refer:https://www.tutorialspoint.com/dbms/dbms_deadlock.htm

- Vijnana Yogi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Parth Patel · Accepted Answer

等待-抢占策略

这是一种用于死锁预防的非抢占技术。当事务T_n请求一个当前由T_k持有的数据项时，只有当T_n的时间戳小于T_k的时间戳（即T_n比T_k旧）时， T_n才能等待，否则将杀死（"die"）T_n。

在这个方案中，如果一个事务请求锁定已被另一个事务以冲突锁定方式持有的资源（数据项），那么可能会发生以下两种情况之一：

Timestamp(T_n) < Timestamp(T_k) - 即T_n请求冲突锁定但比T_k旧 - 那么T_n就可以 "等待" 直到数据项可用。
Timestamp(T_n) > Timestamp(T_k) - 即T_n比T_k年轻 - 那么T_n将被杀死（"dies"）。 T_n稍后会以随机延迟但具有相同时间戳（n）重新启动。

这个方案允许旧的事务 "等待" ，但是杀死年轻的事务 ("die")。

例子

假设事务T₅，T₁₀和T₁₅的时间戳分别为5、10和15。

如果T₅请求一个由T₁₀持有的数据项，则T₅将 "等待"。

如果T₁₅请求一个由T₁₀持有的数据项，则T₁₅将被杀死（"die"）。

伤害-等待策略

这是一种用于死锁预防的抢占技术。这是等待-抢占策略的对应方案。当事务T_n请求一个当前由T_k持有的数据项时，只有当T_n的时间戳大于T_k的时间戳时，T_n才能等待，否则将杀死T_k（即T_n会伤害T_k）。

在这个方案中，如果一个事务请求锁定已被另一个事务以冲突锁定方式持有的资源（数据项），那么可能会发生以下两种情况之一：

时间戳(T_n) < 时间戳(T_k)，那么T_n会强制结束T_k，也就是说T_n会“创伤”T_k。T_k稍后会以同样的时间戳(k)但随机延迟重新启动。
时间戳(T_n) > 时间戳(T_k)，那么T_n会被强制“等待”，直到资源可用。

这个方案允许较年轻的事务在较老的事务持有锁时“等待”，但如果较老的事务请求一个已经由较年轻的事务持有的项的锁，它将强制挂起“创伤”较年轻的事务。

示例

假设事务T₅、T₁₀和T₁₅分别具有时间戳5、10和15。

如果T₅请求由T₁₀持有的数据项，则数据项将从T₁₀中抢占，并暂停T₁₀。（“创伤”）

如果T₁₅请求由T₁₀持有的数据项，则T₁₅将“等待”。

总结

在这两种情况下，只有以较“晚”的时间戳进入系统的事务（即较年轻的事务）才可能被强制结束并重新启动。