Petri网不可达标识的判定方法研究及其在死锁检测中的应用

为进行系统死锁检测,对Petri网特定标识的不可达性判定方法进行研究。对基于虹吸管、陷阱、S-不变量、加模S-不变量等结构特性以及基于状态方程解存在性的不可达标识判定方法进行分析,研究了上述方法可以判定的不可达标识之间的相互关系,建立了Petri网不可达标识的分类体系,为更好地进行标识不可达性判定提供了理论依据。分别结合哲学家就餐问题和一个跨组织协同业务流程Petri网模型的死锁状态,检测说明了标识不可达判定方法的应用。

S^3PR网的可达标识集算法

针对具有特定资源库所的S3PR网,提出了一种基于P不变式和严格极小信标的计算可达标识集的新方法.首先计算出由P不变式所确定的不变式标识集,再通过分析严格极小信标中相应库所的托肯数与其界的关系,提出判定标识是否为伪标识的判定定理,并基于判定定理有效求解伪标识集,最终通过剔除不变式标识集中的伪标识来获得可达标识集.实验结果表明,采用所提的方法,可以快速有效地计算出S3PR网中的可达标识集.

基于带标记的并发可达标识图的关键路径的求解方法

将AOE网转换成有色时延Petri网模型,在模型转换过程中同时计算出各位置所对应的事件的最早开始时间,给出了模拟AOE网的有色时延Petri网模型的带标记的并发可达标识图的构建算法;利用并发可达标识图中的标记序列直接得到关键路径并计算出完成所有活动所需的最短时间。实例与仿真实验结果表明,当AOE网中平均存在3个以上的并发活动时,所提方法执行效率优于传统的求解关键路径的算法,并发活动越多,所提算法效率越高。

一类Petri网可达标识数的有效计算方法

S3PR网是Petri网的一个子类,基于组合学提出一种计算S3PR网可达标识数的代数方法.首先,通过组合学计算S3PR网可达标识数的上限。然后,基于资源回路理论,计算包含2个以及3个资源库所的信标,进而找到大部分甚至全部不可达标识的数量.最后,由可达标识数上限减去不可达标识,得到估算的可达标识数.该方法的性能通过例子计算与分析进行了验证.结果显示该方法可以在较短时间内计算出S3PR网的可达标识数,有助于可达图的生成.

S^3PR网可达标识数的一种有效估算方法

提出一种近似计算S3PR网可达标识数的代数方法.首先,基于组合学,可以找到一个S3PR网可达标识数的上限;然后,通过计算包含两个资源库所的信标,找到大部分甚至全部不可达标识的数量.这样,可达标识数上限减去不可达标识的数量就是估算的可达标识数.

基于可达标识列计时Petri网的时态特征及可控性研究

应用时态逻辑提出计时Ｐｅｔｒｉ网的形式化分析方法，基于可达标识列研究受控系统的时态特征及其可控性与控制不变性，给出控制逻辑存在的充要条件，提出了时态公式分解方法，并讨论了禁止状态避免问题。

一种新的混杂Petri网可达性分析方法

讨论混杂Petri网的标识可达性问题.以混杂Petri网模型行为演变为基础提出了一种新的可达性分析方法.根据混杂Petri网模型行为演变划分了混杂Petri网的四种演变类型,给出并证明了每一种演变类型的可达性判定定理,基于这些定理给出了相应的可达性分析算法.另外,与已有的方法进行比较分析,分析结果表明所提出方法的有效性.

随机Petri网在煤矿水害处理流程中的应用研究

水害作为煤矿开采中的主要灾害之一,直接影响井下生产安全。为保障工作人员的生命安全,确保矿井生产的稳定性,提出了用随机Petri网对煤矿水害处理流程进行建模的方法,根据模型的可达标识图同构的马尔科夫链来对库所繁忙率和变迁利用率2个性能指标进行计算分析,为日后对疑似水害的处理流程进行优化提供了新思路。

数据库系统并发控制的扩展有色Petri网方法

加锁与可串行化是并发控制中采取的2个主要措施.两段锁协议(two-phase locking protocol,简称2PL)是解决可串行化调度较好的方法之一,但满足可串行化的调度可能会出现死锁.为此建立了多个事务并发访问数据库的扩展有色Petri网模型,该模型可使并发事务的调度符合两段锁协议.利用该模型的可达标识图,给出了判断满足两段锁协议的调度是否死锁的充分必要条件,并由此构造出并发事务的无死锁的可串行化调度.

随机Petri网可视化软件的设计与实现

针对随机Petri网建模设计与分析的复杂性问题,通过面向对象方法在VisualC++环境下利用MFC开发了可视化的随机Petri网建模和分析工具SPNSim。利用广度优先思想,设计了可达图的生成算法,给出了随机Petri网模型的编辑器,用户可以直观方便地进行随机Petri网编辑,同时还能进行模型分析,得到可达图、稳态概率等随机Petri网特性和系统性能指标。通过对一个实例的建模与分析,结果验证了软件工具SPNSim的正确性和可用性。

T-时延离散Petri网的运行原理及其性质

T-时延离散Petri网(TTDPN)常用来描述与时间有关的离散系统,因而研究其运行原理及性质是必要的。首先给出了变迁可激发的定义及激发规则,然后讨论了T-时延离散Petri网的运行原理和可达标识图的构造方法,最后给出了两个性质。

多处理器调度算法实现及其Petri网建模与仿真

多处理器调度算法在嵌入式实时系统领域中起着关键的作用。根据多处理器的特点,提出一种实时多处理器动态分割并行调度算法SPara。该算法解决了此前多处理器算法,如Myopic、EDPF等仅依据截止期对任务调度产生的问题,实现了增加任务紧迫度限制的调度策略,以及针对执行时间长、截止期紧迫任务的有效调度方法。同时算法结合高级颜色时间Petri网理论进行建模并仿真。测试结果表明,SPara算法在处理器利用率以及调度成功率方面较Myopic等算法有较大提高。

基于增广自控网的路灯故障检测系统

用带禁止/容许弧的自控网构建一类路灯故障检测系统模型,此系统模型适用于描述对按线性编号的故障路灯设备进行检测的过程,能够准确的检测出多个故障路灯。系统模型采用应答方式的工作原理。最后,用可达标识和关联矩阵对模型进行分析、验证。

基于有色Petri网并发进程模型及死锁避免方法

并发进程具有明显的异步并发性,而Petri网是描述异步并发系统的有效工具,但是目前将Petri网用于并发进程控制问题的研究还几乎没有。为此通过引入扩展有色Petri网,为并发进程建立了模型,并给出了避免死锁的有效方法。

并发事务无死锁的可串行化调度的形式化方法

并发控制是多用户数据库管理系统(DBMS)的重要内容之一。该文对其形式化方法进行了研究,建立了符合两段锁协议的扩展有色Petri网模型。利用该模型的可达标识图,给出了判断满足两段锁协议的调度是否死锁的充分必要条件,并由此构造出并发事务的无死锁的可串行化调度。

基于Petri网的数据库系统并发控制活性分析

从数据库系统在时刻t的状态N出发,构造出相应的Petri网模型,进而构造出其可达标识图。通过分析可达标识图,可判断系统是否为死锁状态。若不是死锁状态,系统是否可能出现死锁,什么情况下系统肯定不会出现死锁。最后,给出了数据库系统中事务并发操作的死锁检测方法与避免措施。

主从任务调度的T-时间Petri网

任务调度是一个NP-hard问题,并且是并行与分布式计算必不可少的组成部分.本文首先提出了适合描述异构环境下独立、等尺寸的大规模任务调度问题的T-时间Petri网模型,然后给出了刻画该模型运行的并发可达图的构造算法,最后,在并发可达图中得到了最优调度策略,该策略实现了稳定状态的最优调度,有效地缩短了调度的初始化及清除阶段的时间.

基于Petri网的并发系统活性分析

本文从数据库系统在时刻 t的状态 N出发 ,构造出相应的 Petri网模型 ,进而构造出其可达标识图 .通过分析可达标识图 ,可判断系统是否为死锁状态 .若不是死锁状态 ,系统是否可能出现死锁 ,什么情况下系统肯定不会出现死锁 .最后 。

事故预测分析的PETRI网

对事故预测分析Ｐｅｔｒｉ网模型中的事件、逻辑门表示及其模型构造进行了讨论；文中以一事故为例，对其ｐｅｔｒｉ网、ｐｅｔｒｉ网的可达标识图制作做了较为详细的介绍。在此基础上，分析可达标识图，求出导致事故发生的最小割集和最小径集，为控制事故的措施选择提供了可靠的理论依据。该方法表现直观，为事故的预测分析开辟了一条新的途径。

理发师问题的Petri网模型

讨论在操作系统中研究的关于进程间通信(IPC)的一个著名的问题:睡眠的理发师问题。给出这个问题的Petri网模型和这个Petri网的可达标识图性质。