The Gateway to Computer Science Excellence

+58 votes

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?

+5

Somebody please contrast the difference between option (C) and (D). Both seem to be possible answers to me.

0

@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

+3

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.

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.

+2

@ 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.

+17

@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?

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.

0

@ akb1115

But we are calculating a[0] and a[1] before b[0] as explained in ur comment itself. Isn't it wrong?

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

@Arjun Sir

I cannot understand how C is correct.

Please look at this sequence

Process Y -> V(S), P(R) blocked

Process X -> Computes a[i] , P(S), V(R) , again computes a[i] for the second time. Y did not yet read one time. So Y cannot complete its full iteration.

I cannot understand how C is correct.

Please look at this sequence

Process Y -> V(S), P(R) blocked

Process X -> Computes a[i] , P(S), V(R) , again computes a[i] for the second time. Y did not yet read one time. So Y cannot complete its full iteration.

0

please close this question because it is duplicate

see this link https://gateoverflow.in/1550/gate2013-39

+93 votes

Best answer

- $X$ is waiting on $R$ and $Y$ is waiting on $X$. So, both cannot proceed.

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

- 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**.

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

0

@Arjun Sir, For option D if I put the events in below order then X produces 2 values and Y none

1. X:V(R)

2. Y:V(S)

3.Y:P(R) , before it completes the wait operation, it fall asleep or context switch.

4. X:P(S), iteration is completed before Y consume the the current value of X.

5. Again X iterates and produce one more value.

So X now has 2 values.

In that case option D also should be valid if you justify the option C by saying on Sachin's comment

"That means 2 iterations are performed by process X - that's not a problem. Process X must be ahead of process Y as it is calculating f(i) and Y is calculating g(f(i)) "

1. X:V(R)

2. Y:V(S)

3.Y:P(R) , before it completes the wait operation, it fall asleep or context switch.

4. X:P(S), iteration is completed before Y consume the the current value of X.

5. Again X iterates and produce one more value.

So X now has 2 values.

In that case option D also should be valid if you justify the option C by saying on Sachin's comment

"That means 2 iterations are performed by process X - that's not a problem. Process X must be ahead of process Y as it is calculating f(i) and Y is calculating g(f(i)) "

0

+5

Option C is indeed correct.

I would like to add why the two semaphores are being used.

**S** semaphore is used to ensure process Y arrives in entry section before X exits.

**R** semaphore is used to ensure b[i]=g(a[i]) executes after a[i]=f(i).

0

**I have doubts related to the option C and D : **

**C : What if the processes are executed in the following order?**

**ExitX()**

**P(S) //After this, the process is preempted**

**EntryY()**

**V(S) //Again preempted**

**ExitX()**

**P(R) **

**and after this, x is again executed. In this fashion, X can execute multiple times. isn't it so?**

**D : Actually both the options, that is C and D seems to serve same purpose to me.**

+11

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

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.

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.

+7

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

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

@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?

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?

+6

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

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.

+2

http://csgatelounge.blogspot.com/2013/11/question-on-semaphores_25.html Check this link.

Hope this will help.

+1

anyone please help me. I'm stuck between option C & D

according to me option D is correct.

but option C is correct,

I'm having doubt that, the reason for option D is wrong, same reason is occurring in option C.

In Option D -

ExitX(R, S) { V(R); P(S); } EntryY(R, S) { V(S); P(R); }

people are saying that option D is wrong because after V(S) & before P(R) in y, process x can come again through 2nd iteration, that's why the corresponding value of process y from x is missing.

I mean there could be possibility that, b[0] != g(a[0]) but b[0] = g(a[1]).

I think same thing can happen with option C also -

ExitX(R, S) { P(S); V(R); } EntryY(R, S) { V(S); P(R); }

In process x, P(S) is blocked , so switched to V(S) of process y, now P(R) is blocked in process y, so switched to process x. Now in process x it may so happen that it will easily execute V(R) & then come again through loop with it's 2nd iteration. a[0] = g(a[1]), but here should be a[0] = g(a[0]).

Moreover in option C , Deadlock is possible.

after coming 2nd iteration, process x will stuck at P(S) & as process Y has already executed V(S) so it will execute from P(R), which is clearly a Deadlock.

Don't know where I'm lagging.

+7 votes

Approach that must be followed while solving this kind of problem :

1. Identify producer and consumer and which semaphore is acting as wake up signal for consumer.

2. Here there must be strict alteration as elements of B is dependent on A and semaphores are binary. If there would have been counting semaphore then no need of strict alteration as count will be maintained by counting semaphore.

3. Producing element in a[] **up(sem 1(signal for consumer))** then block it till b does not calculate f(a[i]) so **down(sem 2 )** here producer will be blocked. Now b will consume signal generated by a(sem 1) and calculate element of b(fa[i]) hence **down (sem 1)** now as a[i] and b[i] is done to calculate next element of a **up (sem 2)** so that producer can get unblocked and produce next element.

c matches this process.

0

"If there would have been counting semaphore then no need of strict alteration as count will be maintained by counting semaphore."

Can you explain this statement a bit more..

Can you explain this statement a bit more..

0

If there would have been counting Semaphore then all the wait signals will keep getting saved and process can use it later (in counting semaphore we maintain integer means collection of bits to represent integer) whereas in binary semaphore or mutex only two bits are there 0 and 1 means only two values it can take ....so if binary semaphore's value is 1 and if signal is performed then it's value will be 1 only (it will not get incremented whereas in counting semaphore it will get incremented and hance signal will se saved)

+4 votes

Let us think of it in this way. To calculate value of $b[0]$, we need to already have value of $a[0]$ with us because $b[0] = g(a[0])$, Else some error will be thrown.

So there can only be 2 cases:

- $Process X$ is selected first, this is good. It will calculate the value of $a[0]$ and then after this if $process Y$ executes, it will already have the corresponding value of $a[0]$ to calculate value of $b[0]$. If this case happens always, we do not need any semaphores.
- $Process Y$ is selected first. This is bad because now $Process Y$ will try to calculate value of $b[0]$ but value of $a[0]$ is not calculated yet. Now look at option $C$. Before calculating the value of $b[0]$, $Process Y$ needs to pass $EntryY$ first. Inititally $S=0, R=0$. To pass $EntryY$, it will first execute $V(S)$, simple up operation on $S$, now $S=1,R=0$. Now it tries to execute next line, $P(R)$. It will be blocked because $R=0$ and will have to wait for $R$ to be $1$, i.e. until up operation is performed on $R$. Now while it is waiting, $Process X$ executes and it finds value of $a[0]$. (now we can find value of $b[0]$ because $b[0] = g(a[0])$). Now it will go inside the $exitX$ and executes $P(S)$ so now $S=0,R=0$. It goes to the next line which is V(R). This is what we have been waiting for and now $S=0,R=1$. Now $process Y$ resumes and calculates $b[0]$. This can be generalized to $i, 0 < i < n$.

And hence we can safely calculate the arrays $a$ and $b$.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,257 answers

198,084 comments

104,732 users