img
Question:
Published on: 24 June, 2024

Describe the wait-die and wound-wait protocols for deadlock prevention. Define three concurrency problems: dirty read, non-repeatable read, phantoms.

Answer:

Wait-die and wound-wait protocols for deadlock prevention:

We can prevent deadlocks by giving each transaction a priority and ensuring that lower priority transactions are not allowed to wait for higher priority transactions (or vice versa). One way to assign priorities is to give each transaction a timestamp when it starts up. The lower the timestamp, the higher the transaction priority that is, the oldest transaction has the highest priority.

If a transaction Ti requests a lock and transaction Tj holds a conflicting lock, the lock manager can use one of the following two policies:

Wait-die scheme: It is a non-preemptive technique for deadlock prevention. When transaction Ti requests a data item currently held by Tj, Ti is allowed to wait only if it has a timestamp smaller than that of Tj (That is Ti is older than Tj), otherwise Ti is rolled back (dies)

For example:

Suppose that transaction T22, T23, T24 have time-stamps 5, 10 and 15 respectively. If T22requests a data item held by T23 then T22 will wait. If T24 requests a data item held by T23, then T24 will be rolled back.

 

Wound-wait scheme: It is a preemptive technique for deadlock prevention. It is a counterpart to the wait-die scheme. When Transaction Ti requests a data item currently held by Tj, Ti is allowed to wait only if it has a timestamp larger than that of Tj, otherwise Tj is rolled back (Tj is wounded by Ti)

For example:

Suppose that Transactions T22, T23, T24 have time-stamps 5, 10 and 15 respectively. If T22 requests a data item held by T23, then data item will be preempted from T23 and T23 will be rolled back. If T24 requests a data item held by T23, then T24 will wait. 

Dirty read:

Situation: Connection A reads an object that has been modified by Connection B but Connection B has not committed yet. Here, Connection B rollback transaction and uncommitted data is already read by Connection A.

This is known as “Dirty Read”

Problem: Transaction T2 was permitted to read the intermediate result of transaction T1 before the transaction T1 was terminated.

Solution: Prevent T2 from reading the account balance until the transaction T1 is terminated. i.e. either committed or rollback.

T1

T2

R(A)

 

A=A-100

 

W(A)

 

 

R(A)

 

X=A*0.02

 

A=A+X

 

W(A)

R(A)

 

FAILS

 

 

Non-repeatable read:

Situation: Connection A performs aggregate sum of accounts, at same time Connection B modifies the database. This is resulted into Inconsistent Analysis

Problem: of unrepeatable read occurs when a transaction reads a several values from database while other transaction updating those values.      

Solution: prevent other transaction to read the values from the database until one transaction release it.

T1

T2

R(A)

 

 

R(A)

 

A=A+100

 

W(A)

R(A)

 

 

Phantoms: The Phantom Problem can occur in database management systems in scenarios involving concurrency, and can cause unexpected and faulty behavior. The phantom problem is explained as in course of a transaction, two identical queries are executed, and the collection of rows returned by the second query is different from the first.

Example:  A transaction that scans a relation (e.g. find all accounts in Kolkata) and a transaction that inserts a tuple in the relation (e.g. insert a new account at Kolkata) may conflict in spite of not accessing any tuples in common. If only tuple locks are used, non-serializable schedules can result: the scan transaction may not see the new account, yet may be serialized before the insert transaction.

Random questions