1.3k views
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?

edited | 1.3k views
0
Are parbegin-parend constructs there in the present syllabus ?

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
0
why S1 and S3 are dependent ? Both are read operations and so they are independent right ???
+1
until S1 reads the value of n, S3 can't compare it with i.
0

@Manu Thakur bro it will be more helpful if you can also explain why you have drawn each and every edge .. feeling a bit confused... actually s6 is transitively dependent on S3 .. Then why one more edge from S3 to S6 ...

0

@vicky i can understand your concern, but to understand this question someone has to know about concurrent execution of processes, and for doing that one hast to understand co-begin co-end or fork() - join concepts.

For all those nodes which are independent we can execute them in parallel by creating a separate process for each node like S1 and S2. there is an edge from S3 to S6 it means, until the process which executes S3 finishes its work, we can't start the process which which will execute S6.

you can watch NPTEL lectures on process management from here:

0
@Manu What will be answer for part b?I think it is NO.Becasue s6 will have dependency from both s3 and s5.Also in the beginning we need to wait at S3 after S1 and s2.
+1
For part b. Answer will be NO.
0

+1

rahul sharma 5

Can you please provide any reference from where I can study this? I have gone through multiple links and none of them has totally cleared my concept.

This was what I found from one of them. If you can explain this it would be really helpful

+2

@MiNiPanda

remaining is easy... comment if you still didn't get it !

+1
0
@Shaik Thank you so much..

So since S3,S4,S5 are to be executed serially so we can't just use parbegin and parend for it..am i right?
0

So since S3,S4,S5 are to be executed serially so we can't just use parbegin and parend for it

in this question ( not from your image ) , yes

0

precedence graph

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

Is precedence graph still in the syllabus?
0
Can someone please suggest a resource to study this topic? Also, is it in the syllabus for Gate 2018?

The precedence graph is as follows

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

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

How to simulate this OR condiition via graph

0
OR should make 2 paths in graph to reach s6. And S1 and S2 can be done in parallel here.
+5

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)

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

1
2