wu@wahoo.tds.kth.se (Wu Handong) (04/06/89)
Is a data flow graph deadlock-free? Let us look at an example. Suppose a node N1 has two input arcs which originate from node a N2 and a node N3 respectively, all the three nodes are allocated in different processor elements. The node N1 cannot be executed until receiving tokens from both N2 and N3. If no token sent from either N2 or N3, N1 is in waiting state. Is the waiting state the same as the dealock state of a logic process in the context of distributed simulation? In distributed simulation a logic process graph is used to represent a simulated system, a node of the graph is a logic process which communicates with other logic processes via its input and output channels. One important issue of distributed simulation deals with maintaining the correct order of time stamped messages. The conservative method owned to Chandy-Misra allows a logic process proceed only after all its input channels having messages. They claim that the logic process is deadlock if no message arrives on one of its input channels. Since we have not considered any deadlock problem of data flow graph so far, people may believe that a data flow graph is deadlock free. What is your opinion? -------- ------------ Handong Wu E-mail: wu@tds.kth.se Dept. of Telecom. & Computer Systems Royal Institute of Technolgy 100 44 Stockholm Sweden
segall@caip.rutgers.edu (Ed Segall) (04/10/89)
> Is a data flow graph deadlock-free? > Let us look at an example. Suppose a node N1 has two input arcs which > originate from node a N2 and a node N3 respectively, all the three nodes > are allocated in different processor elements. The node N1 cannot be > executed until receiving tokens from both N2 and N3. If no token sent > from either N2 or N3, N1 is in waiting state. > Is the waiting state the same as the dealock state of a logic process > in the context of distributed simulation? This is not necessarily deadlock. The critical issue is what you mean by "If no token [is] sent from either N2 or N3...". For example, if a token will eventually be sent from N2 and N3, then N1 is simply waiting, no more. If however, N2 or N3 will never send another token, this may or may not be deadlock. One case in which this is not deadlock is if the program has terminated. Just because a node will never fire again doesn't mean the program is deadlocked. In order for deadlock to occur, termination must depend on a node's firing, and it must be the case that that node will never fire again. --Ed -- uucp: {...}!rutgers!caip.rutgers.edu!segall arpa: segall@caip.rutgers.edu