Transcript Concurrency Control Principles

L06: Concurrency Control & Locking
H.Lu/HKUST
Transactions
Concurrent execution of user programs is essential
for good DBMS performance.
 Because disk accesses are frequent, and relatively
slow, it is important to keep the CPU humming by
working on several user programs concurrently.
 A user’s program may carry out many operations on
the data retrieved from the database, but the DBMS
is only concerned about what data is read/written
from/to the database.
 A transaction is the DBMS’s abstract view of a user
program: a sequence of reads and writes.

H.Lu/HKUST
L06: Concurrency Control & Locking - 2
Transaction
A transaction is a collection of actions that make
consistent transformations of system states while
preserving system consistency.
Database may be
temporarily in an
Database in a
consistent state inconsistent state
during execution
Database in a
consistent state
Execution of Transaction
Begin
Transaction
H.Lu/HKUST
End
Transaction
L06: Concurrency Control & Locking - 3
An Example Transaction
Begin_transaction Reservation
begin
input(flight_no, date, customer_name);
EXEC SQL SELECT STSOLD,CAP
INTO temp1,temp2
FROM FLIGHT
WHERE FNO = flight_no AND DATE = date;
if temp1 = temp2 then output(``no free seats''); Abort
else
EXEC SQL UPDATE FLIGHT
SET STSOLD = STSOLD + 1
WHERE FNO = flight_no AND DATE = date;
EXEC SQL INSERT
INTO FC(FNO, DATE, CNAME, SPECIAL);
VALUES (flight_no, date, customer_name, null);
Commit
output(``reservation completed'')
endif
end . {Reservation}
H.Lu/HKUST
L06: Concurrency Control & Locking - 4
Example Transaction -- Reads & Writes
Begin_transaction Reservation
begin
input(flight_no, date, customer_name);
temp  Read(flight_no(date).stsold);
if temp = flight(date).cap then
begin
output(``no free seats'');
Abort
end
else begin
Write(flight(date).stsold, temp + 1);
Write(flight(date).cname, customer_name);
Write(flight(date).special, null);
Commit;
output(``reservation completed'')
end
end. {Reservation}
H.Lu/HKUST
L06: Concurrency Control & Locking - 5
Transaction Execution
User
Application
…...
User
Application
Begin_transaction,
Read, Write, Commit, Abort
Transaction Manager
(TM)
Read, Write,
Commit, Abort
Results
Scheduler
(SC)
Scheduled
Operations
Results
Recovery Manager
(RM)
H.Lu/HKUST
L06: Concurrency Control & Locking - 6
Properties of Transactions -- ACID
ATOMICITY
all or nothing
CONSISTENCY
no violation of integrity constraints
ISOLATION
concurrent changes invisible and serializable
DURABILITY
committed updates persist
H.Lu/HKUST
L06: Concurrency Control & Locking - 7
Atomicity
Either all or none of the transaction's operations are
performed.
 Atomicity requires that if a transaction is interrupted
by a failure, its partial results must be undone.
 The activity of preserving the transaction's atomicity
in presence of transaction aborts due to input errors,
system overloads, or deadlocks is called transaction
recovery.
 The activity of ensuring atomicity in the presence of
system crashes is called crash recovery.

H.Lu/HKUST
L06: Concurrency Control & Locking - 8
Consistency
Internal consistency
 A transaction which executes alone against a
consistent database leaves it in a consistent state.
 Transactions do not violate database integrity
constraints.
 Transactions are correct programs

H.Lu/HKUST
L06: Concurrency Control & Locking - 9
Isolation
Serializability
 If several transactions are executed concurrently,
the results must be the same as if they were
executed serially in some order.
 Incomplete results
 An incomplete transaction cannot reveal its results
to other transactions before its commitment.
 Necessary to avoid cascading aborts.

H.Lu/HKUST
L06: Concurrency Control & Locking - 10
Durability
Once a transaction commits, the system must
guarantee that the results of its operations will never
be lost, in spite of subsequent failures.
 Database recovery

H.Lu/HKUST
L06: Concurrency Control & Locking - 11
Concurrency in a DBMS

Users submit transactions, and can think of each transaction
as executing by itself.
 Concurrency is achieved by the DBMS, which interleaves
actions (reads/writes of DB objects) of various
transactions.
 Each transaction must leave the database in a consistent
state if the DB is consistent when the transaction begins.
• DBMS will enforce some ICs, depending on the ICs declared in
CREATE TABLE statements.
• Beyond this, the DBMS does not really understand the semantics
of the data. (e.g., it does not understand how the interest on a
bank account is computed).

Issues: Effect of interleaving transactions, and crashes.
H.Lu/HKUST
L06: Concurrency Control & Locking - 12
Why Concurrency Control

Consider two transactions (Xacts):
T1:
T2:


BEGIN A=A+100, B=B-100 END
BEGIN A=1.06*A, B=1.06*B END
Intuitively, the first transaction is transferring $100 from B’s
account to A’s account. The second is crediting both accounts
with a 6% interest payment.
There is no guarantee that T1 will execute before T2 or viceversa, if both are submitted together. However, the net effect
must be equivalent to these two transactions running serially
in some order.
Concurrency control: synchronizing concurrent transactions
such that the consistency of the database is maintained while,
at the same time, maximum degree of concurrency is
achieved.
H.Lu/HKUST
L06: Concurrency Control & Locking - 13
Lost Updates
T1:
Read A
A=A+100
Write A
Read B
B=B-100
Write B
H.Lu/HKUST
T2:
Read A
A=1.06*A
Write A
Read B
B=1.06*B
Write B
T1:
Read A
A=A+100
Write A
T2:
Read A
A=1.06*A
Write A
Read B
B=1.06*B
Write B
Read B
B=B-100
Write B
L06: Concurrency Control & Locking - 14
Dirty Read


Program T2 credits
interest rate based on a
value that is not part of a
consistent state.
Namely, T1 is aborted
later on.
H.Lu/HKUST
Step T1
1
Read(A,a1)
2
a1 :=a1-100
3
Write(A,a1)
T2
4
Read(A, a2)
5
a2:=a2*1.06
6
Write(A, a2)
7
Read(B,b1)
8
…
9
abort
L06: Concurrency Control & Locking - 15
Inconsistent Retrievals


T1 calculates the sum
T2 makes corrections to
previously made data
entrance error:
C:=C+30
D:=D-30
H.Lu/HKUST
T1
T1
T2
T2
T2
T1
T1
T2
T2
T2
T2
T1
Read A
Read B
Read C
C:=C+30
Write C
Read C
Read D
Read D
D:=D-30
Write D
Commit
Read E
100
120
70
220
100
100
35
35
320
355
5
100
455
L06: Concurrency Control & Locking - 16
Scheduling Transactions
Serial schedule: Schedule that does not interleave
the actions of different transactions.
 Equivalent schedules: For any database state, the
effect (on the set of objects in the database) of
executing the first schedule is identical to the effect
of executing the second schedule.
 Serializable schedule: A schedule that is equivalent
to some serial execution of the transactions.
(Note: If each transaction preserves consistency, every
serializable schedule preserves consistency. )

H.Lu/HKUST
L06: Concurrency Control & Locking - 17
Execution Schedule
An order in which the operations of a set of
transactions are executed.
 A schedule can be defined as a partial order over the
operations of a set of transactions.
T1 : Read(x)
T2 : Write(x)
T3 : Read(x)
Write(x)
Write(y)
Read(y)
Commit
Read(z)
Read(z)
Commit
Commit
S1 ={W2 (x), R1 (x), R3 (x), W1 (x), C1 ,W2 (y), R3(y),
R2(z), C2 , R3 (z), C3 }

H.Lu/HKUST
L06: Concurrency Control & Locking - 18
Serial Schedule



All the actions of a transaction occur consecutively.
No interleaving of transaction operations.
If each transaction is consistent (obeys integrity rules), then
the database is guaranteed to be consistent at the end of
executing a serial history.

T1 :
Write(x)
T3 : Read(x)
Write(y)
Read(y)
Read(z)
Read(z)
Commit
Commit
S ={W 2 (x), W 2 (y),R 2(z),C 2 ,R 1(x),W1 (x), C 1, R3(x), R3(y),
R3(z), C3 }
H.Lu/HKUST
Read(x)
Write(x)
Commit
T2 :
L06: Concurrency Control & Locking - 19
Equivalence of Schedules
More than one definition
 Conflict equivalence
 View equivalence
 Conflict equivalence
 Schedules S and S’ are conflict equivalent if the
relative order of execution of the conflicting
operations belonging to unaborted transactions in
two schedules are the same.

H.Lu/HKUST
L06: Concurrency Control & Locking - 20
Serializable Schedule

Transactions execute concurrently, but the net effect of the
resulting schedule upon the database is equivalent to some
serial schedule.
Example:
T1 :
Read(x)
Write(x)
Commit
T2 :
Write(x)
Write(y)
Read(z)
Commit
T3 :
Read(x)
Read(y)
Read(z)
Commit
A serializable schedule.
S = {W2(x), R1(x), W1(x), C1, R3(x), W2(y), R3(y), R2(z), C2,
R3(z), C3 }
H.Lu/HKUST
L06: Concurrency Control & Locking - 21
Serializable Schedule
T1 :
T2 : Write(x)
T3 : Read(x)
Write(y)
Read(y)
Read(z)
Read(z)
Commit
Commit
The following schedule is not serializable:
S1 = {W2(x), R1(x), R3(x),W1(x), C1, R3(y), W2(y),
R2(z), C2, R3(z), C3 }
The following is serializable.
S2 ={W2(x), R1(x), W1(x), C1, R3(x), W2(y), R3(y),
R2(z), C2, R3(z), C3 }
H.Lu/HKUST
Read(x)
Write(x)
Commit
L06: Concurrency Control & Locking - 22
Dependency Graph

Dependency graph:
 One node per Xact;
 edge from Ti to Tj if Tj reads/writes an object last
written by Ti.
A
T1
T2
B
 The cycle in the graph reveals the problem. The
output of T1 depends on T2, and vice-versa.
 Theorem: Schedule is conflict serializable if and only
if its dependency graph is acyclic.
H.Lu/HKUST
L06: Concurrency Control & Locking - 23
Dependency Graph - An Example
R1(X)
T1
T2
W1(X)
Since there are two
transactions,
R2(X)
W2(X)
we have two nodes T1 and T2
R1(X)  W2(X)  edge T2  T1;
R2(X)  W1(x)  edge T1  T21,
W2(X)  W1(X)  edge T1  T2
T1
T2
A cycle in Dependency Graph implies potential for database
inconsistency
H.Lu/HKUST
L06: Concurrency Control & Locking - 24
Locking




Mechanism to ensure serializable execution of interleaving
transactions accessing the same resources
Looking principle
 Before accessing a data item, obtain a lock on the data item
first
 After accessing the data item, release the lock
Locks are either read lock (rl) [also called shared lock] or write
lock (wl) [also called exclusive lock]
Read locks and write locks conflict (because Read and Write
operations are incompatible)
rl wl
rl yes no
wl no no
H.Lu/HKUST
L06: Concurrency Control & Locking - 25
LockingBased Concurrency Control

Transactions indicate their intentions by requesting
locks from the scheduler (called lock manager).
If the request data object is not exclusively locked by
the others, the transaction is granted the lock.
Otherwise, it will be blocked until other transactions
release the lock.
 However, simple locking does not guarantee the
correctness

H.Lu/HKUST
L06: Concurrency Control & Locking - 26
The Two-Phase Locking protocol



This is a protocol which ensures conflict-serializable
schedules.
Phase 1: Growing Phase
 transaction may obtain locks but is not allowed to release
locks
Phase 2: Shrinking Phase
 transaction may release locks but is not allowed to get
new locks
Acquire locks
Release locks
No of locks
acquired
time
H.Lu/HKUST
L06: Concurrency Control & Locking - 27
About 2PL

The protocol assures serializability. It can be proved that the
transaction can be serialized in the order of their lock points
(i.e. the point where a transaction acquired its final lock).

Does 2PL allow S1?
S1 = {R1(x), W1(x), R2(x),W2(x), R2(y),W2(y),R1(y),W1(y) }

How about S2?
S2 = {R1(x), W1(x), R2(x),W2(x), R1(y),W1(y) , R2(y),W2(y)}
H.Lu/HKUST
L06: Concurrency Control & Locking - 28
Strict Two-Phase Locking


Number of locks acquired

Cascading roll-back is possible under two-phase locking
Strict two-phase locking: a transaction must hold all its
exclusive locks till it commits/aborts.
Avoids cascade roll-back but reduces concurrency
T3
Keep all locks
Acquire locks
H.Lu/HKUST
Release locks
time
T4
Lock-X(A)
Lock-X(B)
Write(A)
Unlock(A)
Lock-X(A)
Read(A)
Write(A)
Abort
L06: Concurrency Control & Locking - 29
Deadlock
A transaction is deadlocked if it is blocked and will
remain blocked until there is intervention.
 Lockingbased CC algorithms may cause deadlocks.

Waitfor graph
If transaction Ti waits for
another transaction Tj to
release a lock on an entity,
then Ti  Tj in WFG.
H.Lu/HKUST
T3
Lock-X(B)
Read(B)
B:=B-50
Write(B)
T4
Lock-S(A)
Read(A)
Lock-S(B)
Lock-X(A)
L06: Concurrency Control & Locking - 30
Handling Deadlocks




Ignore
 Let the application programmer deal with it, or restart the
system
Prevention
 Guaranteeing that deadlocks can never occur in the first
place. Check transaction when it is initiated. Requires no
run time support.
Avoidance
 Detecting potential deadlocks in advance and taking
action to insure that deadlock will not occur. Requires run
time support.
Detection and Recovery
 Allowing deadlocks to form and then finding and
breaking them. As in the avoidance scheme, this requires
run time support.
H.Lu/HKUST
L06: Concurrency Control & Locking - 31
Summary




Concurrency control and recovery are among the most
important functions provided by a DBMS.
Users need not worry about concurrency.
 System automatically inserts lock/unlock requests and
schedules actions of different Xacts in such a way as to
ensure that the resulting execution is equivalent to
executing the Xacts one after the other in some order.
There are several lock-based concurrency control schemes
(Strict 2PL, 2PL). Conflicts between transactions can be
detected in the dependency graph
The lock manager keeps track of the locks issued.
Deadlocks can either be prevented or detected.
H.Lu/HKUST
L06: Concurrency Control & Locking - 32