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

摘要

卡恩进程网络(KPN)是一种应用于数据流建模的模型。由于理想的KPN需要无限制容量的用于通信的管道,而这种要求用计算机是无法实现的,所以T.M.Parks提出了一种有界调度策略。然而,这种有界调度又会导致一种理想KPN里不存在的假死锁,即由于写阻塞导致的死锁。本文针对PN中存在的假死锁,提出一种消息复杂度为O(n)的死锁检测算法DRAP,该算法能找到当前死锁的瓶颈所在,通过增加瓶颈管道的容量来解除死锁。