Awesome q2a theme
0 votes
32 views

 please help me to fill these table with YES/NO

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        
in Operating System by (3.7k points) | 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 Answer

+1 vote
Best answer

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 :
    Load R,lock;
    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

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 :

https://gateoverflow.in/220104/doubt-on-progress-bounded-waiting-and-deadlock

https://gateoverflow.in/68510/synchronization-self-doubt

https://gateoverflow.in/38610/does-deadlock-imply-no-bounded-waiting-progress-both-these?show=38610#q38610

by (493 points)
selected by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Dec 2019
  1. Pratyush Priyam Kuan

    158 Points

  2. Vimal Patel

    118 Points

  3. avistein

    65 Points

  4. srestha

    54 Points

  5. Mk Utkarsh

    49 Points

  6. arya_stark

    46 Points

  7. goxul

    39 Points

  8. Sathuri Bharath

    34 Points

  9. vishal burnwal

    31 Points

  10. Shaik Masthan

    26 Points

Monthly Top User and those within 60% of his/her points will get a share of monthly revenue of GO subject to a minimum payout of Rs. 500. Current monthly budget for Top Users is Rs. 75.
2,313 questions
1,294 answers
6,587 comments
89,719 users