S2NPGR2 和S3PGR2的僵局控制

Abstract

當今S3PGR2 的僵局控制受苦於基於致命標記的虹吸管之錯誤活性(liveness)特 徵化。 我們的93 &94 計劃發現非活過渡(transitions) 可能存在，即使沒有致命標記。 那就是在沒有致命標記下，這網模可能是弱活或者在活鎖(livelock)狀況下。這在一種 新liveness 條件下這網模是活的︰ 全部siphons 都必須是max』-controlled。 為了確立 我們在此領域的領先地位，本計劃將以類似於S3PR 的方式，對S3PGR2 藉著增加控制 節點和電弧來作僵局控制。更進一步，李等人提議適合S3PR 的一僵局預防方法。此法 僅對所謂初等虹吸管增加控制節點和電弧，因此大大降低架構的複雜性。 不過，怎樣 把它延長到S3PGR2 和S2CPGR2，迄今是不清楚的，並且沒被研究。 我們提議開拓這 樣的研究。

Current deadlock control approaches for S3PGR2 suffers from incorrect liveness characterization based on the concept of deadly marked siphons (DMS). Our 93&94 proposals discover that nonlive transitions may exist even though there are no DMS. That is the net model may be weakly live or in livelock states under no DMS. It is live under a new liveness condition: all siphons must be max』-controlled. We propose to consolidate our leading position by further working out the deadlock control for S3PGR2 (systems of simple sequential processes with general resources requirement) by adding control nodes and arcs similar to that for S3PR. Next we will extend it to S2CPGR2 ((systems of Synchronized Choice processes with general resources requirement)). Further, Li et. al. proposed a deadlock prevention approach for S3PR to add control nodes and arcs for elementary siphons only greatly reducing the structural complexity. However, it is unclear how to extend it to S3PGR2 and S2CPGR2 and have not been studied so far. We propose to pioneer such study. Abstract: deadlock control prevention live siphons