The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 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?

asked in Operating System by Veteran (59.5k points)
edited by | 993 views

3 Answers

+11 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:


answered by Boss (40.2k points)
edited by
why S1 and S3 are dependent ? Both are read operations and so they are independent right ???
until S1 reads the value of n, S3 can't compare it with i.

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


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

@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.
For part b. Answer will be NO.

 @Rishabh Gupta 2

can you please why answer is NO


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

+6 votes

precedence graph

answered by Veteran (96.3k points)
S2 is not dependent on S1 but S3 is dependent on both S1 and S2 .
This precedence graph is wrong as per my knowledge?

Is precedence graph still in the syllabus?
Can someone please suggest a resource to study this topic? Also, is it in the syllabus for Gate 2018?
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

answered by Junior (731 points)
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 )
OR should make 2 paths in graph to reach s6. And S1 and S2 can be done in parallel here.

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) 

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

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

39,850 questions
46,817 answers
59,074 users