Process Synchronization: operating systems.

Processes can be Synchronous, Asynchronous and Independent. Often there occurs a Race Condition. A race condition occurs when multiple threads/processes try to access/read/write concurrently. The part of the program that enables such a situation where a program accesses a shared resource is called as Critical section.

The Critical Section issue:

Until now we have understood what is a critical section .Now if a process needs to access some resources and adding to that sin, it’s a shared resource.

We have to make sure that when the same process is within the critical section, no other section should enter the critical section. Basically it’s like a single bathroom , so only one person shall be allowed to enter( unless it’s their choice XD).

So we need to graduate an algorithm/protocol that the processes shall follow and hence tread seamlessly through the critical section.

Constrains:

The algorithms that we want as a solution shall fulfil some requirements.

1. Mutual exclusion: Only one process can execute in it’s critical section and no other.
2. Progress: If a process wants to be in C.S then only it will be allowed. If multiple processes wants, then only one of them shall succeed.
3. Bounded Waiting : An bound to the number of times other processes entering to their critical sections after a process has made it’s request

Turn variable, Two process solution:

let us consider 2 processes p1 and p2.

Now let’s discuss the structures of both the processes.

p1:

while(1){
while(turn!=0);
Critical Section
turn =1;
remainder section:
}

p2:

while(1){
while(turn!=1);
Critical Section
turn =0;
remainder section:
}

when the value of turn=0;

p1 can enter the critical section. And if there is context switch in between then also p2 cant interfere as turn value is 0 so p2 will be in an infinite loop.

Once p1 come out of the critical section it makes turn=1. So if next p2 wants to enter, it can.

Here Mutual exclusion is obeyed but Progress isn’t. A process isn’t being asked if it really wants to go to critical section.

Flag variable Method:

We take same P1 and P2:

P1:

while(1){
flag[0]=true;
while(flag[1]);
Critical Section
flag[0]=false;
remainder section:
}

P2:

while(1){
flag[0]=true;
while(flag[0]);
Critical Section
flag[1]=false;
remainder section:
}

Here we take an boolean array

flag={false, false};

if p1 wants to enter, it marks flag[0] as true and checks if the other process is inside C.S . If it’s not then P2 can simply enter C.S .

But if there is a context switch after the true initialization of p1 to p2. Then we get a dead lock. Both values are true and there’s no end to it. So this method also fails in Progress.

Paterson’s Algorithm:

This is somewhat a hybrid of the above algorithm’s.

P1:

while(1){
flag[0]=true;
turn=1;
while(flag[1] && turn==1);
Critical Section
flag[0]=false;
remainder section:
}

P2:

while(1){
flag[1]=true;
turn=0;
while(flag[0] && turn==0);
Critical Section
flag[1]=false;
remainder section:
}

We can clearly see the advantage here, we not only get the decision of the process to be included or not, but also the mutual exclusion holds perfectly. And we don’t even get any deadlock situation.

But Paterson’s Algorithm works good only for 2 process systems. For multiple cases we will see Semaphores (next article).