Mutual Exclusion in Distributed Memory Systems

Discuss mutual exclusion algorithms such as centralized,
decentralized, token-based, and distributed algorithms.

1. Mutual Exclusion in Distributed Memory Systems CS4532 Concurrent Programming Dilum Bandara [email protected] Some slides adapted from U Uthaiyashankar (WSO2) and Rajkumar Buyya’s

2. Exercise Come up with a solution to enforce following synchronization between 2 threads x & y Thread x writes to a file f . Then only thread y should read from f Now suppose x & y are 2 processes on 2 different nodes (assume a shared file system) Propose a suitable solution to achieve synchronization 2

3. Mutual Exclusion Problems Centralized algorithms for mutual exclusion Semaphores, Monitors, Condition Variables Mutual exclusion in distributed memory systems No shared memory Usually, no centralized instance similar to OS kernel that would coordinate access Based on asynchronous, usually failure-prone, network infrastructure Need a solution for distributed mutual exclusion, based solely on message passing 3

4. Mutual Exclusion Requirements Safeness property Liveness property Ordering A fairness issue Efficient 4 Source: http://pk.org/417/notes/10-mutex.html

5. Question from 2013 S7 Paper There are monkeys living on 2 very high rocks. The northern monkeys live on the northern rock that provides water but no food. Conversely, the southern monkeys live on the southern rock that provides food but no water. However, both the northern and southern monkeys have to eat and to drink! There is a small rope between the 2 rocks. The rope can carry up to MaxOnRope monkeys. Concurrent crossing in both directions is not possible. What type of a solution would you recommend for this problem? Briefly explain. [3 marks] Provide a pueudocode to solve the problem. [5 marks] 5

6. Mutual Exclusion Algorithms 6

7. Mutual Exclusion Algorithms (Cont.) Centralized algorithm Decentralized algorithm Token-based algorithm Distributed algorithm 7

8. 1. Centralized Algorithm Central server t hat grants permission to enter critical section 8 Source: http://lycog.com/distributed-systems/centralized-algorithm-mutual-exclusion-in-distributed-systems/

9. Central Server Algorithm Mutual exclusion requirements Safeness property – satisfied Liveness property – satisfied Ordering – not satisfied Due to network delay Other concerns 2 messages per request + 1 message to release Resource can’t be accessed until at least for a round trip time Delay between 1 process leaving critical section & another entering Single point of failure 9

10. 2. Decentralized Algorithm 10

11. 2. Decentralized Algorithm (Cont.) Use many replicas of resources & many coordinators To enter a critical section, a process sends a request message to coordinators & awaits reply Need majority vote from coordinators If denied, back-off & retry later Can lead to low utilization, particularly under high contention Avoids problem of single point of failure 11

12. 3. Token-Based Algorithm Pass a token around Whoever having token has exclusive access to shared resource Examples, token ring 12 Source: http://lycog.com/distributed-systems/token-ring-mutual-exclusion-in-distributed-systems/

13. Ring-Based Algorithm Mutual exclusion requirements Safeness property – satisfied Liveness property – satisfied Ordering – not satisfied Follow ring order, not order requested by processes Other concerns Token passing Worst case waiting time O ( N ) N – no of processes in the ring Delay between 1 process leaving critical section & another entering is O ( N ) 13

14. 4. Distributed Algorithm By Lamport in 1978, Improved by Ricart & Agrawala in 1981 14 Source: http://lycog.com/distributed-systems/distributed-algorithm-mutual-exclusion-distributed-systems/

15. Distributed Algorithm Mutual exclusion requirements Safeness property – satisfied Liveness property – satisfied Ordering – satisfied Events are in total order Other concerns High overhead Gaining entry requires 2( N -1) messages per request N – 1 to multicast request followed by N – 1 replies Resource can’t be accessed until at least for a round trip time Delay between 1 process leaving critical section & another entering is 1 message 15

16. Distributed Algorithm (Cont.) N points of failures Before granting access each process needs to reply If 1 process failed? Probability of failure p vs. Np N bottlenecks Each process need to respond to messages from all other processes 16

17. Mutual Exclusion Algorithm Comparison Comparison assumes that messages are passed sequentially (sent 1 after another) over a network 17

18. Contention vs. Token Based Contention Competition among processes May need to retry repeatedly No token Voting improves fault tolerance What if no majority? More complicated to implement Token Avoid deadlocks Avoid starvation by efficient organization of processes Lost token? How to create a new one? How to create only 1 token? 18