Chapter 21 Concurrency Control Techniques PDF

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe  CHAPTER 21 Concurrency Control Techniques Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Introduction ◼ Concurrency control protocols ◼ Set of rules to guarantee serializability ◼ Tw...

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe  CHAPTER 21 Concurrency Control Techniques Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Introduction ◼ Concurrency control protocols ◼ Set of rules to guarantee serializability ◼ Two-phase locking protocols ◼ Lock data items to prevent concurrent access ◼ Timestamp ◼ Unique identifier for each transaction Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 3 21.1 Two-Phase Locking Techniques for Concurrency Control ◼ Lock ◼ Variable associated with a data item describing status for operations that can be applied ◼ One lock for each item in the database ◼ Binary locks ◼ Two states (values) ◼ Locked (1) ◼ Item cannot be accessed ◼ Unlocked (0) ◼ Item can be accessed when requested Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 4 Two-Phase Locking Techniques for Concurrency Control (cont’d.) ◼ Transaction requests access by issuing a lock_item(X) operation Figure 21.1 Lock and unlock operations for binary locks Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 5 Two-Phase Locking Techniques for Concurrency Control (cont’d.) ◼ Lock table specifies items that have locks ◼ Lock manager subsystem ◼ Keeps track of and controls access to locks ◼ Rules enforced by lock manager module ◼ At most one transaction can hold the lock on an item at a given time ◼ Binary locking too restrictive for database items Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 6 Two-Phase Locking Techniques for Concurrency Control (cont’d.) ◼ Shared/exclusive or read/write locks ◼ Read operations on the same item are not conflicting ◼ Must have exclusive lock to write ◼ Three locking operations ◼ read_lock(X) ◼ write_lock(X) ◼ unlock(X) Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 7 Figure 21.2 Locking and unlocking operations for two-mode (read/write, or shared/exclusive) locks Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21-8 Two-Phase Locking Techniques for Concurrency Control (cont’d.) ◼ Lock conversion ◼ Transaction that already holds a lock allowed to convert the lock from one state to another ◼ Upgrading ◼ Issue a read_lock operation then a write_lock operation ◼ Downgrading ◼ Issue a read_lock operation after a write_lock operation Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 9 Guaranteeing Serializability by Two- Phase Locking ◼ Two-phase locking protocol ◼ All locking operations precede the first unlock operation in the transaction ◼ Phases ◼ Expanding (growing) phase ◼ New locks can be acquired but none can be released ◼ Lock conversion upgrades must be done during this phase ◼ Shrinking phase ◼ Existing locks can be released but none can be acquired ◼ Downgrades must be done during this phase Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 10 Figure 21.3 Transactions that do not obey two-phase locking (a) Two transactions T1 and T2 (b) Results of possible serial schedules of T1 and T2 (c) A nonserializable schedule S that uses locks Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 11 Guaranteeing Serializability by Two- Phase Locking ◼ If every transaction in a schedule follows the two- phase locking protocol, schedule guaranteed to be serializable ◼ Two-phase locking may limit the amount of concurrency that can occur in a schedule ◼ Some serializable schedules will be prohibited by two-phase locking protocol Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 12 Variations of Two-Phase Locking ◼ Basic 2PL ◼ Technique described on previous slides ◼ Conservative (static) 2PL ◼ Requires a transaction to lock all the items it accesses before the transaction begins ◼ Predeclare read-set and write-set ◼ Deadlock-free protocol ◼ Strict 2PL ◼ Transaction does not release exclusive locks until after it commits or aborts Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 13 Variations of Two-Phase Locking (cont’d.) ◼ Rigorous 2PL ◼ Transaction does not release any locks until after it commits or aborts ◼ Concurrency control subsystem responsible for generating read_lock and write_lock requests ◼ Locking generally considered to have high overhead Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 14 Dealing with Deadlock and Starvation ◼ Deadlock ◼ Occurs when each transaction T in a set is waiting for some item locked by some other transaction T’ ◼ Both transactions stuck in a waiting queue Figure 21.5 Illustrating the deadlock problem (a) A partial schedule of T1′ and T2′ that is in a state of deadlock (b) A wait-for graph for the partial schedule in (a) Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 15 Dealing with Deadlock and Starvation (cont’d.) ◼ Deadlock prevention protocols ◼ Every transaction locks all items it needs in advance ◼ Ordering all items in the database ◼ Transaction that needs several items will lock them in that order ◼ Both approaches impractical ◼ Protocols based on a timestamp ◼ Wait-die ◼ Wound-wait Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 16 Dealing with Deadlock and Starvation (cont’d.) ◼ No waiting algorithm ◼ If transaction unable to obtain a lock, immediately aborted and restarted later ◼ Cautious waiting algorithm ◼ Deadlock-free ◼ Deadlock detection ◼ System checks to see if a state of deadlock exists ◼ Wait-for graph Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 17 Dealing with Deadlock and Starvation (cont’d.) ◼ Victim selection ◼ Deciding which transaction to abort in case of deadlock ◼ Timeouts ◼ If system waits longer than a predefined time, it aborts the transaction ◼ Starvation ◼ Occurs if a transaction cannot proceed for an indefinite period of time while other transactions continue normally ◼ Solution: first-come-first-served queue Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 18 21.2 Concurrency Control Based on Timestamp Ordering ◼ Timestamp ◼ Unique identifier assigned by the DBMS to identify a transaction ◼ Assigned in the order submitted ◼ Transaction start time ◼ Concurrency control techniques based on timestamps do not use locks ◼ Deadlocks cannot occur Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 19 Concurrency Control Based on Timestamp Ordering (cont’d.) ◼ Generating timestamps ◼ Counter incremented each time its value is assigned to a transaction ◼ Current date/time value of the system clock ◼ Ensure no two timestamps are generated during the same tick of the clock ◼ General approach ◼ Enforce equivalent serial order on the transactions based on their timestamps Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 20 Concurrency Control Based on Timestamp Ordering (cont’d.) ◼ Timestamp ordering (TO) ◼ Allows interleaving of transaction operations ◼ Must ensure timestamp order is followed for each pair of conflicting operations ◼ Each database item assigned two timestamp values ◼ read_TS(X) ◼ write_TS(X) Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 21 Concurrency Control Based on Timestamp Ordering (cont’d.) ◼ Basic TO algorithm ◼ If conflicting operations detected, later operation rejected by aborting transaction that issued it ◼ Schedules produced guaranteed to be conflict serializable ◼ Starvation may occur ◼ Strict TO algorithm ◼ Ensures schedules are both strict and conflict serializable Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 21- 22