著者

芦原 評 清水 謙多郎

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.38, no.7, pp.1379-1388, 1997-07-15

参考文献数

9

---

特定の故障箇所が存在しないにもかかわらずシステムの永久停止をもたらすデッドロックは計算機システムにおける重要な問題である.デッドロック検出問題は,排他的に使用可能な資源群とそれを要求するプロセス群からなる一般資源システムの状態グラフ還元問題としてモデル化されるが,使用すると消滅する消費資源を含むシステムでのデッドロック検出問題は一般にはNP完全であり,その重要性にもかかわらず注目されることが少なかった.本論文では,消費資源を含むシステムに一定の制限を加えることで,3つのクラスにおいて多項式時間内でのデッドロック検出が可能であることを示す.Deadlock detection in computer systems can be modeled as a graph reduction problem of general resource systems,which consist of processes,reusable resources and consumable resources.Deadlock detection in reusable resource systems is well known.If all resources in the system are released after use,the problem has polynomial-time solutions.However,the problem is NP-complete in general resource systems with consumable resources,units of which vanish after use.This paper provides three special cases of systmes with consumable resources for which polynomial-time deadlock detection algorithms exist.It is shown that those three factors,(1) consumable resources with non-trivial selections in the allocation of currently available units,(2) processes which request more than one unit and (3) resources which wait for more than one process,are all necessary for the problem to be NP-complete.