Understanding Two-Phase Locking Protocol for Database Transactions
Explore the concepts of ACID properties, two-phase locking protocol, transaction management, and conflict serializability in the context of database systems. Learn why the 2PL protocol works effectively and how it ensures transaction consistency and isolation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSCE-608 Database Systems Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 39: Two-phase locking protocol (2PL)
Tranactions Transaction ACID: Atomicity: either all steps of a transaction happen, or none happen Consistency: a transaction transforms a consistent DB into a consistent DB Isolation: execution of a transaction is isolated from that of other transactions Durability: if a transaction commits, its effects persist. T1 Tn What can affect transaction ACID? Accident system failures may destroy Atomicity and Durability, thus Consistency; Concurrent executions of transactions (which is highly desired) may affect Isolation, thus Consistency. Database
lock table DDL DDL language concurrency database file logging & administrator complier control manager recovery transaction manager index/file buffer manager manager query database execution programmer DML (query) DML engine main language complier memory secondary buffers storage DBMS (disks) Graduate Database
Two phase locking (2PL) (for transactions) Ti: ... li(A) li(B) ui(B) ui(A) ... no unlocks no locks # of locks held by Ti time growing phase shrinking phase In a transaction, all lockings precede all unlockings
2PL enforces conflict-serializability In a transaction, all lockings precede all unlockings Schedule D A B 25 25 T1 T2 l1(A); Read(A); A A+100 Write(A); u1(A); l1(B); Read(B); B B+100; u1(A); Write(B); u1(B); 125 l2(A); Read(A); A A 2; Write(A); u2(A); 250 125 l2(B); Read(B); B B 2; Write(B); u2(B); u2(A); 250 250 250 This execution of Schedule D is: r1(A)w1(A)r1(B)r2(A)w2(A)w1(B)r2(B)w2(B), equivalent to the serial schedule: r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B).
Two actions conflict if they are by two transactions on the same element and at least one of the actions is write Why does 2PL work? Theorem. The execution of a 2PL schedule is equivalent to the serial schedule in which transactions are ordered by the time when they start to unlock.
Two actions conflict if they are by two transactions on the same element and at least one of the actions is write Why does 2PL work? Theorem. The execution of a 2PL schedule is equivalent to the serial schedule in which transactions are ordered by the time when they start to unlock. Proof. Let S be a 2PL schedule in which transaction T1 starts its unlocks the latest. Let a be any action of T1. Suppose that there is an action a by another transactions Tkthat conflicts a and appears after a in the schedule S. Thus, S = a a
Two actions conflict if they are by two transactions on the same element and at least one of the actions is write Why does 2PL work? Theorem. The execution of a 2PL schedule is equivalent to the serial schedule in which transactions are ordered by the time when they start to unlock. Proof. Let S be a 2PL schedule in which transaction T1 starts its unlocks the latest. Let a be any action of T1. Suppose that there is an action a by another transactions Tkthat conflicts a and appears after a in the schedule S. Thus, S = a a Since a and a conflict, they are on the same element A. Both T1 and Tk need to lock A before their corresponding actions a and a can be executed. Since a appears in S before a , T1 must lock A before Tkdoes. So the schedule S looks like S = l1(A) a lk (A) a
Two actions conflict if they are by two transactions on the same element and at least one of the actions is write Why does 2PL work? Theorem. The execution of a 2PL schedule is equivalent to the serial schedule in which transactions are ordered by the time when they start to unlock. Proof. Let S be a 2PL schedule in which transaction T1 starts its unlocks the latest. Let a be any action of T1. Suppose that there is an action a by another transactions Tkthat conflicts a and appears after a in the schedule S. Thus, S = a a Since a and a conflict, they are on the same element A. Both T1 and Tk need to lock A before their corresponding actions a and a can be executed. Since a appears in S before a , T1 must lock A before Tkdoes. So the schedule S looks like S = l1(A) a lk (A) a Tk cannot lock A before T1 unlocks A. So S = l1(A) a u1(A) lk (A) a . Since S is 2PL, the first unlock of Tkmust appear after lk (A) , thus after u1(A). But this contradicts the assumption that T1 starts its unlock the latest.
Two actions conflict if they are by two transactions on the same element and at least one of the actions is write Why does 2PL work? Theorem. The execution of a 2PL schedule is equivalent to the serial schedule in which transactions are ordered by the time when they start to unlock. Proof. Let S be a 2PL schedule in which transaction T1 starts its unlocks the latest. Let a be any action of T1. Suppose that there is an action a by another transactions Tkthat conflicts a and appears after a in the schedule S. Thus, S = a a Since a and a conflict, they are on the same element A. Both T1 and Tk need to lock A before their corresponding actions a and a can be executed. Since a appears in S before a , T1 must lock A before Tkdoes. So the schedule S looks like S = l1(A) a lk (A) a Tk cannot lock A before T1 unlocks A. So S = l1(A) a u1(A) lk (A) a . Since S is 2PL, the first unlock of Tkmust appear after lk (A) , thus after u1(A). But this contradicts the assumption that T1 starts its unlock the latest. Thus, in the schedule S, there is no action by transactions other than T1 that conflicts an action of T1 and appears after the conflicting action of T1. So, we can swap the actions in S to move all actions of T1 to the tail of the schedule. The new schedule has a form S1 = 1T1. The new schedule S1 is equivalent to S.
Two actions conflict if they are by two transactions on the same element and at least one of the actions is write Why does 2PL work? Theorem. The execution of a 2PL schedule is equivalent to the serial schedule in which transactions are ordered by the time when they start to unlock. Proof. Let S be a 2PL schedule in which transaction T1 starts its unlocks the latest. Let a be any action of T1. Suppose that there is an action a by another transactions Tkthat conflicts a and appears after a in the schedule S. Thus, S = a a Since a and a conflict, they are on the same element A. Both T1 and Tk need to lock A before their corresponding actions a and a can be executed. Since a appears in S before a , T1 must lock A before Tkdoes. So the schedule S looks like S = l1(A) a lk (A) a Tk cannot lock A before T1 unlocks A. So S = l1(A) a u1(A) lk (A) a . Since S is 2PL, the first unlock of Tkmust appear after lk (A) , thus after u1(A). But this contradicts the assumption that T1 starts its unlock the latest. Thus, in the schedule S, there is no action by transactions other than T1 that conflicts an action of T1 and appears after the conflicting action of T1. So, we can swap the actions in S to move all actions of T1 to the tail of the schedule. The new schedule has a form S1 = 1T1. The new schedule S1 is equivalent to S. Using the same argument, we can move all actions of the transaction T2 that started its unlocks the second latest, to construct a schedule of the form S2 = 2T2T1 that is also equivalent to S. Repeating this process, we will eventually get a serial schedule that is equivalent to S.
Containment Relations Serializable schedules 2PL serial Conflict-serializable schedules Serializable schedule: equivalent to a serial schedule Conflict-serializable schedule: can be swapped into a serial schedule 2PL: transactions locks before any unlock. Serial schedule: transactions are executed one after the other
Containment Relations Serializable schedules 2PL serial Conflict-serializable schedules Serializable schedule: equivalent to a serial schedule Conflict-serializable schedule: can be swapped into a serial schedule 2PL: transactions locks before any unlock. Serial schedule: transactions are executed one after the other
Containment Relations Serializable schedules 2PL serial Conflict-serializable schedules Serializable schedule: equivalent to a serial schedule Conflict-serializable schedule: can be swapped into a serial schedule 2PL: transactions locks before any unlock. Serial schedule: transactions are executed one after the other
Containment Relations Serializable schedules 2PL serial Conflict-serializable schedules Serializable schedule: equivalent to a serial schedule Conflict-serializable schedule: can be swapped into a serial schedule 2PL: transactions locks before any unlock. Serial schedule: transactions are executed one after the other
Containment Relations Serializable schedules 2PL serial Conflict-serializable schedules Serializable schedule: equivalent to a serial schedule Conflict-serializable schedule: can be swapped into a serial schedule 2PL: transactions locks before any unlock. Serial schedule: transactions are executed one after the other
Beyond the simple 2PL protocol, it is all a matter of improving performance and allowing more concurrency .
Recall our study on conflict-serializability Read and write by two transactions T1, T2: swap? swap? w1(A)r2(B) swap? r1(A)r2(B) swap? w1(A)w2(B) r1(A)w2(B) swap? swap? w1(A)r2(A) swap? r1(A)r2(A) swap? w1(A)w2(A) r1(A)w2(A)
Recall our study on conflict-serializability Read and write by two transactions T1, T2: swap? swap? w1(A)r2(B) swap? r1(A)r2(B) swap? w1(A)w2(B) r1(A)w2(B) swap? swap? w1(A)r2(A) swap? r1(A)r2(A) swap? w1(A)w2(A) r1(A)w2(A)
Recall our study on conflict-serializability Read and write by two transactions T1, T2: Concurrent reads on the same element do not conflict. Thus, locking by a read that prevents others from reading discourages concurrency. swap? swap? w1(A)r2(B) swap? r1(A)r2(B) swap? w1(A)w2(B) r1(A)w2(B) swap? swap? w1(A)r2(A) swap? r1(A)r2(A) swap? w1(A)w2(A) r1(A)w2(A)
Recall our study on conflict-serializability Read and write by two transactions T1, T2: Concurrent reads on the same element do not conflict. Thus, locking by a read that prevents others from reading discourages concurrency. swap? swap? w1(A)r2(B) swap? r1(A)r2(B) swap? w1(A)w2(B) r1(A)w2(B) swap? swap? w1(A)r2(A) swap? r1(A)r2(A) swap? However, write conflicts with any other actions w1(A)w2(A) r1(A)w2(A)
Thus, We may have two different kinds of locks on elements:
Thus, We may have two different kinds of locks on elements: Read-lock (shared-lock slk(A)) by Tk on A: friendly to reads, but block writes Write-lock (exclusive-lock xlk(A)) by Tk on A: block any other actions.
Thus, We may have two different kinds of locks on elements: Read-lock (shared-lock slk(A)) by Tk on A: friendly to reads, but block writes Write-lock (exclusive-lock xlk(A)) by Tk on A: block any other actions. Examples: S = ...... sl1(A)r1(A)sl2(A) r1(A) xl1(A)
Thus, We may have two different kinds of locks on elements: Read-lock (shared-lock slk(A)) by Tk on A: friendly to reads, but block writes Write-lock (exclusive-lock xlk(A)) by Tk on A: block any other actions. Examples: S = ...... sl1(A)r1(A)sl2(A) r1(A) xl1(A) does not block T2 because sl1(A) is friendly to sl2(A)
Thus, We may have two different kinds of locks on elements: Read-lock (shared-lock slk(A)) by Tk on A: friendly to reads, but block writes Write-lock (exclusive-lock xlk(A)) by Tk on A: block any other actions. Examples: S = ...... sl1(A)r1(A)sl2(A) r1(A) xl1(A) does not block T2 because sl1(A) is friendly to sl2(A) block T1 because sl2(A) is exclusive of xl1(A).
Some details 1. Using compatibility matrix to represent lock relations: Lock requested shared exclusive shared YES NO Lock held exclusive NO NO
Some details 1. Using compatibility matrix to represent lock relations: Lock requested shared exclusive shared YES NO Lock held exclusive NO NO 2. What if a transaction needs to read and write on an element?
Some details 1. Using compatibility matrix to represent lock relations: Lock requested shared exclusive shared YES NO Lock held exclusive NO NO 2. What if a transaction needs to read and write on an element? Option 1. An exclusive lock allows both read and write: T = ... xl1(A) r1(A) w1(A) u(A)
Some details 1. Using compatibility matrix to represent lock relations: Lock requested shared exclusive shared YES NO Lock held exclusive NO NO 2. What if a transaction needs to read and write on an element? Option 1. An exclusive lock allows both read and write: T = ... xl1(A) r1(A) w1(A) u(A) Option 2. A transaction can exclusively lock an element shared-locked by itself: T = ... sl1(A) r1(A) xl1(A) w1(A) u(A)
Some details 1. Using compatibility matrix to represent lock relations: Lock requested shared exclusive shared YES NO Lock held exclusive NO NO 2. What if a transaction needs to read and write on an element? Option 1. An exclusive lock allows both read and write: T = ... xl1(A) r1(A) w1(A) u(A) Option 2. A transaction can exclusively lock an element shared-locked by itself: T = ... sl1(A) r1(A) xl1(A) w1(A) u(A) 3. How to unlock a shared/exclusive lock?
Some details 1. Using compatibility matrix to represent lock relations: Lock requested shared exclusive shared YES NO Lock held exclusive NO NO 2. What if a transaction needs to read and write on an element? Option 1. An exclusive lock allows both read and write: T = ... xl1(A) r1(A) w1(A) u(A) Option 2. A transaction can exclusively lock an element shared-locked by itself: T = ... sl1(A) r1(A) xl1(A) w1(A) u(A) 3. How to unlock a shared/exclusive lock? Can have either different unlocks for different locks, or a single unlock for all locks (our discussion will use a single unlock).
shared exclusive How Do Shared/Exclusive Locks Affect Serializability? shared YES NO exclusive NO NO Theorem. 2PL still works for shared/exclusive locks.
shared exclusive How Do Shared/Exclusive Locks Affect Serializability? shared YES NO exclusive NO NO Theorem. 2PL still works for shared/exclusive locks. Proof. Let S be a 2PL schedule in which transaction T1 starts its unlocks the latest. Let a be any action of T1. Suppose that there is an action a by another transactions Tkthat conflicts a and appears after a in the schedule S. Thus, S = a a Since a and a conflict, they are on the same element A. Both T1 and Tk need to lock A before their corresponding actions a and a can be executed. Since a appears in S before a , T1 must lock A before Tkdoes. So the schedule S looks like S = l1(A) a lk (A) a Tk cannot lock A before T1 unlocks A. So S = l1(A) a u1(A) lk (A) a . Since S is 2PL, the first unlock of Tkmust appear after lk (A) , thus after u1(A). But this contradicts the assumption that T1 starts its unlock the latest. Thus, in the schedule S, there is no action by transactions other than T1 that conflicts an action of T1 and appears after the conflicting action of T1. So, we can swap the actions in S to move all actions of T1 to the tail of the schedule. The new schedule has a form S1 = 1T1. The new schedule S1 is equivalent to S. Using the same argument, we can move all actions of the transaction T2 that started its unlocks the second latest, to construct a schedule of the form S2 = 2T2T1 that is also equivalent to S. Repeating this process, we will eventually get a serial schedule that is equivalent to S.
shared exclusive How Do Shared/Exclusive Locks Affect Serializability? shared YES NO exclusive NO NO Theorem. 2PL still works for shared/exclusive locks. Proof. Let S be a 2PL schedule in which transaction T1 starts its unlocks the latest. Let a be any action of T1. Suppose that there is an action a by another transactions Tkthat conflicts a and appears after a in the schedule S. Thus, S = a a Since a and a conflict, they are on the same element A. Both T1 and Tk need to lock A before their corresponding actions a and a can be executed. Since a appears in S before a , T1 must lock A before Tkdoes. So the schedule S looks like S = l1(A) a lk (A) a Tk cannot lock A before T1 unlocks A. So S = l1(A) a u1(A) lk (A) a . Since S is 2PL, the first unlock of Tkmust appear after lk (A) , thus after u1(A). But this contradicts the assumption that T1 starts its unlock the latest. Thus, in the schedule S, there is no action by transactions other than T1 that conflicts an action of T1 and appears after the conflicting action of T1. So, we can swap the actions in S to move all actions of T1 to the tail of the schedule. The new schedule has a form S1 = 1T1. The new schedule S1 is equivalent to S. Using the same argument, we can move all actions of the transaction T2 that started its unlocks the second latest, to construct a schedule of the form S2 = 2T2T1 that is also equivalent to S. Repeating this process, we will eventually get a serial schedule that is equivalent to S. and at least one is write. Thus, the locks used by a and a are exclusive
shared exclusive How Do Shared/Exclusive Locks Affect Serializability? shared YES NO exclusive NO NO Theorem. 2PL still works for shared/exclusive locks. Proof. Let S be a 2PL schedule in which transaction T1 starts its unlocks the latest. Let a be any action of T1. Suppose that there is an action a by another transactions Tkthat conflicts a and appears after a in the schedule S. Thus, S = a a Since a and a conflict, they are on the same element A. Both T1 and Tk need to lock A before their corresponding actions a and a can be executed. Since a appears in S before a , T1 must lock A before Tkdoes. So the schedule S looks like S = l1(A) a lk (A) a Tk cannot lock A before T1 unlocks A. So S = l1(A) a u1(A) lk (A) a . Since S is 2PL, the first unlock of Tkmust appear after lk (A) , thus after u1(A). But this contradicts the assumption that T1 starts its unlock the latest. Thus, in the schedule S, there is no action by transactions other than T1 that conflicts an action of T1 and appears after the conflicting action of T1. So, we can swap the actions in S to move all actions of T1 to the tail of the schedule. The new schedule has a form S1 = 1T1. The new schedule S1 is equivalent to S. Using the same argument, we can move all actions of the transaction T2 that started its unlocks the second latest, to construct a schedule of the form S2 = 2T2T1 that is also equivalent to S. Repeating this process, we will eventually get a serial schedule that is equivalent to S. and at least one is write. Thus, the locks used by a and a are exclusive Since l1(A) and lk (A) are exclusive,
How Does Locking Work? Scheduler inserts lock actions for transactions.
How Does Locking Work? Scheduler inserts lock actions for transactions. T1, T2, read(A), write(B), Scheduler, part I lock table l(A), read(A), l(B), write(B), Scheduler, part II read(A), write(B), DB
How Does Locking Work? Scheduler inserts lock actions for transactions. Lock table T1, T2, read(A), write(B), A lock info for A Scheduler, part I B lock info for B lock table l(A), read(A), l(B), write(B), Scheduler, part II A h read(A), write(B), DB ... lock table (a hash table, contains only locked elements)
How Does Locking Work? Scheduler inserts lock actions for transactions. Lock table T1, T2, read(A), write(B), A lock info for A Scheduler, part I B lock info for B lock table l(A), read(A), l(B), write(B), Scheduler, part II A h read(A), write(B), group mode: S waiting: yes DB tran mode wait? next T-link ... T1 S no lock table (a hash table, contains only locked elements) T2 S no T3 yes X
