Operating system: All you need to know about Critical section problem

Photo by Lukas on Unsplash

Operating system: All you need to know about Critical section problem

Critical section is the part of the program where the shared resources are accessed by various processes. By various processes I mean cooperative processes. Cooperative processes are the ones that have something in common. That something can be a common code, memory space, buffer or any other resource.

Every program has two components to it, critical section and non-critical section. So, in simple terms, the code or resources that are unique to the program fall under non-critical section and the code or resources common to programs fall under the critical section.

Race condition: Suppose we have two processes, P1 and P2. Both share a common code in critical section. So, ideally, if P1 is executing the code in the critical section, P2 should not be accessing the critical section. But, when there’s no synchronization between the two processes, this leads to a situation called the race condition. Under this condition, both the processes will try to access the critical section simultaneously.

Moving on, if any process, for example P1, wants to access the critical section, it cannot access it directly. It has to execute the code in the ‘entry section’ first. There are various methods to achieve this like semaphores, lock variables etc. More on that later.

Similarly, P2 also needs to first execute the lines of code present in the entry section to be able to access the critical section.

The above can be easily explained via a day-to-day example. When we come from outside to our house, we open the lock first and then we enter the house. Likewise, while going out again, we lock the same door and go out. Similar analogy applies to entry section of the program.

So, to make the entry of the processes in the critical section synchronous, we have to write the code of entry section in such a way that once one process enters the entry section and thereby critical section, no other process can enter the entry section while it’s being used. Only then can we say that we have achieved synchronization.

Just like the entry section, there’s an exit section too for exiting the critical section.

Conditions for best solutions for synchronization

There are a four conditions that we have to follow to achieve the best solution for process synchronization.

  • Mutual Exclusion
  • Progress
  • Bounded wait
  • No assumption related to hardware or speed.

Any solution or method for process synchronization has to follow the above four rules or conditions to achieve the best possible synchronization. First two are the primary conditions and the remaining two are secondary ones. If not all, at least the first 2 are mandatory ones.

  1. Mutual Exclusion:

All the common code and data between the processes lies in the critical section as we already know. Let us suppose, we have 2 processes, P1 and P2, which are in running state. Both of these processes have their independent code and data i.e. non-critical section as well as dependent code and data i.e. critical section.

Now, when P1 enters the critical section after executing the entry section code, even if P2 wants to enter the critical section, it cannot enter. Only then can we say that Mutual Exclusion is achieved. That means our first condition is achieved.

  1. Progress

All the common code and data between the processes lies in the critical section as we already know.

Now, let us suppose the critical section is empty and is available to be accessed by any process willing to access it. Let us suppose, we have 2 processes, P1 and P2, which are in running state. P1 wants to access the critical section but there’s some code in the entry section of P2 that is prohibiting the P1 process to enter the critical section. Same can be said for P2 if P1 isn’t allowing P2 to enter critical section. In a nutshell, we can conclude that there’s no progress. Ideally, there should be progress.

If the critical section can be accessed by a process without facing obstruction from any other process, then we can say that Progress condition is met.

  1. Bounded wait

Let us suppose, we have 2 processes, P1 and P2, which are in running state. P1 is inside the critical section. So, by default, owing to mutual exclusion rule, P2 won’t be able to access the critical section.

Consider a scenario where P1 exits the critical section and accesses it multiple times while P2 doesn’t get the critical section even once. In this condition, P2 tends to starve as P1 is the only process that is repeatedly entering and exiting the critical section without giving P2 any chance to access the critical section.

Ideally, there should be bounded wait. After a certain period of wait, P2 should have got access to the critical section. But, in our case, it does not happen. It should not happen that one process accesses the critical section infinite times and the other process accesses it only once. Unbounded wait is a serious hindrance to the process synchronization.

  1. No assumption related to hardware or speed.

Let’s suppose our solution to the critical section problem works only if our OS is 32-bit and not 64-bit. Or, if we say, the solution will work only if the processor speed is 1 GHz or more and won’t work if the speed is any less than that.

If such a thing exists, then the solution is not ideal. Solution should work irrespective of your system hardware specifications.

The solution must be universal and should work across all the platforms like windows, linux or macintosh. There’s no room for assumptions.

That’s all about critical section problem in brief. In my next article, I will be exploring more about the solutions to achieve the process synchronization.