Process Synchronization

1. Types of process

On the basis of synchronization, processes are categorized as one of the following two types:

• Independent Process : Execution of one process does not affects the execution of other processes.

• Cooperative Process : Execution of one process affects the execution of other processes.

2. Race Condition

Process synchronization problem arises in the case of Cooperative process also because resources are shared in Cooperative processes. Race Condition When more than one processes are executing the same code or accessing the same memory or any shared variable in that condition there is a possibility that the output or the value of the shared variable is wrong so for that all the processes doing the race to say that my output is correct this condition known as a race condition. Several processes access and process the manipulations over the same data concurrently, then the outcome depends on the particular order in which the access takes place. A race condition is a situation that may occur inside a critical section.

3. Critical Section Problem

Critical section is a code segment that can be accessed by only one process at a time. Critical section contains shared variables which need to be synchronized to maintain consistency of data variables.

In the entry section, the process requests for entry in the Critical Section.

4. Solution for process synchronization

Any solution to the critical section problem must satisfy three requirements:

• Mutual Exclusion : If a process is executing in its critical section, then no other process is allowed to execute in the critical section.

• Progress : If no process is executing in the critical section and other processes are waiting outside the critical section, then only those processes that are not executing in their remainder section can participate in deciding which will enter in the critical section next, and the selection can not be postponed indefinitely.

• Bounded Waiting : A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted.

5. Process synchronization Methods

1. Lock Variable:

A lock variable provides the simplest synchronization mechanism for processes.

1. Its a software mechanism implemented in user mode, i.e. no support required from the Operating System.

2. Its a busy waiting solution (keeps the CPU busy even when its technically waiting).

3. It can be used for more than two processes.

When Lock = 0 implies critical section is vacant (initial value) and Lock = 1 implies critical section occupied.

The pseudocode looks something like this –

Entry section - while(lock != 0);
                Lock = 1;
//critical section
Exit section - Lock = 0;

The Lock Variable doesn’t provide mutual exclusion in some cases.

2. Test and Set lock:-

TestAndSet(lock) algorithm works in this way – it always returns whatever value is sent to it and sets lock to true.

//Shared variable lock initialized to false
boolean lock;

boolean TestAndSet (boolean &target){
    boolean rv = target;
    target = true;
    return rv;
}

while(1){
    while (TestAndSet(lock));
    critical section
    lock = false;
    remainder section
}

3. Turn Variable or Strict Alternation Approach:

Turn Variable or Strict Alternation Approach is the software mechanism implemented at user mode. It is a solution which can be implemented only for two processes.

For Process P0

1. Non - CS

2. while (turn ! = 0);

3. Critical Section

4. turn = 1;

5. Non - CS

For Process P1

1. Non - CS

2. while (turn ! = 1);

3. Critical Section

4. turn = 0;

5. Non - CS

Mutual Exclusion:- The strict alternation approach provides mutual exclusion in every case. This procedure works only for two processes.

Progress: - Progress is not guaranteed in this mechanism. If Pi doesn't want to get enter into the critical section on its turn then Pj got blocked for infinite time.

4. Semaphore

Semaphore is simply a variable that is non-negative and shared between threads. This variable is used to solve the critical section problem and to achieve process synchronization in the multiprocessing environment.

Semaphores are of two types:

1. Binary Semaphore This is also known as mutex lock. It can have only two values – 0 and 1. Its value is initialized to 1. It is used to implement the solution of critical section problems with multiple processes.

2. Counting Semaphore Its value can range over an unrestricted domain. It is used to control access to a resource that has multiple instances.

P operation is also called wait, sleep, or down operation, and V operation is also called signal, wake-up, or up operation.

P(Semaphore s)
{
    s.value = s.value - 1;
    if (s.value < 0)
    {

        // add process to queue
        // here p is a process which is currently executing
        q.push(p);
        block();
    }
    else
        return;
}

V(Semaphore s)
{
    s.value = s.value + 1;
    if (s.value <= 0)
    {

        // remove process p from queue
        Process p = q.pop();
        wakeup(p);
    }
    else
        return;
}