Mutual Exclusion in Operating Systems | OS Tutorials

Mutual exclusion is a condition that guarantees that not more than one process can be in a critical section for shared data at a time. A critical section implementation in an operating system also guarantees that any process wishing to enter the critical section will not be delayed indefinitely.

The operating system can choose not to preempt itself. That is, we do not preempt the system process or processes running in system mode. In this section, we will examine various proposals for achieving mutual exclusion, so that while one process is busy updating shared memory in its critical region, no other process will enter its critical region and cause trouble.

Mutual Exclusion in Operating System

We have multiple approaches to achieve mutual exclusion.

1. Disabling Interrupts
2. Lock Variables
3. Strict Alternation
4. Peterson’s Solution
5. TSL (Test And Set Lock) Instructions
6. XCHG (Exchange) Instruction
7. Sleep and Wakeup Calls

Disabling Interrupts

On a single-processor system, the simplest solution is to have each process disable all interrupts just after entering its critical region and re-enable them just before leaving it. With interrupts disabled, no clock interrupt can occur. The CPU is only switched from process to process as a result of clock or other interrupts.

Thus, once a process has disabled interrupts, it can examine and update the shared memory without fear that any other process will intervene. However, this approach is generally not acceptable. If the system is a multiprocessor, disabling interrupts affects only the CPU that executed the disable instruction. The other ones will continue running and can access the shared memory.

• It is convenient for the kernel itself to disable interrupts for a few instructions while it is updating variables or lists.
• If an interrupt occurred while the list of ready processes, like, was in an inconsistent state, a race condition could occur.
• We can conclude that disabling interrupts is often a useful technique within the operating system itself but is not appropriate as a general mutual exclusion mechanism for user processes.

Lock Variables

It is the second alternative of a software solution for the mutual exclusion problem. In this approach, we consider singlè shared (lock) variable and initialize as 0.

• When a process wants to enter its critical region, it first tests the lock. If the lock is 0, the process sets it to 1 and enters the critical region. If the lock is already 1, the process just waits until it becomes 0.
• Hence, a 0 means that no process is in its critical region, and a 1 means that some process is in its critical region.
• This approach also has some drawbacks. Consider that one process reads the lock and checks for 0; before it can set the lock to 1, another process is scheduled, runs, and sets the lock to 1.
• When the first process runs again, it will also set the lock to 1, and two processes will be in their critical region at the same time.
• The Race condition also suffers from a race condition. In this approach, the second process modifies the lock just after the first process has finished its second check.

Strict Alternation

This is the third approach to the mutual exclusion problem, and it is depicted in code below.

//Process 0

While (True) {
While (turn != 0)
critical_region();
turn = 1;
noncritical_region();
}

//Process 1

While (True) {
While (turn != 1)  /*loop*/
critical_region();
turn = 0;
noncritical_region();
}

• In this program fragment (written in C), the integer variable turn, initially 0, keeps track of whose turn next to enter the critical region and examine or update the shared memory.
• Initially, turn is inspected by process 0, found to be 0, and enter its critical region. Process 1 also finds it to be 0 and therefore, in the loop, continually tests the variable turn to see when it becomes 1.
• When continuously testing a variable until some value appears is called busy waiting. We must avoid it, since it wastes CPU time.
• When there is a reasonable expectation that the wait will be short, is busy-waiting used? A lock that uses busy waiting is called a spin lock.
• When process 0 leaves the critical region, it sets turn to 1 to allow process 1 to enter its critical region. If we assume that process 1 quickly finishes its critical region, so that both processes are in their non-critical regions, with turn set to 0.
• Now process 0 executes its loop quickly, and exits from its critical region, and sets turn to 1. At this point, turn is 1, and both processes are executing in their non-critical regions.
• Suddenly, process 0 finishes its non-critical region and goes back to the top of the loop. Since now turn is 1 and process 1 is busy with its non-critical region, it is not permitted to enter its critical region.
• It hangs in its while loop until process 1 sets turn to 0. Process 0 is being blocked by a process not in its critical region. Hence, this solution requires that the two processes strictly alternate in entering their critical regions.
• This algorithm does avoid all races, even though it is not considered a solution.

Peterson’s Solution

A classic software-based solution to the critical-section problem known as Peterson’s solution.

• Peterson’s solution is restricted to two processes that alternate execution between their critical sections and remainder sections.
• The processes are numbered P₀ and P₁; for convenience, when presenting P_i, we use P_j to denote the other process, that is, j equals 1-i.
• Peterson’s solution requires the two processes to share two data items:

int turn;
boolean flag [2];

• The Variable turn indicates whose turn it is to enter its critical section.
• If turn == i, then process P_i is allowed to execute in its critical section. The flag array is used to indicate if a process is ready to enter its critical section. For example, if flag[i] = true, this indicates that P_i is ready to enter its critical section.
• Peterson’s solution is depicted in the following code.

//Peterson's Solution

do {
     Flag = True;
     turn = j
     while (flag[j] && turn == j)
        
       Critical section
     Flag[i] = FALSE;

       Remainder section
} While (TRUE);
      

• To enter the critical section, process P_i first sets flag [i] to true and then sets turn to j. If the other process wishes to enter the critical section, it can do so.
• If both processes try to enter at the same time, turn will be set to both i and j at roughly the same time. Only one of these assignments will last; the other will occur but will be overwritten immediately.
• The eventual value of turn determines which of the two processes is allowed to enter its critical section first. If we want to prove the solution is correct, we just need to show the following points:-
  1. Mutual exclusion is preserved.
  2. The progress requirement is satisfied.
  3. The bounded-waiting requirement is met.

To prove property 1, we note that each P_i enters its critical section only if either flag [j] == false or turn==i. If both processes can be executing in their critical sections at the same time, then

Flag [0] == true and Flag [1] = = true

To prove properties 2 and 3, we note that a process P_i can be prevented from entering the critical section only if it is stuck in the while loop with the conditions flag [j] == true and turn ==j; this loop is the only one possible.

The TSL (Test And Set Lock) Instructions

This approach requires some level of cooperation from the hardware. Some computers that are designed with multiple processors have an instruction like:

TSL REGISTER, LOCK

• The test-and-set instruction is an instruction used to write to a memory location and returns its old value as a single atomic operation.
• If multiple processes may access the same memory and if a process is currently performing a test and set, no other process may begin another test-and-set until the first process is done.
• CPU may use test-and-set instructions offered by other electronic components, such as Dual-Port RAM; the CPU may offer a test-and-set instruction itself.
• A lock can be built using atomic test-and-set instructions as follows:

Function Lock (boolean *lock)
{
   While(test_and_set (lock == 1);
}

• The calling process obtains the lock if the old value was 0. It spins, writing 1 to the variable until this occurs.

Comments on the “Test and Set” Solution

• When the “lock” variable is set to TRUE, it means someone is in the critical section (ie, buying milk). Note that the process resets the lock to FALSE when finished. Exercise: why can’t another process set it to FALSE?

Good points:

• As there cannot be a context switch between testing the lock and setting its value to TRUE, this solution will ensure only one process buys milk no matter how many processes there are.
• Simple and therefore easy to verify/prove correctness.
• Can have multiple critical sections, each with its own boolean “lock” variable.

Less good points:

• As this solution requires continual testing of the lock, it uses busy waiting.
• Starvation is possible. When many processes wish to enter the critical section, the selection of the next process to test is arbitrary, so a (low-priority) process may miss out. In other words, one flatmate may never get to buy the milk:-)
• Test-and-set is a machine instruction; therefore, coding to use it has to be at machine or assembly level!

WORKING OF TSL Instruction

• TSL instructions read the contents of the memory word locked into register Rx and then store a nonzero value at the locked memory address.
• The Operations of reading the word and storing into it are guaranteed to be indivisible, i.e no other processor can access the memory word until the instruction is finished.
• The CPU executing the TSL Instruction locks the memory bus to prohibit other CPUs from accessing memory until it is done.
• Disabling Interrupts, then performing a read on a memory word followed by a write, does not prevent a second processor on the bus from accessing the word between the read and write.
• Disabling interrupts on processor 1 does not affect processor 2 at all. The only way to keep processor 2 out of the memory until processor 1 is finished is to lock the bus, which requires a special hardware facility.
• To use the TSL instruction, we will use a shared variable (lock) to coordinate access to shared memory.
• When lock is 0, any process may set it to 1 using the TSL instruction and then read or write the shared memory. When it is done, the process sets lock back to 0.
• Now, a question may arise: How can this instruction be used to prevent two processes from simultaneously entering their critical regions?
• Solution to this problem is given in instructions written below:

enter_region:

TSL REGISTER, LOCK      //copy lock to register & set lock to 1
CMP REGISTER, #0        //was the lock zero?
JNE enter_region        //if it was nonzero, lock was set,
RET                     //so loop return to caller; critical

leave_region:
      MOVE LOCK, #0     //store a 0 in lock
      RET               //return to caller

• The above instruction is written in assembly language. The first instruction copies the old value of lock to the register and then sets lock to 1.
• Then the old value is compared with 0; if it is non-zero, the lock was already set, so the program just goes back to the beginning and tests it again. After some time, it will become 0, and the subroutine returns, with the lock set.

Conclusion

• The problem of the critical region is now being solved with TSL Instructions. We just call the two functions as discussed before.
• “A process calls enter-region before entering its critical region, which does busy waiting until the lock is free; then it acquires the lock and returns. After the critical region, the process calls leave-region, which stores a 0 in lock.”

XCHG (Exchange) Instruction

• An alternative instruction to TSL is XCHG, which exchanges the contents of two locations atomically.
• An XCHG instruction can swap the contents of two operands. This instruction takes the place of three MOV instructions. It does not require a temporary location to save the contents of one operand while loading the other. XCHG is especially useful for implementing semaphores or similar data structures for process synchronization.
• Consider an example: to exchange the contents of a register and a memory word, the code (instruction) is given below:

enter_region:            //Put a 1 in the register
  MOVE REGISTER, #1      //swap the content of the register and Lock variable
  XCHG REGISTER, LOCK    //was lock zero?
  CMP REGISTER, #0       //if it was not zero, lock was set
  JNE enter_region       //return to caller, critical region
  RET                    // entered

leave_region:
      MOVE LOCK, #0      //stores a 0 in lock
      RET                //return to caller

• All Intel X86 CPUs use the XCHG instruction for low-level synchronization.

Sleep and Wakeup Calls

The solution of the critical region problem, as discussed before by Peterson’s solution and by TSL Instruction are correct, but both have the defect of requiring busy waiting. To understand the Sleep and Wakeup Call approach, consider a computer with two processes H with high priority and L with low priority.

• The Scheduling rules are such that H is run whenever it is in the ready state. At a certain moment, with L in its critical region, H becomes ready to run.
• H now begins busy waiting, but since L is never scheduled while H is running, L never gets the chance to leave its critical region, so H loops forever. This situation is sometimes referred to as the priority Inversion problem.
• Sleep and wakeup are the interprocess communication primitives. Sleep is a system call that causes the caller to block, that is, be suspended until another process wakes it up.
• The Wakeup call has one parameter: the process to be awakened. Alternatively, both sleep and Wakeup each have one parameter, a memory address used to match up sleeps and Wakeups.