Livelocks and deadlocks of concurrency control

Blocking technology can effectively solve the consistency problem of parallel operation , But it also brings some new problems
Deadlock
Live lock

Live lock

Business T1 Blocked data R
Business T2 And ask for a blockade R, therefore T2 wait for .
T3 And ask for a blockade R, When T1 The release of the R After the blockade on, the system first approved T3 Request ,T2 Still waiting .
T4 And ask for a blockade R, When T3 The release of the R After the blockade, the system approved T4 Request ……
T2 It's possible to wait forever , This is the case with live locks

Avoid live locks ： Adopt a first come, first serve strategy

When multiple transaction requests block the same data object
These transactions are queued in the order in which they are requested to be blocked
Once the lock on the data object is released , First approve the first transaction in the application queue to obtain the lock

Deadlock

Business T1 Blocked data R1
T2 Blocked data R2
T1 And ask for a blockade R2, because T2 It's blocked R2, therefore T1 wait for T2 Release R2 The lock on the
next T2 And apply for a blockade R1, because T1 It's blocked R1,T2 Can only wait T1 Release R1 The lock on the
such T1 Waiting for the T2, and T2 Waiting again T1,T1 and T2 Two things can never end , Formation of a deadlock

The solution to deadlock

Two kinds of methods
1. Deadlock prevention
2. Deadlock diagnosis and release

Deadlock prevention

The cause of deadlock is that two or more transactions have blocked some data objects , Then they all request to lock the data objects that have been blocked for other transactions , So there's a dead wait .
Preventing deadlock is to destroy the condition of deadlock

Ways to prevent deadlocks

（1） One time blockade
Each transaction is required to lock all data to be used at one time , Otherwise, we can't carry on
The problem is
Reduce system concurrency
It is difficult to accurately determine the blocking object in advance
The data in the database is constantly changing , Data that was not required to be blocked , It may become a blocking object during execution , So it's hard to determine exactly what data objects each firm is blocking in advance .
resolvent ： Lock all data objects that may be blocked in the process of transaction execution , This further reduces concurrency .
（2） Sequential blockade
Sequential blocking method is to specify a blocking order for data objects in advance , Everything is blocked in this order .
Problems of sequential blockade method
Maintenance cost
There are many blocked data objects in database system , And with the insertion of data 、 Delete, etc. and change constantly , It's very difficult to maintain the blocking order of such resources , Cost is very high .
Difficult to achieve
The blocking request of a transaction can be determined dynamically with the execution of the transaction , It's hard to determine which objects are blocked by each transaction first , So it's very difficult to impose blockades in the prescribed order

Conclusion

The deadlock prevention strategy widely used in the operating system is not suitable for the characteristics of the database
The method of diagnosing and releasing deadlock is more commonly used in database management system to solve the problem of deadlock

Deadlock diagnosis and release

Deadlock diagnosis
（1） Overtime method
If the waiting time of a transaction exceeds the specified time limit , Think of a deadlock
advantage ： Implement a simple
shortcoming
It is possible to misjudge the deadlock
If the time limit is set too long , It can't be found in time after deadlock
（2） Waiting graph
The transaction waiting graph is used to dynamically reflect the waiting situation of all transactions
The transaction waiting graph is a directed graph G=(T,U)
T For the set of nodes , Each node represents a running transaction
U A collection of sides , Each side represents the transaction waiting
if T1 wait for T2, be T1,T2 Draw a directed edge between , from T1 Point to T2

chart (a) in , Business T1 wait for T2,T2 wait for T1, There's a deadlock
chart (b) in , Business T1 wait for T2,T2 wait for T3,T3 wait for T4,T4 Waiting again T1, There's a deadlock
chart (b) in , Business T3 May still be waiting T2, There are small circuits in the large circuits
The concurrency control subsystem periodically （ For example, every few seconds ） Generate transaction wait graph , Detect transactions . If a circuit is found in the diagram , It means there is a deadlock in the system .
Deadlock Relieving
Choose a transaction with the least deadlock cost , Undo it
Release all locks held by this transaction , Enable other transactions to continue
Welcome to join me for wechat exchange and discussion （ Please note csdn Add ）