Runtime deadlock tracking and prevention of concurrent multithreaded programs: A learning-based approach

Abstract

Allocation of shared resources by multithreaded programs faces problem of deadlock. Many solutions have been presented to resolve this problem. Among others, the deadlock prevention is stressed when the deadlock detection and removal are costly. Removing deadlocks, which is carried out by aborting/recovering deadlocked threads, causes the waste of the resources used by the deadlocked threads. In such case, deadlock prevention can lead to avoiding the waste of resources. To this end, the runtime behavior of threads should be monitored in order to predict possible future deadlocks. In such case, the prediction mechanism becomessignificantbecause a properprediction helps us deny the allocation request of a resource by a thread if the allocation leads to a potential deadlock. A method to attain to proper prediction is learning the behavior of threads based on runtime monitoring their past behavior. In fact, based on past behavior of threads, potential deadlocks in their future behavior are verified, and current allocation request of a resource is denied if a future deadlock is predicted. The current study is an extension of our previous work where just deadlock tracking was predicted and no adaptation was suggested. In this study, a composite structure of a recurrent Neural Network (NN) called NARX (to track a potential deadlock)and a Multi-perceptron NN called MLP (to select a suitable action to resolve the potential deadlock) is proposed. Based on the experimental results, the accuracy of the first NN was about 80%, leading to high performance of the second NN, and more than 82% of the real deadlocks were prevented by selecting suitable actions.