Process Synchronization

Multiple processes can run in either serial mode, which means one process in execution at a time or in parallel mode, where multiple processes are executed parallely at one moment.
Two types of Processes - Cooperative Processes & Independent Processes.
The execution of one cooperaive process has effects on other processes, because they share something in common. This can be variable, memory, code, resources like CPU, Printer etc.
The execution of independent processes doesn't affect other processes running, as they do not share something in common.
Cooperative processes need to be synchronized properly, otherwise it may lead to problems like race condition.
Critical Section - It is a part of program where shared resources are accessed by various concurrent cooperative processes.
If one program is using the critical section, then at the same time, no other program can use the critical section. If two programs use the critical section at the same time, then race condition will occur.
If a program wants to use the critical section, then the code written in entry section has to be executed. If entry section executes without any problems, the program can enter into the critical section and execute the lines of code written there. When program finishes the critical section, an exit section is also coded. The stuff that is not common is put into the rest of section called the non-critical section. These help in preventing problems like race condition.

Some Questions For Practice

Q. Do the producer consumer, printer spooler problem, which is the standard problem for multiple process synchronization.
Q. Practice critical section solution using 'Lock' variable.
Q. Practice critical section solution using 'Test_and_Set' instruction.
Q. Practice critical section solution using 'Turn Variable(Strict alteration)' method.
Q. Practice process synchronization solution using 'Semaphores' method.
Q. Practice producer consumer problem using 'Semaphore'.
Q. Practice Readers-writers problem using 'Binary Semaphore'.
Q. Practice dining philosophers problem using 'Semaphore'.
Q. Producer Consumer Problem Using Semaphores.
Q. Readers Writers Problem Using Binary Semaphore.
Q. Dining Philosophers Problem Using Semaphore.

Producer Consumer Problem

C language program for consumer:

load Rc, m[count]
DECR Rc
Store m[Count], Rc

Consumer takes items from the buffer and processes/consumes them.

void consumer(void){
int itemc;
while(true){
    while(count == 0){
        itemc = Buffer(out);
        out = (out + 1) % n;
        count = count - 1;
        Process_item(itemc);
        }
    }
}

C language program for producer:

load Rp, m[Count]
INCR Rp
Store m[Count], Rp

Producer makes/produces an item and puts it into the buffer.

int count = 0;
void producer(void){
    int  itemp;
    while(true){
        Produce_item(itemp);
        while(count == n){
            Buffer[in] = itemp;
            in = (in + 1) % n;
            count = count + 1;
        }
    }
}

Lets say n = 8 Three variables have to be tracked : in, out & count The buffer and count variables are shared by both producer and consumer program.

Buffer[0.....n-1]
0
1
2
3
4
5
6
7

Printer Spooler Problem

Load Ri, m[in]
Store SD[Ri], "F-N"
INCR Ri
Store m[in], Ri

Keep incrementing the 'in' variable and keep storing the processes in the spooler directory.

Printer's Spooler Directory
0
1
2
3
4
.
.

Synchronization Mechanism

4 Conditions/Rules:

Mutual Exclusion
Progress
Bounded Wait
No assumption related to hardware, speed etc.

Rule 1 & 2 are primary conditions, they have to be fulfilled. Rule 3 & 4 are secondary conditions, which means they are not compulsory for synchronization, but we try to implement them.

Critical Section Solution Using 'Lock'

do{
    acquire lock
    CS
    release lock
}

While(LOCK == 1) (Entry
LOCK = 1 Code)
Critical Section
LOCK = 0 (Exit Code)

Lock 0 means critical section is vacant Lock 1 means critical section is full

Critical Section Solution Using 'Test_and_Set' Instruction

while(test_and_set(&lock)){
CS
lock = false;
}
boolean test_and_set(boolean *target){
boolean r = *target;
*target = TRUE;
return r;
}

Critical Section Solution Using 'Turn Variable(Strict Alteration)' Method

2 process solution
Runs in user mode

	Process 'P0'	Process 'P1'
Entry Code :	While(turn != 0);	while(turn != 1);
CS	critical section	critical section
Exit Code :	turn = 1;	turn = 0;

Process Synchronization Using Semaphores

Semaphore is an integer variable which is used in mutual exclusive manner by various concurrent cooperative processes in order to achieve synchronization. Two types - Counting(-Infinity to +Infinity) and Binary(0, 1).

Two Operations:

P(), Down, Wait
V(), Up, Signal, Post, Release

C Pseudocode for Down

Down(Semaphore S){
    S.Value = S.Value - 1;
    if(S.Value < 0){
    // Put Process (PCB) in Suspended List
    Sleep();
    }
    else{
    return;
    }
}

C Pseudocode for Up

Up(Semaphore S){
    S.Value = S.Value + 1;
    if(S.Value <= 0){
    // Select a process from suspended list
    WakeUp();
    }
}

Binary Semaphores

C Pseudocode for Down

Down(Semaphore S){
    if(S.Value == 1){
        S.Value = 0;
    }
    else{
        //Block this process and place in suspened list
        Sleep();
    }
}

C Pseudocode for Up

Up(Semaphore S){
    if(Suspend list is empty){
    S.Value = 1;
    }
    else {
        //Select a process from suspend list and
        WakeUp();
    }
}