Describe the wait-die and wound-wait protocols for deadlock prevention. Define three concurrency problems: dirty read, non-repeatable read, phantoms.
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.
What are the differences between Primary Index, Secondary Index, and Clustering Index?
Write the recursive algorithm to find x^ n.
What is “Top-Down and Bottom-Up Design” approach?
