Distributed Mutual Exclusion and Distributed Deadlock Detection

Distributed Mutual Exclusion: Classification of distributed mutual exclusion, requirement of mutual exclusion theorem, Token based and non token based algorithms. Distributed Deadlock Detection: system model, resource Vs communication deadlocks, deadlock prevention, avoidance, detection & resolution, centralized dead lock detection

1. Distributed Systems Shikha Gautam Assistant Professor KIET, Ghaziabad

2. UNIT-2 Distributed Mutual Exclusion: Classification of distributed mutual exclusion, requirement of mutual exclusion theorem, Token based and non token based algorithms Distributed Deadlock Detection: system model, resource Vs communication deadlocks, deadlock prevention, avoidance, detection & resolution, centralized dead lock detection

3. Distributed Mutual Exclusion

4. Mutual exclusion Mutual exclusion makes sure that concurrent process access shared resources (or data) in a serialized way. If a process , say P i , is executing in its critical section, then no other processes can be executing in their critical section.

5. Mutual Exclusion: A Centralized Algorithm Process 1 asks the coordinator for permission to enter a critical region. Permission is granted Process 2 then asks permission to enter the same critical region. The coordinator does not reply. When process 1 exits the critical region, it tells the coordinator, when then replies to 2

6. Mutual exclusion: Distributed S ystems All nodes have equal amount of information, on average each node has only a partial picture of the total system and must make decisions based on this information. All nodes bear equal responsibility for the final decision. All nodes expend equal effort, on average, in effecting a final decision. Failure of a node, in general, does not result in a total system collapse. There exits no system wide common clock with which to regulate the time of events.

7. Mutual exclusion in single-computer vs. distributed systems: In a single computer system, the status of a shared resource and the status of users is readily available in the shared memory, and the solutions to the mutual exclusion problem can be easily implemented using shared variable(e.g. semaphores). In DS both shared resources and the users may be distributed and shared memory does not exist. Consequently, approaches based on shared variable are not applicable to DS and approaches based on message passing must be used. The problem of mutual exclusion becomes much more complex in DS because of the lack of both shared memory & a common physical clock &because of unpredictable message delays.

8. General System Model At any instant, a site may have several request for CS.A site queues up these requests and serves them one at a time. A site can be in one of the following three states: Requesting State: blocked until granted access, cannot make additional requests for CS . Executing State: using the CS. Idle State : N either requesting nor executing CS. T he site is executing outside its CS. Note: In the token-based algorithms, a site can also be in a state where a site holding the token is executing outside the CS. Such a state is referred to as an idle token state .

9. Freedom from Deadlock: Two or more sites should not endlessly wait for messages that will never arrive. Mutual Exclusion: Requirements Deadlock  is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.

10. Freedom from Starvation: A site should not be forced to wait indefinitely to execute CS while other sites are repeatedly executing CS. that is, every requesting site should get an opportunity to execute CS in a finite time. Fairness: Fairness dictates that requests must be executed in the order they are made(or the order in which they arrive in the system). Fault Tolerance: A mutual exclusion algorithm is fault-tolerate if in the wake of a failure, it can reorganize itself so that it continues to function without any disruptions. Mutual Exclusion: Requirements

11. Mutual Exclusion Algorithms Non-token based Algorithms : A site/process can enter a critical section when an assertion (condition) becomes true . Algorithm should ensure that the assertion will be true for only one site/process at a time. These algorithms require two or more successive rounds of message exchanges among the sites.

12. 2. Token based Algorithms : A unique token (PRIVILEGE message) is shared among cooperating sites/processes. A site is allowed to enter its CS if it possesses the token and it continues to hold the token until the execution of the CS is over. Need to take care of conditions such as loss of token, crash of token holder, possibility of multiple tokens, etc. These algorithms essentially differ in the way a site carries out the search for the token. Mutual Exclusion Algorithms

13. Performance metrics of Distributed Mutual Exclusion : Number of messages necessary per CS invocation. Synchronization delay : T he time required after a site leaves the CS and before the next site enters the CS. Re sponse time : The time interval a request waits for its CS execution to be over after its request messages have been sent out. Sy stem throughput : The rate at which the system executes requests for the CS. S ystem throughput = 1/ ( sd + E ) Where, sd is the synchronization delay and E is the average critical section execution time.

14. Performance metrics Last site exits CS Next site enters CS Synchronization delay Time Time CS execution time Response Time CS Request Its Request The site enters The site exits Arrives message sent out the CS the CS

15. Non-token-based Algorithms A site communicates with a set of other sites to arbitrate who should execute the CS next. For a site Si, request set Ri contains ids of all those sites from which site Si must acquire permission before entering the CS. These algorithms use timestamps to order requests for CS and to resolve conflicts between simultaneous requests for the CS. Each request for the CS gets a timestamp, and smaller timestamp requests have priority over larger timestamp requests.

16. 1. Lamport’s Algorithm Lamport proposed an algorithm which was based on his clock synchronization scheme. In Lamport messages to be delivered in the FIFO order between every pair of sites. Notations : Si: Site i Ri : Request queue, containing the ids of all Site from which permission must be received before accessing CS. Ri = {S1, S2, …, Sn }, maintained at each Si . Every site S i keeps a request_queue , which contains mutual exclusion requests ordered by their timestamps.

17. Three steps: Requesting the CS: Send REQUEST( tsi , i ): When a site S i wants to enter the CS, it sends a REQUEST(ts i ,i) message to all the sites in its request set R i and places the request on request_queue i ,. ((ts i , i) is the timestamp request message). When a site Sj receives the REQUEST (tsi,i) message from site Si, it returns a timestamped REPLY message to Si and places site Si’s request in request_queue j . Si Sj ( tsi,i ) Si Sj Timestamp reply message

18. 2. Executing the CS: Site Si enters the CS when the two following conditions hold: Si has received a message with timestamp larger than ( tsi , i) from all other sites. Si’s request is at the top of request_queuei . 3. Releasing the CS: Exiting CS: Site Si removes its request from the top of its request queue and sends a time stamped RELEASE message to all the sites in its request set. When a site Sj receives a RELEASE message from site Si, it removes Si’s request from its request queue.

19. Performance Requires 3(N-1) messages per CS invocation: = (N-1) REQUEST, (N-1) REPLY, and (N-1) RELEASE messages. Synchronization delay is T.

20. Lamport’s Algorithm: Example(1) (2,1) (1,2) S1 S2 S3 (1,2) (2,1) (1,2) (2,1) S1 S2 S3 Step 1: Step 2: S2 enters CS (1,2) (2,1)

21. Lamport’s : Example… (1,2) (2,1) (1,2) (2,1) S1 S2 S3 Step 3: (1,2) (2,1) S2 leaves CS (1,2) (2,1) (1,2) (2,1) S1 S2 S3 Step 4: (1,2) (2,1) S1 enters CS (2,1) (2,1) (2,1)

22. Lamport’s Algorithm: Example(2)

23. Optimization Can be optimized to require between 3(N-1) and 2(N-1) messages per CS execution by suppressing REPLY messages in certain cases: E.g. suppose site Sj receives a REQUEST message from site Si after it has sent its own REQUEST messages with timestamp higher than the timestamp of site Si’s request. In this case, site Sj need not send a REPLY message to site Si.

24. 2. THE RICART-AGRAWALA ALGORITHM The Ricart Agrawala algorithm is an optimization of Lamport’s algorithm. It dispenses with RELEASE messages by cleverly merging them with the REPLY messages. Each process pi maintains the Request-Deferred array, RDi , the size of which is the same as the number of processes in the system. Initially , ∀i ∀j: RDi [j]=0. Whenever pi defer the request sent by pj , it sets RDi [j]=1 and after it has sent a REPLY message to pj , it sets RDi [j]=0.

25. Three Steps: Requesting the critical section : When a site Si wants to enter the CS, it sends the time stamped REQUEST message to all sites. Sj sends REPLY to Si, if Sj is not requesting nor executing CS If Sj is requesting CS and Si’s time stamp is smaller than its own request. Otherwise , the reply is deferred and Sj sets RDj [i]=1

26. Executing the CS: Site Si enters the CS after it has received REPLY messages from all the sites in its request set. 3. Releasing the CS: When site Si exits the CS, it sends all the deferred REPLY messages: ∀j if RDi [j]=1, then send a REPLY message to Sj and set RDi [j]=0. i.e., a site’s REPLY messages are blocked only by sites with smaller time stamps

27. Performance: 2(N-1) messages per CS execution. = (N-1) REQUEST + (N-1) REPLY. Synchronization delay: T

28. Ricart-Agrawala : Example(1) (2,1) (1,2) S1 S2 S3 (2,1) S1 S2 S3 Step 1: Step 2: S2 enters CS

29. Ricart-Agrawala: Example… (2,1) S1 S2 S3 Step 3: S1 enters CS S2 leaves CS

30. Ricart-Agrawala : Example(2)

31. Maekawa’s algorithm was the first quorum-based mutual exclusion algorithm. A site does not request permission from all other sites, but only from a subset of the sites . The request set of sites are chosen such that ∀ I,∀ j : 1 ≤ i, j ≤ N :: Ri ∩ Rj != Φ. Consequently, every pair of sites has a site which mediates conflicts between that pair. A site can send only one REPLY message at a time, i.e., a site can send a REPLY message only after receiving a RELEASE message for the previous REPLY message. Maekawa’s Algorithm

32. A simple protocol works as follows: Let ‘a’ is a site in quorum ‘A’. If ‘a’ wants to invoke mutual exclusion, it requests permission from all sites in its quorum ‘A’. Every site does the same to invoke mutual exclusion . Due to the Intersection Property, quorum ‘A’ contains at least one site that is common to the quorum of every other site. These common sites send permission to only one site at any time. Thus, mutual exclusion is guaranteed.

33. With each process i, associate a subset R i . Divide the set of processes into subsets that satisfy the following two conditions: i ∈ R i ∀ i,j : 0≤ i,j ≤ n-1 | R i ⋂ R j ≠ ∅ Main idea . Each process i is required to receive permission from R i only . Correctness requires that multiple processes will never receive permission from all members of their respective subsets. 0,1,2 1,3,5 2,4,5 R R 1 R 2

34. Maekawa’s algorithm: Example Example . Let there be seven processes 0, 1, 2, 3, 4, 5, 6 S = {0, 1, 2} S 1 = {1, 3, 5} S 2 = {2, 4, 5} S 3 = {0, 3, 4} S 4 = {1, 4, 6} S 5 = {0, 5, 6} S 6 = {2, 3, 6}

35. {Life of process i} 1. Send timestamped request to each process in S i . 2. Request received  send reply to process with the lowest timestamp . Thereafter, " lock " (i.e. commit ) yourself to that process, and keep others waiting. 3 . Enter CS if you receive an reply from each member in S i . 4 . To exit CS, send release to every process in S i . 5 . Release received  unlock yourself. Then send reply to the next process with the lowest timestamp. S = {0, 1, 2} S 1 = {1, 3, 5} S 2 = {2, 4, 5} S 3 = {0, 3, 4} S 4 = {1, 4, 6} S 5 = {0, 5, 6} S 6 = {2, 3, 6} Maekawa’s algorithm: Example

36. At most one process can enter its critical section at any time. Let i and j attempt to enter their Critical Sections S i ∩ S j ≠ ∅ implies there is a process k ∊ S i ⋂ S j Process k will never send reply to both . S = {0, 1, 2} S 1 = {1, 3, 5} S 2 = {2, 4, 5} S 3 = {0, 3, 4} S 4 = {1, 4, 6} S 5 = {0, 5, 6} S 6 = {2, 3, 6} Maekawa’s algorithm: Example

37. Requesting CS: Si sends REQUEST(i) to sites in Ri . Sj sends REPLY to Si if Sj has NOT sent a REPLY message to any site after it received the last RELEASE message. Otherwise, queue up Si’s request. Executing CS : after getting REPLY from all sites in Ri . Releasing CS : send RELEASE(i) to all sites in Ri Any Sj after receiving RELEASE message, send REPLY message to the next request in queue. If queue empty, update status indicating receipt of RELEASE.

38. Performance

39. A unique token is shared among all sites. A site is allowed to enter its CS if it possesses the token Token based algorithms use “sequence number” instead of timestamps. Every request for the token contains a sequence number and sequence number of site advances independently. A site increments its sequence number every time it makes the request for the token. A primary function of the sequence number is to distinguish between old and current request. Token based algorithm ensure that mutual exclusion is enforced. T oken-based Algorithms

40. Suzuki- Kasami’s Broadcast Algorithm A unique token is shared among all processes. If a process possesses the token, it is allowed to enter its critical section. The token will be sent after leaving the critical section. If a site wants to enter the CS and it does not have the token, it broadcasts a REQUEST message for the token to all other sites. A site which possesses the token sends it to the requesting site upon the receipt of its REQUEST message. If a site receives a REQUEST message when it is executing the CS, it sends the token only after it has completed the execution of the CS.

41. The Main idea Completely connected network of processes There is one token in the network. The holder of the token has the permission to enter CS. Any other process trying to enter CS must acquire that token. Thus the token will move from one process to another based on demand. I want to enter CS I want to enter CS

42. Process i broadcasts (i, num ) Each process maintains - an array req : req [j] denotes the sequence no of the latest request from process j Additionally, the holder of the token maintains - an array last : last[j] denotes the sequence number of the latest visit to CS for process j. - a queue Q of waiting processes req : array[0..n-1] of integer last : array [0..n-1] of integer Sequence number of the request req req req req req last queue Q

43. Suzuki- Kasami’s Broadcast Algorithm: Example 2 1 3 4 req=[1,0,0,0,0] last=[0,0,0,0,0] req =[1,0,0,0,0] req=[1,0,0,0,0] req=[1,0,0,0,0] req=[1,0,0,0,0] initial state: process 0 has sent a request to all, and grabbed the token

44. 2 1 3 4 req=[1, 1,1 ,0,0] last=[0,0,0,0,0] req=[1, 1,1 ,0,0] req=[1, 1,1 ,0,0] req=[1, 1,1 ,0,0] req=[1, 1,1 ,0,0] 1 & 2 send requests to enter CS

45. 2 1 3 4 req=[1, 1,1 ,0,0] last=[ 1 ,0,0,0,0] Q=(1,2) req=[1, 1,1 ,0,0] req=[1, 1,1 ,0,0] req=[1, 1,1 ,0,0] req=[1, 1,1 ,0,0] 0 prepares to exit CS

46. 2 1 3 4 req=[1, 1,1 ,0,0] req=[1, 1,1 ,0,0] last=[ 1 ,0,0,0,0] Q=(2) req=[1, 1,1 ,0,0] req=[1, 1,1 ,0,0] req=[1, 1,1 ,0,0] 0 passes token (Q and last) to 1

47. 2 1 3 4 req=[ 2 , 1,1 , 1 ,0] req=[ 2 , 1,1 , 1 ,0] last=[ 1 ,0,0,0,0] Q=(2,0,3) req=[ 2 , 1,1 , 1 ,0] req=[ 2 , 1,1 , 1 ,0] req=[ 2 , 1,1 , 1 ,0] 0 and 3 send requests

48. 2 1 3 4 req=[ 2 , 1,1 , 1 ,0] req=[ 2 , 1,1 , 1 ,0] req=[ 2 , 1,1 , 1 ,0] last=[ 1 , 1 ,0,0,0] Q=(0,3) req=[ 2 , 1,1 , 1 ,0] req=[ 2 , 1,1 , 1 ,0] 1 sends token to 2

49. Performance

50. Raymond’s Tree-based Algorithm

51. Sites are logically arranged as a directed tree such that the edges of the tree are assigned direction toward the site i.e. root of the tree that has the token. Every site has a local variable holder that points to an immediate neighbor node on a directed path to the root node. If we follow holder variable at sites, every site has a directed path leading to the site holding the token. At root site holder points to itself. Every sites keeps a FIFO queue called request_q, which stores the request of those neighboring sites that have sent a request to this site but have not yet been sent the token.

52. Singhal’s Heuristic Algorithm

53. Distributed Deadlock Detection

54. The Deadlock problem In a computer system deadlocks arise when members of a group of processes which hold resources are blocked indefinitely from access to resources held by other processes within the group. “A deadlock is a state where a set of processes request resources that are held by other processes in the system.”

55. Deadlock example: The dining philosophers problem is a classic example of deadlock. Each philosopher picks up his or her left fork and waits for the right fork to become available, but it never does.

56. A Communication Deadlock occurs when process A is trying to send a message to process B, which is trying to send a message to process C which is trying to send a message to A. A R esource Deadlock occurs when processes are trying to get exclusive access to devices, files, locks, servers, or other resources. We will not differentiate between these types of deadlock since we can consider communication channels to be resources.

57. Conditions for deadlocks Mutual exclusion : No resource can be shared by more than one process at a time . Hold and wait : There must exist a process that is holding at least one resource and is waiting to acquire additional resources that are currently being held by other processes. No preemption : A process cannot be preempted. Circular wait : There is a cycle in the wait-for graph. All four conditions should satisfy for deadlock to be happen.

58. Graph-theoretic models Wait-for graph. Resource-allocation graph.

59. Figure 1 shows a WFG, where process P11 of site 1 has an edge to process P21 of site 1 and P32 of site 2 is waiting for a resource which is currently held by process P21 . At the same time process P32 is waiting on process P33 to release a resource. If P21 is waiting on process P11, then processes P11, P32 and P21 form a cycle and all the four processes are involved in a deadlock depending upon the request model.

60. Prevention : Preventing any one of the condition(ME, H&W,CW,NP) to occur. Avoidance : S afe/Unsafe State. Detection : Allow deadlock to occur, if detected then correct using one of the following methods- Process Termination. Resource Preemption.

61. Deadlock prevention Provide all resource at once. Preventing any one of the condition(ME, H&W,CW,NP) to occur. inefficient , can become deadlocked at resource acquiring phase, resource requirements are unpredictable -- not an efficient, universal solution . Deadlock avoidance A resource is granted to a process if the resulting state is safe Every site has to maintain the global state. The checking for a safe state must be done with mutual exclusion The number of processes and resources in a distributed system is large Not a practical solution. Deadlock detection deadlock detection can be proceed concurrently with normal activities This is the usual approach .

62. In a distributed system deadlock can neither be prevented nor avoided as the system is so vast that it is impossible to do so. Therefore , only deadlock detection can be implemented. The techniques of deadlock detection in the distributed system require the following:

63. There are three approaches to detect deadlocks in distributed systems. They are as follows: Centralized approach : There is only one site is responsible resource to detect deadlock using Global wait for graph. The advantage of this approach is that it is simple and easy to implement. W hile the drawbacks include excessive workload at one node, single point failure (that is the whole system is dependent on one node if that node fails the whole system crashes) which in turns makes the system less reliable.

64. Distributed approach: In the distributed approach different nodes work together to detect deadlocks. No single point failure as workload is equally divided among all nodes. Difficult to design due to lack of global shared memory. Site may collectively report for global cycle after seeing its segment at different instance. Hierarchical approach: This approach is the most advantageous approach. Sites are arranged in hierarchical fashion and a site detect deadlocks involved in its descendant sites. It is the combination of both centralized and distributed approaches of deadlock detection in a distributed system.

65. Centralized Deadlock‐Detection Algorithms The Completely Centralized Algorithm The Ho- Ramamoorthy Algorithms: – The Two The Two-Phase Algorithm – The One The One-phase Algorithm

66. 1. Completely Centralized Algorithm

67. 2. The Ho- Ramamoorthy Algorithms:

68. Distributed Deadlock Detection Algorithms A Path-Pushing Algorithm Edge-Chasing Algorithm

69. 1. A Path-Pushing Algorithm

70. In this algorithm information about wait for dependency is propagated in the form of paths. Each site maintains its local WFG. In this process local WFG includes an additional nodes Pex : Pi Pex exist in graph if Pi is waiting for resources residing at another site and held by another process. Pex Pj exist in graph if a process at another site is waiting for resources currently being held by Pj in this local site. If local WFG contains a cycle that does not involve node Pex then system is in deadlock state.

71. If cycle involve Pex then, there is possibility of deadlock. Suppose the WFG at local site Si: Pex Pi1Pi2Pi3…. PinPex This indicates that Pin is waiting for resources located in some other site say Sj . Site Si sends a dead lock detection message to Sj containing information about the cycle. When Sj receives this message, it updates its local WFG with new information and searches newly constructed WFG for cycle not including Pex . If deadlock found, take appropriate action to recover. If not found, transmit a deadlock detection message.

72. 2. Edge-Chasing Algorithm

73. A probe is a triplet ( i ,j,k ) denoting that it belong to deadlock detection initiated for process Pi and it is being sent by the home site of process Pj to home site of process Pk. A probe message travel along the edge of the global Transaction WFG. A deadlock is detected when a probe message returns to its initiating process.