DBMS Unit-5.4. Concurrency Control.pptx it is a PPT on the topic of concurrency control

©Silberschatz, Korth and Sudarshan
18.1
Database System Concepts - 7th
Edition
DATABASE MANAGEMENT SYSTEMS
Module - V
Concurrency Control

18.2
Edition
Outline
 Concurrency Control
 Lock-Based Protocols
• Locks
• 2PL
• Strict 2PL
 Multiversion Schemes
• Isolation Levels
Concurrency Control

18.3
Edition
Concurrency Control
 A database must provide a mechanism that will ensure that all
possible schedules are
• either conflict or view serializable, and
• are recoverable and preferably cascadeless
 A policy in which only one transaction can execute at a time
generates serial schedules, but provides a poor degree of
concurrency
• Are serial schedules recoverable/cascadeless?
 Testing a schedule for serializability after it has executed is a
little too late!
 Goal – to develop concurrency control protocols that will assure
serializability.
Concurrency Control

18.4
Edition
Concurrency Control (Cont.)
 Schedules must be conflict or view serializable, and recoverable,
for the sake of database consistency, and preferably
cascadeless.
 A policy in which only one transaction can execute at a time
generates serial schedules, but provides a poor degree of
concurrency.
 Concurrency-control schemes tradeoff between the amount of
concurrency they allow and the amount of overhead that they
incur.
 Some schemes allow only conflict-serializable schedules to be
generated, while others allow view-serializable schedules that
are not conflict-serializable.
Concurrency Control

18.5
Edition
Concurrency Control vs. Serializability Tests
 Concurrency-control protocols allow concurrent schedules, but
ensure that the schedules are conflict/view serializable, and are
recoverable and cascadeless .
 Concurrency control protocols (generally) do not examine the
precedence graph as it is being created
• Instead a protocol imposes a discipline that avoids non-
serializable schedules.
 Different concurrency control protocols provide different
tradeoffs between the amount of concurrency they allow and the
amount of overhead that they incur.
 Tests for serializability help us understand why a concurrency
control protocol is correct.
Concurrency Control

18.6
Edition
Lock-Based Protocols
 A lock is a mechanism to control concurrent access to a data
item
 Data items can be locked in two modes :
1. exclusive (X) mode. Data item can be both read as well as
written. X-lock is requested using lock-X instruction.
2. shared (S) mode. Data item can only be read. S-lock is
requested using lock-S instruction.
 Lock requests are made to concurrency-control manager.
Transaction can proceed only after request is granted.

18.7
Edition
Lock-Based Protocols (Cont.)
 Lock-compatibility matrix
 A transaction may be granted a lock on an item if the requested
lock is compatible with locks already held on the item by other
transactions
 Any number of transactions can hold shared locks on an item,
 But if any transaction holds an exclusive on the item no other
transaction may hold any lock on the item.

18.9
Edition
Schedule With Lock Grants
 Grants omitted
• Assume grant
happens just before
the next instruction
following lock
request
 This schedule is not
serializable (why?)
 A locking protocol is
a set of rules followed
by all transactions while
requesting and
releasing locks.
 Locking protocols
enforce serializability by
restricting the set of
possible schedules.

18.10
Edition
Deadlock
 Consider the partial schedule
 Neither T3 nor T4 can make progress — executing lock-S(B) causes T4 to
wait for T3 to release its lock on B, while executing lock-X(A) causes T3
to wait for T4 to release its lock on A.
 Such a situation is called a deadlock.
• To handle a deadlock one of T3 or T4 must be rolled back
and its locks released.

18.11
Edition
Deadlock (Cont.)
 The potential for deadlock exists in most locking protocols.
Deadlocks are a necessary evil.
 Starvation is also possible if concurrency control manager is
badly designed. For example:
• A transaction may be waiting for an X-lock on an item, while
a sequence of other transactions request and are granted
an S-lock on the same item.
• The same transaction is repeatedly rolled back due to
deadlocks.
 Concurrency control manager can be designed to prevent
starvation.

18.12
Edition
The Two-Phase Locking Protocol (2PL)
 A protocol which ensures conflict-
serializable schedules.
 Phase 1: Growing Phase
• Transaction may obtain locks
• Transaction may not release locks
 Phase 2: Shrinking Phase
• Transaction may release locks
• Transaction may not obtain locks
 The protocol assures serializability. It can be
proved that the transactions can be
serialized in the order of their lock points
(i.e., the point where a transaction acquired
its final lock).
Time
Locks
2PL

18.13
Edition
The Two-Phase Locking Protocol (Cont.)
 Two-phase locking does not ensure freedom from deadlocks
 Extensions to basic two-phase locking needed to ensure
recoverability of freedom from cascading roll-back
• Strict two-phase locking: a transaction must hold all its
exclusive locks till it commits/aborts.
 Ensures recoverability and avoids cascading roll-backs
• Rigorous two-phase locking: a transaction must hold all
locks till commit/abort.
 Transactions can be serialized in the order in which they
commit.
 Most databases implement rigorous two-phase locking, but
refer to it as simply two-phase locking
2PL

18.14
Edition
The Two-Phase Locking Protocol (Cont.)
 Two-phase locking is not a
necessary condition for serializability
• There are conflict serializable
schedules that cannot be
obtained if the two-phase locking
protocol is used.
 In the absence of extra information
(e.g., ordering of access to data),
two-phase locking is necessary for
conflict serializability in the following
sense:
• Given a transaction Ti that does
not follow two-phase locking, we
can find a transaction Tj that
uses two-phase locking, and a
schedule for Ti and Tj that is not
conflict serializable.
2PL

18.15
Edition
2 phase Locking Protocols
2PL

18.16
Edition
2 phase Locking Protocols
2PL

18.17
Edition
Strict 2 phase Locking Protocols
2PL

18.18
Edition
Rigorous 2 phase Locking Protocols
2PL

18.19
Edition
Locking Protocols
 Given a locking protocol (such as 2PL)
• A schedule S is legal under a locking protocol if it can be
generated by a set of transactions that follow the protocol
• A protocol ensures serializability if all legal schedules
under that protocol are serializable
2PL

18.20
Edition
Lock Conversions
 Two-phase locking protocol with lock conversions:
– Growing Phase:
• can acquire a lock-S on item
• can acquire a lock-X on item
• can convert a lock-S to a lock-X (upgrade)
– Shrinking Phase:
• can release a lock-S
• can release a lock-X
• can convert a lock-X to a lock-S (downgrade)
 This protocol ensures serializability
2PL

18.21
Edition
Automatic Acquisition of Locks
 A transaction Ti issues the standard read/write instruction,
without explicit locking calls.
 The operation read(D) is processed as:
if Ti has a lock on D
then
read(D)
else begin
if necessary wait until no other
transaction has a lock-X on D
grant Ti a lock-S on D;
read(D)
end
2PL

18.22
Edition
Automatic Acquisition of Locks (Cont.)
 The operation write(D) is processed as:
if Ti has a lock-X on D
then
write(D)
else begin
if necessary wait until no other trans. has any lock on D,
if Ti has a lock-S on D
then
upgrade lock on D to lock-X
else
grant Ti a lock-X on D
write(D)
end;
 All locks are released after commit or abort
2PL

18.23
Edition
Implementation of Locking
 A lock manager can be implemented as a separate process
 Transactions can send lock and unlock requests as messages
 The lock manager replies to a lock request by sending a lock
grant messages (or a message asking the transaction to roll
back, in case of a deadlock)
• The requesting transaction waits until its request is
answered
 The lock manager maintains an in-memory data-structure
called a lock table to record granted locks and pending
requests
2PL

18.24
Edition
Lock Table
 Dark squares indicate granted locks,
light colored ones indicate waiting
requests
 Lock table also records the type of
lock granted or requested
 New request is added to the end of
the queue of requests for the data
item, and granted if it is compatible
with all earlier locks
 Unlock requests result in the request
being deleted, and later requests are
checked to see if they can now be
granted
 If transaction aborts, all waiting or
granted requests of the transaction
are deleted
• lock manager may keep a list of
locks held by each transaction, to
implement this efficiently
2PL

18.25
Edition
Timestamp Ordering Protocol
2PL
 The Timestamp Ordering Protocol is used to order the transactions based on their
Timestamps. The order of transaction is nothing but the ascending order of the
transaction creation.
 The priority of the older transaction is higher that's why it executes first. To
determine the timestamp of the transaction, this protocol uses system time or
logical counter.
 The lock-based protocol is used to manage the order between conflicting pairs
among transactions at the execution time. But Timestamp based protocols start
working as soon as a transaction is created.
 Let's assume there are two transactions T1 and T2. Suppose the transaction T1
has entered the system at 007 times and transaction T2 has entered the system at
009 times. T1 has the higher priority, so it executes first as it is entered the system
first.
 The timestamp ordering protocol also maintains the timestamp of last 'read' and
'write' operation on a data.

18.26
Edition
Timestamp Ordering Protocol
2PL
 Basic Timestamp ordering protocol works as follows:
1. Check the following condition whenever a transaction Ti issues a Read
(X) operation:
 If W_TS(X) >TS(Ti) then the operation is rejected.
 If W_TS(X) <= TS(Ti) then the operation is executed.
 Timestamps of all the data items are updated.
2. Check the following condition whenever a transaction Ti issues
a Write(X) operation:
 If TS(Ti) < R_TS(X) then the operation is rejected.
 If TS(Ti) < W_TS(X) then the operation is rejected and Ti is rolled back otherwise
the operation is executed.
 TS(TI) denotes the timestamp of the transaction Ti.
 R_TS(X) denotes the Read time-stamp of data-item X.
 W_TS(X) denotes the Write time-stamp of data-item X.

DBMS Unit-5.4. Concurrency Control.pptx it is a PPT on the topic of concurrency control

Recommended

More Related Content

Similar to DBMS Unit-5.4. Concurrency Control.pptx it is a PPT on the topic of concurrency control (20)

Recently uploaded (20)

DBMS Unit-5.4. Concurrency Control.pptx it is a PPT on the topic of concurrency control

Editor's Notes