登入選單

返回Google圖書搜尋

Static Infinite Wait Anomaly Detection in Polynomial Time

Stephen P. MasticolaRutgers University. Department of Computer Science

出版	Rutgers University, Department of Computer Science, Laboratory for Computer Science Research, 1990
URL	http://books.google.com.hk/books?id=G4H1GwAACAAJ&hl=&source=gbs_api

註釋

Abstract: "Infinite wait anomalies associated with a barrier rendezvous model (e.g., Ada) can be divided into two classes: stalls and deadlocks. Although precise static deadlock detection is NP-hard, we present two polynomial time algorithms which use a statically derivable program representation, the sync graph, to certify a useful class of programs free of deadlocks. We also define three conditions on the sync graph necessary for deadlock to occur in a program. We prove that exact checking of these conditions is an NP-hard problem. We also present initial results on the detection and avoidance of stalls."