一种进程网络中的死锁检测算法  

Deadlock Detection Algorithm for Process Networks

作　　者：方晓[1] 齐德昱[1] 

机构地区：[1]华南理工大学计算机科学与工程学院,广州510006

出　　处：《科学技术与工程》2009年第7期1754-1760,共7页Science Technology and Engineering

基　　金：粤港关键领域重点突破项目(2008A011400010);国家技术创新基金项目(技术转移类)(08C26214411198);广州市创新基金项目(2007V41C0301)等资助

摘　　要：卡恩进程网络(KPN)是一种应用于数据流建模的模型。由于理想的KPN需要无限制容量的用于通信的管道,而这种要求用计算机是无法实现的,所以T.M.Parks提出了一种有界调度策略。然而,这种有界调度又会导致一种理想KPN里不存在的假死锁,即由于写阻塞导致的死锁。针对PN中存在的假死锁,提出一种消息复杂度为O(n)的死锁检测算法DRAP,该算法能找到当前死锁的瓶颈所在,通过增加瓶颈管道的容量来解除死锁。Kahn Process Network（KPN） is a popular model for data streaming applications.Since it is impractical to implement an idealized KPN model with unbounded channel capacities,a bounded scheduling policy has been proposed by T.M.Parks.However,this policy would lead to artificial deadlocks in PN（refer to KPNs with bounded channels as PNs）.Several deadlock detection mechanisms have been proposed to address this problem.An efficient deadlock detection algorithm DRAP is proposed which extends M.Prieto＇s algorithm for PN using message cooperation.It achieves a message complexity of O（n） and finds the bottleneck channel to resolve the artificial deadlock.

关 键 词：死锁检测 进程网络 消息复杂度 

分 类 号：TP393.07[自动化与计算机技术—计算机应用技术]