We’ve updated our privacy policy so that we are compliant with changing global privacy regulations and to provide you with insight into the limited ways in which we use your data. Show You can read the details below. By accepting, you agree to the updated privacy policy. Thank you! View updated privacy policy We've encountered a problem, please try again. Download Assignment 3... ACS-4902 Assignment 3 due: March 19, 2014 1. Review questions (20) (a) What is the two-phase locking protocol? How does it guarantee serializability? (b) Describe the wait-die and wound-wait protocols for deadlock prevention. (c) Describe the cautious waiting, no waiting, and timeout protocols for deadlock prevention. (d) What is a timestamp? How does the system generate timestamp? ACS-4902 Assignment 3 due: March 19, 2013 2. Modify the data structure for multiple-mode locks (shared and exclusive) and the algorithm for read_lock(X), write_lock(X), and unlock(X) so that upgrading and downgrading of locks are possible. (The lock and unlock operations can be found on the course page under “figures for Chapter 20”; Hint: The lock needs to check the transaction id(s) that hold the lock, if any.) (20) read_lock (X): B: if LOCK (X)="unlocked" then begin LOCK ( X) "read-locked"; no_of_reads(X) 1 end else if LOCK(X)="read-locked" then no_of_reads(X) no_of _reads(X) + 1 else begin wait (until LOCK (X)="unlocked" and the lock manager wakes up the transaction); go to B end; write_lock (X): B: if LOCK (X)="unlocked" then LOCK (X) "write-locked" else begin wait (until LOCK(X)="unlocked" and he lock manager wakes up the transaction); go to B end; unlock_item (X): if LOCK (X)="write-locked" then begin LOCK (X) "unlocked;“ wakeup one of the waiting transactions, if any end else if LOCK(X)="read-locked" then begin no_of_reads(X) no_of_reads(X) – 1; if no_of_reads(X)=0 then begin LOCK (X)="unlocked"; wakeup one of the waiting transactions, if any end end; ACS-4902 Assignment 3 due: March 19, 2013 3. Apply the timestamp ordering algorithm to the schedules of Figure 19.8(b) and (c), and determine whether the algorithm will allow the execution of the schedules. (the figures can be found on the course page under “figures for chapter 19”.) (20) ACS-4902 Assignment 3 due: March 19, 2013 4. The compatibility matrix of Figure 20.8 shows that IS and IX locks are compatible. Explain why this is valid. (the figures can be found on the course page under “figures for chapter 20”.) (20) 5. What is ‘certify’ lock? Explain why this kind of locks is needed for multiversion 2PL. (20) IS IX S SIX X IS IX S SIX X yes yes yes yes no yes yes no no no yes no yes no no yes no no no no no no no no no A deadlock is a condition where two or more transactions are waiting indefinitely for one another to give up locks. Deadlock is said to be one of the most feared complications in DBMS as no task ever gets finished and is in waiting state forever. For example: In the student table, transaction T1 holds a lock on some rows and needs to update some rows in the grade table. Simultaneously, transaction T2 holds locks on some rows in the grade table and needs to update the rows in the Student table held by Transaction T1. Now, the main problem arises. Now Transaction T1 is waiting for T2 to release its lock and similarly, transaction T2 is waiting for T1 to release its lock. All activities come to a halt state and remain at a standstill. It will remain in a standstill until the DBMS detects the deadlock and aborts one of the transactions.  Deadlock Avoidance
Deadlock DetectionIn a database, when a transaction waits indefinitely to obtain a lock, then the DBMS should detect whether the transaction is involved in a deadlock or not. The lock manager maintains a Wait for the graph to detect the deadlock cycle in the database. Wait for Graph
The wait for a graph for the above scenario is shown below: Deadlock Prevention
Wait-Die schemeIn this scheme, if a transaction requests for a resource which is already held with a conflicting lock by another transaction then the DBMS simply checks the timestamp of both transactions. It allows the older transaction to wait until the resource is available for execution. Let's assume there are two transactions Ti and Tj and let TS(T) is a timestamp of any transaction T. If T2 holds a lock by some other transaction and T1 is requesting for resources held by T2 then the following actions are performed by DBMS:
Wound wait scheme
What are the deadlock prevention protocols?Deadlock can be prevented by eliminating any of the four necessary conditions, which are mutual exclusion, hold and wait, no preemption, and circular wait. Mutual exclusion, hold and wait and no preemption cannot be violated practically.
Can cautious waiting can avoid deadlock?The cautious waiting rules are as follows: Cautious waiting. If Tj is not blocked (not waiting for some other locked item), then Ti is blocked and allowed to wait; otherwise abort Ti. It can be shown that cautious waiting is deadlock-free, because no transaction will ever wait for another blocked transaction.
What are the three basic techniques to control deadlocks?The three basic techniques to control deadlocks are:. Deadlock preventation . A transaction requesting a new lock is aborted when there is the possibility that a deadlock can occur. ... . Deadlock detection. The DBMS periodically tests the database for deadlocks. ... . Deadlock avoidance.. How can you avoid hold and wait which leads to deadlock?Eliminate Hold and wait. Allocate all required resources to the process before the start of its execution, this way hold and wait condition is eliminated but it will lead to low device utilization. ... . The process will make a new request for resources after releasing the current set of resources.. |
