I was reading about Peterson's Solution for Synchronisation. Let's assume the two shared variables to be int bool flag[2] and turn. Lets also consider the two processes as P0 and P1.

Initially, P0 executes causing - flag[0] = true and turn = 1. Now lets assume P0 is pre-empted by P1 causing - flag[1] = true and turn = 0

Now, busy waiting condition of P1

while(flag[0] == true && turn == 0);

puts P1 on an indefinite wait until P0 resumes its execution, completes it and turns flag[0] = false. But wouldn't this again require P1 to be pre-empted, and bring back P0 from 'Ready' to 'Running' and get it executed ? So does a process pre-empt if it's busy waiting?


There are two broad concepts at play here: "synchronization" and "pre-emption". To make sure both processes run mutually exclusively, they first try to make sure the other one executes in the hope that in the future, the other process will ultimately unblock them by setting their respective flags.

To make sure both processes run to completion on this premise, the OS or any scheduler for that matter, should ensure that both processes are given their share on the CPU. Now coming to your question:

So does a process pre-empt if it's busy waiting?

Yes, absolutely. If the scheduler (OS) upholds multi-tasking (say round-robin scheduling?) then the busy-waiting process will indeed pre-empt at some point in time. But keep in mind things get a little complicated when features like process priorities are added into play.

The other question:

But wouldn't this again require P1 to be pre-empted, and bring back P0 from 'Ready' to 'Running' and get it executed ?

follows the answer to previous question that P1 would be pre-empted and eventually, P0 will run to completion thereby allowing P1 to also run to completion.

Final thoughts:

This is a basic synchronization primitive and a great example to help understand synchronization/mutual exclusion concepts. But, it doesn't take into account performance and busy-waiting is definitely not good performance-wise. There are other primitives that operate in post-wait fashion instead of busy-wait (Semaphores, for instance) which could be a better option.


So does a process pre-empt if it's busy waiting? - yes. From the perspective of a pre-emptive scheduler it is yet another process consuming CPU cycles, and can be swapped out.

But wouldn't this again require P1 to be pre-empted, and bring back P0 from 'Ready' to 'Running' and get it executed ? - No, this will not be required.

Let's consider the following for reference, (from Sec. 2.3 Modern Operating Systems 4th edition by Andrew S. Tanenbaum & Herbert Bos)

#define FALSE 0
#define TRUE 1
#define N 2 /*number of processes*/
int turn; /*whose turn is it?*/
int interested[N]; /*all values initially 0 (FALSE)*/
void enter_region(int process); /*process is 0 or 1*/
    int other; /*number of the other process*/
    other = 1-process; /*the opposite of process*/
    interested[process] = TRUE; /*show that you are interested*/
    turn = process; /*set flag*/
    while (turn == process && interested[other] == TRUE) /*null statement*/;
void leave_region(int process) /*process: who is leaving*/
    interested[process] = FALSE; /*indicate departure from critical region*/

Initially both interested[0] and interested[1] are FALSE (interested here is the flag in your code) - indicating that no one is interested in entering the critical region initially.

As you mentioned, let's suppose process 0 needs to enter the critical region and calls into enter_region first. It sets interested[0] to TRUE, and turn to 0. Let's suppose process 0 is pre-empted now - before it could execute the while loop condition.

Process 1 needs the critical region and calls enter_region now, sets interested[1] to TRUE and turn to 1. The while loop condition is

while (turn == 1 && interested[0] == TRUE) 

Think of this is as, "if it's my turn but someone else is interested in getting in - be nice to them, let them in and wait here". (it is not while (turn == 0 && interested[0] == TRUE) like you've mentioned) process 1 enters the loop and cannot return.

Suppose the scheduler decides to pre-empt process 1 and process 0 gets a chance to run. It returns from enter_region immediately to enter the critical region. Remember that the loop condition for process 0 is turn == 0 && interested[1] == TRUE which is certainly not true at this time as turn is 1.

After some time let's suppose process 0 exits the critical region and calls leave_region - it sets interested[0] to FALSE indicating that it is not interested in the critical region anymore.

Later when process 1 gets to run again, it fails turn == 1 && interested[0] == TRUE (as interested[0] is FALSE), and enters the critical region - as you can see, process 1 did not have to wait for process 0 here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.