Concurrency

Concurrency single vs. multi­user systems multiprogramming on a single processor by interleaved execution In multi­user systems multiple transactions may be executed concurrently by interleaving  statements from the various transactions. Concurrent access to data can cause problems: (i.e. correct transaction produces wrong answer because of interference by some other (correct)  transaction)

CS3/3ICT2

Concurrency

1

Classes of Concurrency problems: 1 Lost Update Problem

2. Uncommitted Dependency Problem (or Temporary Update Problem) when a transaction fails, and undoes a change which another transaction has already seen.

3. Inconsistent Analysis Problem when computation of an aggregate value is interleaved with updates to the values being  aggregated.

CS3/3ICT2

Concurrency

2

SERIALIZABILITY AND TPL ­ SUMMARY One way to ensure correctness of concurrent transactions is to enforce serializability of transactions; that is the interleaved execution of the transactions must be equivalent to some serial execution of those transactions. The interleaved execution of a set of transactions is considered correct iff it is serializable. For reasonable definitions of equivalence, testing equivalence of two schedules is difficult. Instead determine protocols that guarantee serializability: e.g. Two-phase locking protocol (TPL) Timestamp methods … TPL: It can be proved that if all transactions obey the "two-phase locking protocol" then all possible interleaved executions are serializable.

CS3/3ICT2

Concurrency

3

EQUIVALENCE OF SCHEDULES (A schedule is an interelaved execution of operations of concurrent transactions.) Each data item affected by the schedule should have the operations applied to that item in the same order in both schedules. (Formally) two schedules S1 and S2 in which exactly the same transactions T1, … Tn participate are equivalent if 1. each read (X) operation executed by Ti in S1 sees the same write(X) as the corresponding read in S2. 2. For all X for which there is a write(X) operation, if the final write(X) in S1 is by Ti, the final write(X) in S2 is the same operation of Ti.

CS3/3ICT2

Concurrency

4

SERIALIZABILITY A schedule is serializable if it is equivalent to some serial schedule (i.e. transactions not interleaved at all). PRECEDENCE GRAPHS For testing serializability of a shcedule. One node for each transaction in the schedule. An edge Ti Tj if X  Tj reads X after Ti writes X  Tj writes X after Ti reads X  Tj writes X after Ti writes X If the precedence graph has a cycle the schedule is not serialisable. If it has no cycle, any ordering of the transactions which obeys the arrows is an equivalent  serial schedule, so the schedule is serializable.

CS3/3ICT2

Concurrency

5

SCHEDULES AND RECOVERY Recoverable Schedules In a recoverable schedule, once a transaction has committed it never has to be rolled back (i.e. durability property). This could occur because of the failure of another transaction whose update it read (see the Temporary Update problem above). In a recoverable schedule, no transaction T commits until all transactions whose updates T reads have committed. Avoiding Cascading Rollback Cascading rollback is where the failure and rollback of some transaction requires the rollback of other uncommitted transactions because they read updates of the failed transaction. Cascading rollback is expensive. Avoiding cascading rollback involves only reading items that were updated by committed transactions.

CS3/3ICT2

Concurrency

6

Strict Schedules Strict schedules simplify the process of recovering write operations to replacing the before image of the write. This requires that a transaction neither read nor write an item until the last transaction that wrote it has committed.

CS3/3ICT2

Concurrency

7

LOCKING Locks are a popular approach to concurrency control. Transactions request and acquire locks on data items which they wish to access and which they do not want other transactions to update. i.e. a lock locks other transactions out. Transactions can not access data items unless they have the appropriate lock. Most locking protocols are based on two types of locks: WRITE (or exclusive) locks: if a transaction holds a write lock on an item no other transaction  may acquire a read or write lock on that item. READ (or shared) locks: if a transaction holds a read lock on an item no other transaction may  acquire a write lock. Transactions go into a WAIT state till required lock is available. Acquisition of locks is the responsibility of the transaction management subsystem.

RELEASE OF LOCKS For strict schedules - i.e. simple recovery, transactions should hold all exclusive locks until COMMIT or ROLLBACK time. Thus no transaction can read or update an item until the last transaction that updated it has committed and released the exclusive lock.

CS3/3ICT2

Concurrency

8

TWO-PHASE LOCKING PROTOCOL: 1. Transactions must acquire a write lock before updating an item, and a read lock before reading  an item. (This enforces a single writer/multiple reader protocol.) 2. All locking operations in a transaction must precede the first unlocking operation in that  transaction. (Transactions have a lock acquisition phase followed by  a lock release phase.) This locking protocol guarantees serializable execution and therefore correctness. N.B. Any transaction that releases a lock and then goes on to acquire another lock always runs the  risk of producing incorrect results. Even if no existing transaction can interfere, a future  one might. Strict TPL (most popular protocol) ­ all (exclusive) locks are held till Commit or Abort time.

CS3/3ICT2

Concurrency

9

Deadlock Two­phase locking may limit the amount of concurrency that can occur ­ transactions will be  holding locks for items which they are not actually accessing now. This is the price for the guarantee of correctness. In the limit, deadlock can occur.  Deadlock is when each of two (in the simplest case) transactions is waiting for the other to release  a lock on an item. Deadlock detection ­ usually uses a wait­for graph ­ when a cycle occurs, there is deadlock ­  rollback one of the transactions involved (preferably one that hasn't done too much work  yet). Check for cycles if transactions are waiting more than some time.  Detection is attractive if interference among transactions is unlikely.

CS3/3ICT2

Concurrency

10

Deadlock Prevention ­ transaction manager should not allow a transaction to wait for a lock on  an item if this could give rise to deadlock. i.e avoid wait­for cycles arising. An approach used in operating systems is to insist that a transaction acquires all locks before it  starts. If it fails it releases all locks and tries again later. But this results in even less  concurrency, and is more appropriate for resource allocation in OS than lock acquisition  in DBs. Transaction­ordering methods: Order all transactions (e.g. timestamp order) and ensure that all  waiting observes this ordering.  wait­die protocol ­ allow older transactions wait for younger ones but rollback a younger  transaction that wants a lock held by an older one. wound­wait protocol ­ allow younger transactions to wait for older ones but if an older  transaction requests a lock that a younger one holds the younger one is rolled­back. These protocols prevent deadlock but abort transactions that might never actually have caused  deadlock. Non­timestamp methods: no­waiting approach ­ if a transaction is unable to get a lock it is aborted and restarts after a  certain delay. cautious­waiting approach ­ only wait on a transaction that is not blocked (waiting for a lock)

CS3/3ICT2

Concurrency

11

Timestamp Techniques for Concurrency Control Idea is to enforce a serializable execution equivalent to the serial execution of the transactions in timestamp order. Resolve conflicts by rolling back and restarting the transaction (so it gets a new start timestamp). No locks ⇒ no waiting ⇒ no deadlock. CONFLICTS: - attempt to read a record that has been updated by a younger transaction. - Attempt to update a record that has been seen or updated by a younger transaction. System maintains for every item the timestamp of the transaction that last read and the timestamp of the transaction that last updated the item.

CS3/3ICT2

Concurrency

12

The basic algorithm rollsback the transaction that would cause a conflict. This may require that other (committed) transactions also be rolled baDefer all updates to commit time so that restart does not involve rollback. Timestamp methods are particularly interesting for distributed systems, since locking requires communication overhead.

CS3/3ICT2

Concurrency

13

Optimistic Concurrency Control Techniques Check for conflicts at commit time. Avoids all locking and waiting, on the premise that conflict is  very rare. Defer updates till commit. If there is a conflict at commit time, restart the  transaction. Redoing completed transactions is very costly ­ optimistic methods only suit  in predominantly read­only environments. Transactions have a read phase (with writes to transaction­local copies of data), validation phase  (check for confilcts), write phase (update the DB). Validation requires information about the set of data items read by or written by each transaction  and about the timing of the transaction phases relative to other overlapping transactions. e.g. there is no conflict if this transaction starts its write phase after another has finished its write  phse and there is no item read by this transaction and written by that other transaction.

CS3/3ICT2

Concurrency

14