CS 3551 DISTRIBUTED
COMPUTING
Critical Section + Mutual
Exclusion
Critical
Section
Shared Resources
1. Data
System 1 2. Communication
Process 1 channel System
3. Computation 2
Process
2
Critical
Section
● In process synchronization, a critical section is a section of code that
accesses shared resources such as variables or data structures, and which
must be executed by only one process at a time to avoid race conditions and
other synchronization-related issues.
● Mutual exclusion ensures that concurrent access of processes to a shared
resource or data is serialized, that is, executed in a mutually exclusive manner
● 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.
● The decision as to which process is allowed access to the CS next is arrived at by
message passing, in which each process learns about the state of all other
processes in some consistent way
3 Approaches for Implementing
Mutex
Key
Points
● Token Based Approach
○ In the token-based approach, a unique token (also known as the PRIVILEGE message)
is shared among the sites.
○ A site is allowed to enter its CS if it possesses the token and it continues to hold the
token until the
execution of the CS is over.
○ Mutual exclusion is ensured because the token is unique.
● Non-token-based approach
○ two or more successive rounds of messages are exchanged among the sites to
determine which site will enter the CS next.
○ A site enters the critical section (CS) when an assertion, defined on its local variables,
becomes true.
Mutual exclusion is enforced because the assertion becomes true only at one site at any
given time.
● Quorum-based approach
○ each site requests permission to execute the CS from a subset of sites (called a quorum).
○ The quorums are formed in such a way that when two sites concurrently request access
to the CS, at least one site receives both the requests and this site is responsible to
make sure that only one request executes the CS at any time.
1. System
Model
● The system consists of N sites, S , S , , S .with a single process is running on
1 2 N
each site.
● The process at site Si is denoted by pi.
● All these processes communicate asynchronously over an underlying
communication network.
● A process wishing to enter the CS requests all other or a subset of processes
by sending REQUEST messages, and waits for appropriate replies before
entering the CS.
● While waiting the process is not allowed to make further requests to enter the
CS.
● States for a Site:
○ 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 cannot make further
requests for the CS.
● In the “idle” state, the site is executing outside the CS.
● In the token-based algorithms, a site can also be in a state where a site holding
the token is executing outside the CS. Such state is referred to as the idle token
state.
2. Requirements for
Algorithms
3. Performance
Metrics
Low and High Load
Performance
● Under low load conditions, there is rarely more than one
request for the critical section present in the system
simultaneously.
● Under heavy load conditions, there is always a pending request for
critical section at a site. Thus, in heavy load conditions, after
having executed a request, a site immediately initiates activities
to execute its next CS request.
● A site is seldom in the idle state in heavy load conditions
Lamport’s
Algorithm
Coordinator
Stude HOD
nt
Dean
Key
Points
● The algorithm is fair in the sense that a request for CS are executed in
the order of their timestamps and time is determined by logical clocks.
● When a site processes a request for the CS, it updates its local clock and
assigns
the request a timestamp.
● The algorithm executes CS requests in the increasing order of
timestamps.
● Every site Si keeps a queue, request_queuei, which contains mutual
exclusion requests ordered by their timestamps. (Note that this
queue is different from the queue that contains local requests for CS
execution awaiting their turn.)
● This algorithm requires communication channels to deliver messages
in FIFO order.
● When a site removes a request from its request queue, its own request
may come at the top of the queue, enabling it to enter the CS. Clearly,
when a site receives a REQUEST, REPLY, or RELEASE message, it updates
Lamport’s algorithm achieves mutual exclusion
Lamport’s algorithm is fair.