A given set of processes can be implemented by using only parbegin/parend statements, if the precedence graph of these processes is ______ A. a tree B. a directed acyclic graph C. a series-parallel graph D. a complete bipartite graph

GATE 1991 · Operating System · Precedence Graph · medium

Answer: C. a series-parallel graph — parbegin/parend can implement exactly those processes whose precedence graph is series-parallel.

1. Recall the expressiveness of parbegin/parend: parbegin/parend supports two operations: (a) Sequential composition: S1; S2 (series) (b) Parallel composition: parbegin S1; S2; ... Sn parend (parallel) These two operations, applied recursively (nested parbegin/parend), generate exactly the class of series-parallel directed acyclic graphs.
2. Why other options are wrong: A. Trees: Trees are a subset of series-parallel graphs, so this is too restrictive. Not all series-parallel graphs are trees. B. Directed Acyclic Graphs (DAGs): All precedence graphs are DAGs, but not all DAGs are series-parallel. For example, the N-structure (also called the W-pattern) is a DAG but not series-parallel and cannot be expressed with just parbegin/parend. D. Complete bipartite graphs: These represent a very specific structure with no sequential ordering, not a meaningful characterisation of expressible precedence graphs.
3. Confirm the answer: The theoretical result is: A concurrent program can be written using only parbegin/parend if and only if its precedence graph is a series-parallel graph. Therefore the answer is C. a series-parallel graph.