Mutual Exclusion in Distributed System:

Mutual Exclusion ensures that no other process will use shared resources at same time

• Centralized Algorithm

• Distributed Algorithm

• Token Ring Algorithm.

One process is elected as coordinator.

Whenever process wants to enter a critical region , it sends request msg to coordinator asking for permission.

If no other process is currently in that critical region, the coordinator sends back a reply granting permission.

When reply arrives, the requesting process enters the critical region.

If the coordinator knows that a different process is already in critical regions, so it cannot be granted permission. Centralized Algorithm:

Advantages:

• Guarantees mutual exclusion.

• Fair Approach (Request Granted In FCFS).

• No Starvation.

• Easy to Implement.

• Only 3 Msgs per use of Critical Section (request, grant, release).

Drawbacks:

• Single point of failure.

• Dead co-ordinate & permission denied cannot distinguish.

• In large systems, single coordinators can create performance bottleneck.

Distributed Algorithm:

• Timestamps are used for distributed mutual exclusion.

• Kieart & Agarwala’s Algorithm:

When process wants to enter critical region, it builds message containing name of critical region its process number and current time

It sends msg to all including itself.

If receiver if not in critical region and doesn’t want to enter it sends back Ok msg to sender.

If the receiver is already in critical region, it doesn’t reply, instead it queues request.

If the receiver wants to enter critical region but has not yet done, so it compares the timestamp in the incoming msg the lowest one wins.

If its own msg has lower timestamp, the receiver queues the incoming request and sends nothing.

Drawbacks:

If any process fails (Crashes), then it does not respond to request.

It can be misinterpreted as denial of permission thus may cause blocking of all processes.

RPCART & AGARWALA’S SOLUTION :

Same algorithm with reply always given by receiver either by granting or denying permission.

Other problem is either group communication must be used, or each process must maintain group information (who enters, who left, etc)

Other problems is bottleneck

• Solution can be given with permission from simple majority of processes rather than from all with conditions that a process granted permission to one that a process granted permission to one process cant grant other permission until first has released.

Other problems - Slower

• Complicated

• More expensive.

TOKEN RING ALGORITHM

Mutual Exclusion – Token Ring Algorithm

In software, a logical ring is constructed in which each process is assigned a position in the ring.

The ring positions may be allocated in numerical order of network address 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.

Working of Token Ring Algorithm :

When the ring is initialized, process 0 is given a token.

The token circulates around the ring.

It passes from process K to process Kt(module the ring size) in point to point messages.

When a process acquires the token from its neighbor, it checks to see if it is attempting to enter a critical region.

If so, the process enters the region, does all the work it needs to, and leaves the region.

After it h excited, it passes the token along the ring.

It is not permitted to enter the second critical region with using the same token.

If a process is handed the token by its neighbor & is not interested in entering a critical region, it just passes it along.

As a consequence, when no processes want to enter any critical regions the token just circulates at high speed around the ring.

Only one process has the token at any instant, so only one process can actually be in the critical region.