More Related Content
What's hot (20)
Similar to Distributed Mutual exclusion algorithms (20)
More from MNM Jain Engineering College (17)
Recently uploaded (20)
Distributed Mutual exclusion algorithms
- 1. Clock Synchronization Physical Clocks 1 The time difference between two computers is known as drift. Clock drift over time is known as skew. 2 Logical Clocks Often, it is not necessary for a computer to know the exact time, only relative time. This is known as “logical time”. Logical time is not based on timing but on the ordering of events. Non-interacting processes cannot share a logical clock. Computers generally obtain logical time using interrupts to update a software clock. The more interrupts (the more frequently time is updated), the higher the overhead.
- 2. Process Synchroniztion Process synchronization is the set of techniques that are used to coordinate execution among processes. For example, a process may need to run to a certain point, at which point it will stop and wait for another process to finish certain actions. A shared resource, such as a file or fields in a database, may require exclusive access and processes have to coordinate among themselves to ensure that access to the resource is fair and exclusive. Distributed processes often need to coordinate their activities. If a collection of processes share a resource or collection of resources, then often mutual exclusion is required to prevent interference and ensure consistency when accessing the resources. Critical Section (CS) enter(): enter a critical section - block if necessary. resourceAccess(): access shared resources in critical section. exit(): leave critical section - other processes may now enter. In computer science, mutual exclusion (MUTEX) refers to a way of making sure that if one process is using shared modifiable data or resources then the other processes will be excluded from doing the same thing at the same time. A number of mutual exclusion algorithms are available in the literature, with different performance metrics and with different techniques. The Selection for a “good” mutual exclusion algorithm is a key point. These mutual exclusion algorithms can be broadly classified into token and non-token based algorithm. Distributed Mutual Exclusion Any viable mutual exclusion algorithm must satisfy three properties: Safety At any instant, only one process may hold the resource. Liveness Processes should not wait forever for messages that will never arrive. Ordering If one request to enter the CS happened-before another, then entry to the CS is granted in that order.
- 3. 1. Token based approaches A unique token (PRIVILEGE msg) is shared among the processes. A process is allowed to enter its CS if it possesses the token. Centralized Algorithm Ring Based Algorithms Centralized Algorithm One process is elected as the coordinator. When any process wants to enter a critical section, it sends a request message to the coordinator stating which critical section it wants to access. If no other process is currently in that critical section, the coordinator sends back a reply granting permission. When the reply arrives, the requesting process enters the critical section. If another process requests access to the same critical section, it is ignored or blocked until the first process exits the critical section and sends a message to the coordinator stating that it has exited. Ring Based Algorithms Another approach is to create a logical or physical ring. Each process knows the identity of the process succeeding it. When the ring is initialized, Process 0 is given a token. The token circulates around the ring in order, from Process k to Process k + 1. When a process receives the token from its neighbor, it checks to see if it is attempting to enter a critical section. If so, the process enters the critical section and does its work, keeping the token the whole time.
- 4. After the process exits the critical section, it passes the token to the next process in the ring. It is not permitted to enter a second critical section using the same token. If a process is handed a token an is not interested in entering a critical section, it passes the token to the next process. Distributed Algorithms It is often unacceptable to have a single point of failure. Therefore researchers continue to look for distributed mutual exclusion algorithms. 2. Non Token based approaches Two or more successive rounds of messages are exchanged among the processes to determine which process will enter the CS next. Lamport’s mutual exclusion algorithm • In this algorithm, every process in the group maintains a request queue. There is a list of processes (p1,p2,p3) that want to access a resource. • All messages are sent reliably and in FIFO order and each message is time stamped with unique Lamport timestamps. All items in the request queues are sorted by message timestamps. • The basic mechanism of this algorithm is that a process that wants to use the resource sends a timestamped request for the resource to all group members as well as to itself. • Every recipient adds the received request to its request queue, which is sorted in timestamp order. Because all processes get all request messages, all timestamps are unique, and all queues are sorted, every process has the exact same items on its queue.
- 5. • If a process sees itself at the head of the queue, it knows that it can access the resource: no other process will be at the head of the queue. • When it is done, it sends a release message to all group members and removes its ID from its local queue. • Each group member, upon receiving a release message, removes that process ID from the request queue and checks to see whether it is at the head of the queue and can access the resource.
- 7. • Lamport’s algorithm is not a great one. We replaced the single point of failure of the centralized algorithm with an algorithm that has N points of failure. • In addition, there is a lot of messaging traffic. Each request requires sending N–1 messages (one to each group member) and getting N–1 acknowledgements. • Finally, when a resource lock is released, a process must send N–1 release messages. Ricart and Agrawala: • There must be a total ordering of all events in the system. Lamport’s Algorithm can be used for this purpose. • When a process wants to enter a critical section, it builds a message containing the name of the critical section, its process number, and the current time. It then sends the message (broadcast) to all other processes, as well as to itself. 1 When a process receives a request message, the action it takes depends on its state with respect to the critical section named in the message. 2
- 8. There are three cases: 1. If the receiver is not in the critical section and does not want to enter it, it sends an OK message to the sender. 2. If the receiver is in the critical section, it does not reply. It instead queues the request. 3. If the receiver also wants to enter the same critical section, it compares the time stamp in the incoming message with the time stamp in the message it has sent out. The lowest time stamp wins. If its own message has a lower time stamp, it does not reply and queues the request from the sending process. When a process has received OK messages from all other processes, it enters the critical section. Upon exiting the critical section, it sends OK messages to all processes in its queue and deletes them all from the queue.