随着计算、通信以及传感技术的飞速发展，出现了许多新的动态系统，如计算机与通讯网络系统、自动制造系统、分布式数据库系统等。这些动态系统都存在对有限资源分配以及竞争的问题，所以可将他们抽象为资源分配系统。
图论[1]、自动机和Petri 网是研究资源分配系统及死锁与控制系统的主要工具[2, 3]。图论的方法简单直观，适合于描述任务和资源之间的交互关系。自动机是有限状态机( FSM )的数学模型，他的一个重要特点是能与外界交换信息，并根据交换得来的信息改变自己的动作，即改变自己的功能，甚至改变自己的结构，以适应外界的变化。也就是说在一定程度上具有类似于生命有机体那样的适应环境变化的能力。而Petri网是对离散并行系统的数学表示，适合于描述异步的、并发的计算机系统模型。不同的工具对于资源系统的描述并不相同，但都反应与揭露了物理系统本身的本质特性，使我们可以通过对模型的分析和研究，把握系统的本质，以便对系统进行控制。所以为资源分配系统挑选合适的建模方式成为工作的前提。而面对纷杂的资源分配系统我想以自动制造系统( AMS )为例来进行建模与死锁预防的研究。
制造系统建模与分析方法主要包括自动机( automaton )理论、状态流图( state chart )、图论( graph theory )、进程代数( process algebra )以及时序逻辑( temporal logic )等。Castillo等研究了不同形式化方法用于自动制造系统建模与分析的优缺点[4].实践证明Petri网是制造系统设计方法的最好选择。一般认为，Petri网用于制造系统的设计具有以下优势[5, 6]：1)可简单准确地表示系统中的并发、资源共享、冲突、相互抑制以及非确定性等特征；2)可以使用自顶向下和自底向上的设计方法，使系统具有不同的抽象层次成为可能；3)从Petri网模型可以直接生成控制代码；4)良好定义的语义能为系统设计提供定性和定量的分析；5)图形界面可给出系统的直观视图；6)Petri网可用于系统设计的各个阶段，从系统建模、分析、仿真、确认、性能评价、到调度、控制和监视过程。所以我打算用Petri网建模，或者说Petri网更适合自动制造系统( AMS )。
由于存在有限资源的共享与竞争，自动制造系统在运行过程往往容易产生死锁( deadlock )。死锁意味着整个或部分系统的停顿，会导致生产率下降，甚至可能造成重大的财产损失和灾难性后果。所以对死锁的描述、分析、控制和求解对系统正常运行起至关重要的作用。
死锁问题的研究起源于操作系统中的资源分配问题[7]。尽管人们已对操作系统进行了深入的研究，但是因为物理特性的差异，有些方法并不能直接应用于制造系统中。Coffman等给出了系统死锁的四个必要（非充分）条件[8]。
- 相互抑制( mutual exclusion )：一个资源每次只能被一个进程使用。
- 持有并等待( hold and wait )：持有资源的进程允许申请其他资源。
- 非剥夺条件( no preemption )：除非资源被释放，否则一个资源不允许被强行剥夺。
- 循环等待( circular wait )：若干进程形成了一个进程链，该进程链中的每一个成员等
待着他的下一个进程持有资源。
研究表明，前三个条件是由系统和资源的物理特性决定的，也就是说他们不会随着时间而变化。而第四个条件却可因资源的请求、分配、与释放随时间而变化。只要发生死锁，上述四个条件必然发生。反之，只要一个条件不满足，系统也不会发生死锁，所以对于死锁的处理，通过破坏发生死锁的四个必要条件，也是一个容易理解的做法。
主要用于处理自动制造系统死锁的工具，有图论、自动机和Petri网。有四种死锁解决方法：1)鸵鸟算法( ostrich algorithm )；2)死锁的检测与恢复( deadlock detection and recovery )；3)死锁避免( deadlock avoidance )；4)死锁预防( deadlock prevention )。我主要研究的是死锁预防。因为图论和自动机本身的特性，对于死锁预防( deadlock prevention )并没有深入的研究，而对其他解决方法有着全面的研究。所以我以Petri网为工具进行死锁预防的研究。
基于Petri网的死锁预防是一种静态的方法，使用离线计算的机制来控制资源的请求。一般来说，死锁预防策略的缺点主要是保守性，他使系统的生产率和关键资源的利用率极低。以下我列举了一些利用Petri网设计自动制造系统死锁预防策略的例子。这些方法都是在实践中不断完善而改进的。
早期用Petri网进行死锁预防和系统的Petri网构建密切相关。如，Zhou和DiCesare研究了具有共享资源自助制造系统的建模问题，进而提出了并行抑制和顺序相互抑制的概念[9]。将系统的行为性质表达为B-place和C-place的初始标识关系的死锁预防方法因为其保守性而大大降低了系统的生产率。随后，Ezpeleta等提出了一种基于控制库所( monitor )的活性Petri网控制器的设计方法[10]。他们提出了一种Petri网的子网S3PR (system of simple sequential processes with resources )，提出了一种添加控制库所的方法，最终得到活性的Petri网控制器。这种方法的优点在于成功的分离了系统模型和控制器，使得他们有了清晰的界限。然而这样的死锁控制方法也有三个方面的不足：1)行为许可性；2)计算复杂性；3)结构复杂性。之后的许多工作，都是围绕如何克服上述三种不足而进行。
