Experiment No-7
Aim: Stimulate the Distributed Mutual Exclusion
Theory :
In a distributed system, multiple processes often share resources, such as files or databases, and it is
crucial to manage access to these shared resources in a way that avoids conflicts. Mutual Exclusion
(ME) is a fundamental concept that ensures that no two processes can enter a critical section (the
section of code that accesses shared resources) simultaneously. In a centralized system, mutual
exclusion is easily achieved by using a lock or a monitor. However, in a distributed system, where
processes do not share a single memory space and are connected via communication networks,
achieving mutual exclusion becomes more complex.
Distributed Mutual Exclusion aims to solve the problem of coordinating the access of distributed
processes to critical sections while ensuring that:
Only one process can access the critical section at any given time.
No process is locked out indefinitely (no starvation).
Processes can execute independently and asynchronously without needing a central
authority.
Approaches to Distributed Mutual Exclusion: Several algorithms exist for achieving distributed
mutual exclusion, including:
1. Lamport's Algorithm: A widely used solution that relies on logical clocks and message-
passing. Each process maintains a logical timestamp for requests, and a request to enter the
critical section is sent to all other processes. A process can enter the critical section only
after receiving responses from all other processes.
2. Ricart-Agrawala Algorithm: This algorithm also uses a message-passing approach, where
a requesting process sends a request to all other processes and waits for a reply from each.
The reply is based on the timestamp of the request and the current state of the system.
3. Token-based Algorithms: In these algorithms, a token (a special message or object) is
passed among processes. The process holding the token can enter the critical section, and
after using the resource, it passes the token to another process.
4. Quorum-based Algorithms: These algorithms involve creating a set of processes called a
quorum. A process can enter the critical section only if it obtains permission from a
majority of the processes in the quorum.
Lamport’s Distributed Mutual Exclusion Algorithm:
The Lamport’s algorithm is based on logical clocks and guarantees mutual exclusion using a
request-reply mechanism:
Request: A process that wants to enter the critical section sends a request message to all
other processes, including a timestamp.
Reply: Each process responds to the request by sending a reply, based on the logical
timestamp of the requesting process.
Entering the Critical Section: A process can enter the critical section when it has received
all replies from other processes and its timestamp is the smallest.
Program Code :
import threading
import time
import random
from queue import PriorityQueue
# Number of processes
N = 10
# Global clock
lamport_clock = 0
clock_lock = threading.Lock()
# Priority queue for request queue (to order requests by timestamp)
request_queue = PriorityQueue()
queue_lock = threading.Lock()
# Track completed processes
completed_processes = 0
completed_lock = threading.Lock()
def process_function(process_id):
global lamport_clock, completed_processes
# Request to enter the critical section
with clock_lock:
lamport_clock += 1
request_time = lamport_clock
print(f"Process {process_id} requests critical section at {request_time}")
# Add the request to the queue
with queue_lock:
request_queue.put((request_time, process_id))
# Simulate some delay before entering critical section
time.sleep(random.uniform(0.1, 0.5))
# Check if it's this process's turn
while True:
with queue_lock:
if request_queue.queue[0] == (request_time, process_id):
# Remove the request from the queue
request_queue.get()
break
# Enter critical section
with clock_lock:
lamport_clock += 1
entry_time = lamport_clock
print(f"Process {process_id} enters critical section at {entry_time}")
# Simulate work in the critical section
time.sleep(0.5)
# Exit critical section
with clock_lock:
lamport_clock += 1
exit_time = lamport_clock
print(f"Process {process_id} exits critical section at {exit_time}")
# Track completed processes
with completed_lock:
completed_processes += 1
if completed_processes == N:
print("Mutual execution complete.")
# Create and start threads for each process
threads = []
for i in range(N):
t = threading.Thread(target=process_function, args=(i,))
threads.append(t)
t.start()
# Wait for all threads to finish
for t in threads:
t.join()
Output :
Conclusion : Distributed mutual exclusion is essential for coordinating access to shared resources
in distributed systems, ensuring fairness and preventing conflicts. Lamport's algorithm provides a
reliable method for achieving mutual exclusion through message-passing and logical timestamps.
