Week 7 – Concurrency and Control
CONCURRENCY
CONTROL
Dr Bailin Deng
• Operations by different clients may interfere with each other
• Example: bank account transfer
• Transactions and concurrency
control: ensure consistent state
of shared objects when accessed
by multiple transactions and in
server crashes.
Overview
T1
getBalance
£100
withdraw
-£50
setBalance
£50
T2
getBalance
£100
deposit
+£50
setBalance
£150
balance
£100£150£50
Transactions
• A transaction is a series of operations between a client and server.
• A transaction is committed or aborted.
• Commit – all operations completed, results are written to permanent
storage, operation cannot be undone.
• Abort – transaction cannot be completed, all operations are undone.
Transactions
• Transaction properties (ACID):
• Atomicity
• “all-or-nothing”.
• Either a transaction completes successfully, and all effects are applied to all
objects, or it has no effect at all.
• Consistency
• A transaction must move the system from one consistent state to another
consistent state.
• Example: sum of all account balances equal to branch’s total accounts.
• Isolation
• The intermediate effects of a transaction must not be visible to other transactions.
• Example: for an account transfer, cannot see accounts after withdrawal but before
deposit
• Durability
• After a transaction has been processed, its effects are saved to permanent
storage
Problems of Concurrent Transactions
• Lost Updates
• One transaction may overwrite the result of another.
• Suppose order is T1, U1, U2, T2, T3, U3
• Balance of b is £220 (not £242 as it should be).
Transaction T wants to
increase b’s balance by
10%, transferring from a.
1. bal = b.getBalance()
2. setBalance(bal*1.1)
3. a.withdraw(bal/10)
Transaction U wants to
increase b’s balance by
10%, transferring from c.
1. bal = b.getBalance()
2. b.setBalance(bal*1.1)
3. c.withdraw(bal/10)
bal = 200 balance
£200
bal*1.1 = 220
£220
bal = 200
bal*1.1 = 220
£220
Problems of Concurrent Transactions
• Inconsistent Retrievals
• An inconsistent value may be reported if a transaction is in progress.
• If W1 executes between V1 and V2
• The total will be short £100.
Transaction V transfers
£100 from a to b.
1. a.withdraw(100)
2. b.deposit(100)
Transaction W gets the
total of all accounts at
the bank branch.
1. getBranchTotal()
a
£300
b
£200
£200
£300
total
£500£400
A Simple / Poor Solution
• Ensure transactions are done one at a time
• Reduces concurrency unnecessarily: e.g. prevents concurrent reads
T1, T2, T3 U1, U2, U3
U1, U2, U3 T1, T2, T3
Concurrency Control
• Serially equivalent interleaving: an interleaving of the operations of
transactions with the same combined effect as if the transactions had
been performed one at a time in some order.
Concurrency Control
• Serially equivalent interleaving: an interleaving of the operations of
transactions with the same combined effect as if the transactions had
been performed one at a time in some order.
Transaction T:
1. bal = b.getBalance()
2. setBalance(bal*1.1)
3. a.withdraw(bal/10)
Transaction U:
1. bal = b.getBalance()
2. b.setBalance(bal*1.1)
3. c.withdraw(bal/10)
A serially equivalent interleaving: T1, T2, U1, U2, T3, U3
Concurrency Control
• Conflicting operations: combined effect depends on the order in which
they are executed.
Operations Conflict
read read No
read write Yes
write write Yes
Concurrency Control
• For two transactions to be serially equivalent, it is necessary and
sufficient that all pairs of conflicting operations of the two transactions
be executed in the same order at all of the objects they both access.
Concurrency Control
• For two transactions to be serially equivalent, it is necessary and
sufficient that all pairs of conflicting operations of the two transactions
be executed in the same order at all of the objects they both access.
Transaction T:
1. bal = b.getBalance()
2. setBalance(bal*1.1)
3. a.withdraw(bal/10)
Transaction U:
1. bal = b.getBalance()
2. b.setBalance(bal*1.1)
3. c.withdraw(bal/10)
A serially equivalent interleaving: T1, T2, U1, U2, T3, U3
Concurrency Control
• For two transactions to be serially equivalent, it is necessary and
sufficient that all pairs of conflicting operations of the two transactions
be executed in the same order at all of the objects they both access.
SECTION 16.2 TRANSACTIONS 687
Consider as an example the transactions T and U, defined as follows:
T: x = read(i); write(i, 10); write(j, 20);
U: y = read(j); write(j, 30); z = read (i);
Then consider the interleaving of their executions, shown in Figure 16.10
Figure 16.10 A non–serially-equivalent interleaving of operations of transactions T and U
Transaction T: Transaction U:
x = read(i)
write(i, 10)
y = read(j)
write(j, 30)
write(j, 20)
z = read (i)
. Note that
each transaction’s access to objects i and j is serialized with respect to one another,
because T makes all of its accesses to i before U does and U makes all of its accesses to
j before T does. But the ordering is not serially equivalent, because the pairs of
conflicting operations are not done in the same order at both objects. Serially equivalent
orderings require one of the following two conditions:
1. T accesses i before U and T accesses j before U.
2. U accesses i before T and U accesses j before T.
Serial equivalence is used as a criterion for the derivation of concurrency control
protocols. These protocols attempt to serialize transactions in their access to objects.
Three alternative approaches to concurrency control are commonly used: locking,
optimistic concurrency control and timestamp ordering. However, most practical
systems use locking, which is discussed in Section 16.4. When locking is used, the
server sets a lock, labelled with the transaction identifier, on each object just before it is
accessed and removes these locks when the transaction has completed. While an object
is locked, only the transaction that it is locked for can access that object; other
transactions must either wait until the object is unlocked or, in some cases, share the
lock. The use of locks can lead to deadlocks, with transactions waiting for each other to
release locks – for example, when a pair of transactions each has an object locked that
the other needs to access. We discuss the deadlock problem and some remedies for it in
Section 16.4.1.
Optimistic concurrency control is described in Section 16.5. In optimistic
schemes, a transaction proceeds until it asks to commit, and before it is allowed to
commit the server performs a check to discover whether it has performed operations on
any objects that conflict with the operations of other concurrent transactions, in which
case the server aborts it and the client may restart it. The aim of the check is to ensure
that all the objects are correct.
Timestamp ordering is described in Section 16.6. In timestamp ordering, a server
records the most recent time of reading and writing of each object and for each
Are T and U serially equivalent?
Concurrency Control
• Concurrency control protocols attempt to serialize transactions in their
access to objects, and are based on the criterion of serial equivalence.
• Three approaches:
• Locking
• Optimistic concurrency control
• Timestamp ordering
• Please read:
Page 723-734 in George Coulouris et al., “Distributed Systems:
Concepts and Design”, 5th Edition, Pearson, 2011
Locking
• Retrieve a lock on a resource before accessing it
• Access requests from other transactions are suspended until the lock
is released
LockingFigure 16.14 Transactions T and U with exclusive locks
Transaction T: Transaction U:
balance = b.getBalance()
b.setBalance(bal*1.1)
a.withdraw(bal/10)
balance = b.getBalance()
b.setBalance(bal*1.1)
c.withdraw(bal/10)
Operations Locks Operations Locks
openTransaction
bal = b.getBalance() lock B
b.setBalance(bal*1.1) openTransaction
a.withdraw(bal/10) lock A bal = b.getBalance() waits for T’s
lock on B
closeTransaction unlock A, B • • •
lock B
b.setBalance(bal*1.1)
c.withdraw(bal/10) lock C
closeTransaction unlock B, C
SECTION 16.4 LOCKS 693
locked for T, so transaction U waits. When transaction T is committed, B is unlocked,
whereupon transaction U is resumed. The use of the lock on B effectively serializes the
access to B. Note that if, for example, T released the lock on B between its getBalance
and setBalance operations, transaction U’s getBalance operation on B could be
interleaved between them.
Serial equivalence requires that all of a transaction’s accesses to a particular object
be serialized with respect to accesses by other transactions. All pairs of conflicting
operations of two transactions should be executed in the same order. To ensure this, a
transaction is not allowed any new locks after it has released a lock. The first phase of
each transaction is a ‘growing phase’, during which new locks are acquired. In the
second phase, the locks are released (a ‘shrinking phase’). This is called two-phase
locking.
We saw in Section 16.2.2 that because transactions may abort, strict executions
are needed to prevent dirty reads and premature writes. Under a strict execution regime,
a transaction that needs to read or write an object must be delayed until other
transactions that wrote the same object have committed or aborted. To enforce this rule,
any locks applied during the progress of a transaction are held until the transaction
commits or aborts. This is called strict two-phase locking. The presence of the locks
prevents other transactions reading or writing the objects. When a transaction commits,
to ensure recoverability, the locks must be held until all the objects it updated have been
written to permanent storage.
A server generally contains a large number of objects, and a typical transaction
accesses only a few of them and is unlikely to clash with other current transactions. The
granularity with which concurrency control can be applied to objects is an important
Two-phase Locking
• Two phase locking: to ensure serial equivalence, a transaction is not
allowed any new locks after it has released a lock.
“growing phase” – new locks are acquired
“shrinking phase” – the locks are released
Two-phase Locking
• Strict two phase locking: any locks applied during the progress of a
transaction are held until the transaction commits or aborts.
• Prevents dirty reads and premature writes.
Locking
• Dirty read
• a transaction sees a value that is part of another transaction that is
later aborted.
• T1: bal1 = a.getBalance() (£100)
• T2: a.setBalance(bal1+10) (£110)
• U1: bal2 = a.getBalance() (£110)
• U2: a.setBalance(bal2+20) (£130)
• U commits
• T aborts
• U cannot be undone
Locking
• Premature writes
• an aborted operation is reset to the wrong value
• Some systems store the before image with a write and roll back to
that value in the event of an abort. This is a problem if another
process overwrites the value before the abort.
• a – balance is £100
• T: a.setBalance(£105) – (before image: 100)
• U: a.setBalance(£110) – (before image: 105)
• U commits, T aborts and resets to 100 — should be 110
• If T aborts, then U aborts, result will be 105, but should be 100.
Read and Write Locks
• Allow concurrent reads for better performance
694 CHAPTER 16 TRANSACTIONS AND CONCURRENCY CONTROL
issue, since the scope for concurrent access to objects in a server will be limited severely
if concurrency control (for example, locks) can only be applied to all the objects at once.
In our banking example, if locks were applied to all customer accounts at a branch, only
one bank clerk could perform an online banking transaction at any time – hardly an
acceptable constraint!
The portion of the objects to which access must be serialized should be as small
as possible; that is, just that part involved in each operation requested by transactions.
In our banking example, a branch holds a set of accounts, each of which has a balance.
Each banking operation affects one or more account balances – deposit and withdraw
affect one account balance, and branchTotal affects all of them.
The description of concurrency control schemes given below does not assume any
particular granularity. We discuss concurrency control protocols that are applicable to
objects whose operations can be modelled in terms of read and write operations on the
objects. For the protocols to work correctly, it is essential that each read and write
operation is atomic in its effects on objects.
Concurrency control protocols are designed to cope with conflicts between
operations in different transactions on the same object. In this chapter, we use the notion
of conflict between operations to explain the protocols. The conflict rules for read and
write operations are given in Figure 16.9, which shows that pairs of read operations
from different transactions on the same object do not conflict. Therefore, a simple
exclusive lock that is used for both read and write operations reduces concurrency more
than is necessary.
It is preferable to adopt a locking scheme that controls the access to each object so
that there can be several concurrent transactions reading an object, or a single
transaction writing an object, but not both. This is commonly referred to as a ‘many
readers/single writer’ scheme. Two types of locks are used: read locks and write locks.
Before a transaction’s read operation is performed, a read lock should be set on the
object. Before a transaction’s write operation is performed, a write lock should be set on
the object. Whenever it is impossible to set a lock immediately, the transaction (and the
client) must wait until it is possible to do so – a client’s request is never rejected.
As pairs of read operations from different transactions do not conflict, an attempt
to set a read lock on an object with a read lock is always successful. All the transactions
reading the same object share its read lock – for this reason, read locks are sometimes
called shared locks.
The operation conflict rules tell us that:
1. If a transaction T has already performed a read operation on a particular object,
then a concurrent transaction U must not write that object until T commits or
aborts.
2. If a transaction T has already performed a write operation on a particular object,
then a concurrent transaction U must not read or write that object until T commits
or aborts.
To enforce condition 1, a request for a write lock on an object is delayed by the presence
of a read lock belonging to another transaction. To enforce condition 2, a request for
either a read lock or a write lock on an object is delayed by the presence of a write lock
belonging to another transaction.
Read and Write Locks
• Use “read locks” and “write locks”
SECTION 16.4 LOCKS 695
Figure 16.15
Figure 16.15 Lock compatibility
For one object Lock requested
read write
Lock already set none OK OK
read OK wait
write wait wait
shows the compatibility of read locks and write locks on any
particular object. The entries to the left of the first column in the table show the type of
lock already set, if any. The entries above the first row show the type of lock requested.
The entry in each cell shows the effect on a transaction that requests the type of lock
given above when the object has been locked in another transaction with the type of lock
on the left.
Inconsistent retrievals and lost updates are caused by conflicts between read
operations in one transaction and write operations in another without the protection of a
concurrency control scheme such as locking. Inconsistent retrievals are prevented by
performing the retrieval transaction before or after the update transaction. If the retrieval
transaction comes first, its read locks delay the update transaction. If it comes second,
its request for read locks causes it to be delayed until the update transaction has
completed.
Lost updates occur when two transactions read a value of an object and then use
it to calculate a new value. Lost updates are prevented by making later transactions delay
their reads until the earlier ones have completed. This is achieved by each transaction
setting a read lock when it reads an object and then promoting it to a write lock when it
writes the same object – when a subsequent transaction requires a read lock it will be
delayed until any current transaction has completed.
A transaction with a read lock that is shared with other transactions cannot
promote its read lock to a write lock, because the latter would conflict with the read locks
held by the other transactions. Therefore, such a transaction must request a write lock
and wait for the other read locks to be released.
Lock promotion refers to the conversion of a lock to a stronger lock – that is, a
lock that is more exclusive. The lock compatibility table in Figure 16.15 shows the
relative exclusivity of locks. The read lock allows other read locks, whereas the write
lock does not. Neither allows other write locks. Therefore, a write lock is more exclusive
than a read lock. Locks may be promoted because the result is a more exclusive lock. It
is not safe to demote a lock held by a transaction before it commits, because the result
will be more permissive than the previous one and may allow executions by other
transactions that are inconsistent with serial equivalence.
The rules for the use of locks in a strict two-phase locking implementation are
summarized in Figure 16.16. To ensure that these rules are adhered to, the client has no
access to operations for locking or unlocking items of data. Locking is performed when
the requests for read and write operations are about to be applied to the recoverable
objects, and unlocking is performed by the commit or abort operations of the transaction
coordinator.
Dead Locks
• Each member of a group of transactions is waiting for some other
member to release a lock.
• Example:
Transaction T: Transaction U:
Operations Locks Operations Locks
openTransaction openTransaction
a.deposit(100) lock a b.deposit(50) lock b
b.withdraw(100) wait for lock on b a.withdraw(50) wait for lock on a
…… ……
Dead Locks
• Deadlock prevention
• Atomically acquire all locks at beginning of transaction
• Unnecessarily restricts access to shared resources
• Hard to predict which objects will be used at the beginning
• Deadlock detection
• Find cycles in the wait-for graph
• Then a transaction be selected
for abortion to break the cycle.
• Lock manager: grants locks,
holds wait-for graph, detects deadlock,
force transaction to abort
T U
a
b
Held by
Waits for
Waits for
Held by