01-04-2014, 02:49 PM
Distributed Mutual Exclusion
INTRODUCTION
The mutual exclusion (ME) problem frequently arises when concurrent access to shared resources by several sites is involved (e.g., directory management where updates and reads to a directory must be done atomically to ensure correctness.)
Mutual exclusion is a fundamental issue in the design of distributed systems, and an efficient and robust technique for mutual exclusion is essential.
Because of resource distribution, transmission delays, and lack of global information, mutual exclusion algorithms developed for single-computer systems are not applicable in a distributed environment.
Algorithms developed for distributed systems can be grouped into two classes:
Nontoken-based (assertion based) approach : a site enters its critical section (CS) when an assertion defined on its local variables becomes true, which can be established through two or more rounds of message exchanges.
Token-based approach : a site enters its CS if it possesses the single token that is shared among the sites.
System model
At any instant, a site may have several requests for CS. The site queues them up and serves them one at a time.
A site can be in one of three states:
1. Requesting CS -- the site is blocked and cannot make further requests for CS
2. Executing CS -- the site is in its critical section
3. Idle -- the site is neither requesting nor executing CS
Objectives of ME algorithms
Guarantee mutual exclusion (required)
Freedom from deadlocks (desirable)
Freedom from starvation -- every requesting site should get to enter CS in a finite time (desirable)
Fairness -- requests should be executed in the order of arrivals, which would be based on logical clocks (desirable)
Fault tolerance -- failure in the distributed system will be recognized and therefore not cause any unduly prolonged disruptions (desirable)
NON-TOKEN-BASED ALGORITHMS
In non-token-based mutual exclusion algorithms, a site communicates with a set of other sites to arbitrate who should execute the CS next. Each site maintains a request set that contains ids of all those sites from which it must acquire permission before entering the CS. A site can proceed to its CS only after it has acquired permission from all those sites in its request set. Messages are timestamped using Lamport’s logical clock scheme. Messages with the same virtual timestamp are resolved by the ids of the message sending sites. Smaller timestamp requests have priority over larger timestamp requests.
Singhal’s Heuristic Algorithm
Instead of broadcasting request messages for acquiring the token, Singhal’s algorithm has each site keep information about the state of other sites and use the information to select the sites that are likely to have the token. The objective of this effort is to reduce the number of messages required for the CS execution. It is called a heuristic algorithm because sites are heuristically selected for sending the request messages. In order to avoid the request being unanswered, a requesting site must send the request message to a site that either holds the token or is going to obtain the token in the near future. Hence one design requirement of this algorithm is that a site must select a subset of sites such that at least one of those sites is guaranteed to get the token in the near future.