TRANSACTIONS2

Information about TRANSACTIONS2

Published on July 15, 2014

Author: indranisen2003

Source: authorstream.com

Content

TRANSACTIONS: TRANSACTIONS Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: Transactions in a database environment have two main purposes:- Reliability of data: In case of unpredictable circumstances such as power failures or system failures while a database is getting updated or being read, the transactions should ensure to give us consistent and accurate data. Concurrent Access of data: When more than one user or application programs are trying to access the same data, the transactions should provide isolation between the programs accessing a database concurrently . Otherwise concurrent read or write operations to a database may lead to inconsistent or erronaeous data. Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: Begin the transaction. Execute a set of data manipulations and/or queries. If no errors occur then commit the transaction and end it. If errors occur then rollback the transaction and end it. Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: BEGIN TRANSACTION SELECT A TABLE “X” FOR UPDATE INSERT INTO TABLE RECORD1 INSERT INTO TABLE RECORD2 INSERT INTO TABLE RECORD3 UPDATE TABLE “X” COMMIT ROLLBACK Prof Indrani Sen ,MCA,MPhil Computer Science Atomicity: A transaction is an atomic unit of processing ; it is either performed in its entirety or not performed at all . The atomicity property requires that we execute a transaction to completion. It is the responsibility of the recovery subsystem of a DBMS to ensure atomicity. If a transaction fails to complete for some reason, such as a system crash in the midst of transaction execution, the recovery technique must undo any effects of the transaction on the database. Prof Indrani Sen ,MCA,MPhil Computer Science Atomicity PowerPoint Presentation: ATM(withdrawal) Database Recovery Manager Account_Balance = Account_Balance -Withdraw _amt Account debited Crash/Transaction Error Transaction rollback Account_Balance = Account_Balance + Withdraw _amt Account credited/ reversed Prof Indrani Sen ,MCA,MPhil Computer Science Consistency preservation:: The DBMS has to ensure that the transaction preserves data consistency in a database and does not violate any integrity constraints . A database program should be written in a way that guarantees that, if the database is in a consistent state before executing the transaction, it will be in a consistent state after the complete execution of the transaction, assuming that no interference with other transactions occurs Prof Indrani Sen ,MCA,MPhil Computer Science Consistency preservation: PowerPoint Presentation: Consider an account hoder tries to withdraw an amount from his Account where withdraw_amt is greater than the balance, then the transaction should not cause a change in the database as the action will violate a constraint in the database . So the DBMS programmers must ensure that such a constraint should exist which will not allow the database to go in an inconsistent state. A Bank employee tries to open an Account with the same Account_no which already has been assigned to another Account holder, in this case the transaction should ensure that the Account_no should not be duplicated and hence maintain database integrity. Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science Isolation:: A transaction should appear as though it is being executed in isolation from other transactions. That is, the execution of a transaction should not be interfered with by any other transactions executing concurrently. Prof Indrani Sen ,MCA,MPhil Computer Science Isolation: PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science Durability or permanency: The changes applied to the database by a committed transaction must be permanent in the database. These changes must not be lost because of any failure. For example ,Consider the Account_holder is transferring funds from Account A to Account B then under the following conditions, the changes should be permanent and cannot be reversed even if the application crashes or an error occurs or the user decides to cancel the transaction after the transaction is over Prof Indrani Sen ,MCA,MPhil Computer Science Durability or permanency Some Transaction Primitives : Examples of primitives for transactions. Prof Indrani Sen ,MCA,MPhil Computer Science Some Transaction Primitives Primitive Description BEGIN_TRANSACTION Make the start of a transaction END_TRANSACTION Terminate the transaction and try to commit ABORT_TRANSACTION Kill the transaction and restore the old values READ Read data from a file, a table, etc. WRITE Write data to a file, a table, etc. TRANSACTION CONTROL LANGUAGE STATEMENTS: : Transaction Control (TCL) statements are used to manage the changes made by DML statements . It allows statements to be grouped together into logical transactions. It plays an important role in SQL. Transaction control language is used for managing the changes made by DML statements. It allows statements to be grouped together to form a logical transaction. There are lots of TCL commands which are used in SQL in which some are defined as follows: Prof Indrani Sen ,MCA,MPhil Computer Science TRANSACTION CONTROL LANGUAGE STATEMENTS: COMMIT:: Commit command is used for saving work done in database. It is the responsibility of the programmer to execute commits statement only after ensuring the correctness and integrity of data. You cannot cancel or undo the changes performed by a transaction after a commit transaction statement is issued because the database modifications are made permanent after that. A SQL statement that is executed successfully without any errors does not confirm that the Transaction is committed. Executing successfully means that the specific statement was: Parsed Found to be syntactically correct and a valid SQL statement Does not throw any errors or exceptions. Prof Indrani Sen ,MCA,MPhil Computer Science COMMIT: When a transaction is committed?: A statement is said to be committed when the user gives the COMMIT statement explicitly. An implicit request occurs in either of the following conditions: After normal termination of an application using END statement Successful execution of a data definition language (DDL) operation. Prof Indrani Sen ,MCA,MPhil Computer Science When a transaction is committed? PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science ROLLBACK:: The rollback command cancels the modifications done by the recent DML statements and restore database to original state since the last COMMIT. The Roll back of the transactions can occur under the following circumstances: Transaction can be rolled back due to a statement execution error. The Transaction can Rollback to a Savepoint if explicitly specified. Rollback of a transaction due to user request (ROLLBACK statement) Rollback of a transaction due to abnormal application termination like PC shut down or accidentally closure of the SQL command line window. Rollback of incomplete transactions during database recovery. Prof Indrani Sen ,MCA,MPhil Computer Science ROLLBACK: SAVEPOINT:: This command is used to identify a point in a particular database object till which the changes made can be cancelled or undone . This command is used to identify a point in a particular database object till which the changes made can be cancelled or undone. Consider the following Transactions: T1: Deposit 5000 to Account A00121 T2: Deposit 1000 to Account A00234 The state of the database after each Transaction is saved by creating Savepoints . After a Savepoint has been created, processing can be continued, the Transaction can be committed, or the entire Transaction can be Rollback, or the Transaction can Roll back to the Savepoint . Prof Indrani Sen ,MCA,MPhil Computer Science SAVEPOINT: PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science CONCURRENCY CONTROL: : The coordination of simultaneous execution of transactions in a multiprocessing database system is known as concurrency control. The objective of concurrency control is to ensure serialisability of transactions in a multiuser database environment. Concurrency control is important because the simultaneous execution of transactions over a shared database can create several data integrity and consistency problems. The three main problems are lost updates, uncommitted data and inconsistent retrievals. Prof Indrani Sen ,MCA,MPhil Computer Science CONCURRENCY CONTROL: Lost Updates: : Lost update problem results in storing a wrong updated value for a particular row or column of a relation due to the simultaneous execution of concurrent transactions. Prof Indrani Sen ,MCA,MPhil Computer Science Lost Updates: PowerPoint Presentation: T1: DEPOSIT (A01208, 15,000) SQL: UPDATE Account SET Balance = Balance + 15,000 WHERE AcNo = ’A01208’; T2: WITHDRAW (A01208, 20,000) SQL: UPDATE Account SET Balance = Balance – 20,000 WHERE AcNo = ’A01208’; Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science Uncommitted Data: : The data of the last transaction is automatically committed when another transaction is executed or when the user types the “COMMIT” command. But when two transactions are concurrently executed data is not committed unless the last transaction finishes. In between if transaction T1 is rolled back then transaction T2 has already accessed the uncommitted data violating the isolation property of the two transactions. A transaction can be rolled back due to several reasons like power failure, system crash. For the above example UNCOMMITTED DATA will lead to a situation causing inconsistent update. Prof Indrani Sen ,MCA,MPhil Computer Science Uncommitted Data: PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science Inconsistent Retrievals: : Inconsistent retrievals occur when a transaction calculates some summary aggregate functions over a set of data while the other transactions are updating the data. The problem is that the transaction might read some data before they are changed and some other data after the values are modified yielding inconsistent results. Prof Indrani Sen ,MCA,MPhil Computer Science Inconsistent Retrievals: PowerPoint Presentation: Consider Transaction T3 which calculates the total Balance of the Savings account operated in the branch B02. While T3 calculates the Balance, T1 and T2 updates the balance of Account number A01208. This leads to incorrect calculation by the aggregate function SUM(). Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science THE SCHEDULER: : For example, consider the following sequence of arithmetic operations among which 2 and 3 are executed concurrently: A = 0, B = 1, X = 0 X = A + B Z = X + 10 If the above transactions occur in the order 1-2-3 then Z = 11 If the order is 1, 3, 2 then Z = 10 Prof Indrani Sen ,MCA,MPhil Computer Science THE SCHEDULER: PowerPoint Presentation: The scheduler establishes the order in which the operations within the concurrent transactions are executed. To determine the appropriate order, the scheduler performs actions based on concurrency control algorithms such as locking or time stamping methods. Prof Indrani Sen ,MCA,MPhil Computer Science SERIALISABILITY: : Identifies data transactions as occurring serially, independent of one another, even though they may have occurred concurrently. A schedule or list of transactions is correct if they are serialized, otherwise, they may contain errors that can lead to duplication or overlap. Two transactions need serialization if they involve the same data element and one of them is attempting a write operation on the data. Prof Indrani Sen ,MCA,MPhil Computer Science SERIALISABILITY: PowerPoint Presentation: The types of concurrent transactions are as follows where R and W is equivalent to Read and Write respectively: T1: R(Account, Balance),T2: R(Account, Balance) T1: R(Account, Balance),T2: W(Account, Balance) T1: W (Account, Balance),T2: R(Account, Balance) T1: W(Account, Balance), T2: W(Account, Balance) Prof Indrani Sen ,MCA,MPhil Computer Science The rules to ensure serialisability : : If two transactions T1 and T2 only read a data item, they do not conflict and the order of execution does not matter. If two transactions T1 and T2 write separate data items, the execution order is not important. If two transactions T1 and T2 operate on the same data item and one of the operations is a write then the order of execution is important. Prof Indrani Sen ,MCA,MPhil Computer Science The rules to ensure serialisability : PowerPoint Presentation: A (possibly concurrent) schedule is serializable if it is equivalent to a serial schedule. Different forms of schedule equivalence gives rise to the notions of : 1. conflict serializability 2. view serializability Prof Indrani Sen ,MCA,MPhil Computer Science CONFLICT SERIALIZABLE: : The transactions having at least one write operations are said to have conflicts and if their schedules converted to a serial schedule, they are known as CONFLICT SERIALISABLE. The set of edges in the Precedence graph consists of all edges Ti  Tj for which one of three conditions holds: Ti executes write(X) before Tj executes read(X). Ti executes read(X) before Tj executes write(X). Ti executes write(X) before Tj executes write(X). Prof Indrani Sen ,MCA,MPhil Computer Science CONFLICT SERIALIZABLE: Precedence Graph : Method : To draw one; Draw a node for each transaction in the schedule Where transaction A writes to an attribute which transaction B has read from, draw an line pointing from B to A. Where transaction A writes to an attribute which transaction B has written to, draw a line pointing from B to A. Where transaction A reads from an attribute which transaction B has written to, draw a line pointing from B to A. Prof Indrani Sen ,MCA,MPhil Computer Science Precedence Graph : Method PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science T1 T2 Stored value Read (A01208,Balance) 45,000 Write(A01208,Balance) 45,000 + 15,000 = 60,000 Read(A01208,balance) 60,000 Write (A01208,Balance) 60,000 – 20,000 = 40,000 Schedule 1: PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: The graph is acyclic and the schedule is not interleaved Hence it is a serial schedule.   Prof Indrani Sen ,MCA,MPhil Computer Science Schedule 2:: Prof Indrani Sen ,MCA,MPhil Computer Science Schedule 2: T1 T2 Stored value Read(A01208,balance) 45,000 Write (A01208,Balance) 45,000 – 20,000 = 25,000 Read(A01208,Balance) Write(A01208,Balance) 25,000 25,000 + 15,000 = 40,000 PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: The graph does not have cycles. This schedule is also a serial schedule. Prof Indrani Sen ,MCA,MPhil Computer Science Schedule 3:: Prof Indrani Sen ,MCA,MPhil Computer Science Schedule 3: T1 T2 Stored value Read(A01208,balance) 45,000 Read (A01208,Balance) 45,000 Write(A01208,Balance) 45,000 + 15,000 = 60,000 Write (A01208,Balance) 45,000-20,000 = 25,000 (Balance overwritten) PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science Schedule 4: : Prof Indrani Sen ,MCA,MPhil Computer Science Schedule 4: T1 T2 Stored value Read(A01208,balance) 45,000 Read (A01208,Balance) 45,000 Write (A01208,Balance) 45,000 – 20,000 = 25,000 Write(A01208,Balance) 45,000 + 15,000 = 60,000 (Balance overwritten) PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science Schedule 5: : Prof Indrani Sen ,MCA,MPhil Computer Science Schedule 5: Time Interval T1 T2 T3 t1 Read A t2 Read B t3 Read A t4 Read B t5 Write A t6 Write C t7 Write B t8 Write C PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science T1 T3 T2 Write A Write A Write C Write B Algorithm to find an equivalent serial schedule :: Algorithm to find an equivalent serial schedule S2: Construct the precedence graph for the schedule S1. Randomly choose a vertex with no incoming edges. Remove the vertex and its outgoing edges from S1 and add its operations to S2. Repeat the vertex removal until there are no more vertices or a cycle occurs. Prof Indrani Sen ,MCA,MPhil Computer Science Algorithm to find an equivalent serial schedule : Converting to a serial schedule: Converting to a serial schedule Randomly chose a vertex with no incoming edges. In the figure the vertex T2 has no incoming edges so we choose the same. Remove T2 and its outgoing edges. After removing T2 the vertex with no incoming edges is T1. Thus if we serialize the schedule to T2->T1->T3 the schedule will be an equivalent serial schedule with the order of the conflicting operations preserved. Prof Indrani Sen ,MCA,MPhil Computer Science T1 T3 T2 Write A Write A Write C Write B PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science Time Interval T2 T1 T3 t1 Read A t2 Read B t3 Read A t4 Read B t5 Write C t6 Write B t7 Write A t8 Write C PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science T1 T2 Stored value Read (A00987, Balance) 78,600 Write(A00987, Balance) 78,600 – 30,000 = 48,600 Read(A00023, balance) 90,000 Write (A00023, Balance) 90,000 + 30,000 = 1,20,000 PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science T1 T2 Stored value Read (A00987, Balance) 78,600 Read(A00023, balance) 90,000 Write(A00987, Balance) 78,600 – 30,000 = 48,600 Write (A00023, Balance) 90,000 + 30,000 = 1,20,000 PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science VIEW SERIALIZABILITY : Two schedules S1 and S2 are said to be view equivalent if all of the following conditions hold:- The same sets of transactions participate in S1 and S2 and involve the same set of operations on those transactions. If a value X read by transaction T1 is written by transaction T2 in schedule S1, the same condition must hold for schedule S2. If there is a final write operation which writes the value of Y in schedule S1, then there must also be a final write operation in schedule S2 which writes the value of Y. Prof Indrani Sen ,MCA,MPhil Computer Science VIEW SERIALIZABILITY PowerPoint Presentation: For example the following is a list of operations in the transactions involved in railway ticket booking of Seat-no “S2-38”:- T1: CHECK AVAILABILITY(“S2-38”) BOOK _SEAT(“S2-38”,”RIMA NARAYAN”) T2 BOOK SEAT(“S2-38”,”TASHI JOSHI”) T3 BOOK SEAT(“S2-38”,”RINA JOSHI”) Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science T1 T2 T3 CHECK_AVAILABILITY(“S2-38”) { READ (Seat) } BOOK _SEAT(“S2-38”,”TASHI JOSHI”) { WRITE (Seat) } BOOK _SEAT(“S2-38”,”RIMA NARAYAN”) { WRITE (Seat) } BOOK_ SEAT(“S2-38”,”RINA JOSHI”) { WRITE (Seat) } PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science T1 T2 T3 PowerPoint Presentation: In the above schedule we can see that T2 and T3 perform blind writes to the data item S2-38. Hence the final write will determine the final value of the data item . That is the Seat_No S2-38 is booked in the name of the passenger “RINA JOSHI”. The schedule is view equivalent to a serial schedule T1->T2->T3 If we consider the equivalent serial schedule we find that the final booking of the Seat_No S2-38 in the schedule below is done in the name of the passenger “RINA JOSHI”.   Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science T1 T2 T3 CHECK_AVAILABILITY(“S2-38”) { READ S2-38 } BOOK _SEAT(“S2-38”,”RIMA NARAYAN”) { WRITE S2-38 } BOOK _SEAT(“S2-38”,”TASHI JOSHI”) { WRITE S2-38 } BOOK_ SEAT(“S2-38”,”RINA JOSHI”) { WRITE S2-38 } PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science Serial Schedule Serialisable Schedule Transactions are fully executed Before one transaction is fully executed another transaction begins Execution happens one at a time Execution happens concurrently No interleaving Transactions are interleaved Different orders of execution may produce different values It is equivalent to some serial schedule LOCKING techniques: : A lock guarantees exclusive use of a data item to a current transaction. In other words transaction T1 does not have any access to a data item that is currently used by T2. A transaction acquires a lock prior to the data access. The lock is released when the transaction is completed, so that another transaction can lock the data item for exclusive use. Most multiuser DBMS automatically initiate and enforce locking procedures. All lock information is managed by a lock manager which is responsible for assigning the locks to the transactions. Prof Indrani Sen ,MCA,MPhil Computer Science LOCKING techniques: SHARED LOCK and EXCLUSIVE LOCK: : When a statement reads data without making any update or modifications, its transaction obtains a shared lock on the data. Another transaction that requests reading the same data is permitted to read, but a transaction that tries to update the data will be prevented from doing so until the shared lock is released. Share lock mode allows the associated resource to be shared, among the various ongoing Transactions. But shared locks do not allow concurrent writes to a data which needs exclusive locking for write operation. Several transactions at the same time can acquire shared locks on the same data. Prof Indrani Sen ,MCA,MPhil Computer Science SHARED LOCK and EXCLUSIVE LOCK: PowerPoint Presentation: Exclusive locks lock the resource for the transaction from a specific user and prevent the associated resource from being shared. This lock mode is specially obtained to modify data. No other transactions can access the resource for read or modify before the transaction which has locked the resource releases the lock. The lock manager in the DBMS assigns locks to the transactions and records them in the data dictionary. Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: Shared Lock Exclusive Lock It is meant for read operation. It is meant for write operation. Can be acquired by multiple transactions on the same data. Can be acquired by only a single transaction on a particular data. While a data item is locked by a shared lock, it cannot be locked exclusively for write but another Shared lock can be acquired. While a data item is locked by an Exclusive lock, no shared lock or another Exclusive lock can be acquired on that data. i.e. When a data is locked for write exclusively it cannot be read or written by any other Transaction. Prof Indrani Sen ,MCA,MPhil Computer Science TWO PHASE LOCKING Protocol: : The two-phase locking protocol (2PL) compels the transaction to acquire all the locks on the data item before it unlocks them. It has two phases, (1) Growing phase where locks are acquired on resources and (2) Shrinking phase where locks are released. The two-phase locking protocol is based on two rules. Rule 1: A data object has to be locked by Exclusive or Shared lock before it can be accessed by a transaction. Rule 2: As soon as a transaction unlocks its first data object, it cannot acquire any further locks (shrinking phase). Consider the following schedules which are following Two phase Locking based on the same set of Transaction T1 and T2 Prof Indrani Sen ,MCA,MPhil Computer Science TWO PHASE LOCKING Protocol: PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science T1 T2 Stored value Request Read_Lock(A01208,Balance) (ALLOWED) Read(A01208,Balance) 45,000 Request Read_Lock (A01208,Balance) (ALLOWED) Read(A01208,Balance) 45,000 Balance=Balance-20,000 Request Write_Lock(A01208,Balance) (DENIED) Balance=Balance+15000 Request Write_Lock (A01208,Balance) (DENIED) PowerPoint Presentation: In the above schedule if the Transactions T1 and T2 have acquired a Shared lock (read lock) on a single data item, they cannot acquire a Exclusive lock on the same. So to acquire an Exclusive lock they both have to release the locks. According to Two Phase locking, once the Transaction releases a lock, it cannot acquire a lock again. So the LOST UPDATE problem does not incur in this case. Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science T1 T2 Stored value Request Read_Lock (A01208,Balance) (ALLOWED) Read(A01208,Balance) UNLOCK (A01208, Balance) 45,000 Request Write _Lock(A01208,Balance) (ALLOWED) Balance=Balance+15000 Write(A01208,Balance) 60,000 Request Read_Lock (A01208,Balance) (DENIED) WAIT(T2) ROLLBACK(T1) 45,000 UNLOCK(A01208,Balance) Request Read_Lock (A01208,Balance) (ALLOWED) Read(A01208, Balance) Balance=Balance-20000 UNLOCK (A01208, Balance) Write _Lock(A01208,Balance) (ALLOWED) Write(A01208,Balance) UNLOCK(A01208,Balance) COMMIT 25,000 PowerPoint Presentation: Consider the above figure which indicates that Transaction T1 requests for the Shared Lock, Reads the data and then acquires a consecutive Exclusive lock to update the Balance. But the Transaction T1 is then rolled back and the change is undone. In the mean time if Transaction T2 request for the shared lock it is denied access because T1 has a Exclusive Write lock acquired on the data. So T2 has to wait unless and until Transaction T1 releases the Exclusive Write Lock and then T2 can update the data Prof Indrani Sen ,MCA,MPhil Computer Science DEADLOCK: : Deadlocks occur when Transaction T1 requests for Resource R2, without releasing resource R1 while Transaction T2 has locked the resource. Again Transaction T2 requests for the resource R1 which is tied to Transaction T1, without releasing the resource R2. Both the Transactions wait infinitely for one another and is in a deadlock situation. The DBMS can go for prevention and resolving of a Deadlock. The DBMS will choose one Transaction as the "victim" and roll back that Transaction. The Transaction which will be easiest to roll back is chosen as the Victim. Prof Indrani Sen ,MCA,MPhil Computer Science DEADLOCK: PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: T1: Transfer funds 1000 from Account A01208 to Account A00987 T2: Transfer funds 5000 from Account A00987 to Account A01208 Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science Deadlock Prevention : To prevent deadlocks we should assign each transaction a priority so that the transactions do not have to wait endlessly for each other. One method to assign priority is to create a timestamp each time a new transaction begins. The priority increases inversely with the timestamp such that the oldest transaction has the highest priority. If transactions T1 request a lock which T2 is holding then the lock manager can use one of the following policies:- Prof Indrani Sen ,MCA,MPhil Computer Science Deadlock Prevention PowerPoint Presentation: Wait-Die: If T2has higher priority than T1 then T2 waits for completion of T1 else T2 dies or it is aborted. Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science t1<t2 Older Transaction Newer Transaction T1:t2 T2:t1 Request Read A Write A Wait Request Read B Write B ABORT A B PowerPoint Presentation: Wound-Wait: If T2 requesting for a resource has higher priority than T1, abort T1, otherwise T2 waits. In the wound-wait scheme, higher priority transactions never wait for lower priority transactions. So no deadlock cycle can happen. Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science Write B t1<t2 Older Transaction Newer Transaction T1:t2 T2:t1 Request Read A Write A GRANT Request Read B ABORT WAIT A B PowerPoint Presentation: In both schemes, the higher priority transaction is never aborted. When a transaction is aborted and restarted; it should be given the same timestamp that it originally had. In this way gradually it will become the oldest transaction. The wait-die scheme is non-preemptive; only a transaction requesting a lock can be aborted. While a Wound-wait scheme on the other hand is preemptive and a transaction holding all locks can be aborted. Prof Indrani Sen ,MCA,MPhil Computer Science DEADLOCK DETECTION : Deadlock detection attempts to find and resolve actual deadlocks. One such deadlock detection algorithm makes use of a wait-for graph to track which other processes are holding resources in a cyclic fashion. In a wait-for graph, transactions are represented as nodes, and an edge from Transaction T1 to Transaction T2 implies T2 is holding a resource that T1 needs and thus T1 is waiting for T2 to release its lock on that resource. When we get a cycle in our graph a deadlock is detected. Example 1: Consider the following transactions T1 and T2 T1: Lock (A) and request read B with intention to write T2: Lock (B) and request C with intention to write T3 Lock (C) and request A with intention to write Prof Indrani Sen ,MCA,MPhil Computer Science DEADLOCK DETECTION PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science T3 T1 T2

Related presentations


Other presentations created by indranisen2003

LOCKING and CONCURRENCY CONTROL2
15. 07. 2014
0 views

LOCKING and CONCURRENCY CONTROL2

Functional dependancy2
15. 07. 2014
0 views

Functional dependancy2