Model Checking Approach for Deadlock Detection in an Operating System Process-Resource Graph Using Dynamic Model Generating and Computation Tree Logic Specification

摘要

Deadlock between processes and resources is a serious problem in development of operating system. Multiple methods were invented to deal with deadlock issue. Deadlock detection is one method that allows a deadlock to take place then detects thereafter which processes and resources have caused it. In traditional process-resource graph, we propose an approach to detect a deadlock by implementing model checking technique and Computation Tree Logic (CTL) specification. In this paper, we modified traditional process-resource graph such that the outcome graph satisfied valid model of Kripke structure, which overcame limitations of traditional representation of process-resource graph and still preserved every proposition, correctness, and property of the system. With the modified graph, we designed a CTL specification that verified whether or not there existed a deadlock caused by one or more pairs of process and resource. A Java application was developed to implement the proposed approach such that it was capable of dynamically generating a valid model for any process-resource graph input, dynamically generating CTL formula for specification, and verifying the model with corresponding CTL formula.