Concurrency Control in Distributed Systems.pptx

Parallel and distributed computing

1. Concurrency Control in Distributed Systems Definition, Working & Algorithms

2. Definition Concurrent  means happening at the same time.  Concurrency ,  concurrent , or  concurrence  may refer to: Concurrency (computer science) , the property of program, algorithm, or problem decomposition into order-independent or partially-ordered units  without affecting the outcome. Concurrent computing , the overlapping execution of multiple interacting computational tasks.

3. Objectives Throughput: Number of transactions processed per unit time E.g. 1 million transactions per second Maximum transaction throughput (work perform) while preventing interference among multiple users. |Efficient use of resources Advantages Waiting time will be decreased. Response time will decrease. Resource utilization will increase. System performance & Efficiency is increased.

4. Main problems in using Concurrency The problems which arise while using concurrency are as follows Updates will be lost  − One transaction does some changes and another transaction deletes that change. One transaction nullifies the updates of another transaction. Uncommitted Dependency or dirty read problem  − One variable has updated in one transaction, at the same time another transaction has started and deleted the value of the variable there the variable is not getting updated or committed that has been done on the first transaction this gives us false values or the previous values of the variables this is a major problem. Inconsistent retrievals  − One transaction is updating multiple different variables, another transaction is in a process to update those variables, and the problem occurs is inconsistency of the same variable in different instances.

5. Algorithms (Concurrency Control Mechanisms) Two-Phase L ocking (2PL) algorithms Lock guaranties exclusive use of data items to a current transaction. It first accesses the data items by acquiring a lock, after completion of the transaction it releases the lock. Timestamps ordering( T/O ) a lgorithms Whatever transaction we are doing it stores the starting time of the transaction and denotes a specific time. O ptimistic algorithms It is based on the assumption that conflict is rare and it is more efficient to allow transactions to proceed without imposing delays to ensure serializability.

6. Locking R/W locks The lock Manager Responsible to maintain the list of locked files Shared Locks Transaction can read only the data item values Exclusive Locks Used for both read and write data item values

7. Two-Phase Locking

8. Strict Two-Phase Locking

9. Two-Phase locking can lead to deadlocks If two processes each try to acquire the same pair of locks but in the opposite order, a deadlock may result. Hold and wait cycle. Deadlock detection T. sec / Timeout scheme can be used.

10. Optimistic Concurrency Control Second Approach to handling multiple transactions at the same time is optimistic concurrency control The idea behind this technique is surprisingly simple: just go ahead and do whatever you want to, without paying attention to what anybody else is doing. If there is a problem, worry about it later.

11. Optimistic Concurrency Control What Optimistic concurrency control does is: Keep track of which files have been read and written At the point of committing, it checks all other transactions to see if any of its files have been changed since the transaction started. If so, the transaction is aborted. If not, it is committed.

12. Optimistic Concurrency Control Optimistic Concurrency control fits best with the implementation based on private workspaces. That way, each transaction changes its files privately, without interference from the others. At the end, the new files are either committed or released.

13. Advantages / Disadvantages of (OCC) Advantages : Deadlock Free Maximum parallelism Disadvantages: it may fail , in which case the transaction has to be run all over again Under condition of heavy load the probability of failure may go up

14. Program Demo Talk is cheap, show me the code.

15. Summary(Mind-map)

16. Any question?

17. References Philip A. Bernstein , Vassos Hadzilacos , Nathan Goodman (1987):  Concurrency Control and Recovery in Database Systems  (free PDF download), Addison Wesley Publishing Company, 1987,  ISBN   0-201-10715-5 Concurrency Control from tutorialspoint.com wikipedia.org/wiki/ Concurrency_control Nancy Lynch , Michael Merritt, William Weihl , Alan Fekete (1993):  Atomic Transactions in Concurrent and Distributed Systems  ,  Morgan Kaufmann  (Elsevier), August 1993,  ISBN   978-1-55860-104-8 ,  ISBN   1-55860-104-X Yoav Raz  (1992):  "The Principle of Commitment Ordering, or Guaranteeing Serializability in a Heterogeneous Environment of Multiple Autonomous Resource Managers Using Atomic Commitment."  ( PDF ), Proceedings of the Eighteenth International Conference on Very Large Data Bases (VLDB), pp. 292-312, Vancouver, Canada, August 1992. (also DEC-TR 841,  Digital Equipment Corporation , November 1990)