What is a Need for Mutual Exclusion?

An easy way to visualize the significance of mutual exclusion is to imagine a linked list of several items, with the fourth and fifth items needing to be removed. By changing the previous node’s next reference to point to the succeeding node, the node that lies between the other two nodes is deleted.

To put it simply, whenever node “i” wants to be removed, node “with – 1″‘s subsequent reference is changed to point to node “ith + 1” at that time. Two distinct nodes can be removed by two threads at the same time when a shared linked list is being used by many threads. This occurs when the first thread modifies node “ith – 1” next reference, pointing towards the node “ith + 1,” and the second thread modifies node “ith” next reference, pointing towards the node “ith + 2.” Although both nodes have been removed, the linked list’s required state has not yet been reached because node “i + 1” still exists in the list because node “ith – 1” next reference still points to it.

Now, this situation is called a race condition. Race conditions can be prevented by mutual exclusion so that updates at the same time cannot happen to the very bit about the list.

Example:

In the clothes section of a supermarket, two people are shopping for clothes.

Boy, A decides upon some clothes to buy and heads to the changing room to try them out. Now, while boy A is inside the changing room, there is an ‘occupied’ sign on it – indicating that no one else can come in. Girl B has to use the changing room too, so she has to wait till boy A is done using the changing room. 

Once boy A comes out of the changing room, the sign on it changes from ‘occupied’ to ‘vacant’ – indicating that another person can use it. Hence, girl B proceeds to use the changing room, while the sign displays ‘occupied’ again.

The changing room is nothing but the critical section, boy A and girl B are two different processes, while the sign outside the changing room indicates the process synchronization mechanism being used.

During concurrent execution of processes, processes need to enter the critical section (or the section of the program shared across processes) at times for execution. It might happen that because of the execution of multiple processes at once, the values stored in the critical section become inconsistent. In other words, the values depend on the sequence of execution of instructions – also known as a race condition. The primary task of process synchronization is to get rid of race conditions while executing the critical section.

This is primarily achieved through mutual exclusion.