LOCK VARIABLE :-
//Following code is in high level language
// Start of Critical Section
// Exit Section
//Equvivalent Machine Language Code, LOCK is a variable in memory.
By checking the code in High Level language, we thought " Mutual Exclusion " is Satisfied, but when we observe the code in low level Machine instructions, if we preempt process Pi after the instruction cmp and executing another process Pj... Then both Pi and Pj can enter into the Critical Section.
Mutual Exclusion Fails
Is it Satisfies the progress ? The process which are not interesting to enter into the CS, doesn't stop the process which are willing to enter inn CS
Is it Bounded Waiting Satisfied ?
let P1 enter into CS... P2 continuously waiting in while loop .... P3 also continuously waiting in while loop...
now P1 exit from CS, and P3 entered into CS.
Now P1 again want to enter into CS, P1 is continuously waiting in while loop,
now P3 exit from CS, and P1 entered into CS.
Now P3 again want to enter into CS, P3 is continuously waiting in while loop,
now P1 exit from CS, and P3 entered into CS...... Same steps repeats
it conclude, there is no bound time to enter into cs for P2. ===> Bounded waiting not satisfied.
in general, in these types Unless you maintain a queue for waiting processes, you can't satisfied the Bounded Waiting.
Starvation also possible But not deadlock due to Mutual exclusion which is a necessary condition fails.
Processes continuously executing While loop for entering into CS ==> Busy waiting
There is no H/W support we took in this model.
For this same code, if we take H/W support for Testing and Setting the Lock as atomic
ME, progress guarenteed but Bounded Waiting not guarenteed.
Starvation may happen but not the Deadlock.
STRICT ALTERATION :- Between Two processes Pi and Pj
//entry section of Pi
//exit section of Pi
only one process can enter into CS ===> ME satisfied
let initially turn = i and Pi wants to CS, but Pj not interested to enter into CS.
Pi can enter into CS, after sometime Pi exit.
now Pi again wants to enter into CS where Pj still not interested... But Pi can not enter into CS ===> progress not satisfied.
Pi enters and exit, then next Pj should be enter and exit, after that Pi enters and exit....... ==> BW guarenteed.
No Hardware Support we took in this model.
Starvation may possible but not the deadlock.
Interested Method :-
PetersonSynchronizing Method :-
ME and Progress and Bounded waiting is Satisfied.
No H/w Support need
Deadlock not possibile
suffer from busy waiting.
Coming to semaphores and sleep and wake up,
ME and progress and deadlock ---- depends upon code
Bounded waiting --- queue which follows FIFO ---- satisfied
Take H/w support.
All are Non-Busy waiting
other links :