文件名称：（WSPR）-P-3的活力：复杂性和决策
文件大小：6.09MB
文件格式：PDF
更新时间：2024-05-29 04:06:58
concurrent systems; Petri nets; liveness;
Petri网是一种形式语言，由于其对资源分配的自然描述和对死锁的精确表征的能力，被广泛应用于与资源分配相关的并发系统中。 具有资源的简单顺序过程的加权系统（（WSPR）-P-3）是Petri网的重要子类，可以建模许多资源分配系统，其中1）多个进程可以并行运行，以及2）每个进程的每个执行步骤。 可以使用同一资源类型的多个单元，但不能使用多种资源类型。 我们首先根据分区问题证明（WSPR）-P-3的活跃性问题是共NP难题。 此外，我们基于两个新概念（结构循环等待（SCW）和阻塞标记（BM））为（WSPR）-P-3的生命力提供了充要条件，即（WSPR）-P-3为如果每个SCW没有BM，则上线。 还提出了充分条件来保证SCW没有BM。 此外，与其他基于虹吸管的系统相比，我们展示了使用SCW分析死锁问题的一些优势，并讨论了SCW与虹吸管之间的关系。 这些结果对于（WSPR）-P-3的死锁预防或避免的进一步研究是有价值的。