并发操作系统中基于有色Petri网的死锁检测与避免

1.引言系统的并发性与资源的共享性是并发操作系统的主要特征,其目的是最大限度地提高计算机资源的利用率。死锁是并发操作系统必须解决的一个重要问题。人们试图用不同的方法来解决死锁问题。如Dijkstra提出的有名的死锁避免的“银行家算法”,Coffman等人给出的死锁检测算法。 Petri网模型作为模拟与分析并发、异步、分布式系统的一种有效工具,已被用于解决操作系统中的许多问题。如进程通讯中的生产者/消费者问题、哲学家用餐问题,资源竞

Colored Petri Net-Based Deadlock Detection and Avoidance in Concurrent Operating System

Concurrency and sharing resource of system are the main properties of concurrent operating system. Dead-lock is a important problem to solve in concurrent operating system. As a useful tool of modeling and analyzing con-current, asynchronous and distributed system ,Petri net has been used to solve many problems of operating system.However, most of the models are common Petri net. The common Petri net model is too complex when the scale ofsystem is bigger. This paper models the concurrent system with colored Petri net. It makes the model much simpler.Moreover, the paper gives an algorithm for constructing reachable marking graph of colored Petri net. As a result,the paper gives a sufficient and necessary condition for judging the system deadlock and a method for avoiding the sys-tem deadlock.