In this tutorial you are going to learn about Mutual Exclusion in Distributed System.
Introduction
When a process is accessing a shared variable, the process is said to be in a critical section (CS). No two process can be in same critical condition at the same time. This is called mutual exclusion.
Mutual exclusion will ensure that there will be no other process that should enter the critical section i.e. uses the already shared resources at the same time.
Eg: When both the processes P1 and P2 are asking for same item at the same time from the system, it is said to be in critical section.
This algorithm provides timestamp for distributed mutual exclusion.
Distributed Mutual Exclusion
Assume there is an agreement on how a resource is identified.
- Pass identifier with the requests.
- Create an algorithm to allow a process to obtain exclusive access to a resource.
At the sender side:
- When a process want to access a shared resource, it builds a message containing the name of the resource, it's process number and the current time (logical time).
- Then it sends the messages to all other processes including itself.
At the receiver side:
- When a process receives a request message from another process, the action it takes depends on its own state with respect to the resource named in the message.
At the receiver side there are three different cases. We will look to the cases one by one.
- If the receiver is not accessing the resource and does not want to access it, it simply sends back an OK message to the sender.
- If the receiver is already accessing the shared resource, it simply does not reply. Instead, it queues the request of other processes.
- If the receiver wants to access the resource but has not yet done. So, it compares the timestamp of the incoming message with the one contained in the message that it has sent to everyone.
- The lowest one always wins.
The different algorithms based on message passing to implement mutual exclusion in distributed system are:
- Centralized algorithm
- Token Ring algorithm
- Distributed algorithm
- Decentralized algorithm
Centralized Algorithm
- In a centralized algorithm, one process is elected as the coordinator.
- Whenever a process wants to access a shared resource, it sends request to coordinator to ask for permission.
- Coordinator checks whether the queue is empty or not, if the queue is empty it sends the message.
- Coordinator may queue the requests.
- Coordinator takes only one requests at a time, until the queue is not empty. It won’t reply to any other permission asked by any other processes.
- Mutual understanding will be there between the processes.
Requirements of centralized mutual exclusion algorithms :
- The primary goal of the centralized algorithms is to request only one access to the critical section at a time.
- Freedom from the deadlocks.
- Freedom from starvation.
- Fairness.
- Fault tolerance.
Disadvantage of the Distributed Algorithm
- It is comparatively slow.
- The algorithm is more complex to understand.
- More expensive.
- It is less robust then the original centralized one.
This article on Mutual Exclusion in Distributed System is contributed by Hemalatha P. If you like TheCode11 and would like to contribute, you can also write your article and mail to thecode11info@gmail.com