search
Log In
13 votes
1.4k views

A given set of processes can be implemented by using only parbegin/parend statement, if the precedence graph of these processes is ______

in Operating System
edited by
1.4k views
0
precedence Graph should be a Null Graph.. because if there is even a single edge , we must use Begin/End..
1
is precedence graph in syllabus in 2017?
1
pls explain the concept of precedence graph @Arjun Sir @Bikram Sir
6

A precedence graph is a directed, acyclic graph whose nodes correspond to individual statements.

see the example here  http://uclab.khu.ac.kr/lectures/2003_autumn_os/lecture3.pdf

also read https://cis.temple.edu/~giorgio/old/cis307s96/readings/precedence.html

1 Answer

12 votes
 
Best answer

A given set of processes can be implemented by using only parbegin/parendstatement, if the precedence graph of these processes is properly nested 

Reference : http://nob.cs.ucdavis.edu/classes/ecs150-2008-04/handouts/sync.pdf

  1. It should be closed under par begin and par end.
  2. Process execute concurrently.


https://gateoverflow.in/1739/gate1998_24#viewbutton

In this question precedence graph is nested.

  1. All the process execute concurrently,  closed under par begin and par end.
     
  2. If you see all the serial  execution come then signal the resource and and parallel process down the value (resource ) similar all the process which are which are dependent to other one, other one release the resource then it will be got that with down and after release the its own resource. In the sense all the process are executing concurrently.

edited by
2
graph is nested means?
1
1. it should be closed under par begin and par end ...

2. process execute concurrently ....

https://gateoverflow.in/1739/gate1998_24#viewbutton

in this question precedence graph is nested ....

1) all the process execute concurrently ..closed under par begin and par end ..

2) if you see all the serial  execution come then signal the resource and and parallel process down the value (resource ) similar all the process which are which are dependent to other one , other one release the resource then it will be got that with down ..and after release the its own resource .. in the sense all the process are executing concurrently ...

may be my words are not clear to understand .... but moto is clear i think ...
1
yes :) its about that word "nested"
0

@Sonam :Please explain the second aspect 2) if you see all the serial  execution come then signal the resource and and parallel process down the value (resource ) similar all the process which are which are dependent to other one , other one release the resource then it will be got that with down ..and after release the its own resource .. in the sense all the process are executing concurrently ...

2
in simple words if some process hold resource then , and that want other ,so process which have resource ,will up and release that and other one down on it and got the resource
1
The meaning of nested is not clear from the answer and the link provided:(
1

I think "properly nested" graphs represent any one of the below:

  1. inner loops of begin-end which is enclosed in the outer loop of parbegin-parend
  2. inner loops of parbegin-parend which is enclosed in the outer loop of begin-end. (Example of this is the below diagram.)

And the question is asking for precedence graph of processes that can be implemented using only parbegin and parend. I think it is different from "properly nested" graphs. The graph expected in the question would be as the below diagram. (I don't know the exact name given for these type of precedence graphs)

 

Reference: https://www.ics.uci.edu/~bic/os/OS/PROOFS/bicc02v2.pdf

An important class of process flow graphs are those that are properly nested. Let S(p1,...,pn) denote the serial execution of processes p1 through pn and let P(p1,...,pn) denote the parallel execution of processes p1 through pn. Then a process flow graph is properly nested if it can be described by the functions S and P, and only function composition.

Related questions

22 votes
4 answers
1
2.7k views
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: If $F_1$, $F_2$ and $F_3$ are propositional formulae such that $F_1 \land F_2 \rightarrow F_3$ and $F_1 \land F_2 \rightarrow \sim F_3$ are both ... and $F_2$ are tautologies The conjunction $F_1 \land F_2$ is not satisfiable Neither is tautologous Neither is satisfiable None of the above.
asked Sep 12, 2014 in Mathematical Logic Kathleen 2.7k views
42 votes
3 answers
2
5.7k views
The maximum number of possible edges in an undirected graph with $n$ vertices and $k$ components is ______.
asked Sep 12, 2014 in Graph Theory Kathleen 5.7k views
12 votes
3 answers
3
2.2k views
If the longest chain in a partial order is of length $n$, then the partial order can be written as a _____ of $n$ antichains.
asked Sep 12, 2014 in Set Theory & Algebra Kathleen 2.2k views
20 votes
6 answers
4
2.7k views
Consider the following recursive definition of $fib$: fib(n) := if n = 0 then 1 else if n = 1 then 1 else fib(n-1) + fib(n-2) The number of times $fib$ is called (including the first call) for evaluation of $fib(7)$ is___________.
asked Sep 12, 2014 in Programming Kathleen 2.7k views
...