Solutions to Mutual Exclusion

Three basic approaches are available for the implementation of mutual exclusion problem.

1.   Software Solution

2.   Hardware Solution

3.   As mutual exclusion primitives (Semaphore)

The software implementation depends on an arrangement of checks to ensure mutual exclusion. The correctness of the critical section implementation thus depends on the correctness of these checks, and it is hard to prove due to complexity of checks. This is a serious drawback in the development of large concurrent systems. However, the major advantage of the software approach is that no special hardware or software is required to implement a critical section.

Hardware solution use special hardware instructions implemented in the form of language constructs for process synchronization. Since the language constructs has well defined semantics which is enforced by the language compiler, construction of large concurrent systems becomes more practical.

A set of primitives for mutual exclusion (eg P and V primitives of Dijkstra) developed to overcome the complexity of software approach. These primitives could be implemented either in the form of busy-waiting (software solution or hardware solution) or as operating system services invoked by system calls.

Both hardware and solutions of critical section are implemented in the form of busy-waiting. In busy-waiting, a process is in a tight loop, checking a particular condition until it is allowed to enter its critical section. Thus, if busy waiting is employed, while a process is waiting for access to a critical section, it continuous to
consume processor time. This is highly undesirable in a multiprogramming environment because busy waiting wastes CPU cycles that some other process might be able to use productively.

Software Solution

The Dutch Mathematician Dekker is believed to have been the first to solve the mutual exclusion problem. Dekker’s solution in its original form works for only two processes and cannot be easily extended beyond that number. This restriction does not diminish the theoretical importance of Dekker’s solution but tends to limit its direct applicability.

Hardware Solution

A common hardware solution to the mutual exclusion problem is a machine instruction called TEST-AND-SET (testandset). As the name implies, this instruction combines the action of testing a variable and consequently setting it to a stipulated value. The testandset instruction performs both these tasks in a single integer machine instruction, which cannot be interrupted. The testandset operates on a single integer variable. If the variable has a value of zero, it replaces it with 1 and return false, otherwise its value is not changed and true is returned. 

      NEXT: Semaphore 

Previous:  Mutual exclusion and critical section

      Index : Operating System