When a collection of processes share the same common resource, they may require mutual exclusive access to this shared resource. The problem is to design a program that acts as a "mutual exclusive layer" that resolves the conflict between the processes.
A trivial solution could be to write a single central program that maintains a queue of outstanding requests. Requests are granted one at a time. This guarantees safety and progress.
However, the centralized program could be a bottleneck.
So let us step back and consider a more general problem where mutual exclusion is an example. This is the problem of maintaining a distributed variable value.
Let us say the variable x needs to be updated. Different processes keep a local copy and manage it with broadcasts.
Each process keeps as part of its state the following:
copy of x,
the logical clock,
queue of modifying requests ( with their logical time stamps )
list of known times, one for each other process.
The process executes a request when the request has the minimum logical time of all the requests and all the known requests are later than that time.
The processes are connected in a well defined fixed topology that is the processes are finite and well-connected. We will consider the processes as arranged in a ring.
Now lets consider the use of a single indivisible token. A token is a very useful concept. It can neither be created nor destroyed.
A process is allowed to enter the critical section only if it holds the token. Every process that tries to enter a critical section also gets a token,
In a token ring the token moves constantly in a clockwise direction.
If the processes want to enter the critical section, it simply waits for the token.
The algorithm to use is therefore
To use resource:
hungry = true;
when token arrives:
if hungry
use resource
send token on clockwise direction
Courtesy : Introduction to Distributed Systems
book by Dr, Paul Sivilotti
A trivial solution could be to write a single central program that maintains a queue of outstanding requests. Requests are granted one at a time. This guarantees safety and progress.
However, the centralized program could be a bottleneck.
So let us step back and consider a more general problem where mutual exclusion is an example. This is the problem of maintaining a distributed variable value.
Let us say the variable x needs to be updated. Different processes keep a local copy and manage it with broadcasts.
Each process keeps as part of its state the following:
copy of x,
the logical clock,
queue of modifying requests ( with their logical time stamps )
list of known times, one for each other process.
The process executes a request when the request has the minimum logical time of all the requests and all the known requests are later than that time.
The processes are connected in a well defined fixed topology that is the processes are finite and well-connected. We will consider the processes as arranged in a ring.
Now lets consider the use of a single indivisible token. A token is a very useful concept. It can neither be created nor destroyed.
A process is allowed to enter the critical section only if it holds the token. Every process that tries to enter a critical section also gets a token,
In a token ring the token moves constantly in a clockwise direction.
If the processes want to enter the critical section, it simply waits for the token.
The algorithm to use is therefore
To use resource:
hungry = true;
when token arrives:
if hungry
use resource
send token on clockwise direction
Courtesy : Introduction to Distributed Systems
book by Dr, Paul Sivilotti
No comments:
Post a Comment