Solution:

What is mutual exclusion?

• Mutual exclusion is a mechanism to ensure that only one process is doing certain things at one time, this avoid data inconsistency.

• Mutual exclusion algorithm ensures that if a process is already performing write operation on a data object no other process/thread is allowed to access the same object until the first process has finished writing upon the data object and released the object for other processes to read and write upon.

• All others should be prevented from modifying shared data until the current process finishes. There is thus exclusion of one process by another. In certain regions of an operating system.

• The requirement of mutual exclusion was first Solution of a problem in concurrent programming control, and is credited as the first topic in the study of concurrent algorithms.

Mutual exclusion Algorithm:

1) No Starvation:

• Any site should not wait indefinitely to execute critical section while other site are repeatedly executing critical section

2) No Deadlock:

• Two or more site should not endlessly wait for any message that will never arrive.

3) Fault Tolerance:

• In case, it should be able to recognize it by itself in order to continue functioning without any disruption.

4) Fairness:

• Any request to execute critical section must be executed in the order they are made.

Distributed algorithm:

• A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors.

• Distributed algorithms are used in different application areas of distributed computing, such as telecommunications, scientific computing, distributed information processing, and real-time process control.

Mutual exclusion in distributed system algorithm:

• The status of shared resources and the status of users is easily available in the shared memory so with the help of shared variable (For example: Semaphores) mutual exclusion problem can be easily solved.

• A site in distributed system do not have complete information of state of the system due to lack of shared memory, and a common physical clock in OS.

1) Token Based Algorithm:

• If a site possesses the unique token, it is allowed to enter its critical section.
• This approach insures Mutual exclusion as the token is unique.
• Each requests for critical section contains a sequence number. This sequence number is used to distinguish old and current requests.
• This approach insures Mutual exclusion as the token is unique.
• Example: Suzuki-Kasami’s Broadcast Algorithm

2) Non-token based approach:

• All algorithm which follows non-token based approach maintains a logical clock. Logical clocks get updated according to Lamport’s scheme.

• A site communicates with other sites in order to determine which sites should execute critical section next.

• This requires exchange of two or more successive round of messages among sites.

• Example: Lamport's algorithm, Ricart–Agrawala algorithm.

3) Quorum based approach:

• Instead of requesting permission to execute the critical section from all other sites, Each site requests only a subset of sites which is called a quorum.

• Any two subsets of sites or Quorum contains a common site. This common site is responsible to ensure mutual exclusion.

• Example: Maekawa’s Algorithm.