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.