Failure Avoidance Based On Discrete Control Theory In Multithreaded Software

With a wide application of software in many top-end fields, large and complex systems, users are concerned about the reliability and security of software. Especially compared to fast development of multicore technology in hardware, the development of software is relatively lagged. It can not exploit the full performance potential of multicore architectures. And multithread mutex and synchronization are more serious. These concurrency bugs can not only decrease efficiency, weaken security, but also harm the interests of users. One important class of failures arising in parallel software is circular-wait deadlock in multithreaded programs. In order to handle deadlocks in multithreaded program easily, we adopt Gadara net, a special class of Petri net, to model multithreaded program. Based on this model framework, the main contents of this paper are as follows:(1) The link between discrete control theory and software failure avoidance is introduced firstly. Then it discribes briefly how to model for multithreaded program and an example is given to illustrate it.(2) After the model phase, we should analyse the net model and get ready for adding monitors. Based on existing controllability conditions, a new modified siphon controllability condition named W-controlled is defined and then a sufficient and necessary condition under which a controlled Gadara net is live is proposed. Examples are illustrated to demonstrate it.(3) From a perspective of threads, suppose a transition of a thread is dead and find a dead-transition loop from which a corresponding minimal siphon can be extracted. Then compute the constraints for the minimal siphon. In order to avoiding redundant control logic, the basic law computing optimal constraints is concluded from specific to general. Besides, a simple algorithm judging the deadlock-freeness of a controlled Gadara net from looking for dead-transition loops is also proposed.(4) It is necessary to check the liveness of the controlled net again after adding monitors according to constraints. Some problems arising in adding monitors are discussed in the paper. For example, if two or more monitors are added, the interaction among monitors may introduce new potential deadlocks. So iterative analysis and control are necessary until no new deadlock can be found in the controlled net.