naive Critical section implementation

Naive attempt 1

Have a register: Lock

while (Lock != 0); // poll for lock = 0
Lock = 1; // acquire lock


Lock = 0; // release

However, 2 processes can access a Lock at the same time!

We have a scenario where p1, p2 access Lock, see it is 0. They both then proceed to update Lock = 1. and access the critical section together.

This is incorrect and violates the Mutual exclusion principle, since only 1 process should access critical section at once.

Naive attempt 2

Have a register: Turn = 0

Process A

while (Turn != 0); // Turn = 0, acquire
Turn = 1;

Process B

while (Turn != 1); // Turn = 1, acquire
Turn = 0;

Now even if they accessed Turn at the same time, because each have a specific value of turn, only 1 process will gain access.


  • A & B executes the above in loop
  • Take turn to enter critical section


  • Starvation: if A never runs, it never enters CS, it also never updates Turn. So B starves

  • Violates the Independence property

Naive attempt 3

Have 2 registers: I, J

Process A

I = 1;
J = 0;

Process B

J = 1;
I = 0;

Now, we have 2 slots. When we want to access a resource we do 2 things:

  1. Update the register assigned to us
  2. Continue if the register for the other process indicates it is done

Now, in the scenario that A does not trigger, B still gets cleared:

Register I (assigned to A) = 0 So B is able to continue on executing.

However, we can still have a deadlock!

Both A, B enter:

They update their respective registers => I = 1, J = 1

Then both of them get stuck:





Previously we used Turn (in naive attempt 2), to ensure that although 2 processes might access concurrently, only one can trigger when acquiring a lock.

The current solution works well, with the only shortfall of both acquiring a lock.

It solves the problem of just turn above, since we do not have to wait for a specific process to kickstart.

See the actual solution: peterson’s algorithm