Abstract: The paper studies deadlock-free behavioral routing algorithm on star graph. First, two minimum deadlock-free routing restrictions on star graph are presented. Then the deadlock-free behavioral routing algorithm based on these two restrictions is presented. Finally, the paper proves that the deadlock-free routing restrictions presented in reference[4] is a specific example of the minimum deadlock-free routing restrictions presented in this paper.

Key words: Star graph; Deadlock; Routing restriction

摘要： 针对星形图中可能产生死锁的问题，对星形图上无死锁的路径算法进行了研究，得到了星形图上的两类最小无死锁受限条件，并给出了一个满足该两类最小无死锁受限条件的无死锁路径算法。同时还证明了文献[4]中提出的两个无死锁受限条件分别只是该文所提出的两类最小无死锁受限条件的一个特例。

关键词: 星形图；死锁；受限条件