edited by
6,155 views
34 votes
34 votes
The concurrent programming constructs fork and join are as below:

Fork <label> which creates a new process executing from the specified label

Join <variable> which decrements the specified synchronization variable (by $1$) and terminates the process if the new value is not $0$.  

Show the precedence graph for $S1$, $S2$, $S3$, $S4$, and $S5$ of the concurrent program below.

$N=2$
$M=2$
Fork $L3$
Fork $L4$
$S1$
$L1$ : join $N$
$S3$
$L2$ : join $M$
$S5$
$L3:S2$
Goto $L1$
$L4:S4$
Goto $L2$
Next:
edited by

1 Answer

Best answer
42 votes
42 votes

$S1, S2, S3, S4$ and $S5$ are the statements to be executed.

Fork() creates a child to execute in parallel.

There will be $3$ processes running concurrently. 
One will execute S1, $2^{nd}$ will execute $S2$ and $3^{rd}$ will execute $S4$.

Initially there is one process which started execution. Suppose this process name is $P_0.$

It executes $N=2$, $M=2$ and after that it executes

Fork: $L3$,
At $L3$ these is a statement $S2$, Fork creates a new process suppose $P_1$ which starts its execution from level $L3$, means it starts executing $S2$.

$P_0$ executes fork $L4$, it creates another new process $P_2$ which starts its execution from level $L4$ means it starts executing $S4$.

When $P_1$ finishes executing $S2$, it executes next line which is goto $L1.$
When $P_2$ finishes executing $S4$, it executes next line which is goto $L2.$

$L1$ is executed by both processes $P_0($ which has executed S1$)$  and $P_1($ which has executed S2$)$
Hence, S1 and S2 are combined together, as either $P_0$ or $P_1$ will terminate $(\because N = 2)$ and only one process will continue its execution.

Similarly $L2$ is executed by two processes $P_2($ which executed S4) and one of $P_0$ or $P_1($ which executed S3$).$ So, $S4$ and S3 are joined together, as one of them will terminate $(\because M = 2)$ and then one which survives will execute the final statement $S5$.

www.csc.lsu.edu/~rkannan/Fork_Cobegin_Creationtime.docx 
http://www.cis.temple.edu/~giorgio/old/cis307s96/readings/precedence.html

edited by

Related questions

23 votes
23 votes
1 answer
2
Kathleen asked Oct 9, 2014
5,625 views
A critical section is a program segmentwhich should run in a certain amount of timewhich avoids deadlockswhere shared resources are accessedwhich must be enclosed by a pa...
38 votes
38 votes
2 answers
3
Kathleen asked Oct 9, 2014
9,819 views
A file system with a one-level directory structure is implemented on a disk with disk block size of $4K$ bytes. The disk is used as follows:$$\begin{array}{|l|}\hline \te...