A Deadlock Prevention Policy for a Class of Multithreaded Software

Abstract

Deadlock is an undesired situation in multithreaded software since it can lead to the stoppage of software. This paper studies the problem of deadlock control of multithreaded software based on Gadara nets, which are well studied for modelling concurrent programs. In particular, an iterative deadlock prevention policy based on siphons is proposed for a class of ordinary Gadara nets where the initial marking of each idle place is one. At each iteration, we compute emptiable siphons containing the smallest number of resource places. Then, bad markings are computed based on these siphons. On the basis of the bad markings, a constraint is constructed that forbids not only bad markings that empty one of the siphons but also some other bad markings. The algorithm is carried out until no emptiable siphon exists in the net. Compared with the existing methods, the resultant net derived from the proposed method is live and maximally permissive with a simpler supervisor. Finally, two examples are provided to illustrate the proposed deadlock prevention policy.

Keywords

• Petri nets
• multithreaded software
• deadlock prevention