The Gateway to Computer Science Excellence
0 votes
407 views

B does not satisfy Bounded wait. Ans should be None of these only. Please verify.

in Operating System by Loyal (7.9k points) | 407 views
0
why its not satisfy bounded wait ..can you explain ur approach?
0
they can starve but bounded  wait .
0
Bounded wait is definitely satisfied. Since only two processes are there and if wait(P) wait(Q) wait(P) wait(Q) is the sequence then no matter how long a process uses the shared variable whenever other process $\textbf{willing} $ to use the shared variable will definitely be able to use them. Hence bounded waiting is always satisfied.
0
If there are more than 2 processes then there can be a chance that once process is getting starved due to other processes.
+1
for those who are saying bounded wait is satisfied, If a process enters the critical section, there is a chance that the same process will enter CS, again and again, violating the bounded wait requirement for the other process.
+1

There is no strict alteration or any other thing in the code which makes it satisfy bounded wait so according to me BOUNDED WAIT VIOLATED.

@Arjun sir, please check.

0
its called stravation not bounded waiting ..

and and these are not implied by each other
+1

 if you are saying that starvation and bounded wait are not related,

you can refer this link https://stackoverflow.com/questions/42871471/relation-between-starvation-freedom-and-bounded-waiting

0
See if a processes is going again and again inside the critical section means that process is $\textbf{willing}$ to enter the critical section and this is the definition of

$\textbf{Progress :}$if a process is running inside the critical section then no other process should make the running process to leave the critical section or if a process is not in the critical section then it should not restrict other $\textbf{willing}$ process to enter into the critical section.
0

 

  please tell whether compare and swap satisfy bounded wait or not!

 

0

@!KARAN @minal both of you please see above code and tell if it satisfies BW

0
0
Can you answer the above question? :)
+1

@Utkarsh Joshi you are correct and this is a very basic thing. But when the top coaching institute is making solutions like these what can we expect from students :) 

0
Hmm! Thanks sir :)
0

but @Arjun Sir, see the below implementation of wait and signal taken from Galvin.

Sir according to above implementation if semaphore value is less than 0 and one process(B) is blocked in list then if other process(A) performed signal then blocked process will be release from list then how that other process(A) will get chance again and again?  Please clarify this doubt. that's why bounded waiting should be satisfy here. Right sir?

@Arjun Sir, Please check the above point. I know i am troubling you. Please  check the above comment of mine. Whether its valid or not.

0

 you are talking about the pic you posted, or about the q i asked?

0
check the implementation of wait and signal from pic and relate this with your question. According to above implementation bounded waiting will be satisfy in question which you mentioned.
0

@Shubhgupta

Scheduler picks process from the list. It need not be a FIFO list. Hence, there is a chance that A can try to enter CS again and again and always get selected (by the scheduler). Thus, one cannot give a definite bound to waiting time for B.

0

@gauravkc, How there is a chance that A will get chance again and again if list is maintained one process A is performing signal operation on one semaphore then count will increase and process B will be released. in that sequence A even not entered in list. By the way Binary semaphore by default implements queue and for two process above solution will always satisfy bounded waiting.

0

@Shubhgupta I think you are correct or may be I'm missing something.

A cannot enter again. As soon as A performs Signal(P), B will get it's chance on P but will still be blocked on Wait(Q). When A performs Signal(Q), B enters CS. Now, if A tries again, it gets blocked as both semaphores are 0.

@Arjun Sir please check this.

0

@Utkarsh Joshi

I had the same doubt..posted this one before..check the answer here

https://gateoverflow.in/248790/test-series-checking-bounded-waiting

As you said A might be brought to Cpu again and again without letting B get it's chance is not right according to screenshot of implementation posted here.

When A is in CS and B tries to enter CS the semaphore value is -1 and B is sent to blocked state. Now when A executes Signal then B is removed from blocked state to ready state and semaphore value now is 0.

So doubt is what if A executes wait again and gets selected by CPU. But that won't happen because when A executes Wait then semaphore value becomes -1 from 0. So now A is blocked.

Correct me if you find this wrong.

0

@ can a binary semaphore have value -1? 

0

@Utkarsh Joshi

no.. okay then the implementation screenshot is for counting semaphores only right?

​​​​​​I missed it.. :P

 

+1
:) hmm so same doubt you posted earlier right? now I guess it is clear that BW is not satisfied here.
+3

This is the implementation of Binary semaphore. (William Stallings has this same implementation)

Now, A performs Wait(P). P=0 now

A performs Wait(Q). Q=0 now.

B tries to perform Wait. So it goes in else part. It gets placed in the queue. B is blocked now.

A does it's work.

A performs Signal(P). Now, the queue is not empty. So, it goes in else part. The process (which has to be B) is placed on ready list from queue. B is ready now.

Now 2 cases.

     A executes. Performs Signal(Q) makes Q=1. Now even if A again tries to execute. It get's blocked as P=0. B is ready though.

     or say B executes. B tries Wait(Q) now but gets blocked and placed in queue. When A signals Q, B is placed in ready queue.

 

In any case B gets it's turn after A. Can u tell me the case when A gets it's turn again? I might be missing a trivial point still explain please it's not clear to me. @Utkarsh Joshi @MiNiPanda

0

okay! @ well written. Are you sure about s.value=1; part in signal()?? Because everytime process executes signal, it sets the value of the semaphore to 1. are you sure that in else part s.value=1; will not come?

0
Yes. I verified implementation before posting here.
0

Thanks @gauravkc, Putting this point here. 

0
so according to this implementation, progress is not satisfied.
0

this is what i was considering.

+1
Answer $B$ is correct if you consider the Blocking queue definition(Given in Galvin) of Semaphores.

But if consider the Busy Waiting definition (given in Galvin) for Semaphores then Answer will be $D$ as Bounded Waiting is Not Satisfied in that case.

Though, I always Prefer the Blocking Queue Definition if nothing is mentioned regarding which definition to use because Most Authors like William Stallings or Tanenbaum defined/reserve the word Semaphore that way Only. And They use the word $Spinlocks$ for Busy Waiting definition.

1 Answer

+3 votes
Best answer

Answer :

Option D (If we consider the Classical Busy Waiting Definition of Semaphores (Such Semaphores are called Spinlocks, Given in Galvin Book))

or

Option B (If we consider the Blocking Definition of Semaphores(Queue implementation as some Students call it)).

NOTE that Galvin provides both the definitions and calls both the definitions (Busy Waiting definition and Blocking Queue Definition) as Semaphores. Hence, the confusion arises which definition to use. But....

Many other authors(William Stallings or Tanenbaum) use the term semaphore only for blocking solutions(Queue implementation as some Students call it) and would call Busy waiting solutions spin locks.  


Semaphores can be of one of the Two types : Binary Semaphores or Counting Semaphores(General Semaphore). 

Furthermore, There are Two definitions of Semaphores, One is with busy waiting (Called Classical Definition) and One with Blocking solutions. Some authors use the term semaphore only for blocking solutions and would call Busy waiting solutions spin locks.

So, We have Four possible scenarios here regarding Semaphores. 

1. Binary semaphores with Busy Waiting

2. Binary semaphores with Blocking Solution

3. Counting semaphores with Busy Waiting

4. Counting semaphores with Blocking Solution

Since in the Question He has said that the Semaphore is Binary semaphore, so, let's analyze the given Question for Option $B$, using each of the two definitions of Binary Semaphore. 


                                                1. Considering Binary semaphores with Busy Waiting :

Definition of "Binary Semaphores with Busy Waiting" :

In classical definition of Binary Semaphore, Binary semaphore is just a simple Boolean Variable.

A binary semaphore $S$ takes on two possible values ``1(Open/Available)' and ``0(Closed/Unavailable)''

  • Two usual Atomic semaphore operations are supported $P,V$
  • $P(S)$ is
       P(S) {
             while (S==0) {}  // Loop as long as S is 0.
             S = 0 ;   // This is NOT the body of the while, It means Set S with value 0 if S was 1 earlier.
    }
  • V(S) is simply S<-- 1

i.e. $V(S)  \{$

          $S = 1;$

           $\}$ 

Analyzing the given Program using this Definition :

In this case i.e. When Considering Binary Semaphore with Busy Waiting, Bounded Waiting is Not satisfied.

Let me show you a possibility of Process $A$  getting into CS again and again without any Bound even after the Process $B$ has shown interest in entering into CS by executing the Entry code.

Run Process $A$ first, and since initially value of semaphore $P,Q$ is $1,$ so, By the above definition of $Wait$ operation, Process $A$ will get into CS and make the value of $P,Q$ as $0$. Now, preempt process $A$ and let process $B$ execute the $Wait(P) $ line of entry code. And Since the value of semaphore $P$ is $0$, so, process $B$ will be stuck in the Loop(While loop in the definition of Wait operation).  Now at this moment, preempt $B$ and run $A.$ Let it run the entire Remainder code and make $P,Q$ as $1$. Now, Let $A$ execute $Wait(P)$ and make $P$ as $0$ and Preempt. Now the same situation will continue for process $B$ and It will find Semaphore value as $0$ and continue looping the entry code. So, this scenario could repeat indefinitely and Process $A$ will get into CS many times without bound while process $B$ even after showing interest, will not get into CS for uncertain amount of time. 

So, When Binary Semaphores with Busy Waiting Considered, Answer will be Option $D.$


                                                  2. Considering Binary Semaphores with Blocking Solution.

 Definition of "Binary Semaphores with Blocking Solution" :

The main disadvantage of the semaphore definition with busy waiting given above is that it requires Busy Waiting. While a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the entry code. This continual looping is clearly a problem in a real multiprogramming system, where a single CPU is shared among many processes. Busy waiting wastes CPU cycles that some other process might be able to use productively. This type of semaphore is also called a Spinlock because the process "spins" while waiting for the lock. 

To overcome the need for busy waiting, we can modify the definition of the wait() and signal() semaphore operations. When a process executes the wait () operation and finds that the semaphore value is not positive, it must wait. However, rather than engaging in busy waiting, the process can block itself. The block operation places a process into a waiting queue associated with the semaphore, and the state of the process is switched to the waiting state. Then control is transferred to the CPU scheduler, which selects another process to execute.

A process that is blocked, waiting on a semaphore S, should be restarted when some other process executes a signal() operation. The process is restarted by a wakeup () operation, which changes the process from the waiting state to the ready state. The process is then placed in the ready queue. (The CPU may or may not be switched from the running process to the newly ready process, depending on the CPU-scheduling algorithm.) To implement semaphores under this definition, we define a semaphore as a "C' structure :

Each semaphore has a Boolean value and a list of processes list. When a process must wait on a semaphore, it is added to the list of processes. A signal() operation removes one process from the list of waiting processes and awakens that process.

The wait(), and Signal() semaphore operations can now be defined as following (Image source : William Stallings Book) :

The block() operation suspends the process that invokes it. The wakeup(P) operation resumes the execution of a blocked process P. These two operations are provided by the operating system as basic system calls.

Analyzing the given program using this definition :

In this case i.e. When Considering Binary Semaphore with Blocking Solution, Bounded waiting will satisfy.

The Idea/Hint is that If a process blocks itself on Semaphore $X$ then the other process will wake it up. And Hence, as soon as a process shows interest in accessing CS by executing its Entry code, It will get into CS within a bound of 1. So, Here, Bounded Waiting is Also Satisfied. So, If you analyze the given program using Blocking solution definition of Binary semaphore little bit more, you'll find that Starvation, Deadlock etc are Not possible and BW is Satisfied. 

Note that Bounded Waiting is Not related to Starvation/Deadlock in any way. 

So, When Binary Semaphores with Blocking Solution is Considered, Answer will be Option $B.$


                                                  

P.S. :

Note 1 : By default, Semaphore means Counting Semaphore.

Note 2 : The above codes are not real, i.e., it is not an implementation of P/V. It is, instead, a definition of the effect P/V is to have.

Note 3 : Answer could be any of B or D. Both are correct.

Note 4 : Though both options $B$ or $D$ are correct depending on which definition of Semaphore is considered, But in my opinion, better answer should be Option $B$ (i.e. Blocking Queue definition considered) Because most authors like William Stallings or Tanenbaum consider the Blocking queue definition only for Semaphores. The busy waiting definition is called Spinlock according to most authors (even Galvin also calls the Busy waiting definition of Semaphores as Spinlocks)

Note 5 : Some students analyze the program for Starvation or Bounded waiting by arguing that "A process could run continuously and thus other process will starve.." .. Well, this is Not a correct analysis. Refer the definitions of Bounded waiting or Starvation in Galvin and you'll find that the concept that such students are missing is "" A Process is $"willing"$ to enter the CS""


Refer my answer on the following GATE question (Same issue in this also .. Which definition to consider ) : 

https://gateoverflow.in/3788/gate2005-it-41 

Resources :

https://www2.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/5_Synchronization.html

https://cs.nyu.edu/courses/spring02/V22.0202-002/lecture-06.html

Operating System Concepts, written by Peter B. Galvin, Greg Gagne and Abraham Silberschatz.

Modern Operating Systems by AS Tanenbaum 

Operating Systems: Internals and Design Principles  Book by William Stallings (Best Resource for Semaphores in my opinion)

 

 

 

by Boss (27.6k points)
selected by
0

@Deepakk Poonia (Dee)\

Thank you for such detailed explanation!! :)

For Binary semaphore with Blocking Solution, can you check this comment https://gateoverflow.in/279020/me-test-series?show=279284#c279284

I think this explains how Bounded waiting is satisfied.

Also during exams, which one to consider? Okay I think you are hinting at using the blocking solution.. got it..

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
50,737 questions
57,388 answers
198,574 comments
105,411 users