Mutual Exclusion in Distributed System:

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

  1) Centralized Algorithm

  2) Distributed Algorithm

  3) 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

    i) Slower
  
    ii) Complicated
  
    iii) 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.

                 Fig. An Unordered group of process in network

     Figure : A Logical ring Constructed in S/W