Chapter 18 2 Distributed Coordination Chapter 18 Distributed Coordination Chapter 18 1 Event Ordering Mutual Exclusion Atomicity Chapter 18 2 Concurrency Control Deadlock Handling Chapter 18 3 Deadlock Prevention Election Algorithms Reaching Agreement Operating System Concepts 18 2 Silberschatz Galvin and Gagne 2005 Chapter Objectives To show how some currency control schemes can be modified for use in a distributed environment To present schemes for handling deadlock prevention deadlock avoidance and deadlock detection in a distributed system Operating System Concepts 18 3 Silberschatz Galvin and Gagne 2005 Concurrency Control Locking Protocols using replicated and non replicated schemes Time Stamping Operating System Concepts 18 4 Silberschatz Galvin and Gagne 2005 Concurrency Control Background While concurrency issues from earlier chapters apply the issue of distributed control significantly complicates these testy issues To begin with we must recognize that Transactions may be either local or global Clearly local considerations are simpler to deal with But with global transactions we must modify the centralized concurrency schemes to accommodate the distribution of transactions To put transactions into perspective A Local transaction only executes at one site A Global transaction executes at several sites As we ve had in the past we have Transaction Managers that are responsible for coordinating execution of transactions that access data at all local sites Operating System Concepts 18 5 Silberschatz Galvin and Gagne 2005 Concurrency Control with Locking Protocols Can use a two phase locking protocol that we ve discussed before in a distributed environment by changing how the lock manager is implemented We have two primary implmentation schemes Operating System Concepts Non replicated schemes and Replicated schemes We will first discuss the non replicated scheme 18 6 Silberschatz Galvin and Gagne 2005 Non Replicated Schema This is the relatively easy case Here each site maintains a local lock manager which administers lock and unlock requests for those data items stored in that site Simple implementation involves two message transfers for handling lock requests and a single message transfer for unlock requests When a transaction wishes to lock some data item Q at some site S it merely sends a message to the lock manager at S a request to a lock If site S can comply the lock manager replies citing lock has been granted Clearly if the lock cannot be granted request is delayed until lock can be granted This is a simple scheme conceptually and implementation As stated only two plus one message transfers are needed Deadlock can be much more complex since lock and unlock requests are not made at a single site Much more ahead on this one This is the only non replicated scheme we will discuss here Operating System Concepts 18 7 Silberschatz Galvin and Gagne 2005 Replicated Schemes Single Coordinator Approach In this approach a single lock manager resides in a single chosen site that site All lock and unlock requests are made a So when some transaction needs a lock a data item it sends a request to this single site where the lock manager at this site determines if lock can be granted If so it sends a positive reply back to the site requesting the lock If not the request is delayed at which time a postive message is then transmitted to the requesting site Since we have replication the requesting site can read data item from any site With a write operation however all sites where the replicas are found must be involved in the writing issues more Operating System Concepts 18 8 Silberschatz Galvin and Gagne 2005 Replicated Schemes Single Coordinator Approach Now here s the deal On the plus side We clearly have simple implementation and simple deadlock handling On the negative side It is clear that there is a real possibility of bottleneck because all requests must go through this central site Also a biggee a single central site is vulnerable to loss of concurrency controller if this single site fails Compromise Multiple coordinator approach distributes lock manager function over several sites Helps bottleneck problem but significantly impacts the deadlock problem because both lock and unlock requests are not made at a single site Much more ahead on a major section in this chapter addressing deadlock Operating System Concepts 18 9 Silberschatz Galvin and Gagne 2005 Replicated Schemes the Majority Protocol Similar to the non replicated scheme but here we have a lock manager at each site controlling locks for all data or data replicas stored at that site So when some transaction needs to lock a data item replicated at several different sites lock requests must be sent to more than one half of the number of sites where the data item is stored Each lock manager must then determine if the lock can be granted The transaction cannot continue until a majority of locks are granted Clearly if a lock cannot be granted at some site S then positive responses will be delayed until the requests can be granted The Majority Protocol avoids drawbacks of central control by dealing with replicated data in a decentralized manner but Much more complicated to implement and Deadlock handling algorithms must clearly be modified Operating System Concepts 18 10 Silberschatz Galvin and Gagne 2005 Replicated Schemes The Biased Protocol Similar to majority protocol but requests for shared locks prioritized over requests for exclusive locks We have a lock manager at each site manages all locks at that site but differently Shared Locks When one site needs a lock for a data item it simply requests a lock for that item from any site having that item Exclusive locks Request for a lock must be sent to the lock manager for each site having a replica As expected permissions cannot be granted if a lock is tied up and the granting is delayed until the request can be honored Net result is less overhead on read operations than in majority protocol Would appear that a shared lock is sufficient here But additional overhead on writes Good approach where we anticipate a lot more reads than writes For exclusive locks there must be a great deal of additional overhead Like majority protocol deadlock handling is complex later on deadlock Operating System Concepts 18 11 Silberschatz Galvin and Gagne 2005 Replicated Locks The Primary Copy Another approach sees one of the replicated sites as the primary copy This copy must reside at