Mutual Exclusion

Lecture Notes

Distributed Mutual Exclusion

• Distributed processes need to coordinate access to shared resources, variables, etc. in a critical section (CS) so that only one process at a time can be in the CS.

• In a distributed system
• No shared variables (semaphores)
• No local kernel that coordinates access to resources
• Message passing is the sole means for implementing distributed mutual exclusion
• Algorithms must del with unpredictable message delays and incomplete knowledge of the system state.

• Assumptions
• Only one CS
• System is asynchronous
• msg delivery is reliable and msgs are delivered intact
• processes do not fail

• Application-level protocol
• enter()
• enter critical section
• block if necessary
• resourceAccess()
• access shared resources in CS
• exit()
• leave CS
• other processes may now enter

Properties for Mutual Exclusion

• ME1: (Safety)
• at most one process may execute in the CS at a time

• ME2: (Liveness)
• Requests to enter and exit the CS eventually succeed (i.e., no deadlock or starvation)

• ME3:( Ordering)
• if one request to a resource happened before another request then should enter the CS before

Evaluation of Mutual Exclusion Algorithms

• Bandwidth consumption
• number of msg required per CS execution, i.e.;
• number of msg that it takes to enter the CS + number of msg that it takes to exit the CS

• Client delay
• the delay incurred by a process at each enter and exit operation

• Throughput
• Rate at which the processes can access the CS
• = avg. time spent in CS
• = Synchronisation Delay = Time interval between one process exiting the CS and the next process entering it (when there is only on process waiting)

Comparisons and Details of 4 Mutual Exclusion Algorithms

FYI: Hover on an algorithm then click "OPEN", you could see the details of the algorithm