Deadlock Prediction: Easy and Difficult Cases

摘要: The subject of this paper is the computational complexity deadlock prediction problem for resource allocation. This question “Is avoidable?” i.e. there a feasible sequence in which to allocate all requests?” given current status allocation system. defined by (1) vector held banker, quantity resources presently available allocation, and (2) requests processes: Each process required make termination request form “Give me y I will eventually terminate return z.” Also, each can any number partial “If you can’t give y, then smaller $y'$ be able reach point at halt temporarily $z'$, although still need $y - y' + z'$ terminate.”If are reusable not allowed, ...