How To

Everything about the critical section and semaphores

Summary of every problem and its solution we have previously discussed

At first, we have a problem called producer-consumer problem and we will end up having a robust solution named as semaphores.

Initially,

There was a producer-consumer problem with a bounded buffer which can store at a maximum of N-1 items in it.

To solve the above problem,

The count variable is used and initialized with a “0” value, as count = 0 and its value is incremented for a new item and decremented on the removal of an item. Now, if the producer process runs count++ and consumer process runs count – – separately then, in that case, there is no problem but if they run concurrently/parallel then that action leads to a Data Inconsistency and a Race Condition problem arises which states, that the final output is dependent on the order of execution of statements.

So, to solve the Race Condition problem discussed above,

We need to ensure that only one process can able to manipulate the count variable, which is nothing but a shared variable and for that we should now go for a process synchronization or coordination mechanisms. We have several mechanisms and all those solutions must satisfy the following conditions in order to be a good solution for the producer-consumer problem and those conditions are:

  1. Mutual Exclusion: It says that at a particular time only one process can enter into the critical section.
  2. Progress: One process cannot stop another process for entering into the critical section.
  3. Bounded Waiting: If more than one process wants to enter into the critical section then one process will give chance to another process after taking a finite number of chances itself.
  4. Portability OR Architectural Neutrality: The solution or the mechanism should be independent of architecture.

In addition to the above,

At a given time, there can be a moment when more than one kernel-mode processes are executing at once in the critical section. So, it can lead to a Race Condition and OS code(kernel code) must have proper mechanisms to avoid such problems.

Example: X is a kernel data structure which contains the list of open files. So, if two processes open files simultaneously then separate updates to this list can result in Race Condition.

However, if categorized, there are only 2 approaches for handling the critical section in OS(kernel).

  1. Preemptive kernel: This type of kernel is used many OS’s out there and is real-time, responsive, preferable and every Linux Kernel above version 2.6 is a Preemptive Kernel.
  2. Non-Preemptive kernel: This type of kernel is completely free from such kind of problems.

Note: Every solution is based on some kind of LOCK.

The following are few mechanisms available to avoid or remove the critical section problem:

  • Peterson’s Solution
  • Sync Hardware: disable interrupts by another process when a process is in the critical section; this approach is taken by non-preemptive kernels; but, this is only good for single processors; not good for multi-processors, as disabling interrupts on a multi-processor is a time-consuming process.
  • Test and Set Lock: an atomic instruction provided directly by hardware; only good for the multi-processor system; it is a complicated solution for hardware designers to implement and hard for software programmers to use; so to overcome these problems, semaphores came to picture
  • Mutex Locks: Mut + Ex = mutual exclusion solution; software solution for the critical section problem; used to prevent critical regions and this prevents Race Conditions; Disadvantages: requires Busy Waiting, which wastes CPU-time, also called SPIN-LOCK because another process keeps spinning on acquire(), this continued looping is also a problem in TestAndSet(); Advantages: often used in the multi-processor system because only one thread can “spin” on one processor and other can run on another, no context switch is required because context switches can waste time (reasonable time) but when a LOCK is expected to be held for short time, they are useful; Although, this is a simple solution but now we will look at some more Robust Tool = Semaphores.
  • Semaphores: although a semaphore variable helps to solve several problems still they have a problem of Busy Waiting.

Solution/Modification for semaphore in order to remove the “Busy Waiting” problem.

The waiting process (basically spinning) should go to sleep() = Waiting Queue / Blocks Itself and when the 1st process comes out of the critical section, then it comes out of sleep by executing wakeup() = Read Queue and after that CPU scheduling algorithms are used in order to give it a CPU control.

Semaphore basically have two things:

  1. Value = value can be anything in accordance with the problem and situation.
  2. List = process is added to this list when it goes waiting and signal() = removes it from it and awakens that process.

Following is code for the modified version of wait() for a semaphore:

wait(semaphore *S) {
S -> value --;
if (S -> value < 0) {
add this process to S -> list;
block(); // Suspend = system call
 }
}

Following is code for the modified version of signal() for a semaphore:

signal(semaphore *S) {
S -> value++;
if(S -> value = 0) {
remove a process P from S-> list;
wakeup(P); // Resume = system call
 }
}

Differences between a normal semaphore and a modified semaphore:

  1. Classic Semaphore = its value can never be negative (-ve)
  2. Modified Semaphore = its value can be negative(-ve) and whatever the value is in negative it simply states that those number of processes are waiting on that semaphore.

Now modified version of semaphore states that:

  1. Value = it can be anything.
  2. Pointer to a list of PCBs = to ensure Busy Waiting (FIFO Queue is used).

Now after discussing all the problems and solutions discussed above, it is time to discuss a little bit about Single-core processor and Multi-core processor:

  • Single-core processor = it is critical to run wait() and signal() atomically and again we have the critical section problem. So, to solve this in single processor systems we can simply use Disable Interrupt mechanism.
  • Multi-core processor = if we use Disable Interrupt mechanism here, the interrupt should be disabled on each available core/processor in the system and this is difficult as well as it results in a decreased performance. So, there should be something like Compare_And_Swap() or TestAndSet(). So that wait() and signal() can be performed atomically.

Note: Still Busy Waiting is there, but not in the entry section and in the critical section itself because wait() also have a critical section and signal also have a critical section. So, we have limited Busy Waiting to their’s critical sections only. Moreover, because these sections are short and if properly coded, they are not more than 10 lines of code. So, Busy Waiting will last only for a short time.

Note: In the modified version of semaphores, we have used Busy Waiting as a feature to it.

Comment here