The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+37 votes
5.4k views

A certain computation generates two arrays a and b such that $a[i] = f(i)$ for $0 \leq i < n$ and $b[i] = g(a[i])$ for $0 \leq i < n$. Suppose this computation is decomposed into two concurrent processes $X$ and $Y$ such that $X$ computes the array $a$ and $Y$ computes the array $b$. The processes employ two binary semaphores $R$ and $S$, both initialized to zero. The array $a$ is shared by the two processes. The structures of the processes are shown below.

Process X:

private i; 
for (i=0; i< n; i++) { 

 a[i] = f(i); 

 ExitX(R, S); 

} 

Process Y:

private i;
for (i=0; i< n; i++) { 

 EntryY(R, S); 

 b[i] = g(a[i]); 

 }

Which one of the following represents the CORRECT implementations of ExitX and EntryY?

  1. ExitX(R, S) { 
    P(R); 
    V(S); 
    }
    EntryY(R, S) { 
    P(S); 
    V(R); 
    }
    
  2. ExitX(R, S) { 
    V(R); 
    V(S); 
    }
    EntryY(R, S) { 
    P(R); 
    P(S); 
    }
    
  3. ExitX(R, S) { 
    P(S); 
    V(R); 
    }
    EntryY(R, S) { 
    V(S); 
    P(R); 
    }
    
  4. ExitX(R, S) { 
    V(R); 
    P(S); 
    }
    EntryY(R, S) { 
    V(S); 
    P(R); 
    }
    
asked in Operating System by Veteran (355k points)
edited by | 5.4k views
+5
Somebody please contrast the difference between option (C) and (D). Both seem to be possible answers to me.
+1
give solution if anybody knows...
–1

@Arjun Sir

How C can be the correct answer to this because we can have a sequence possible for option C also just like option D where we can execute Process X two times Before execution of Process Y so some iterations of Y will not be completed. Here Process X and Y are (after inserting ExitX and EntryY from option C):-

Process X                                   Process Y
{                                           {
 1) private i;                               1) private i;
 2) for (i=0; i< n; i++)                     2) for (i=0; i< n; i++)  
    {                                           {                                                 
 3) a[i] = f(i);                             3) V(S);
 4) P(S);                                    4) P(R);
 5) V(R);                                    5) b[i] = g(a[i]);   
}}                                           }} 

The sequence is:-

Process X:

Line 1  

Line 2

Line 3    // it computes a[0]

--------------------------------Got Preempted -------------------------

Process Y:

Line 1

Line 2

Line 3  // It makes S=1 because no one was yet waiting on S

-----------------Got Preempted----------------------

Process X

Line 4 // As S=1 so P(S) will be successful and makes S=0 

Line 5// It makes R=1 because no one was yet waiting on R

Line 2 // here i=1 

Line 3// it computes  a[1]

--------------got preempted--------------------

Process Y

Line 4 // as R=1 so P(R) will be successful

Line 5// computes b[0]

Clearly here we can see that we can have two iterations of process X before any iteration of Y in between

+1
Option C is correct only...

in option C

Process X does Wait(S) followed by Signal(R)

in option D

Process X does Signal(R) then it is followed by Wait(S)

as the signals are getting lost their corresponding iterations will be missed out in Process Y .

If we change the order of Signal(S) and Wait(R) in Entry Y , then D option also correct.
+1

akb1115 

Read the question again and read the best answer again, it is correct and C is the right answer.

your counter example is complete wrong, there is NO preemption possible.

Both  Process X and  Process Y will be executed without any intervention by other processs.

+4

@Bikram Sir

Now I got what you were trying to explain thank you, Sir, for clearing my doubt.

My Mistake:-

I am wrong because I am trying to preempt the processes at any time when I want which is not the case in the real time.

Why Option C is Correct:-

--Firstly process X runs and finds a[0] then it executes P(S) and will be blocked.

--Then Process Y runs and executes V(S) which makes process X to go to ready state from blocked state.

--Then Process Y executes P(R) and got blocked.

--Then Process X which the was in the ready state starts running and executes V(R) which makes process Y to go to ready state from blocked state.

--Then Process X finds a[1].and again executes P(S)  and get blocked.

--Then Process Y which was in ready state enters to running state and computes b[0].

and so on

Hence here no iteration of Process Y will be missed out and the placement of ExitX and EntryY is in such a way that both the process will able to complete their iterations and not two iterations of Process X can compete for consecutively without having one complete iteration of process Y in between these  two iterations of process X

+1
@Arjun [email protected] Sir Can u plz tell me
what that line means  in ans of C) option
"So, this ensures that no two iterations of either X or Y can proceed without an iteration of the other being executed in between."
V(S) cannot executes without V(R) once
or we can say S cannot execute fully without R once,rt?
+1

@srestha

So, this ensures that no two iterations of either X or Y can proceed without an iteration of the other being executed in between."

This means both X and Y are proceed without any preemption by other. It want to say Both X and Y are atomic.

+1
please elaborate more. Unable to understand difference between C and D?
+1
@Bikram Sir, Why Preemption is not possible in the middle?
0
@ akb1115
But we are calculating a[0] and a[1] before b[0] as explained in ur comment itself. Isn't it wrong?
0

Had  it been given "Counting Semaphores" instead of Binary Semaphores then option B) & D) would have been correct?

0

Hi @sushmita ji,

Option (D) is also providing Mutual Exclusion. But process Y may not access entire array(means Y will not be able to compute b) because in some special cases signal loss may occur(Because S and R are Binary semaphore ) same is mentioned in the selected answer and various comments. 

0
explain further

1 Answer

+62 votes
Best answer
  1. $X$ is waiting on $R$ and $Y$ is waiting on $X$. So, both cannot proceed.
     
  2. Process $X$ is doing Signal operation on $R$ and $S$ without any wait and hence multiple signal operations can happen on the binary semaphore so Process $Y$ won't be able to get exactly $n$ successful wait operations. i.e., Process $Y$ may not be able to complete all the iterations.
     
  3. Process $X$ does Wait(S) followed by Signal(R) while Process $Y$ does Signal(S) followed by Wait(R). So, this ensures that no two iterations of either $X$ or $Y$ can proceed without an iteration of the other being executed in between. i.e., this ensures that all $n$ iterations of $X$ and $Y$ succeeds and hence the answer.
     
  4. Process $X$ does Signal(R) followed by Wait(S) while Process $Y$ does Signal(S) followed by Wait(R). There is a problem here that $X$ can do two Signal(R) operation without a Wait(R) being done in between by $Y$. This happens in the following scenario:
    Process $Y$: Does Signal (S); Wait(R) fails; goes to sleep.
    Process $X$: Does Signal(R); Wait(S) succeeds; In next iteration Signal(R) again happens;

So, this can result in some Signal operations getting lost as the semaphore is a binary one and thus Process $Y$ may not be able to complete all the iterations. If we change the order of Signal(S) and Wait(R) in EntryY, then (D) option also can work. 

answered by Veteran (355k points)
edited by
+5
For those who are confusing in C and D,please see if my comment helps

In Y process we are doing P(R), but not V(R). So basically someone has to do V(R) for Y.Now Y does P(R) on every iteration so someone has to do V(R) for every iteration of Y,Now who can signal V(R) ?Only X.

Now if any V(R) from X is lost then at least one iteration of Y can be blocked.

Lets us see why d is wrong:-Assume we want to compute for i=1,2

X does V(R),now R is set to 1.

 Y does V(S) now S=1.

X does P(S) ,now S=0.

Now X has done one iteration and it starts the second iteration.

X does V(R), set R=1.

X does P(S), and goes to block queue of S.

Now here X is in 2nd iteration and Y is in first iteration.

Now x has computed a[1] and [2]

Now Y does V(S),unblocks X.

X will exit now,it has computed a[1] and a[2]

Now Y does P(R) ,and set R=0 and compute b[1].

Now Y does second iteration and does V(s),and proceeds

Now does P(R) and goes to block state.

Now,there is no one to wake process Y

So thats why it is wrong.

Shortcut is to see that Y needs someone to do V(R) for its each iteration.X is doin but if some signal is lost,y will be blocked
0
@ Sushant Gokhale how is it deadlock?

EntryY is now looping in P(R) but ExitX which is currently at V(R) according to your sequence can proceed. When it does, then EntryY can also stop looping and move forward.
0
Can i falsify D based upon following approach?

S=0 , R=0

X executes V(R) and set R=1. Now s=0 and R=1 and X preempted.

Y comes it does V(S) and set S=1.Now S=1,R=1 .Now Y does P(R) as R=1 so success.

So Y is about to start b[0] here as a[0] is not available.Whihc is wrong.Hence D cannot be the answer
0
yes @rahul  it's correct.
0
Then this seems to be easy way to eliminate option d as compared to the one mentioned in answer:)
0
Sir excellent approach
0
@rahul

Your approach of negating option D is exactly how I thought. But as Arjun sir in his ans said " If we change the order of Signal(S) and Wait(R) in EntryY, then D option also can work." In our case even this alternative won't work right?
0

@ rahul sharma 5

Can i falsify D based upon following approach?

S=0 , R=0

X executes V(R) and set R=1. Now s=0 and R=1 and X preempted.

Y comes it does V(S) and set S=1.Now S=1,R=1 .Now Y does P(R) as R=1 so success.

So Y is about to start b[0] here as a[0] is not available.Whihc is wrong.Hence D cannot be the answer

This approach is wrong ! Why ?

Because , when X executes V(R) and set R=1.  then a[0] is already computed because ExitX() is code performed on exit i.e. after i=0 iteration of 'for loop' is completed.

0
semaphore operation is atomic.can not preempted in between.
0

rahul sharma 5

I think you did some mistake in your example

in below line of your example you already executed V(S) in first iteration of Y.

 Y does V(S) now S=1.

 

 and again you are executing V(S) again in this line

Now Y does V(S),unblocks X.
Answer:

Related questions



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

37,939 questions
45,453 answers
131,192 comments
48,208 users