16-10-2012, 01:11 PM
Distributed Mutual Exclusion
Distributed Mutual.ppt (Size: 560.5 KB / Downloads: 173)
Mutual exclusion in DOS
There are three major communication scenarios:
1. One-way Communication usually do not need synchronization.
Client/server communication is for multiple clients making service request to a shared server. If co-ordination is required among the clients, it is handled by the server and there is no explicit interaction among client process.
Centralized algorithms contd..
Advantages
Fair algorithm, grants in the order of requests
The scheme is easy to implement
Scheme can be used for general resource allocation
Critical Question: When there is no reply, does this mean that the coordinator is “dead” or just busy?
Shortcomings
Single point of failure. No fault tolerance
Confusion between No-reply and permission denied
Performance bottleneck of single coordinator in a large system
Distributed Algorithms
Distributed Mutual Exclusion
Contention-based Mutual Exclusion
Timestamp Prioritized Schemes
Voting Schemes
Token-based Mutual Exclusion
Ring Structure
Tree Structure
Broadcast Structure
Timestamp Prioritized Schemes
Lamport’s “logical clock” is used to generate timestamps. These are the general properties for the method:
The general mechanism is that a process P[i] has to send a REQUEST ( with ID and time stamp ) to all other processes.
When a process P[j] receives such a request, it sends a REPLY back.
When responses are received from all processes, then P[i] can enter its Critical Section.
When P[i] exits its critical section, the process sends RELEASE messages to all its deferred requests.
The total message count is 3*(N-1), where N is the number of cooperating processes.
Ricart and Agrawala algorithm
Requesting Site:
A requesting site Pi sends a message request(ts,i) to all sites.
Receiving Site:
Upon reception of a request(ts,i) message, the receiving site Pj will immediately send a timestamped reply(ts,j) message if and only if:
Pj is not requesting or executing the critical section OR
Pj is requesting the critical section but sent a request with a higher timestamp than the timestamp of Pi
Otherwise, Pj will defer the reply message.
Voting schemes
Requestor:
Send a request to all other processes.
Enter critical section once REPLY from a majority is received
Broadcast RELEASE upon exit from the critical section.
Other processes:
REPLY to a request if no REPLY has been sent. Otherwise, hold the request in a queue.
If a REPLY has been sent, do not send another REPLY till the RELEASE is received. [1]
Possibility of a Deadlock
Consider a situation when each candidate wins one-third of votes…..
Tree structure
The root of the tree holds the token to start off.
The processes are organized in a logical tree structure, each node pointing to its parent.
Further, each node maintains a FIFO list of token requesting neighbors.
Each node has a variable Tokenholder initialized to false for everybody except for the first token holder (token generator).