02-11-2012, 12:38 PM
ELECTION ALGORITHMS
[attachment=37872]
MUTUAL EXCLUSION
Systems involving multiple processes are often most easily programmed using
critical regions. When a process has to read or update certain shared data structures,
it first enters a critical region to achieve mutual exclusion and ensure that
no other process will use the shared data structures at the same time. In singleprocessor
systems, critical regions are protected using semaphores, monitors, and
similar constructs. We will now look at a few examples of how critical regions
and mutual exclusion can be implemented in distributed systems. For a taxonomy
and bibliography of other methods, see (Raynal, 1991; and Singhal, 1993).
A Centralized Algorithm
The most straightforward way to achieve mutual exclusion in a distributed
system is to simulate how it is done in a one-processor system. One process is
elected as the coordinator (e.g., the one running on the machine with the highest
network address). Whenever a process wants to enter a critical region, it sends a
request message to the coordinator stating which critical region it wants to enter
and asking for permission. If no other process is currently in that critical region,
the coordinator sends back a reply granting permission, as shown in Fig. 5-5(a).
When the reply arrives, the requesting process enters the critical region.
SYNCHRONIZATION CHAP. 5
When process 1 exits the critical region, it sends a message to the coordinator
releasing its exclusive access, as shown in Fig. 5-5©. The coordinator takes the
first item off the queue of deferred requests and sends that process a grant message.
If the process was still blocked (i.e., this is the first message to it), it
unblocks and enters the critical region. If an explicit message has already been
sent denying permission, the process will have to poll for incoming traffic or
block later. Either way, when it sees the grant, it can enter the critical region.
It is easy to see that the algorithm guarantees mutual exclusion: the coordinator
only lets one process at a time into each critical region. It is also fair, since
requests are granted in the order in which they are received. No process ever waits
forever (no starvation). The scheme is easy to implement, too, and requires only
three messages per use of a critical region (request, grant, release). It can also be
used for more general resource allocation rather than just managing critical
regions.
A Distributed Algorithm
Having a single point of failure is frequently unacceptable, so researchers
have looked for distributed mutual exclusion algorithms. Lamport’s 1978 paper on
clock synchronization presented the first one. Ricart and Agrawala (1981) made it
more efficient. In this section we will describe their method.
Ricart and Agrawala’s algorithm requires that there be a total ordering of all
events in the system. That is, for any pair of events, such as messages, it must be
unambiguous which one actually happened first. Lamport’s algorithm presented in
Sec. 5.2.1 is one way to achieve this ordering and can be used to provide timestamps
for distributed mutual exclusion.
The algorithm works as follows. When a process wants to enter a critical
region, it builds a message containing the name of the critical region it wants to
enter, its process number, and the current time. It then sends the message to all
other processes, conceptually including itself. The sending of messages is
assumed to be reliable; that is, every message is acknowledged. Reliable group
communication if available, can be used instead of individual messages.
When a process receives a request message from another process, the action it
takes depends on its state with respect to the critical region named in the message.
A Token Ring Algorithm
A completely different approach to achieving mutual exclusion in a distributed
system is illustrated in Fig. 5-7. Here we have a bus network, as shown in
Fig. 5-7(a), (e.g., Ethernet), with no inherent ordering of the processes. In
software, a logical ring is constructed in which each process is assigned a position
in the ring, as shown in Fig. 5-7(b). The ring positions may be allocated in
numerical order of network addresses or some other means. It does not matter
what the ordering is. All that matters is that each process knows who is next in
line after itself.
A Comparison of the Three Algorithms
A brief comparison of the three mutual exclusion algorithms we have looked
at is instructive. In Fig. 5-8 we have listed the algorithms and three key properties:
the number of messages required for a process to enter and exit a critical region,
the delay before entry can occur (assuming messages are passed sequentially over
a network), and some problems associated with each algorithm.