32 views

SYNCHRONIZATION MECHANISMS

 DISABLE INTERRUPTS LOCK  VARIABLE STRICT ALTERATION PETERSON SOLUTION TEST AND SET LOCK INSTRUCTION SLEEP AND WAKE UP BINARY SEMAPHORE COUNTING SEMAPHORE MUTUAL EXCLUSION IS SATISFIED ? NO YES YES YES YES PROGRESS IS SATISFIED ? YES NO YES YES BOUNDED WAITING IS SATISFIED ? NO NO YES YES STRAVATION PROBLEM CAN OCCUR ? DEADLOCK CAN OCCUR ? DOES IT SUFFERS FROM BUSY WAITING PROBLEM ? NO YES YES YES NO SOFTWARE OR HARDWARE BASED IMPLEMENATION ? HARDWARE SOFTWARE SOFTWARE SOFTWARE
| 32 views
0

@Satbir

If counting or binary semaphore satisfy or not, it depends on code , on which it is executing

0
yes ,

so we can have starvation and deadlock problem and all other problems mentioned above when using semaphores ?
0
Strict alteration, ME satisfied but Progress maynot satisfied and bounded waiting maynot satisfied too, but sometimes it will satisfy.
0

@Satbir

how r u telling that lock variable doesnot satisfy ME and BW?

0
entry section

{

while(lock!=0);

lock

}

Critical section

exit section

{

lock=0;

}

If lock is not 0 then we have busy waiting.

It does not guarantees mutual exclusion since the instruction can split into multiple instructions.

0
U mean shared lock or read lock. right??

But that thing , I havenot seen in any prev year question. Have u seen any?
0
No...but seen them in test series. The above is the code when using lock variable.

+1 vote

LOCK VARIABLE :-

//Following code is in high level language
//Entry Section
while(lock!=0)
lock=1;

// Start of Critical Section
CS

// Exit Section
lock=0;

//Equvivalent Machine Language Code, LOCK is a variable in memory.

loop :
cmp R,0;
jz enter;
jump loop;
enter:
store lock,1

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

Progress Satisfied

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
while(turn==j);

CS

//exit section of Pi
turn=j;


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 :-

https://gateoverflow.in/226875/critical-section

PetersonSynchronizing Method :-

ME and Progress and Bounded waiting is Satisfied.

No H/w Support need

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