Process Synchronization

In this blog, we will learn what is process synchronization and why we need it.

Photo by Daniel Klein on Unsplash

Process synchronization is a method used to manage processes that use shared data. There are two types of processes in the operating system:-

1. Independent Processes: These processes don’t affect or gets affected by other processes while it is executing. Example- The processes that don't share data, files, etc.
2. Cooperating Processes: These processes affect or get affected while it is executing. Example: The process that shares data, files, etc.

Whenever two processes try to communicate with each other then they require shared memory. This may cause data inconsistency as both the process can write the data independently in any order. This is the reason we need process synchronization. These types of processes are cooperating processes.

Process Synchronization is used for cooperating processes that use shared resources.

Race Condition: It is a condition where several processes try to access the shared resource and modify the shared data. The order of execution of instructions defines the result produced.

Before moving forward we will go through important terms that will be used throughout the blog.

Diagram showing critical section.

Following are the definition of the above-mentioned terms in the diagram

Entry Section: This decides which process will enter the critical section out of many processes that are trying to enter the critical section.

Critical Section: It is the part of the program where shared resources are accessed by the processes. At a time only one process can access this section.

Exit Section: This section helps other processes to access the critical section by changing some flags that we will encounter later. Once a process finishes its execution in a critical section then it is removed through the critical section.

Non-critical section: The part of the program other than the entry, critical, and exit sections is called the non-critical section.

Now we will see the conditions that are necessary to guarantee process synchronization. These are as follows:

1. Mutual Exclusion: This ensures that at a time only one process should be able to access the critical section.
2. Progress: This states that if a process doesn’t want to access the critical section then it should not stop other processes to access the critical section.
3. Bounded waiting: A process that is waiting to get access to the critical section should not wait for a very long period of time. There should be an upper bound on the waiting time.
4. Portability or architectural neutrality: The synchronization should be platform-independent. This means if a solution works on one architecture then it should also work on other architecture.

There are two types of synchronization mechanisms

1. With busy waiting: In this, the process which is trying to access the critical section continuously tries to get into the critical section by checking the condition. This wastes CPU time.
2. Without busy waiting: In this, the process which is trying to access the critical section checks the condition only once. If another process is present in the critical section then it goes to sleep. When the process in the critical section gets completed then this process is waked.

In this section, we will see various synchronization mechanisms.

1. Lock variable: This is a software mechanism implemented in user mode. This is a busy waiting solution and can be used for more than two processes. In this mechanism, we use a lock variable. A process that wants to enter the critical section check if the lock is 0 or not. If it is zero then it changes the lock variable to 1 and enters the critical section, otherwise, it waits. When it exits the critical section it resets the lock to zero. Given below is the pseudo-code of this mechanism:

pseudo-code of lock variable mechanism

Now assume we have two processes p0 and p1. Initially assume lock is 0 and p0 tries to access the critical section. Since the lock is 0 while loop will break. Now if p0 gets pre-empted because of some reason and p1 gets scheduled. It will see the lock value 0 and will also break the while loop and set the lock to 1 and enter the critical section. Now the state of p0 is changed from waiting to running and since it has checked earlier that lock was 0, it will also set the lock to 1 and will enter the critical section. Now we have 2 processes in the critical section which violate the mutual exclusion condition. Hence this cannot be used for process synchronization.

2. Test And Set Lock: This mechanism is a modification to the lock variable mechanism. In the local variable mechanism, checking the lock and setting it to 1 were 2 separate instructions, but in this mechanism, these two are treated as an atomic instruction. This is achieved by modifying assembly-level code. Atomic instruction means both the instruction will be treated as single instruction and will be executed together.

This can be achieved if the hardware and operating system provide special instruction. This instruction is called TSL(Test and Set Lock). Hence this is a hardware approach to synchronization.

Mutual exclusion is guaranteed as preemption can not occur before setting the lock variable to 1.

A process that doesn't want to enter the critical section will not execute TSL instruction. Hence this guarantees progress.

Bounded waiting and architectural neutrality are not guaranteed.

The drawback of TSL is that it can cause priority inversion.

Let's assume p0 is in the critical section and now p1 arrives which has a higher priority than p0. Therefore, the scheduler wants to preempt p0 and execute p2, but because of the synchronization mechanism, it cannot do so. Here p1 wants the critical section but p0 needs CPU to move out of the critical section, but CPU is busy with p1. This condition is called spin-lock.

Now because of this, a low priority process is in the critical section instead of a high priority process. This condition is called priority inversion.

3. Disabling Interrupts: This is hardware implementation. We can use interrupts to synchronize the process so that at a time only one process enters the critical section.

This is done by disabling the interrupt before entering into the critical section and after exiting the critical section, enable the interrupt. Once the interrupt is disabled none of the processes can be preempted thus only one process can be present in the critical section. This guarantees mutual exclusion.

If a process doesn’t want to enter the critical section then the interrupt remains enabled and other processes can enter the critical section. Hence process is guaranteed.

Bounded waiting and architectural neutrality are not guaranteed.

4. Turn Variable or Strict Alteration Method: This is a software mechanism implemented in user mode. This is a busy waiting solution that works for 2 processes only. In this approach, the two process shares the same variable called turn variable. The pseudo-code is given below

pseudo-code for turn variable mechanism.

Mutual exclusion is guaranteed.

Progress is not guaranteed as the process which is having the key will not release the key unless it had entered the critical section. This can be handled using interested variable. We will see this in Peterson’s Solution.

The process has to release the key once it comes out of the critical section. After entering once into the critical section the process has to release the key. Therefore bounded waiting is guaranteed.

This is architectural neutral as it doesn't depend on the hardware or operating system.

5. Peterson’s Solution/Dekker’s Algorithm: This is a software mechanism implemented in user-mode. This is 2 process solution with busy waiting. This solution is a combination of a turn variable and an interested variable. Interested variable used to indicate which process is interested to access critical section. The pseudo-code of the mechanism is given below:

pseudo-code of Peterson’s Solution

You can try to take two processes p0 and p1 and check for various scenarios. This algorithm will always ensure that only one process accesses the critical section at once. I suggest you do it yourself with pen and paper. This will make it more clear.

Mutual exclusion is guaranteed.

Progress is guaranteed.

This is architectural neutral.

In this mechanism, the process which sets the value of turn 1st enters the critical section. Hence this method guarantees bounded waiting.

6. Sleep and Wake(Producer and Consumer Problem): This is a software mechanism that is without busy waiting. This works for any number of processes. Below is the pseudo-code of the algorithm.

pseudo-code for the producer-consumer problem.

There is a problem with this method as some conditions may arise where a wake-up call gets wasted.

Explanation: Suppose on line 22 after checking the if condition the function consumer() gets preempted without going to sleep. (Here the initial value of the count is 0).

Now the function producer gets executed. Since the count is 0. Therefore on line 13, the value of count will be incremented to 1. Because of this on line 15 a wake-up call will be done to the consumer but the consumer is not sleeping right now. Therefore wake-up call is wasted.

Now after some time consumer will go to sleep and the producer will also go to sleep when its buffer is full thinking that the consumer will wake up. This causes the problem.

This can be solved by maintaining a bit. If the bit is set(i.e. 1) then don’t sleep and if it is not set(i.e. 0) then go to sleep. This mechanism is called Semaphore. This needs the support of the operating system.

I will not make this very long. I Will cover Semaphores in the next article.

I hope this clears how process synchronization is done in an operating system.

If you have any questions please do ask in the comments.

References :

1. https://www.javatpoint.com/os-process-synchronization-introduction
2. https://en.wikipedia.org/wiki/Synchronization_(computer_science)