naive Critical section implementation

Naive attempt 1

Have a register: Lock

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

critical_section();

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
critical_section();
Turn = 1;

Process B

while (Turn != 1); // Turn = 1, acquire
critical_section();
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.

Assumption:

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

Problems:

  • 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;
while(J);
critical_section();
J = 0;

Process B

J = 1;
while(I);
critical_section();
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:

A

while(J)

B

while(I)

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

logo