In this post, we will study about process synchronization in operating system. We will see how to maintain shared data consistency between cooperating processes. We will learn about critical section, it’s problem and solution using Peterson’s solution, hardware synchronization etc.

Process Synchronization is a way to coordinate process that use the shared data. It means sharing system resources by processes in such a way that concurrent access to shared data is handled, thereby, minimizing the chance of inconsistent data.

On the basis of synchronization, there are two types of process categorized.

1. Independent Process: When one process is executing, it doesn’t affect other executing processes.
2. Cooperative Process: When one process is executing, it affects other executing processes.

Process synchronization helps to maintain shared data consistency and cooperating process execution. When processes execute, it should be ensured that concurrent access to shared data does not create inconsistencies.

Race Condition: A race condition occurs when two or more processes are executed at the same time, not scheduled in proper sequence and not executed in the critical section correctly.

In process synchronization, we will see the how to maintain data consistency between cooperating processes. We will learn about critical section that is shared between different processes.

1. Critical Section

Critical Section is a segment of code that can be accessed by only one process at a time. It contains shared resources that need to be accessed by all processes. If one process is executing in Critical Section, then, other process has to wait until the first one finishes.

The structure of Critical Section is –

Critical Section Structure

Since only one process can access critical section, all other process must be stopped from accessing it. There should be some requirements that must be fulfilled while accessing it.

2. Requirements of Critical Section

Critical Section problem must satisfy three requirements –

1. Mutual Exclusion: If process Pi is executing in its Critical Section, then, no other process can be executing in their Critical Sections.
2. Progress: If no process is executing in its Critical Section and there exist some process that wish to enter their Critical Section, then the selection of the processes that will enter the Critical Section can’t be postponed indefinitely.
3. Bounded Waiting: After a process makes a request for getting into its Critical Section, there is a limit for how many other processes can get into their Critical Section, before this process’s request is granted. So, after the limit is reached, system must grant the process permission to get into its Critical Section.

3. Solution to Critical Section Problem

In Process Synchronization, critical section play a main role So, it’s problem must be solved. We can solve this critical section problem using Peterson’s solution or hardware synchronization or attempting an approach for hardware to provide certain atomic operations. We will go through it one by one.

3.1 Peterson’s Solution

Peterson’s solution is a software based solution, developed by Gary L Perterson in 1981, to the Critical Section problem. It a programming algorithm for mutual exclusion that allows two or more processes to share single-use resource without conflict. It uses shared memory for communication. Here, we are going to discuss the solution only for 2 processes. However, it can be generalised for n processes as well.

Peterson’s solution for 2 processes

It is based on two processes P0 and P1, which allows them to alternatively get access to Critical Section and Remainder Section.

Peterson’s Solution requires two shared data items:
(i) Boolean flag [i]: Initialized to FALSE. This is because no processes are allowed to enter into critical section. When process wants to enter their Critical Section, it sets flag [i] to true.

(ii) int TURN: Indicates whose turn is it to enter into the Critical Section. If Turn == i, then process i is allowed into their Critical Section.

Peterson’s Algorithm

In the entry section, process i first raises flag and wants to enter the Critical Section. Then, turn is set to j to allow to another process to enter their Critical Section if process j wants.
The while loop is a busy loop (semicolon at the end), which makes process i wait as long as process j has the turn and wants to enter the Critical Section. Process i false the flag in the exit Section, allowing process j to continue if it is waiting.

Peterson’s Solution satisfy all three conditions:

1. Mutual Exclusion: Mutual exclusion is assured as only one process can access the Critical Section at any time. If both processes attempt to enter at the same time, the last process to execute “turn = j” will be blocked.
2. Progress: Progress is also satisfied. A process outside the Critical Section does not blocks other processes from entering the Critical Section. The flag variable allows one process to release the other when exiting their Critical Section.
3. Bounded Waiting: Bounded waiting assure that each process will have to let the other process go first at most one time before it becomes their turn again. Thus, bounded waiting is also assured as each process gets a fair chance.

Drawback of this Peterson’s Solution

• It is limited for 2 processes.
• It involves busy waiting.

3.2 Generalized Solution of Critical Section Problem

To generalize the solution, you can use below techniques –

(a) Hardware Synchronization
(b) Atomic Operation

(a) Hardware Synchronization

To generalize the solution of critical-section problem, each process when entering their Critical Section must set some sort of locks. This is done to prevent the other processes from entering their Critical Section simultaneously. Process must release the lock when exiting their Critical Section. This is done to allow another process to enter into their critical section.

Solution using Locks –

Solution using Lock

(b) Atomic Operations

Another approach is for hardware to provide certain atomic operations. There are two approach for this operation.

1. Test and Set operation.
2. Swap contents of two memory words.

1. Test and Set instructions

This operation sets a Boolean lock variable and returns it previous value.

Definition

Boolean TestAndSet(Boolean *target) {
    Boolean rv = *target;
    *target = TRUE; 
    Return rv;
}

Solution

lock = false; //shared Boolean variable 
do {
   While(TestAndSet(&lock)); 
      //Critical Section
   lock = false;
      // remainder section
} while(true);

2. Swap Instructions

Another method is Swap instruction. There are two Boolean variables to compare and swap.

Definition:

Void Swap(boolean *a, boolean *b)
{
    boolean temp = *a; 
    *a = *b;
    *b = temp;
}

Solution using Swap:
Shared Boolean variable lock initialized to false. Each process has a local Boolean variable key.

do {
Key = true;
While(Key == true) 
  Swap(&lock, &Key);
// Critical Section 
lock = false;
// remainder section 
} while(true);

These examples ( Test and Set instructions, Swap instructions) satisfy the mutual exclusion requirement and progress. But, they don’t give surety about bounded waiting. If there are multiple processes trying to get into their Critical Sections. There is no surety on what order they will enter. Moreover, any one process could have the bad luck to wait forever until they got their turn into Critical Section.

That’s end of first part of tutorial on Process Synchronization in operating system. Go to next post to learn more…