# An Enhanced Supervisory Control Strategy for Periodicity Mutual Exclusions in Discrete Event Systems Based on Petri Nets

Authors: Zhongyuan Jiang; Huan Wang; Xiaoliang Chen; Mingwei Tang; Jianhong Ye
Journal: Discrete Dynamics in Nature and Society
 (2017)

---

## Abstract

Mutual exclusion problems widely exist in discrete event systems in which several processes will compete for the common resource for maintaining their normal running. This competition is mutually exclusive. However, a special behavior, that is, periodic mutual exclusion behavior, is important for many discrete event systems. Once a process obtains the common resource, it will consecutively obtain the common resource in the following several competitions. The other processes should wait for the release of the common resource. All processes will compete for the common resource again after the common resource is released. These competitions have obvious periodicity. In this paper, a methodology is proposed to design periodic mutual exclusion supervisors to control the periodic mutual exclusion behavior in discrete event systems. Moreover, two original structural conversion concepts, calledk-derivation and k-convergence processes, are proposed to construct the periodic mutual exclusion supervisors. The discussion results show that many undesirable execution sequences are forbidden since the periodic mutual exclusion behavior is controlled by the proposed periodic mutual exclusion supervisors. Finally, an example is used to illustrate the proposed methodology.


---

## Body

## 1. Introduction

Discrete event systems [1] are classic dynamic systems, which widely exist in communication, manufacturing, traffic, and computer network fields, such as e-business systems, online game server systems, embedded systems, flexible manufacturing systems, and traffic management systems [2]. The concurrency behavior [3] of discrete event systems is to consider several events that simultaneously occur and potentially interact with each other. Concurrent events can be alternately executed on a single processor but can be also concurrently executed on several processors. The occurrence sequences of these concurrent events are important since system concurrency behavior can optimize system performances and promote the sufficient utilization for finite system resources [4].The occurrence of some concurrent events may simultaneously occupy some special resources, such as a CPU, a printer, a robot, or a shared file. These special resources are finite because of the restriction of high implementation costs. Therefore, these concurrent events should share their special resources. This will form a competition among these concurrent events [5]. On the other hand, the competition will maximize the utilization of shared special resources. A most widespread and important phenomenon is that only one special resource can be used for several concurrent events. This results in a mutual exclusion behavior [6] for these concurrent events (only one of them can obtain the special resource at the same time and the other events should wait for the release of the occupied special resource). Mutual exclusion behaviors as an important character in discrete event systems are usually used for resource allocation (resource sharing) or marking constraint in Petri nets [7], such as the user request distribution in a single input cluster of computer servers, the raw material distribution of a robot for two production lines, and the database access control for multiple processes.In discrete event systems, the special resource utilization rates are an important indicator to measure the performance of discrete event systems. It is necessary to design appropriate control strategies to control the special resource distribution for discrete event systems. The purpose is to maximize the utilization of shared special resources. The authors in [8] consider deterministic feasibility and time complexity of two fundamental tasks in the distributed computing of consensus and mutual exclusions. In [9], a mutual exclusion element is described using a reflective semiconductor optical amplifier and a simple scheme for contention resolution in arrayed waveguide grating router based optical switches in data centers. The authors in [10] propose an approach to compete for the privilege of passing the intersection that is a classical mutual exclusion problem via the communications among vehicles and infrastructure. In [11], two algorithms are presented to compete for exclusive access to a shared resource among geographically close nodes in a mobile ad hoc network.Supervisory control theory [12, 13] is widely used to perform the controller syntheses of discrete event systems, which is proposed by Ramadge and Wonham based on automata [14, 15]. In order to avoid the numerous state representations of automata, the subsequent researchers use Petri nets to study the control strategies. The authors in [16] present a framework for supervisor synthesis for discrete event systems. The approach is based on compositional minimization by using concepts of process equivalence. For the studies of control strategies in discrete event systems, maximally permissive problems should be considered. The authors in [17] present a computational method to design optimal control places in order to obtain a maximally permissive liveness-enforcing supervisor by using a vector covering approach. The authors in [18] distinguish between the offline and the online computation that is required for the effective implementation of the maximally permissive deadlock avoidance policy. The authors in [19] study the maximally permissive abstractions for the hierarchical and decentralized control of large-scale discrete event systems. Moreover, the structure optimization problems of supervisors are also important. The authors in [20] present two iterative deadlock prevention policies for flexible manufacturing systems. The proposed methods can reduce the overall computational time. The authors in [21] propose a deadlock prevention method to obtain maximally permissive supervisor and minimize its structure. The authors in [22] propose a deadlock prevention method for a flexible manufacturing system with a minimal supervisory structure. Furthermore, researchers also concern the design and implementation problems of Petri net based supervisors. In [23], the authors present the design, generation, and implementation of coordinating discrete event control code using Petri nets for an operating flexible manufacturing system. The authors in [24] use Petri nets to model the operated behaviors and to synthesize the command filters in a command filtering framework. Automation Petri nets can be used to perform the design and implementation of discrete event control systems by converting automation Petri nets into ladder diagrams on programmable logic controllers [25].The main researches of supervisory control theory are divided into several classic problems based on Petri nets, that is, forbidden-state problems [26, 27], forbidden-string problems [28, 29], deadlock prevention problem [30], and liveness maintenance problems [31, 32]. The deadlock prevention problems and liveness maintenance problems can be transformed to forbidden-state problems directly [33, 34]. The authors in [35] address the forbidden-state problem of Petri nets by computing maximally permissive Petri net controllers. The design of control strategies for mutual exclusion mechanisms can be considered as resolving a forbidden-string problem. The authors in [36] use a colored generalized stochastic Petri net model to study the performance and correctness of a Lamport concurrent algorithm to solve the mutual exclusion problems. The authors in [37] discuss the simultaneous events in mutual exclusion transitions. The execution modes of sequential function charts are presented based on Petri nets. In [38], a method is proposed to control the occurrence of simultaneous events in mutual exclusion transitions by Petri nets based on supervisory control theory. The authors in [5] formulate two resource-sharing concepts, that is, parallel mutual exclusion and sequential mutual exclusion, and provide a theoretical basis for Petri net synthesis methods to model systems.A class of specifications, that is, generalized mutual exclusion constraints, is studied in [39] for discrete event systems modeled using place/transition nets. According to these specifications, many constraints that deal with mutual exclusion problems between state and events or just events themselves can be transformed into generalized mutual exclusion constraints. This can be enforced by a set of places if all transitions are controllable. For the transitions that are uncontrollable, this specification is not always applicable. The authors in [40] provide a class of generalized mutual exclusion constraints on a class of forward-concurrent-free nets. In [41], a type of specification, called OR-AND generalized mutual exclusion constraints, is defined for place/transition nets. Such a specification consists of a disjunction of conjunction of several single generalized mutual exclusion constraints. The authors in [42] enforce the generalized mutual exclusion constraints on a Petri net plant by replacing the classical partition of event set into controllable and uncontrollable events from supervisory control theory. In [43], an algorithm is presented to transform a given generalized mutual exclusion constraint into an optimal admissible one for a class of Petri nets whose uncontrollable influence subnets are forward synchronization and backward conflict-free nets.It is difficult to summarize the constraints for complex mutual exclusion mechanisms and special optimization problems in discrete event systems by using the existing control strategies, such as the following described periodic mutual exclusion problems. In many discrete event systems, one of the concurrent processes will occupy a common resource to maintain its normal running. To satisfy some special requirements, this process will consecutively obtain the common resource during the competition of the following finite times after it won a competition. The other processes only can wait for the release of the common resource. All concurrent processes will form a new competition again after this process finishes a periodical operation for the special requirements and the common resource is released. This mutually exclusive competition among these concurrent processes has periodicity, called periodic mutual exclusion behavior. It is necessary to design appropriate control strategies to distribute the common resources for these concurrent processes to control the periodic mutual exclusion problems.In this paper, a methodology is proposed to design periodic mutual exclusion supervisors to control the periodic mutual exclusion behavior in discrete event systems. The structures of general mutual exclusion systems and periodic mutual exclusion systems are defined by using Petri nets. The proposal is convenient to construct formal models to analyze the properties of the two classes of mutual exclusion systems. Two original structural conversion concepts, calledk-derivation process and k-convergence process, are proposed to construct the periodic mutual exclusion supervisors. The main idea is to derive a common resource to several virtual resources by the preliminary k-derivation processes if a process obtains the common resource and these derived virtual resources will be converged into a common resource by the final k-convergence processes after this process releases the common resource. The execution sequences of all processes are discussed in mutual exclusion systems with general mutual exclusion supervisors and periodic mutual exclusion supervisors, respectively. The discussion results show that many undesirable execution sequences are forbidden in the mutual exclusion systems with the periodic mutual exclusion supervisors because the periodic mutual exclusion behavior is controlled by these periodic mutual exclusion supervisors. Finally, a real example is used to illustrate the proposed methodology.The main contributions of this paper are concluded as follows:(1)
The structures of general mutual exclusion systems and periodic mutual exclusion systems are defined by using Petri nets. The proposal is convenient for constructing formal models for these two classes of mutual exclusion systems.(2)
Two original structural conversion concepts, that is,k-derivation process and k-convergence process, are proposed to derive a common resource to several virtual resources in the preliminary stage and converge these virtual resources into a common resource in the final stage, respectively. The purpose is to enhance the execution permission for each process that obtains the common resource.(3)
A methodology is proposed to design periodic mutual exclusion supervisors to control the periodic mutual exclusion behavior in discrete event systems. In the enhanced mutual exclusion systems, many undesirable execution sequences of all processes are forbidden by the periodic mutual exclusion supervisors.The rest of this paper is organized as follows. Section2 briefly recalls some basics of Petri nets. Section 3 introduces a class of mutual exclusion systems with resources and their periodic mutual exclusion behavior is discussed. Section 4 proposes the design method of periodic mutual exclusion supervisors. Section 5 gives the discussion of periodic mutual exclusion behavior in general mutual exclusion systems and periodic mutual exclusion systems. Section 6 introduces two examples to illustrate the proposed methods. Finally, the proposed methods are concluded in Section 7.


## 2. Preliminaries

We assume that the readers are familiar with the basics of Petri nets. Only some key concepts of Petri nets are provided. More details can be found in [44].A Petri net is a 4-tupleN=(P,T,F,W), where P and T are finite, P≠∅, T≠∅, and P∩T=∅. P is a set of places and T is a set of transitions. F⊆(P×T)∪(T×P) is called a flow relation represented by an arc with arrow from places to transitions and transitions to places. W:F→N∖{0} is a mapping that assigns a weight to an arc, where N is the set of nonnegative integers. A Petri net N=(P,T,F,W) is called an ordinary net if, ∀f∈F, W(f)=1 (denoted as N=(P,T,F)). An ordinary net N=(P,T,F) is called a state machine if t∈T such that t has only one input place and only one output place. A Petri net is self-loop-free if and only if ∃x,y∈P∪T such that f(x,y)∈F and f(y,x)∈F.A markingM of N is a mapping from P to N. (N,M0) is called a net system, where M0 is the initial marking of N. The preincidence matrix Pre:P×T→N of N is Pre(p,t)=W(p,t). The postincidence matrix Post:P×T→N of N is Postp,t=Wt,p. A self-loop-free Petri net N=(P,T,F,W) can be represented by its incidence matrix [N], where [N] is a P×T integer matrix with [N](p,t)=Postp,t-Pre(p,t). For p∈P, M(p) denotes the sum of tokens contained in place p. Place p is marked by a marking M if and only if M(p)>0. A subset S⊆P is marked by M if and only if ∃p∈S such that p is marked by M. The sum of tokens in all places in S is denoted by M(S); that is, M(S)=∑p∈SMp. The subset S is said to be empty at M if and only if M(S)=0.The preset of a nodex∈P∪T is defined as x•=y∈P∪T∣(y,x)∈F and the postset of a node x∈P∪T is defined as x•=y∈P∪T∣(x,y)∈F. For a set of nodes X⊆P∪T, X•=⋃x∈Xx• and X•=⋃x∈Xx•. X represents the item count in X. A transition t∈T is enabled at a marking M if p∈t• such that M(p)>W(p,t), which is denoted as Mt. If t is enabled, its firing yields another marking M′ such that, ∀p∈P,M′(p)=M(p)-W(p,t)+W(t,p), denoted as MtM′. Marking M′ is called reachable from M if there exists a firing sequence σ=t1t2⋯tn such that Mt1M1t2〉M2⋯Mn-1tn〉M′. This is denoted by MσM′.AP-vector is a column vector I:P→Z indexed by P, where Z is the set of integers. We denote a column vector where every entry equals 0(1) by0(1). IT and [N]T are the transposed versions of vector I and matrix [N], respectively. P-vector I is a P-invariant if I≠0 and IT[N]=0T. I=p∈P∣I(p)≠0 is called the support of I. I+=p∈P∣I(p)>0 (resp., I-=p∈P∣I(p)<0) denotes the positive (resp., negative) support of I. P-invariant I is called a minimal P-invariant if I is not a superset of the support of any other one and its components are mutually prime. If I is a P-invariant of N, then M∈RN,M0 such that IT·M=IT·M0.


## 3. Mutual Exclusion Systems with Resources

In this section, the model of mutual exclusion systems with resources (MESRs) is defined by using Petri nets with three classical patterns, that is, parallel pattern, dispersive pattern, and polymeric pattern. The details are shown as follows.Definition 1.
LetN=(P,T,F,W) be a Petri net and c∈P∪T be a node of N. Node c is called a root of N if c•=∅. Node c is called a leaf of N if c•=∅.For a Petri net, it may contain one or more roots and leaves. However, it is impossible to contain one or more roots or leaves in any closed-loop Petri net.Definition 2.
LetN=(P,T,F,W) be a Petri net and s1,s2,…,sn∈P∪T be n nodes such that si≠sj, where i≠j, ∀i,j∈{1,2,…,n}, and n≥2. A transient process, denoted as S=s1s2,…,sn, can be defined if si∈s•i+1, where i∈{1,2,…,n-1}.Definition 3.
LetN=(PK∪{pr}∪{pl},T,F) be a state machine and s1,s2,…,sPK∪T∈PK∪T be PK∪T nodes such that si≠sj, where i≠j and ∀i,j=1,2,…,PK∪T. N is called a linearity process if (1)
PK is a set of places that represent the states of system;(2)
N contains only a root and a leaf, where pr∉PK is the root of N, pl∉PK is the leaf of N, and pl≠pr;(3)
N only exhibits a transient process, denoted as SN=prs1s2⋯sPK∪Tpl.Definition 4.
LetN=PK∪pr∪pl,T,F be a linearity process and S be the transient process from pr to pl. If all places are removed from S, the rest of the transient process S, denoted as ST, is called the T-Process of N.Figure1(a) shows a linearity process N1=p2∪p1∪p3,t1,t2,F. Place p1 is a root and place p3 is a leaf of N1. SN1=p1t1p2t2p3 is a transient process and SN1T=t1t2 is a T-Process of N1. Figure 1(b) shows another linearity process N2=({p5}∪{p4}∪{p6},{t3,t4},F). Place p4 is a root and place p6 is a leaf of N2. SN2=p4t3p5t4p6 is a transient process and SN2T=t3t4 is a T-Process of N2. Figure 1(c) shows a Petri net that is not a linearity process since it contains two transient processes SN3=p1t1p2t2p3 and SN3′=p1t1p2t5p3. Figure 1(d) shows a Petri net that is also not a linearity process since it is not a state machine.Figure 1
Illustration of linearity processes.
(a) (b) (c) (d)In a linearity process, the firing of its transitions may be restrained by some special resources, such as a CPU, a robot, a balancer, or a printer. Therefore, a linearity process with a special resource is defined as follows.Definition 5.
LetN=(PK∪{pr}∪{pl},T,F) be a linearity process and place ps∉(PK∪{pr}∪{pl}) be a resource. A linearity process with the resource ps, denoted as N=(PK∪{pr}∪{pl}∪{ps},T,F), is defined as follows: (1)
pr•=ps• and •pl=•ps.(2)
t∈T∖(pr•∪•pl) such that ps∉•t and ps∉t•.(3)
M0(ps)=1, where M0 is the initial marking.LetN=(PK∪{pr}∪{pl}∪{ps},T,F) be a linearity process with the resource ps. ∀t∈pr•, the firing of t will obtain the special resource ps. Conversely, ∀t′∈p•l, the firing of t′ will release the special resource ps. Figure 2(a) shows two linearity processes with two special resources ps and ps′; that is, N1=({p2}∪{p1}∪{p3}∪{ps},{t1,t2},F) and N2=({p5}∪{p4}∪{p6}∪{ps′},{t3,t4},F). In N1, the special resource is occupied if t1 fires and it is released if t2 fires. This characteristic also exists in N2.Figure 2
(a) Two linearity processes with two special resources, (b) an MESR with dispersive pattern, (c) an MESR with parallel pattern, and (d) an MESR with polymeric pattern.
(a) (b) (c) (d)In a discrete event system, it may contain several linearity processes that compete for a common special resource. These linearity processes of the discrete event system can construct a mutual exclusion system.Definition 6.
LetN1,N2,… and Nn with Ni=(PKi∪{pri}∪{pli}∪{psi},Ti,Fi) (∀i∈{1,2,…,n}) be n (n≥2) linearity processes with resources such that PK1=PK2=⋯=PKn, T1=T2=⋯=Tn, ps1=ps2=⋯=psn. An MESR, denoted as N=(PK∪PR∪PL∪{ps},T,F), is defined as follows: (1)
PK=⋃i=1nPKi, PR={pr1,pr2,…,prn}, PL={pl1,pl2,…,pln}, ps=ps1, M0(ps)=1, where M0 is the initial marking of N.(2)
T=⋃i=1nTi.(3)
F=⋃i=1nFi.
The MESRN can be represented with one of the following three classical patterns: (i)
N is represented with dispersive pattern if pr1=pr2=⋯=prn, ⋂i=1n(PKi∪{pli})=∅, and ⋂i=1nTi=∅.(ii)
N is represented with parallel pattern if ⋂i=1n(PKi∪{pri}∪{pli})=∅ and ⋂i=1nTi=∅.(iii)
N is represented with polymeric pattern if pri≠prj, pri•≠prj•, i≠j, ∀i,j∈{1,2,…,n}, PK1=PK2=⋯=PKn, pl1=pl2=⋯=pln, and T1∖pr1•=T2∖pr2•=⋯=Tn∖prn•.Figure2(b) shows an MESR with dispersive pattern, which resulted from the composition of N1 and N2 depicted in Figure 2(a) via ps=ps′ and p1=p4. Figure 2(c) shows an MESR with parallel pattern, which resulted from the composition of N1 and N2 via ps=ps′. Figure 2(d) shows an MESR with polymeric pattern, which resulted from the composition of N1 and N2 via ps=ps′, p2=p5, t2=t4, and p3=p6.Property 1.
LetN be an MESR with N=(PK∪PR∪PL∪{ps},T,F) and M0 be the initial marking of N. Then, M∈RN,M0 satisfies(1)Mps+∑pi∈PKMpi=M0ps=1.Proof.
It is easy to see that placeps and all places in PK can construct a P-invariant. The result naturally holds.For example, the MESR with dispersive pattern depicted in Figure2(b) satisfies the restriction M(p2)+M(p5)+M(ps)=1. Similarly, the MESR with parallel pattern depicted in Figure 2(c) satisfies the restriction M(p2)+M(p5)+M(ps)=1. For the MESR with polymeric pattern depicted in Figure 2(d), it satisfies the restriction M(p2)+M(ps)=1.Property 2.
LetN=PK∪PR∪PL∪ps,T,F be an MESR with dispersive pattern and M∈R(N,M0) be a marking of N, where M0 is the initial marking of N. Then, t∈PR• such that Mt holds if ∃t′∈PR• such that Mt′ holds.Proof.
SinceN is an MESR with dispersive pattern, we can assume PR={pr}. Then, we have PR•=pr•. If ∃t′∈pr• such that Mt′ holds, we have M(pr)≥1 and M(ps)=1. However, ∀t∈pr•, we have t•=pr,ps according to the structure of the MESR with dispersive pattern. Therefore, ∀t∈pr•, Mt holds since M(pr)≥1 and M(ps)=1. This means that, ∀t∈PR•, Mt holds.Property 3.
LetN=(PK∪PR∪PL∪{ps},T,F) be an MESR with parallel or polymeric pattern and M∈R(N,M0) be a marking of N, where M0 is the initial marking of N. Then, ∀t∈PR•, Mt holds if M(ps)=1 and ∀pr∈PR such that M(pr)≥1.Proof.
∀ t ∈ P R •, we have t•=PR∪{ps} according to the structure of the MESR with parallel or polymeric pattern. If M(ps)=1 and ∀pr∈PR such that M(pr)≥1, we have that, ∀t∈PR•, Mt holds.LetN=(PK∪PR∪PL∪{ps},T,F) be an MESR. Then, all transitions contained in PR• are mutually exclusive. ∀ti∈PR•, ti will compete for the common resource for running its linearity process. If ti fires (its linearity process obtains the common resource), ∀tj∈PR•∖ti cannot fire (they need to wait until they obtain the common resource) since N only contains a common resource. ∀ti∈P•L, ti will release the common resource from its linearity process. This should particularly emphasize that all transitions contained in PR• will compete for the common resource again for their linearity processes if the common resource is released. For the MESR with dispersive pattern depicted in Figure 2(b), transitions t1 and t3 are both enabled or disenabled for all marking. If they are enabled, they will compete for the common resource ps. Once the common resource ps is released by one of the transitions t2 and t4, transitions t1 and t3 will compete for the common resource again. Similar competitions also exist in the two MESRs depicted in Figures 2(c) and 2(d).For an MESR, it may have some special requirements that are concluded as follows:(i)
One of its linearity processes will be consecutively executedk times once this linearity process obtains the common resource, where k≥1 is an integer. The other linearity processes cannot be executed and need to wait until they obtain the common resource.(ii)
Once this linearity process is consecutively executedk times and the common resource is released, all linearity processes will compete for the common resource again.These linearity processes are mutually exclusive with these special requirements. Their mutual exclusion characteristics are called periodic mutual exclusion behavior that widely exists in discrete event systems, such as the online team game server systems, flexible manufacturing systems, and intelligence traffic dispatch systems.For the traditional mutual exclusion behavior, the methods of generalized mutual exclusion constraints presented in [39] can be used to design supervisors to perform the control of mutual exclusion mechanisms. However, it is difficult to use generalized mutual exclusion constraints to control the periodic mutual exclusion behavior. Therefore, the general mutual exclusion supervisors should be extended to handle these special problems.


## 4. Design of Enforced Supervisors

In this section, the methods of generalized mutual exclusion constraints are simply reviewed, which can be used to design general mutual exclusion supervisors. Furthermore, two important concepts, that is,k-derivation process and k-convergence process, are defined to extend the general mutual exclusion supervisors. Finally, a method is proposed to design periodic mutual exclusion supervisors to control periodic mutual exclusion problems.The mutually exclusive competition for a common resource is a classical character in MESRs. Generalized mutual exclusion constraints can be used to design supervisors to perform the mutual exclusion mechanisms. For example, Figure3(a) shows a plant that is composed of two linearity processes. If we assume that only one of the competition transitions t1 and t3 can fire in the plant, we have a restriction M(p2)+M(p5)≤1, where M is a marking of the plant. A supervisor of the plant can be obtained by using the methods of generalized mutual exclusion constraints, as shown in Figure 3(b). The details about the methods of generalized mutual exclusion constraints can be found in [39]. The controlled system that is combined by the plant and the supervisor is shown in Figure 2(b). It can satisfy the restriction M(p2)+M(p5)≤1.Figure 3
(a) A plant and (b) the corresponding supervisor obtained by generalized mutual exclusion constraints.
(a) (b)In order to design enhanced supervisors to control the periodic mutual exclusion behavior for MESRs, two important concepts,k-derivation process and k-convergence process, are defined as follows.Definition 7.
LetN=({p},{t},F,W) be a Petri net such that p•={t}, t•={p}, and W(p,t)=1, pb≠p be a place, tb≠t be a transition, and k≥1 be an integer. Then, a k-derivation process from p to t, denoted as Nd=({p}∪{pb},{t}∪{tb},Fd,Wd), is a Petri net if t•b={p}, tb•={pb}, p•b=tb, pb•={t}, Wd(p,tb)=1, Wd(tb,pb)=k, and Wd(pb,t)=1. Transition tb is called the derivative transition of Nd. Place pb is called the derivation place of Nd. k is called the derivation coefficient of Nd.In the Petri net depicted in Figure4(a), transition t can fire only once since place p contains only one token. Figure 4(b) shows a three-derivation process from p to t, which is transformed from the Petri net depicted in Figure 4(a). Transition tb is the derivative transition. Place pb is the derivative place and the derivation coefficient is three. Transition t can fire three times after tb fired. The firing time of t is derived from one to three.Figure 4
(a) A Petri net, (b) a three-derivation process, (c) a Petri net, and (d) a three-convergence process.
(a) (b) (c) (d)Definition 8.
LetN=({p},{t},F,W) be a Petri net such that t•={p}, p•=t, and W(t,p)=1, pb≠p be a place, tb≠t be a transition, and k≥1 be an integer. Then, a k-convergence process from t to p, denoted as Nc=p∪pb,t∪tb,Fc,Wc, is a Petri net if p•b={t}, pb•={tb}, t•b=pb, tb•=p, Wct,pb=1, Wc(pb,tb)=k, and Wc(tb,p)=1. Transition tb is called the emergence transition of Nc. Place pb is called the emergence place of Nc. k is called the emergence coefficient of Nc.Ak-convergence process from t to p is an inverse process of a k-derivation process from p to t. In the Petri net depicted in Figure 4(c), each firing of transition t will add a token to place p. Figure 4(d) shows a three-convergence process from t to p, which is transformed from the Petri net depicted in Figure 4(c). Transition tb is the convergence transition. Place pb is the convergence place and the convergence coefficient is three. Only one token is added to place p after transition t fires three times. The firing time of t is converged from three to one.Definition 9.
LetN be an MESR with N=(PK∪PR∪PL∪{ps},T,F). Petri net NM with NM=({p},TMI∪TMO,FM) is called the mutual exclusion supervisor of N if p=ps, TMI=PR•, TMO=P•L, and FM=⋃ti∈TMI{(ps,ti)}∪⋃ti∈TMO{(ti,ps)}.For example, Petri netNM=({ps},{t1,t3}∪{t2,t4},FM) depicted in Figure 3(b) is the mutual exclusion supervisor of the two MESRs depicted in Figures 2(b) and 2(c), respectively.Actually, ak-derivation process is a virtual resource expansion process. It can derive a resource to k(k>0) resources. The common resource can be virtually derived to k virtual resources by the k-derivation process. Similarly, a k-convergence process is a virtual resource constriction process. It can converge k resources to a resource. The k virtual resources can be converged to a common resource by the k-convergence process. Therefore, the methods of k-derivation process and k-convergence process can be used to extend general mutual exclusion supervisors to control periodic mutual exclusion behavior.Definition 10.
LetN be an MESR, NM=({p},TMI∪TMO,FM) be the mutual exclusion supervisor of N with TMI={t1,t2,…,tn} and TMO={t1′,t2′,…,tn′}, PBD={pb1,pb2,…,pbn} and PBC={pb′1,pb′2,…,pb′n} be two sets of places such that pbi≠pbj and pb′i≠pb′j, and TBD={tb1,tb2,…,tbn} and TBC={tb′1,tb′2,…,tb′n} be two sets of transitions such that tbi≠tbj and tb′i≠tb′j, where i≠j, i,j∈{1,2,…,n}, and n≥2. Then, Petri net NS=({p}∪PBD∪PBC,TMI∪TMO∪TBD∪TBC,FS,WS) is called the periodic mutual exclusion supervisor of N if, ∀i∈{1,2,…,n}, Ndi and Nci satisfy the notion that (i)
Petri netNdi=({p}∪{pbi},{ti}∪{tbi},Fdi,Wdi) is a k-derivation process from p to ti;(ii)
Petri netNci=({p}∪{pb′i},{ti′}∪{tb′i},Fci,Wci) is a k-convergence process from ti′ to p.k (k≥1) is the derivation coefficient and convergence coefficient of Ndi and Nci, respectively.The main idea of designing periodic mutual exclusion supervisors is to derive a common resource to several virtual resources by the preliminaryk-derivation processes and these derived virtual resources will be converged to a common resource by the final k-convergence processes. Note that the k-derivation processes and the k-convergence processes come in pairs to derive and converge the common resource, respectively, in the periodic mutual exclusion supervisor of any MESR.Figure5 shows the periodic mutual exclusion supervisor NS=({p}∪PBD∪PBC,TMI∪TMO∪TBD∪TBC,FS,WS) for the two MESRs depicted in Figures 2(b) and 2(c), where p=ps, PBD={pb1,pb3}, PBC={pb2,pb4}, TMI={t1,t3}, TMO={t2,t4}, TBD={tb1,tb3}, and TBC={tb2,tb4}. N1=({ps}∪{pb1},{t1}∪{tb1},F1,W1) is a three-derivation process from ps to t1 and N2=({ps}∪{pb2},{t2}∪{tb2},F2,W2) is a three-convergence process from t2 to ps. Similarly, N3=({ps}∪{pb3},{t3}∪{tb3},F3,W3) is a three-derivation process from ps to t3 and N4=({ps}∪{pb4},{t4}∪{tb4},F4,W4) is a three-convergence process from t4 to ps.Figure 5
The periodic mutual exclusion supervisor of the two MESRs depicted in Figures2(b) and 2(c).For a given MESRN with N=(PK∪PR∪PL∪{ps},T,F), it may contain the behavior of periodicity mutual exclusion. This behavior contains two important features, that is, mutual exclusion feature and periodic feature. The proposed approach to design the periodic mutual exclusion supervisor for MESR N can be decomposed into two main steps as follows:(1)
Extracting the mutual exclusion supervisorNM=({p},TMI∪TMO,FM) from the given MESR N according to Definition 9(2)
Converting the extracted mutual exclusion supervisorNM into the periodic mutual exclusion supervisor NS=({p}∪PBD∪PBC,TMI∪TMO∪TBD∪TBC,FS,WS) by using the paired k-derivation processes and k-convergence processes according to Definition 10.After obtaining the periodic mutual exclusion supervisorNS, the periodic mutual exclusion behavior of MESR N can be controlled by combining the periodic mutual exclusion supervisor NS with the MESR N.Definition 11.
LetN be an MESR with N=(PK∪PR∪PL∪{ps},T,F) and NS=({p}∪PBD∪PBC,TMI∪TMO∪TBD∪TBC,FS,WS) be the periodic mutual exclusion supervisor of N, where TMI⊆PR• and TMO⊆P•R. Petri net NC=(PC,TC,FC,WC) is called the enhanced MESR if PC=PK∪PR∪PL∪{ps}∪{p}∪PBD∪PBC, TC=T∪TBD∪TBC, FC=F∪FS, ∀f∈FSs.t.WC(f)=WS(f), and ∀f′∈Fs.t.WC(f′)=1.In an enhanced MESR, all of its linearity processes will compete for a common resource with periodic mutual exclusion behavior. However, the periodic mutual exclusion behavior is controlled by its periodic mutual exclusion supervisor. One of its all linearity processes can consecutively obtain the common resource withk times from the following k competitions, where k≥1 is an integer. All of its linearity processes will compete for the common resource again after this linearity process releases the common resource.


## 5. Discussion

LetN1,N2,… and Nn with Ni=PKi∪pri∪pli∪psi,Ti,Fi (∀i∈1,2,…,n and n≥2) be n linearity processes with n resources, N=(PK∪PR∪PL∪{ps},T,F) be an MESR that is composed of the n linearity processes, and M0 be the initial marking of N. Then, the permutation [45] of executing the n T-Processes of the n linearity processes in N, denoted as ψ(N), is discussed as follows:(i)
IfN is represented with dispersive pattern, we assume PR={pr}. Then, pr=pr1=pr2=⋯=pn, and pr•=n. In the MESR N, ∀t∈pr•, the linearity process that contains transition t will be executed if t fires. The firing of transition t will take away a token from ps and a token from pr. Therefore, each token contained in place pr may be taken away by one of the n transitions in pr•. Let M0(pr)>0. According to the methods of combinatorics [45], we assume that all tokens contained in pr are taken away by the n transitions. The permutation of executing the n T-Processes of the n linearity processes in N is a full permutation that is(2)ψN=n·n·…·n︷M0pr=nM0pr.(ii)
IfN is represented with parallel or polymeric pattern, we have pri•=1, pri≠prj, i≠j, ∀i,j∈{1,2,…,n}, and ⋂i=1npri•=∅. Then, ∀i∈{1,2,…,n}, all tokens contained in place pri only can be taken away by the transitions contained in pri•. Let M0(pri)>0, where i∈{1,2,…,n}. According to the methods of combinatorics [45], a multiset B={M0(pr1)·N1,M0(pr2)·N2,…,M0(prn)·Nn} is constructed. Therefore, the permutation of executing the n T-Processes of the n linearity processes in N is also a full permutation that is(3)ψN=∑i=1nM0pri!M0pr1!·M0pr2!·…·M0prn!.If the MESRN is supervised by a periodic mutual exclusion supervisor NS with NS=({p}∪PBD∪PBC,TMI∪TMO∪TBD∪TBC,FS,WS), the periodic mutual exclusion behavior will be controlled. Let k be the derivation coefficient and emergence coefficient of the k-derivation processes and the k-convergence processes in the periodic mutual exclusion supervisor NS, respectively, where k≥1 is an integer. In the enhanced MESR NC that is constructed by combining the MESR N with the periodic mutual exclusion supervisor NS, the permutation of executing the n T-Processes of the n linearity processes in NC, denoted as ψ(NC), is discussed as follows:(i)
IfNC is represented with dispersive pattern, we have PR=1 and pr•=n. We assume PR={pr}. In the enhanced MESR NC, ∀t∈pr•, each firing of t will continuously take away k tokens from pr once t obtains the common resource since it will continuously fire k times. Let M0(pr)>0. The tokens contained in place pr can supply the firing of these transitions contained in pr• with ⌈M0(pr)/k⌉ times, where ⌈x⌉ is the ceiling function of x. According to the methods of combinatorics [45], the permutation of executing the n T-Processes of the n linearity processes in NC is(4)ψNC=n·n·…·n︷M0pr/k=nM0pr/k.(ii)
IfN is represented with parallel or polymeric pattern, similarly, we have pri•=1, pri≠prj, i≠j, ∀i,j∈{1,2,…,n}, and ⋂i=1npri•=∅. Then, ∀i∈{1,2,…,n}, all tokens contained in place pri only can be taken away by the transitions contained in pri•. Let M0(pri)>0, where i∈{1,2,…,n}. Then, ∀i∈{1,2,…,n}, all tokens contained in place pri can supply the firing of these transitions contained in pri• with ⌈M0(pri)/k⌉ times, where ⌈x⌉ is the ceiling function of x. According to the methods of combinatorics [45], a multiset B={⌈M0(pr1)/k⌉·N1,⌈M0(pr2)/k⌉·N2,…,⌈M0(prn)/k⌉·Nn} is constructed. Therefore, the permutation of executing the n T-Processes of the n linearity processes in NC is(5)ψNC=∑i=1nM0pri/k!M0pr1/k!·M0pr2/k!·…·M0prn/k!.LetM0(pr)=k·x, where k≥1 and x≥1 are two integers. For the MESR N with dispersive pattern and its enhanced MESR NC, according to (2) and (4), we have(6)ψN=n·n·…·n︷M0pr=nM0pr=nk·x,ψNC=n·n·…·n︷M0pr/k=nM0pr/k=nx.Let, ∀i∈{1,2,…,n}, M0(pri)=k·x, where k≥1 and x≥1 are two integers. For the MESR N with parallel or polymeric pattern and its enhanced MESR NC, according to (3) and (5), we have(7)ψN=∑i=1nM0pri!M0pr1!·M0pr2!·…·M0prn!=n·k·x!n·k·x!,ψNC=∑i=1nM0pri/k!M0pr1/k!·M0pr2/k!·…·M0prn/k!=n·x!n·x!.It is clear that ψ(N)≥ψ(NC), where ψ(N)=ψ(NC) if k=1. This means that many undesirable execution sequences of the n T-Processes in NC are forbidden compared with that in N. The reduced parts are due to the control of the periodic mutual exclusion supervisor NS for NC.


## 6. Example

In real world applications, periodic mutual exclusion behavior widely exists in many discrete event systems, such as game server systems, flexible manufacturing systems, intelligent security inspection systems, and other resource distribution systems. The server systems of many online team games suffer from periodic mutual exclusion problems. Figure6(a) shows a server system of QQ Chinese Poker that is a popular online team game in China. It is constructed with two local servers, called Server 1 and Server 2, that are geographically distributed in different regions. All players need to visit the server system through the Internet and log in the server system. The load balancer of the server system should reasonably distribute all legal players into the two local servers unless they choose Server 1 or Server 2 themselves. The load balancer contains two main distribution rules that are concluded as follows:(1)
Players should join a team if they want to play a game and each team consists of four players. A team can be created only when all four players participate in the same server system. Then, the four players can play a game together.(2)
A player can join only one team at a time.Figure 6
(a) The topology group of the server system of QQ Chinese Poker, (b) the Petri net model of the server system, and (c) the MESR of the server system.
(a) (b) (c)Figure6(b) shows the Petri net model of the server system. Figure 6(c) shows an MESR with dispersive pattern, denoted as N=({p3,p6}∪{p2}∪{p4,p7}∪{ps},T,F), which is a subsystem of the server system. It contains two linearity processes N1=({p3}∪{p2}∪{p4},{t2,t3},F1) and N2=({p6}∪{p2}∪{p7},{t6,t7},F2) that represent the two distribution processes of the two server systems. The two linearity processes share a common resource ps that represents the load balancer. The two T-Processes of the two linearity processes N1 and N2 are t2t3 and t6t7, respectively. The nodes of the MESR depicted in Figure 6(c) are illustrated as follows:(i)
Placep2 is the root of the MESR N. It represents the notion that all players are waiting for the distribution of the load balancer.(ii)
Placep3 (resp., p6) represents the notion that a player is being distributed to Server 1 (resp., Server 2).(iii)
Placep4 (resp., p7) represents the notion that a player has been distributed to Server 1 (resp., Server 2).(iv)
Transitiont2 (resp., t6) represents the notion that the load balancer begins to distribute a player to Server 1 (resp., Server 2).(v)
Transitiont3 (resp., t7) represents the notion that the load balancer finished distributing a player to Server 1 (resp., Server 2).We can assume that there are nine players that are waiting for the distribution of the load balancer in MESRN. This means M0(p2)=9 and M0(ps)=1, where M0 is the initial marking of N. If the periodic mutual exclusion behavior is ignored in the MESR N, according to (2), the permutation of executing the two T-Processes in N is(8)ψN=n·n·…·n︷M0pr=nM0pr=29=512.This means that there are 512 distribution results for the nine players. For example, a distribution result is constituted by the six T-Processt2t3 and three T-Process t6t7. This distribution result represents the notion that six players are distributed into Server 1 and only three players are distributed into Server 2. In this distribution result, only one team can be created and only four players can play game in Server 1 at this time according to the distribution rules. Figure 7(a) shows the firing sequence of the six T-Process t2t3 and three T-Process t6t7. Similarly, Figure 7(b) shows another distribution result that is constituted by three T-Process t2t3 and six T-Process t6t7. In this distribution result, only one team can be created and only four players can play a game in Server 2 at this time. The two distribution results are unreasonable since there are five players that cannot be distributed into a team to play a game. They are only two of the 512 distribution results. There are many similar unreasonable distribution results in the 512 distribution results, which should be controlled by a periodic mutual exclusion supervisor.Figure 7
The firing sequences of (a) six T-Processt2t3 and three T-Process t6t7, (b) three T-Process t2t3 and six T-Process t6t7, (c) five T-Process t2t3 and four T-Process t6t7, and (d) four T-Process t2t3 and five T-Process t6t7.
(a) (b) (c) (d)According to the distribution rules, the MESR has the periodic mutual exclusion behavior. In fact, there is an ideal result that two teams can be created and eight players can play a game at the same time for the nine players. The distribution result depicted in Figure7(c) is an ideal distribution result that is constituted by five T-Process t2t3 and four T-Process t6t7. In this distribution result, eight players can play a game at this time, where a team is created in Server 1 and another team is created in Server 2. Similarly, Figure 7(d) shows also an ideal distribution result that is constituted by four T-Process t2t3 and five T-Process t6t7. In the two distribution results, only one player is waiting to join a team. We can see that the last two distribution results are better than the previous two distribution results. Therefore, this server system is not optimal.In order to optimize this server system, we stipulate that if the load balancer distributes a player into Server 1 (resp., Server 2), the following three players should be also distributed into Server 1 (resp., Server 2). This is a classical periodic mutual exclusion problem. Therefore, a periodic mutual exclusion supervisor can be designed to control the load balancer to reasonably distribute players into Server 1 or Server 2.For the MESRN with N=({p3,p6}∪{p2}∪{p4,p7}∪{ps},T,F), we can extract the mutual exclusion supervisor NM=({ps},{t2,t6}∪{t3,t7},FM) from N according to Definition 9. Figure 8(a) shows the extracted mutual exclusion supervisor NM. Next, we can convert the extracted mutual exclusion supervisor NM into the periodic mutual exclusion supervisor NS=({ps}∪{pb2,pb6}∪{pb3,pb7},{t2,t6}∪{t3,t7}∪{tb2,tb6}∪{tb3,tb7},FS,WS) by using two paired k-derivation processes and k-convergence processes according to Definition 10, where the derivation coefficient and convergence coefficient are four; that is, k=4. Figure 8(b) shows the details of the conversion processes. The conversion processes from ps to t2 and from ps to t6 are two four-derivation processes and the conversion processes from t3 to ps and from t7 to ps are two four-convergence processes. Figure 8(c) shows the converted periodic mutual exclusion supervisor NS.Figure 8
(a) The mutual exclusion supervisorNM, (b) the conversion processes from NM to the periodic mutual exclusion supervisor NS, and (c) the converted periodic mutual exclusion supervisor NS.
(a) (b) (c)After obtaining the periodic mutual exclusion supervisorNS, an enhanced MESR NC with dispersive pattern can be constructed according to Definition 11. Figure 9(a) shows the enhanced MESR NC. Transitions t2 and t6 of the two T-Processes are mutually exclusive. According to (4), the permutation for executing the two T-Processes in NC is(9)ψNC=n·n·…·n︷M0pr/k=nM0pr/k=29/4=23=8.Figure 9
(a) The enhanced MESRNC with dispersive pattern and (b) the complete control system with periodic mutual exclusion supervisor NS.
(a) (b)This means that there are eight distribution results for the nine players in the enhanced MESRNC. It contains the two distribution results depicted in Figures 7(c) and 7(d). Comparing with the general MESR N, about 504 (98.44%) undesirable distribution results are forbidden by the periodic mutual exclusion supervisor NS. The complete control system with periodic mutual exclusion supervisor NS is shown in Figure 9(b). For the nine players in the complete control system, two teams can be created and eight players can play a game. Only one player needs to wait for other players to visit this server.Periodic mutual exclusion problems also exist in flexible manufacturing systems. For example, let a flexible manufacturing system contain a robot, two conveyors, and two machines. The robot is responsible for moving a part from one of the two conveyors to a corresponding machine. The two machines can use four parts to produce a product, respectively. This flexible manufacturing system will suffer from periodic mutual exclusion problems. If there are only nine parts that will be used to produce products, an ideal result is that two products are produced by eight parts. However, it is possible in this flexible manufacturing system that only one product is produced by four of the nine parts. For the other five parts, two parts are distributed to a machine and three parts are distributed to another machine. Therefore, it is feasible to design a periodic mutual exclusion supervisor to control the periodic mutual exclusion behavior of this flexible manufacturing system. Moreover, intelligent security inspection systems also suffer from periodic mutual exclusion problems. An effective measure to solve the heavy congestion problems of public transportation stations is to quickly disperse passengers. Generally, several familiar passengers will adjacently stand in the same queue to go through a security inspection system. They will leave the station after all of them go through the security inspection system. When all passengers stand in several queues to go through a security inspection system, it is a typical periodic mutual exclusion problem. If a passenger goes through the security inspection system, the adjacent passengers who stand in the same queue with the previous one should preferentially go through the security inspection system since they may be familiar with each other. Therefore, the proposed periodic mutual exclusion supervisors can control the periodic mutual exclusion behavior in the security inspection system to improve the congestion problems as far as possible. Furthermore, many resource distribution systems also suffer from periodic mutual exclusion problems. The proposed methodology can be extended to design periodic mutual exclusion supervisors to control these periodic mutual exclusion problems.


## 7. Conclusions

In this paper, periodic mutual exclusion behavior is controlled by the proposed periodic mutual exclusion supervisors in discrete event systems. The proposedk-derivation processes and k-convergence processes can forbid the undesirable execution sequences. The purpose is to optimize the control ability of the designed periodic mutual exclusion supervisors. The example results illustrate that a common resource can be derived to several virtual resources by using a k-derivation process. Similarly, several virtual resources can be converged into a common resource by using a k-convergence process after the executing process releases all virtual resources. The performance of the enhanced MESRs is optimized by using the proposed periodic mutual exclusion supervisors to control the distribution of the common resources. In future work, the performance of the proposed periodic mutual exclusion supervisors should be simulated and verified by developing a simulating tool. The construction method of periodic mutual exclusion supervisors should be optimized by constructing linear constraints based on some extended generalized mutual exclusion constraints.



---

*Source: 1395142-2017-01-30.xml*