27-06-2013, 01:10 PM
Distributed Mutual Exclusion Algorithms
Distributed Mutual.pdf (Size: 911.64 KB / Downloads: 178)
Introduction
Mutual exclusion: Concurrent access of processes to a shared resource or
data is executed in mutually exclusive manner.
Only one process is allowed to execute the critical section (CS) at any given
time.
In a distributed system, shared variables (semaphores) or a local kernel
cannot be used to implement mutual exclusion.
Message passing is the sole means for implementing distributed mutual
exclusion.
System Model
The system consists of N sites, S1, S2, ..., SN.
We assume that a single process is running on each site. The process at site
Si is denoted by pi .
A site can be in one of the following three states: requesting the CS,
executing the CS, or neither requesting nor executing the CS (i.e., idle).
In the ‘requesting the CS’ state, the site is blocked and can not make further
requests for the CS. In the ‘idle’ state, the site is executing outside the CS.
In token-based algorithms, a site can also be in a state where a site holding
the token is executing outside the CS (called the idle token state).
At any instant, a site may have several pending requests for CS. A site
queues up these requests and serves them one at a time.
Requirements of Mutual Exclusion Algorithms
1 Safety Property: At any instant, only one process can execute the critical
section.
2 Liveness Property: This property states the absence of deadlock and
starvation. Two or more sites should not endlessly wait for messages which
will never arrive.
3 Fairness: Each process gets a fair chance to execute the CS. Fairness
property generally means the CS execution requests are executed in the order
of their arrival (time is determined by a logical clock) in the system.