GATE IT 2005 | Question: 41

Question

Dark Mode

GATE IT 2005 | Question: 41

Ishrat Jahan asked in Operating System Nov 3, 2014 edited Apr 15, 2019 by Pooja Khatri

23,892 views

Given below is a program which when executed spawns two concurrent processes :
semaphore $X : = 0 ;$
/* Process now forks into concurrent processes $P1$ & $P2$ */

$\begin{array}{|l|l|}\hline \text{$P1$} & \text{$P2$} \\\hline \text{repeat forever } & \text{repeat forever} \\ \text{$V (X) ;$ } & \text{$ P(X) ;$} \\ \text{Compute; } & \text{Compute;}\\ \text{$P(X) ;$ } & \text{$V(X) ;$} \\\hline \end{array}$

Consider the following statements about processes $P1$ and $P2:$

It is possible for process $P1$ to starve.
It is possible for process $P2$ to starve.

Which of the following holds?

Both (I) and (II) are true.
(I) is true but (II) is false.
(II) is true but (I) is false
Both (I) and (II) are false

Ishrat Jahan asked in Operating System Nov 3, 2014 edited Apr 15, 2019 by Pooja Khatri

by Ishrat Jahan

23.9k views

23 Comments

by Bikram

commented Jul 12, 2017

Down operation means P ( wait) , it means if the value of semaphore variable is not negative, decrement the value by 1. If the semaphore variable is now negative, the process executing wait is blocked (i.e., added to the semaphore's queue) until the value is greater or equal to 1.

And Up operation (Signal ) V means : First increments the value of semaphore variable by 1. After the increment, if the pre-increment value was negative (meaning there are processes waiting for a resource), it transfers a blocked process from the semaphore's waiting queue to the ready queue.

Here P1 is performing up and P2 performing down operation.

if we start from P1, initially x ==0 , so after V(x) it's new value would be x==1

and for P2 , x==0 so it need to wait until x become 1.

by Divyanshum29

commented Oct 9, 2018

P1	P2
repeat forever 1.V(X); Compute ; 2.P(X);	repeat forever 3.P(X); Compute ; 4.V(X);

It is possible for process P1 to starve.

yes this can be happen here x=0; In P1:1,compute,2 (here after V (x) operation x=1 so P(x) will also be execute again line no 1 is up operaton it will execute..... like this it can go infinitly so P2 have to starve. )

2.It is possible for process P2 to starve

if we start our execution from P2 then X=0, so P(x) will not be performed because it is down operation and mutex value is 0 , now it will go to process P1 then V(x) operation will performed so X=1 Now Assume after v(x) p1 preempted then it will go to P2 here x=0 so down condition of p2 will performed again v(x) of p2 like...

P2:line 1(blocked)|P1:line1(preempted)|P2 line1,(compute), line 2(Vx) so after it it value of X=1 so again P2 will executed again compute and v(X)....... INFINITLY. THATS WHY A is the correct option

11 Answers

4 Comments

Show 46 previous comments

Page:

1
2
3
next »

Pooja Palod · Answer 1 · 2015-08-13T02:24:08+0000

A is the answer.

Case 1:Here P1 is performing signal operation so it is first one to start...Now it may happen that after executing CS it makes X=0 again tries to enter CS my making X=1 so it is possible that P2 can starve(just a possibility)

Case 2:If P1 executes signal operation and its execution is suspended temporarily, P2 executes wait and enter CS and then execute signal operation making X=1 now P2 can enter critical section by executing wait operation..this may happen for infinite amount of time..so in this P1 may starve

Deepak Poonia · Answer 2 · 2018-12-15T21:27:55+0000

Answer :

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

or

Option D (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.

Let's see everything in detail.

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

Let's analyze the given Question using each of the above definitions.

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, It is possible for both processes to Starve.

It is possible for $P2$ to starve :

Let me show you a possibility of $P2$ getting starved for CS.

Run $P2$ first, and since initially value of semaphore $X$ is $0,$ so, By the above definition of $P$ operation, Process $P2$ will be stuck in the loop. Now, When $P1's$ turn will come, It will execute $V(X)$ and the $X$ will become $1.$ Now, $P1$ will enter into CS. And Let it execute $P(X)$ and now $X$ will become 0. Now at this moment, preempt $P1$ and run $P2.$ Since value of semaphore $X$ is still 0, It will continue looping in the while loop. And turn will go to $P1$ again, which will then execute $V(X)$ and make $X= 1.$ Now the same scenario may repeat as above. i.e. Preempt $P1$ after executing $P(X)$ and run $P2.$ and so on.. So, $P2$ will starve for Critical Section(CS) this way.

It is possible for $P1$ to starve :

We can make a similar situation for $P1$ as well.

Let me show you a possibility of $P1$ getting starved for CS.

Run $P1$ first, and since initially value of semaphore $X$ is $0,$ so, By the above definition of $V$ operation, $X$ will become 1. Now, $P1$ will enter into CS. And Now preempt it and run $P2.$ Let it execute $P(X)$ and now $X$ will become 0. Now $P2$ will enter into CS. Now preempt $P2$ and let $P1$ run. Since the value of semaphore $X$ is $0,$ so, By the above definition of $P$ operation, Process $P1$ will be stuck in the loop. Now, When $P2's$ turn will come, It will execute $V(X)$ and the $X$ will become $1.$ Now, let $P2$ execute $P(X)$ and now $X$ will become 0. And $P2$ will enter into CS. Now at this moment, preempt $P2$ and run $P1.$ Since value of semaphore $X$ is still 0, It will continue looping in the while loop. And turn will go to $P2$ again, which will then execute $V(X)$ and make $X= 1.$ Now the same scenario may repeat as above. i.e. Preempt $P2$ after executing $P(X)$ and run $P1.$ and so on.. So, $P1$ will starve for Critical Section(CS) this way.

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

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, It is NOT possible for any process to Starve.

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 $D.$

3 . Considering Counting Semaphore with Busy Waiting :

Definition of "Counting Semaphores with Busy Waiting" :

In this scenario, A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait () and signal ().

The definition of wait () is as follows:

$P(S)$ is

   P(S) {
         while (S<=0) {}  // Loop as long as S is 0.
         S-- ;   // This is NOT the body of the while, It means decrment S if S was > 0 earlier.
}

V(S) is simply S++

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

$S++;$

$\}$

Analyzing the given Program using this Definition :

In this case i.e. When Considering Counting Semaphore with Busy Waiting, It is possible for both processes to Starve.

It is possible for $P2$ to starve :

Let me show you a possibility of $P2$ getting starved for CS.

Run $P2$ first, and since initially value of semaphore $X$ is $0,$ so, By the above definition of $P$ operation, Process $P2$ will be stuck in the loop. Now, When $P1's$ turn will come, It will execute $V(X)$ and the $X$ will become $1.$ Now, $P1$ will enter into CS. And Let it execute $P(X)$ and now $X$ will become 0. Now at this moment, preempt $P1$ and run $P2.$ Since value of semaphore $X$ is still 0, It will continue looping in the while loop. And turn will go to $P1$ again, which will then execute $V(X)$ and make $X= 1.$ Now the same scenario may repeat as above. i.e. Preempt $P1$ after executing $P(X)$ and run $P2.$ and so on.. So, $P2$ will starve for Critical Section(CS) this way.

It is possible for $P1$ to starve :

We can make a similar situation for $P1$ as well.

Let me show you a possibility of $P1$ getting starved for CS.

Run $P1$ first, and since initially value of semaphore $X$ is $0,$ so, By the above definition of $V$ operation, $X$ will become 1. Now, $P1$ will enter into CS. And Now preempt it and run $P2.$ Let it execute $P(X)$ and now $X$ will become 0. Now $P2$ will enter into CS. Now preempt $P2$ and let $P1$ run. Since the value of semaphore $X$ is $0,$ so, By the above definition of $P$ operation, Process $P1$ will be stuck in the loop. Now, When $P2's$ turn will come, It will execute $V(X)$ and the $X$ will become $1.$ Now, let $P2$ execute $P(X)$ and now $X$ will become 0. And $P2$ will enter into CS. Now at this moment, preempt $P2$ and run $P1.$ Since value of semaphore $X$ is still 0, It will continue looping in the while loop. And turn will go to $P2$ again, which will then execute $V(X)$ and make $X= 1.$ Now the same scenario may repeat as above. i.e. Preempt $P2$ after executing $P(X)$ and run $P1.$ and so on.. So, $P1$ will starve for Critical Section(CS) this way.

So, When Counting Semaphores with Busy Waiting Considered, Answer will be Option $A.$

4. Considering Counting Semaphore with Blocking Solutions :

Definition of "Counting Semaphores with Blocking Solution" :

Analyzing the given program using this definition :

In this case i.e. When Considering Counting Semaphore with Blocking Solution, It is NOT possible for any process to Starve.

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 Counting 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 Counting Semaphores with Blocking Solution is Considered, Answer will be Option $D.$

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 A, D. Both are correct. I do not know which was the official answer of GATE that year Or was it $A\,\,or\,\,D.$

Note 4 : Though both options $A$ or $D$ are correct depending on which definition of Semaphore is considered, But in my opinion, better answer should be Option $D$ (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""

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)

srestha · Answer 3 · 2016-06-13T00:30:41+0000

Ans A)

P₁ starts , and go infinitely . So P₂ starves here.

P₂ cannot start process any time.right?

Now, P₁ starts and makes semaphore value X=1 and executes CS once. Now, P₂ takes this semaphore and executes infinitely. So, P₁ starves here

Now, P₁ starts and makes semaphore value X=1 and executes CS once. Now, P₂ takes that semaphore and it also executes it's critical section then P₁again takes this semaphore and looks which one executes next V(s) of P₁ or P(s) of P₁ or P(x) for P₂ .

So, more than one process can be in CS here

So, Mutual Exclusion violated , But Progress and Bounded Waiting satisfied here

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

GATE IT 2005 | Question: 41

23 Comments

will you please explain your line

Please log in or register to add a comment.

Please log in or register to answer this question.

11 Answers

4 Comments

Please log in or register to add a comment.

4 Comments

Please log in or register to add a comment.

Modern Operating Systems by AS Tanenbaum

4 Comments

Please log in or register to add a comment.

4 Comments

Please log in or register to add a comment.

Related questions

Subscribe to GATE CSE 2024 Test Series

Subscribe to GO Classes for GATE CSE 2024

Subjects

GATE IT 2005 | Question: 41

23 Comments

will you please explain your line

Please log in or register to add a comment.

Please log in or register to answer this question.

11 Answers

4 Comments

Please log in or register to add a comment.

4 Comments

Please log in or register to add a comment.

Modern Operating Systems by AS Tanenbaum

4 Comments

Please log in or register to add a comment.

4 Comments

Please log in or register to add a comment.

Related questions

Subscribe to GATE CSE 2024 Test Series

Subscribe to GO Classes for GATE CSE 2024

Recent Posts

Subjects

Recent Blog Comments