in Operating System recategorized by
5,927 views
18 votes
18 votes
  1. Draw a precedence graph for the following sequential code. The statements are numbered from $S_1$ to $S_6$
    $S_1$ read n
    $S_2$ i := 1
    $S_3$ if i > n next
    $S_4$ a(i) := i+1
    $S_5$ i := i+1
    $S_6$ next : write a(i)
  2. Can this graph be converted to a concurrent program using parbegin-parend construct only?

in Operating System recategorized by
5.9k views

2 Comments

Are parbegin-parend constructs there in the present syllabus ?
3
3

Does this section of intermediate code leads to the storage of garbage value in a[i+1], as i is incremented before write in a[i]?

Thus, is a[i]=i+1 lost?

 

0
0

3 Answers

21 votes
21 votes
Best answer

Following must be the correct precedence graph, $S_1$ abd $S_2$ are independent, hence these can be executed in parallel.

For all those nodes which are independent we can execute them in parallel by creating a separate process for each node like $S_1$ and $S_2$. There is an edge from $S_3$ to $S_6$ it means, until the process which executes $S_3$ finishes its work, we can't start the process which will execute $S_6$.

For more understanding watch the following NPTEL lectures on process management:

 

edited by

4 Comments

edited by

@ sir, i think the answer for B will be YES.

I think graph can be converted to a concurrent program as follows.

par-begin
    s1
    s2
par-end

begin
    s3
    s4
    s5
    s6
end

Sir for concurrency it is not necessary that each and every operation must be concurrent, but all the dependencies must be preserved and no new dependency must appear,

Our question is an easy version of

graph code

source: http://uclab.khu.ac.kr/lectures/2006_1_os/lecture3-concurrent-process.pdf

Ignore the GATE question’s s1 and s2. (which won’t change the dependencies of the subsequent subtree)

And ignore s5 and s3 from the diagram i have posted above.

Now compare both of them, they are equivalent.

1
1

I think here the edge must be from S4->S6 because in S6 we are writing the value of a[i]  and a[i] is calculated in S4 so S6 should happen after S4 right? how can we do it in parallel to S4??

0
0
I think Edge from S5 to S6 will not be there.

becuase “next” is a label , means S6 is somewhere else , if S3 sondition meet then only we can reach there.
0
0
6 votes
6 votes

precedence graph

4 Comments

S2 is not dependent on S1 but S3 is dependent on both S1 and S2 .
0
0
This precedence graph is wrong as per my knowledge?

Is precedence graph still in the syllabus?
1
1
Can someone please suggest a resource to study this topic? Also, is it in the syllabus for Gate 2018?
0
0
Why S1 and S2 are not dependent and why should they run in parallel. Can any one explain.
0
0
0 votes
0 votes

The precedence graph is as follows

 precedence graph

i feel parbegin .parend can be used between s1 and s2 and then be serialized but some solutions are showing they cant be used.

someone please rectify me if  i am wrong  and please  make me understand my mistake

by

4 Comments

s6 depends on any one ie s3 or s5 so even if one is executed

How to simulate this OR condiition via graph

(your image link seems to be broken picture isn't loading )
0
0
OR should make 2 paths in graph to reach s6. And S1 and S2 can be done in parallel here.
0
0

now as per the graph i have drawn Doesn't it shows that S6 can only be executed after S5 and S3 both have executed

Because in dependency graph it means s6 depends on s3 and s5 so it cannot execute unless other 2 have finished

But as per ques if s3 has executed s6 can execute ( s5 need not execute ,it won't actually) 

5
5
I Think, This precedence graph is correct ....
0
0

Related questions