GATE CSE
First time here? Checkout the FAQ!
x
0 votes
262 views
I have some fundamental doubts regarding the conditions which need to be followed for a correct synchronisation solution i.e. about mutual exclusion , progress and bounded wait. I m asking these. Plz address to these doubts but give a valid reason prior to conlusion.So ,

Q 1 . Can bounded wait condition be invalidated for 2 process solution ? If yes ,plz explain how ?

Q 2.  Is it true that the entry section is the decisive factor for the fact whether the solution satisfies mutual exclusion and progress condition and remainder section for the fact whether the bounded wait condition is satisfied or not? Also plz support your answer with proper reason..
asked in Operating System by Veteran (87k points) 15 57 292 | 262 views

2 Answers

+6 votes
Best answer

Deadlock and Bounded waiting are independent of each other . What bounded waiting says => That if a process expresses its desire to enter critical section then there exists a bound on the number of processes that can enter CS, after this request has been made .

Take the function B = Count of the processes that can enter CS after any process has made a request .

1). One of the GATE questions,

/*  P1   */
while (true) {
    wants1 = true;
    while (wants2 == true);
    /* Critical Section */
    wants1 = false;
}
/* Remainder section */

/*  P2   */
while (true) {
    wants2 = true;
    while (wants1 == true);
    /* Critical Section */
    wants2=false;
}
/* Remainder section */

Clearly, Deadlock can happen in this case but is the BW satisfied ?

Yes, it is as when P1 and P2 are both in a while loop busy waiting , then both are desiring to go into the CS. So, suppose P1 wants to enter CS , then think of the case that how many times P2 has bypassed P1 before P1 is allowed to enter critical section. If you agree, that the number of times a process P1 may be bypassed is 0 ,i.e, B = 0 then yes, bounded waiting holds .

But, any other condition was not given in this question like priority of any process is higher or anything else, we can think like this. But, if there is a synchronization protocol, like CPU always executes P2, and never provides P1 the CPU to execute.

Well thats how suppose Synchronization mechanism is programmed for P1 and P2, that Mutex is satisfied and Progress is satisfied, but CPU always makes P2 run. 

Now, if P1 has a desire to enter CS, then how many times has P2 bypassed it. It can be finite but not bounded, as there is a difference between Finite and bounded . So, it all depends on how the synchronization protocol is designed .


2). Yes, thats how the progress works. Progress means finite decisive time to enter critical section, that some day process will enter CS which is done in the entery section only.

For bounded waiting, How many processes in remainder section are allowed to enter CS after any other process has made a request . Also, all other parts of code which are not CS, i.e, except CS are called remainder sections, so how many of those processes are allowed to enter CS or bypass the process which has made a request to enter CS .

answered by Veteran (50.4k points) 22 90 410
selected by
So final conclusion is answer to both question is "YES" ??
Yes..
Ok fine..Thanks a lot @Kapilp
1)What is the difference between finite and bounded?

2)Is there any difference in bounded waiting and busy waiting?
For progress remainder sectionwill also matter
@Kapilp

Can u plz answer my query?

I think bounded waiting is finite.

And bounded waiting is called in another word busy waiting.

No difference at all
Bounded waiting as the name suggests is bounded . Finite is something that will surely happen . Dont know when but will happen but that is not the limit or bound , right ?

Busy waiting is different . It is wasting CPU cycles in a  while loop by repeatedly checking the condition inside while loop. Bounded waiting is different thing. i have provided the definition in the answer .
@Kapilp bounded means it has certain bound say 10,20 or 100 which is finite.

Can u have any link or source which differentiate between bound and finite??
Who they are downvoting comment of @Aakash plz give reason also why he is wrong??
#Strict Alteration Code

turn=0 initially

Process 0 can be written as:

 

while (TRUE)

{

     Non-CS

      while (turn != 0); //Entry section

     critical_ region();

     turn = 1 ;//Exit

    Non-CS

}

And code for Process 1:

while (TRUE)

{

    Non-CS

   while (turn != 1);//Entry

    critical_ region();

    turn = 0 ;//Exit

   Non-CS

}

We know Strict alteration not satisfy progress.

Here without seeing the code of exit section we cant decide progress satisfied or not .

See if I will make the code  turn=0 inside exit part of P0 then there is progress( but no bounded waiting) so   the decision of progress cant be taken by only seeing the Entry section.

And same ans  for the Bounded waiting.
Plz verify my above comment and my ans @Kapilp @habibkhan @Manojk
so we can say that if there is a bounded waiting  there can't be indefinite blocking?
Ya since when we say a solution satisfies bounded waiting , this means the bound is specified that after how many process the concerned process is going to get its chance .

In other words , a process will enter into a critical section after a stipulated number of processes leaves the remainder section of the code.

Hence bounded waiting prevents starvation (or) indefinite blocking.
0 votes
Bounded waiting:->>There exists a bound, or limit, on the number of times other processes are allowed to enter their critical sections after a process has made request to enter its critical section and before that request is granted.

Part1:->>
Yes; Bounded Waiting Can be violated with 2 processes.
#Psudocode

/* i is this process; j is the other process */

while (true)

{

         while (turn != i); /* spin until it’s my turn */      

           <<< critical section >>>

            turn = j;

             <<< code outside critical section >>>

}

Here Only Process i Get acess to CS repetadely but process j never gets CS (though it may get CPU time).

So No bounded Waiting for Process j.

Part2:->> partialy Yes

Mutual exclusion is implemented @entry section to restrict malfunction of cuncurrent processes at the critical section where shared resources are used.

But wheather ME satisfy or not we cant take decision by looking only @Entry section it depends on code of Exit section also.

I M commenting for Progress and  Bounded waiting.
answered by Veteran (20.3k points) 13 78 206
edited by

Related questions

0 votes
0 answers
2
asked in Operating System by Arnabi Boss (6.9k points) 5 30 84 | 126 views
0 votes
1 answer
3
asked in Operating System by agoh Active (1.9k points) 1 14 33 | 94 views


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
Top Users Oct 2017
  1. Arjun

    23210 Points

  2. Bikram

    17018 Points

  3. Habibkhan

    6652 Points

  4. srestha

    5864 Points

  5. Debashish Deka

    5430 Points

  6. jothee

    4908 Points

  7. Sachin Mittal 1

    4762 Points

  8. joshi_nitish

    4274 Points

  9. sushmita

    3954 Points

  10. Silpa

    3698 Points


Recent Badges

Regular Juhi Sehgal
Popular Question vineet.ildm
Nice Comment Arjun
100 Club vipul verma
Notable Question jothee
Popular Question jothee
Nice Question shivangi5
Regular rinks5
Notable Question shipra tressa
Regular sasi
27,247 questions
35,056 answers
83,703 comments
33,183 users