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 theprinciple, since only 1 process should access critical section at once.
Naive attempt 2
Have a register:
Turn = 0
while (Turn != 0); // Turn = 0, acquire critical_section(); Turn = 1;
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.
- 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
Naive attempt 3
Have 2 registers: I, J
I = 1; while(J); critical_section(); J = 0;
J = 1; while(I); critical_section(); I = 0;
Now, we have 2 slots. When we want to access a resource we do 2 things:
- Update the register assigned to us
- 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: