It is important in the processing of the processes and threads that it is ensured that any two threads or processes do not coincide with each other i.e., they both do not utilize the critical section simultaneously. Here, critical section is referred to as the duration when a shared resource is accessed by the different processes. Shared memory is one such resource.
In this article we discuss about various solutions and mechanisms available for addressing the problem of mutual exclusion. Today we have solutions available in both the categories hardware and software for the enforcement of the mutual exclusion. First we shall discuss about the hardware solutions.
Hardware Solutions for Mutual Exclusion
Disabling the Interrupts:
– This is the simplest of the solutions for the uni-processor systems to achieve the mutual exclusion.
– The interrupts are disabled during the execution of the critical section of a process.
– By doing so, any interrupt service routines are prevented from being run thus preventing the preemption of a process effectively.
– While simplicity is the main advantage of this process, there are associated problems also.
– If the process has a long critical section, every time when it will be executed, there will be a drift in the system clock.
– This is because of no more servicing of the timer interrupt and so the control is not returned to the other processes and the entire system comes to a halt.
– This is more effective than the previous one and holds good for uni-processor systems and multiprocessor systems as well.
– In this, the atomic test and set instruction and shared memory is used for providing the mutual exclusion.
– The operations are atomic and in a shared memory location, the process can test and set.
– Because of the atomic nature of the operations, flag can be set by only one process.
– If a process had a failure in setting the flag, it can go for the other tasks and come back for this one later.
CAS or Compare and Swap:
– This method is effective in achieving the wait free mutual exclusion for any kind of data structure.
– A linked list is created where the desired operation to be carried out is represented by each node.
– It is also used in changing the pointers of this list for the insertion of new nodes.
– Out of all the processes trying for CAS, only one is successful and therefore others have to try again.
– A local copy is then kept by each of the processes.
Software Solutions for Mutual Exclusion
– The following software solutions make use of the busy waiting for achieving the goal of mutual exclusion:
- Dekker’s algorithm
- Lamport’s bakery algorithm
- Taubenfield’s black – white bakery algorithm
- Szymanski’s algorithm
- Peterson’s algorithm
– If the platform executing these algorithms is following out of order execution, then there are chances that these algorithms will not work.
– The ordering of the memory operations has to be strictly specified by the programmer within the process or the thread.
– Mostly, it is preferred to use the synchronization options that are available in the multi-threading library of the operating system in order to benefit from the hardware solutions.
– If no hardware solutions are available, then the software solutions are used.
– Reduction of the busy waits and latency is quite often the focus of the most of the modern mutual exclusion methods. – They achieve this with the help of context switches and queuing.
– Spin locks also prove to be an effective solution.
– The synchronization primitives mentioned below can be built from the above explained solutions:
- Reentrant mutexes
- Tuple space
- Message passing
Most of the mutual exclusion forms come with side – effects such as semaphores with deadlocks.