Deadlock Detection and Avoidance using Signal Interpreted Petri Nets

Z. Aspar1, Mohamed Khalil-Hani2 and Nasir Shaikh-Husin3 VeCAD Research Lab., Faculty of Electrical Engineering,

Universiti Teknologi Malaysia, 81310 UTM Skudai, Johor, Malaysia

zulfakar@fke.utm.my1, khalil@fke.utm.my2, nasirsh@fke.utm.my3

Abstract – Ladder Logic Diagram (LLD) modeling is a popular method that is used in designing programmable logic controllers (PLC) for industrial automation. However, as systems get more complex, they become increasingly difficult to detect and debug for design problems using these LLD models. Deadlock is one of the critical problems faced in complex PLCs applied in industry today. This paper proposes a method to analyse the deadlock problem in an LLD model. The LLD model is first converted to an equivalent Signal Interpreted Petri Net (SIPN). Deadlocks are detected by applying the approach of transitive matrix of resource share places in this SIPN. A new deadlock avoidance algorithm is proposed, that uses the Boolean transitions of the SIPN model. A key advantage of the proposed algorithm over existing methods is that there are no additional elements or resources introduced to eliminate the deadlock problem. Thus, the complexity of the net remains unchanged.

Index Terms—Ladder Logic Diagram; Signal Interpreted Petri

Net; PLC; Deadlock Detection and Avoidance.

I. INTRODUCTION Both Petri Net (PN) and Ladder Logic Diagram (LLD)

models were born in 1960’s but for different reasons. PN was invented by C. A. Petri to study asynchronous nature in communication [1]. Meanwhile, LLD was invented due to the need to minimize retraining time by mimicking the existing electromechanical relays when the Programmable Logic Controller (PLC) was introduced. As PN grows with more functionalities, and LLD evolves into a very important tool in PLC implementation, research on both modelling started to merge together at the end of 1990’s. A comprehensive introduction into Petri Nets can be found in [1].

LLD has been widely used in the design of PLC. However, PLC implementation in process control and automation are becoming increasingly complex due to increase in the complexity of product specification, shorter design cycles, and shorter product life cycles. As a result, it is harder to detect and debug design problems in an LLD model. To circumvent this problem, there are research performed that have taken the approach to model the PLC at higher level of abstraction such as using Petri Nets, as reported in [6], [7], [8] and [9].

Among the critical design problem in an LLD model that is difficult to debug is deadlock. This research adopts the transitive matrix approach on a PN, as proposed in [10], to perform the deadlock analysis. It is based on resource share

analysis on the relationship between the input places and output places. Calculating the relationship, deadlock in a PN sub-net can be detected. If all sub-nets are deadlock free, then the whole PN model is also deadlock free. In this paper, it is shown that transitive matrix, such as that presented in [10], [11], [12] and [13], can be applied with Signal Interpreted Petri Net (SIPN), which is an extension of the original PN.

In this paper, an algorithm to detect and avoid deadlocks in an LLD model is proposed. The technique is based on a deadlock analysis on the transitive matrix of resource share places in an SIPN model that is equivalent to the LLD model. An example problem is presented to illustrate the effectiveness of the algorithm. The proposed deadlock avoidance part of the algorithm does not introduce any additional elements or resources into the model to remove a deadlock, which is a novel advantage over existing PN-based deadlock analysis methods.

The rest of the paper is organized as follows. Section II reviews the fundamentals of LLD, SIPN and Transitive Matrix. Section III proposes the new algorithm for deadlock detection and avoidance in LLD based on SIPN. Results and discussion are in Section IV, while conclusion and future work are given in Section V.

II. BACKGROUND

A. Ladder Logic Diagram (LLD) Figure 1 is an example of a complete LLD model, which is

used as our example problem to illustrate the proposed

Figure 1: LLD model of the example problem

978-1-4673-3119-7/12/$31.00 ©2012 IEEE 150

algorithm. This is an LLD model of a bottle filling procedure on a conveyor, an example case study presented in the work by K. Latha in [5].

The combination of all the rung outputs in an LLD represents a state. The state can change if any of the output changes due to changes in any of the step input. Thus, the LLD state varies with the step combination. The step input changes either directly from external or physical inputs or due to the feedback from any output rung. The LLD can be implemented on a microprocessor or an FPGA-based design. While the former has variable processing cycles, the latter has customized architecture with faster and consistent processing cycle [2]. Alternatively, LLD models can be converted to higher level models, such as PNs, for analysis [3].

B. Signal Interpreted Petri Net (SIPN) A Signal Interpreted Petri Net (SIPN) is an extension of the

(Condition/Event) Petri Net, that allows the handling of binary I/O signals in a well-defined way. An SIPN is suitable for modeling design control algorithms for discrete event systems. An SIPN is defined as a 10-tuple SIPN = P, T, F, W, m0, I, O, φ, ω, Ω, where P, T, F, W, m0 is the ordinary PN. P is a finite set of places: P=p1, p2, p3 … pn denoted by circles, T is a finite set of transitions: T = t1, t2, t3 … tn denoted by small bars, F is a set of arcs (flow relation), W is a weight function of F denoted by numbers on the arc, and m0 is the initial marking of the places denoted by marked token in the place [1]. To become SIPN, the extensions are: I – input signals, |I| > 0; O – output signals, |O| > 0 and I ∩ O = Ø; φ – Boolean function in I at T; ω – a mapping associating every place pi ∈ P with an output ω(pi) ∈ (0, 1, -), (-) means ‘don’t care’; Ω – output function combines the output ω of all marked places. A more formal discussion of SIPN is available in [1], [6], [7], [8] and [9].

Figure 2 is an example of a complete SIPN model, which is the model of our example problem, the bottle filling procedure of Latha [5]. This SIPN is equivalent in behaviour to the LLD model given in Figure 1. Normally, the SIPN has an initial marking as shown by the initial position of the token marked by a black dot as shown in Figure 2. States of a process are modeled by tokens in places and state transitions leading from one state to another are modeled by transitions.

The dynamic behavior of an SIPN can be observed based

on the state changes as marked by the token movement. The token firing process is defined by four rules:

1. A transition is enabled, if all its pre-places are marked and firing ensures binary marking of all its post-places.

2. A transition fires immediately, if it is enabled and its firing condition is fulfilled.

3. All transitions that can fire and are not in conflict with other transitions fire simultaneously.

4. The firing process is iterated until a stable marking is reached (i.e. until no transition can fire anymore). Since firing of a transition is supposed to take no time, iterative firing is interpreted as simultaneous. For that reason, no changes of input signals may occur during the firing process.

After a new stable marking is reached, the output signals are computed according to the marking and the signal algebra. The main difference between an ordinary PN firing rules and a SIPN firing rules is the fourth rule. Due to the Boolean equation, it is possible the transitions are independent from previous places condition. As a result, a stable state must be observed before the next firing can commence.

C. Transitive Matrix The transitive matrix was developed to analyze FMS

(Flexible Management System) using a Petri Net model. Detailed definitions and examples of transitive matrices can be found in [11], [12] and [13]. For the purpose of this paper, we summarize here the main definitions.

Let MPR be a transitive matrix of PN = (PR,T,I,O,m0). Then,

MPR = B- .(B+)T where B- is an input function matrix (equal to Pre or I matrix) and B+ is an output function matrix (equal to Post or O matrix) of m rows by n columns in PN.

Let a reachable marking MR(k+1) from M(k) be an m-vector of nonnegative integers. The transformation is defined by MR(k+ 1)T = M(k) T MPR . The elements of MPR describe the direct transferring relation from one place to another place through one or more transitions, tk.

Let #(pri, O(tk)) be a number of output value from pi to transition tk, and #(pri, E(tk)) be a number of input value from tk to place pi. The definition of the relation conditions in column are as follows: (i) #(pri, O(tk)) = #(pri, E(tk)) ∑ : It maintains a

control scope under a firing of the token at tk. (ii) #(pri, O(tk)) > #(pri, E(tk)) ∑ : It expands the

control scope under a firing of the token at tk. (iii) #(pri, O(tk)) < #(pri, E(tk)) ∑ : It reduces the

control scope under a firing of the token at tk.

Therefore, we can obtain that the sum of transitions of a row direction of a transitive matrix is 1 in any situation. If a value of ∑ ( )i is smaller than 1, we know that the net has fault. The PN is considered deadlock-free if a relationship in row(column) of the resource share place is

2

2

T12

T11 P4, BFV,Bottle Fill Valve

T4 T6

T10

P2, TFV, Tank Fill Valve

T2

P1, Run

T1

P5, Idle

T5

T14 T3

P3, RM, Run Motor

T13

Figure 2: The SIPN model of the example problem

151

∑ , where n 1 and integer, else the PN is deadlock [11], [12] and [13]. Hence, the algorithm based on transitive matrix to find a deadlock in the model is: 1. Define MPR of a Petri Net, initial N. 2. Find all relations of the resource share places in each

column of MPR. 3. Calculate MR from the initial marking. The reachable

marking can be calculated in a transitive matrix as defined by MR(k+ 1)T = M(k) T MPR.

4. If they have one deadlock node then this net, N is a deadlock net but if not, it is deadlock free.

III. THE PROPOSED DEADLOCK ANALYSIS ALGORITHM Although the logic in each rung of a LLD model is easily

understood, the relationship between rungs are difficult to trace. As LLD model size grows, the model becomes more complex as the number of rungs increases. The model complexity makes it very hard to detect any design fault. To alleviate this complexity problem, we propose a solution where the LLD model is converted to an equivalent SIPN model, which is at a higher level of abstraction. Analysis at this level is more feasible, as is demonstrated with the deadlock problem. The proposed algorithm can detect any deadlock in the original LLD. Once a deadlock is identified, the SIPN is modified such that the deadlock is removed. The deadlock-free SIPN model is then re-converted to its equivalent LLD model, which is then also free of deadlocks. In summary, the proposed deadlock analysis procedure is:

(i) Convert the LLD model to SIPN model, (ii) Use transitive matrix algorithm to detect any deadlock, (iii) Analyse the shared resources based on LLD

behaviour, (iv) Use the proposed deadlock avoidance algorithm to

eliminate any possible deadlock.

A. Prelude: Deadlocks in SIPN and LLD SIPN can be used to model either sequential or concurrent

processes. In LLD, the process flow can also be traced either as sequential or concurrent processes. Since this paper is focused on concurrent process, it is important to understand the nature of deadlock both in SIPN or LLD models.

A deadlock problem occurs by the conflict place in the net. In an SIPN model, a deadlock will cause a state to stay the same instead of going to the predetermined state. A deadlock may occur due to several circumstances. A possible deadllock situation arises when certain transitions from a particular place cannot be fired because the place does not have sufficient token. In another scenario, the same sequence of transitions are always activated in a cycle, creating a deadlock where the same states are reached without the possibility to enter other possible states. While in random transition activation, loops are also executed but the alternative branches or routes cannot be taken as intended. Hence, the deadlock will produce unintended sequences.

In LLD, there are three possibilities for a deadlock to occur. A random activated steps causes random rungs to be activated while the intended or complement rungs are not. Like in SIPN, the same activation sequence in a scan cycle may be repeated everytime. As a result, the same set of rungs is activated each time, creating a deadlock as the other rungs are not activated at all. In the third deadlock case, two steps are activated at the same time. In this case, both rungs are activated whereas only one next rung should be activated.

In concurrent process, two or more places are activated at a time. In the whole SIPN model, there are two or more tokens available either in the same place or different places at a time. When tokens are at different places, a concurrent process exist. Each process can be analyzed as a separate sequential process. As in any pure sequential process, a deadlock can be identified if a conflict place exists.

B. Illustration of Deadlock Detection in Example Problem The example problem to illustrate how the proposed

algorithm works is the bottle filling procedure on a conveyor modeled by the LLD shown in Figure 1. The equivalent SIPN model is given in Figure 2. The transitions include T1- Start, T2 - TLL (Tank Lower Level), T6 - TUL (Tank Upper Level), T3 - *BP (Not Bottle in Position), and T4 - BP (Bottle in Position). T5, T10, T11 and T12 are equal to Stop. T13 is also BP (Bottle in Position), and T14 is BF (Bottle Full). It should be noted here that, in LLD-to-SIPN conversion process, the transitions T7, T8, and T9 in the LLD are eliminated. This LLD-to-SIPN mapping step is not presented here since it is out of the scope of this paper.

The raw MPR table is first derived as shown in Table I. Then, the required MPR table is derived as given in Table II.

TABLE I. RAW MPR TABLE FOR EXAMPLE PROBLEM

P1 P2 P3 P4 P5 0 T2 T3 T4 T5 P1

T6 0 0 0 T10 P2 0 0 0 T13 T11 P3 0 0 T14 0 T12 P4

T1 0 0 0 0 P5

There are four places where resources are shared (P1, P2, P3 and P4). There are also two concurrent processes represented by P1-P2 and P3-P4 cycles. P1 is the place where the concurrent processes may branch into the two separate sequential processes. Since each independent process can be viewed as a separate sequential process, each of them may have deadlocks, like any other sequential process. Hence, concurrent SIPN model may have deadlocks too.

TABLE II. MPR TABLE FOR EXAMPLE PROBLEM

P1 P2 P3 P4 P5 ∑ 0 1 1 1 1 P1 4 1 0 0 0 1 P2 2 0 0 0 1 1 P3 2 0 0 1 0 1 P4 2 1 0 0 0 0 P5 1 2 1 2 2 4 ∑

152

The relationship between shared resources are analyzed using the Transitive Matrix. (Rr is relation in row while Rc is relation in column). Case of:

1. P1: Dr(P1) = Rr – Rc = 2 – 4 = -2 (deadlock) 2. P2: Dr(P2) = Rr – Rc = 1 – 2 = -1 (deadlock) 3. P3: Dr(P3) = Rr – Rc = 2 – 2 = 0 (deadlock free) 4. P4: Dr(P4) = Rr - Rc = 2 – 0 = 0 (deadlock free)

Analyzing the model, P5 is definitely deadlock-free, since there is only a single path for any token to go through. At P1, there are three output arcs. Since the system has only two tokens, a deadlock may arise at P1. However, there is no deadlock if a token is passed to P2 and P1 holds only one token. According to SIPN firing rule, T2 cannot be fired again if P2 is already activated. Thus any available token at P1 can be channelled only to either P3 or P4. Since T3 is the complement of T4, they will never be fired at the same time. Thus, a deadlock does not occur. Therefore, P1 can be assured to be deadlock free if P1 either has no token at all or it has both tokens. Hence, the modification of the input and output arcs at T1 is justified. T3 and T4 do not need any modification. In the model, T6 and T10 are not complementary to each other, hence P2 has the potential to be in a deadlock situation. T10 is used to end the whole process flow while T6 is used to suspend the P2 operation by waiting at P1. Thus, T10 has the higher priority to be fired. P3 has the potential to be in a deadlock situation since T11 and T13 are not complimentary to each other. T11 is used to end the whole process flow while T13 is used to interchange the P3 operation with P4. Thus, T11 has the higher priority to be fired. P4 has the potential to be in a deadlock situation since T12 and T14 are not complimentary to each other. T12 is used to end the whole process flow while T14 is used to interchange the P4 operation with P3. Thus, T12 has the higher priority to be fired.

C. Our Proposed Deadlock Avoidance Algorithm Although the Transitive Matrix approach can be used to

detect any possible deadlock as illustrated above, based on SIPN model of the example problem, there are other possibilities for deadlocks to occur, particularly when simultaneous transitions are enabled. In existing methods for deadlock detection and avoidance, modifications are made to the model by adding more arcs or transitions. This results in a much more complex model, making the modified model difficult to understand and more expensive to be implemented. Furthermore, many proposed methods do not specifically try to emulate for LLD behaviour.

Our proposed deadlock avoidance algorithm does not need any additional arc or transition. Instead, the connected transitions must be modified by changing the Boolean equation of the transitions. The proposed algorithm is as follows: a) Based on the number of concurrent processes, add the

number of tokens accordingly. However, the placement of the tokens depends on the dynamic or behaviour analysis.

b) If the sub-net is a deadlock free, verify it is truely free by ensuring all connected transitions has complement Boolean

equations. If the transitions are not complimentary to each other, each of them must be prioritized by adding the inverted condition of the other transitions or places.

c) If the sub-net is a deadlock, ensure that only sufficient number of transitions can be enabled at a time which is equivalent to number of tokens. If the number of tokens is not sufficient, modify the transition equations to include priority condition either by adding the condition of other transitions or places. If all of the above analysis and modifications still fail to

avoid any deadlock, then the current practice of existing methods in changing the SIPN structure can be applied. As analysed in the example, P5 is definitely deadlock-free since there is only a single path for any token to go through. Hence, no modification is necessary to the transition. P2 has the potential to be in a deadlock and to solve the potential deadlock situation, T6 must be modified from TUL to TUL.*Stop. This is to ensure T6 can only be fired if Stop is not active. P3 has the potential to be in a deadlock, and to solve the potential deadlock situation, T13 must be modified from BP.*BF to BP.*BF.*Stop. This is to ensure T13 can only be fired if Stop is not active. P4 has the potential to be in a deadlock and to solve this problem, T14 must be modified from BF to BF.*Stop. This is to ensure T14 can only be fired if Stop is not active.

IV. RESULTS The LLD and the equivalent SIPN models are described

and simulated in MATLAB and C programs respectively. The simulation behaviour of both models is compared using State Transition Tables as shown in Table III and IV. Using Transitive Matrix, the analysis is focussed on the resource share places to reduce the analysis time. In order to save space, only the active inputs (transitions) are shown in each sequence. All outputs (places) are always available. Seq. represents sequence while I represents the initial position. X is don’t care condition. The symbol ‘–‘ means not relevant.

LLD model has no token, hence one rung is only represented by one output enabling at a time. Rung P1 in line 3 was modified so that P1 is still enabled even if either P2 or P3 or P4 is enabled. If P2-P3 or P2-P4 are enabled, P1 will be disabled. After deadlock avoidance algorithm is implemented as prescribed in Section IIIC, the results of the simulations of the modified SIPN and LLD are shown in Table V and VI respectively. After the modifications, it is not possible to fire two or more transitions simultaneously if both transitions are complementary to each other as in T3 and T4.

If priority transition is applied, one of the transitions will be fired such as T5, T10, T11, T12. The structure of the SIPN remains the same. For the LLD model, T6 step becomes T6.*T10 (TUL to TUL.*Stop). T13 must be modified to become T13.*T11 (from BP.*BF to BP.*BF.*Stop). T14 must be modified to become T14.*T12 (from BF to BF.*Stop). In addition, T5 was not included in the Transition Tables of Table III, IV, V and VI to simplify the results. Since T5 has higher priority compared to T2, T3 and T4, T2 must become T2.*T5, T3 becomes T3.*T5, and T4 becomes T4.*T5.

153

The changes to the steps in LLD model does not change the performance of the PLC. If ladder rung processor in [2] is used, the number of processing cycles is still the same. The size of the memory to contain the modified SIPN or LLD models are still the same. Since in ladder rung processor, the fixed size of steps and lines per rung is held by the same size of memory location.

TABLE III. STATE TRANSITION OF SIPN MODEL

Place Seq. Input Output P1,P2,P3,P4,P5

P1 I X 2, 0, 0, 0, 0 - 1 T2 1, 1, 0, 0, 0 No deadlock 2 T3 0, 1, 1, 0, 0 No deadlock I X 1, 1, 0, 0, 0 - 1 T4 0, 1, 0, 1, 0 No deadlock I X 1, 1, 0, 0, 0 - 1 T3,T4 1, 1, 0, 0, 0 Deadlock P2 I X 1, 1, 0, 0, 0 - 1 T6 2, 0, 0, 0, 0 No deadlock 2 T2 1, 1, 0, 0, 0 No deadlock 3 T10 1, 0, 0, 0, 1 No deadlock I X 1, 1, 0, 0, 0 - 1 T6,T10 1, 1, 0, 0, 0 Deadlock P3 I X 1, 0, 1, 0, 0 - 1 T11 1, 0, 0, 0, 1 No deadlock I X 1, 0, 1, 0, 0 - 1 T13 1, 0, 0, 1, 0 No deadlock I X 1, 0, 1, 0, 0 - 1 T11,T13 1, 0, 1, 0, 0 Deadlock P4 I X 1, 0, 0, 1, 0 - 1 T12 1, 0, 0, 0, 1 No deadlock I X 1, 0, 0, 1, 0 - 1 T14 1, 0, 1, 0, 0 No deadlock I X 1, 0, 0, 1, 0 - 1 T12,T14 1, 0, 0, 1, 0 Deadlock

TABLE IV. STATE TRANSITION OF LLD MODEL Place Seq. Input Output P1,P2,P3,P4,P5 P1 I X 2, 0, 0, 0, 0 - 1 T2 1, 1, 0, 0, 0 No deadlock 2 T3 0, 1, 1, 0, 0 No deadlock I X 1, 1, 0, 0, 0 - 1 T4 0, 1, 0, 1, 0 No deadlock I X 1, 1, 0, 0, 0 - 1 T3,T4 1, 1, 0, 0, 0 Deadlock P2 I X 1, 1, 0, 0, 0 - 1 T6 1, 0, 0, 0, 0 No deadlock 2 T2 1, 1, 0, 0, 0 No deadlock 3 T10 1, 0, 0, 0, 1 No deadlock I X 1, 1, 0, 0, 0 - 1 T6,T10 1, 1, 0, 0, 1 False no DeadlockP3 I X 1, 0, 1, 0, 0 - 1 T11 1, 0, 0, 0, 1 No deadlock I X 1, 0, 1, 0, 0 - 1 T13 1, 0, 0, 1, 0 No deadlock I X 1, 0, 1, 0, 0 - 1 T11,T13 1, 0, 1, 0, 1 False no DeadlockP4 I X 1, 0, 0, 1, 0 - 1 T12 1, 0, 0, 0, 1 No deadlock I X 1, 0, 0, 1, 0 - 1 T14 1, 0, 1, 0, 0 No deadlock I X 1, 0, 0, 1, 0 - 1 T12,T14 1, 0, 0, 1, 1 False no Deadlock

TABLE V. STATE TRANSITION OF MODIFIED SIPN MODEL

Place Seq. Input Output P1,P2,P3,P4,P5

P1 I X 2, 0, 0, 0, 0 - 1 T2 1, 1, 0, 0, 0 No deadlock 2 T3 0, 1, 1, 0, 0 No deadlock I X 1, 1, 0, 0, 0 - 1 T4 0, 1, 0, 1, 0 No deadlock I X 1, 1, 0, 0, 0 - 1 T3,T4 1, 1, 0, 0, 0 Not possible P2 I X 1, 1, 0, 0, 0 - 1 T6 2, 0, 0, 0, 0 No deadlock 2 T2 1, 1, 0, 0, 0 No deadlock 3 T10 1, 0, 0, 0, 1 No deadlock I X 1, 1, 0, 0, 0 - 1 T6,T10 1, 0, 0, 0, 1 No deadlock P3 I X 1, 0, 1, 0, 0 - 1 T11 1, 0, 0, 0, 1 No deadlock I X 1, 0, 1, 0, 0 - 1 T13 1, 0, 0, 1, 0 No deadlock I X 1, 0, 1, 0, 0 - 1 T11,T13 1, 0, 0, 0, 1 No deadlock P4 I X 1, 0, 0, 1, 0 - 1 T12 1, 0, 0, 0, 1 No deadlock I X 1, 0, 0, 1, 0 - 1 T14 1, 0, 1, 0, 0 No deadlock I X 1, 0, 0, 1, 0 - 1 T12,T14 1, 0, 0, 0, 1 No deadlock

TABLE VI. STATE TRANSITION OF MODIFIED LLD MODEL

Place Seq. Input Output P1,P2,P3,P4,P5

P1 I X 2, 0, 0, 0, 0 - 1 T2 1, 1, 0, 0, 0 No deadlock 2 T3 0, 1, 1, 0, 0 No deadlock I X 1, 1, 0, 0, 0 - 1 T4 0, 1, 0, 1, 0 No deadlock I X 1, 1, 0, 0, 0 - 1 T3,T4 1, 1, 0, 0, 0 Not possible P2 I X 1, 1, 0, 0, 0 - 1 T6 1, 0, 0, 0, 0 No deadlock 2 T2 1, 1, 0, 0, 0 No deadlock 3 T10 1, 0, 0, 0, 1 No deadlock I X 1, 1, 0, 0, 0 - 1 T6,T10 1, 0, 0, 0, 1 No Deadlock P3 I X 1, 0, 1, 0, 0 - 1 T11 1, 0, 0, 0, 1 No deadlock I X 1, 0, 1, 0, 0 - 1 T13 1, 0, 0, 1, 0 No deadlock I X 1, 0, 1, 0, 0 - 1 T11,T13 1, 0, 0, 0, 1 No Deadlock P4 I X 1, 0, 0, 1, 0 - 1 T12 1, 0, 0, 0, 1 No deadlock I X 1, 0, 0, 1, 0 - 1 T14 1, 0, 1, 0, 0 No deadlock I X 1, 0, 0, 1, 0 - 1 T12,T14 1, 0, 0, 0, 1 No Deadlock The results can be benchmarked with the existing deadlock

avoidance method [13], where additional elements or resources have to be introduced to eliminate the deadlock. The proposed algorithm has the same number of places, transitions and arcs, that is, it does not add new elements into the model.

154

V. CONCLUSION Transitive matrix can be used as the first level of deadlock

detection. Although it is originally used in PN modeling for FMS, it can also be used in SIPN modeling. However, a more thorough deadlock detection is required if the SIPN model is to be transformed to a lower-level modeling such as the LLD model. Since the deadlock behaviour in LLD model has a slightly different deadlock behaviour as that in the equivalent SIPN model, a more efficient deadlock avoidance is formulated. Instead of adding more complexites to the SIPN model, the proposed deadlock avoidance algorithm manipulates the Boolean transitions of the SIPN model, resulting in the complexity of the net remaining unchanged.

ACKNOWLEDGMENT The authors are grateful to the Ministry of Science,

Technology and Innovation (MOSTI), Ministry of Higher Education (MOHE), and Universiti Teknologi Malaysia for the financial support through the grants MOSTI 4S003 and MOHE KTP R.J130000.7823.4L500.

REFERENCES [1] Murata, T., “Petri Nets: Properties, analysis and applications.

Proceedings of the IEEE”, 1989. 77(4): p. 541 – 580. [2] Zulfakar Aspar and Mohamed Khalil-Hani, “Modeling of a

Ladder Logic Processor for high performance Programmable Logic Controller”, accepted for publication in Third Asia International Conference on Modeling & Simulation. 2009: Bandung and Bali, Indonesia. p. 6.

[3] Shih Sen Peng and Meng Chu Zhou., “Conversion between Ladder Diagrams and PN in Discrete-Event Control design - a survey”, in Systems, Man, and Cybernetics 2001. 2001: Tucson, AZ, USA. p. 6.

[4] J-L Chirn and D. C. McFarlane, “Petri Nets based design of Ladder Logic Diagrams”, in Control 2000, Cambridge, UK, September, 2000. 2000. p. 4.

[5] K. Latha, and B. Umamaheswari, “Supervisory Control of an automated system with Ladder Logic Programming and analysis using Petri Nets”, in Systems, Man and Cybernetics, International Conference on. 2002. p. 5.

[6] Georg Frey, “Automatic implementation of Petri Net based Control algorithms On PLC”, Proceedings Of The American Control Conference, Chicago, Illinois June 2000, 2819-2823.

[7] Georg Frey and Lothar Litz, “Transparency analysis of Petri Net based Logic Controllers - a measure for software quality in automation”, American Control Conference, Chicago, Illinois, 2000, 5, 3182 - 3186.

[8] Stéphane Klein, Xiying Weng, Georg Frey, Jean-Jacques Lesage and Lothar Litz, “Controller design for an FMS using signal Interpreted Petri Nets and SFC - validation of both descriptions via Model-Checking”, Proceedings of the American Control Conference 2002. 5: 6, 4141 - 4146.

[9] Stéphane Klein, Georg Frey, Jean-Jacques Lesage and Lothar Litz, “Supporting the changeability of SIPN based Logic Control algorithms by verification and validation“, IMACS-IEEE International Conference on Computational Engineering in Systems Applications (CESA'03). Lille, France, 9 July 2003.

[10] Kimmo Varpaaniemi, “Efficient detection of deadlocks in Petri Nets”, Faculty of Information Technology, Helsinki, Helsinki University of Technology. Master Thesis, 1993.

[11] Yu-Jin Song and Jong-Kun Lee, “Analysis of Petri net models using transitive matrix”, IEEE International Conference on Systems, Man, and Cybernetics, 2000 Nashville, TN, 08 -11 Oct 2000, Vol. 4, 3122-3127.

[12] Jongwoog Kim and Jongkun Lee, “Efficient deadlock detection in FMS based on the Transitive Matrix of resource share Places”, The 23rd International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC 2008). Shimonoseki City, Yamaguchi Pref., Japan, 6-9 July 2008, 277-280.

[13] Sanghwan Kim, Sangho Lee and Jongkun Lee, “Deadlock analysis of Petri Nets based on the resource share Places relationship”, IMACS Multiconference on Computational Engineering in Systems Applications, 4-6 Oct. 2006, Vol. 1, 59 – 64.

155