Strict two-phase locking
In computer science, strict two-phase locking (Strict 2PL) is a locking method used in concurrent systems.
The two rules of Strict 2PL are:
- If a transaction T wants to read/write an object, it must request a shared/exclusive lock on the object.
- All exclusive locks held by transaction T are released when T commits (and not before).
Here is an example of Strict 2PL in action with interleaved actions.
- <math>
D = \begin{bmatrix}
T1 & T2 \\
S(A) & \\
R(A) & \\
& S(A) \\
& R(A) \\
& X(B) \\
& R(B) \\
& W(B) \\
& Commit \\
X(C) & \\
R(C) & \\
W(C) & \\
Commit &
\end{bmatrix}
</math>
or in text form:
T1: S(A), R(A); T2: S(A), R(A), X(B), R(B), W(B), Commit; T1: X(C), R(C), W(C), Commit
where
- S(O) is a shared lock action on an object O
- X(O) is an exclusive lock action on an object O
- R(O) is a read action on an object O
- W(O) is a write action on an object O
Strict 2PL prevents transactions reading uncommitted data, overwriting uncommitted data, and unrepeatable reads. Thus, it prevents cascading rollbacks, since eXclusive locks (for write privileges) must be held until a transaction commits.
Strict 2PL does not guarantee a deadlock-free schedule
Avoiding deadlocks can be important in real time systems, and may additionally be difficult to enforce in distributed data bases, or fault tolerant systems with multiple redundancy.
A deadlocked schedule allowed under Strict 2PL:
- <math>G = \begin{bmatrix}
T1 & T2\\
X(A) & \\
& X(B) & \\
X(B) & \\
& X(A) \end{bmatrix}</math>
Text:
T1: X(A) T2:X(B) T1:X(B) T2: X(A)
T1 is waiting for T2’s lock on B to be released, while T2 is waiting for T1’s lock on A to be released. These transactions cannot proceed and both are deadlocked.
There is no general solution to the problem of deadlocks in computing systems, so they must be anticipated and dealt with accordingly. Nonetheless, several solutions such as the Banker’s algorithm or the imposition of a partial ordering on lock acquisition exist for avoiding deadlocks under certain conditions.
Even more strict than strict two-phase locking is rigorous two-phase locking, in which transactions can be serialized by the order in which they commit. Under rigorous 2PL, all locks (shared and exclusive) must be held until a transaction commits. Most database systems use strict 2PL.