Multicore SDK: A Practical and Efficient Deadlock Detector for Real-World Applications

摘要

Traditional deadlock detection algorithms depend on finding cycles in lock graphs created from the application code. Usually, these approaches suffer from scalability and performance problems and cannot handle large industrial strength applications. The main problem for lack of scalability and poor performance is caused by the size of the lock graphs that have to be analyzed. In this paper we show a new two-phase deadlock detection algorithm that is efficient both in terms of memory utilization and time and also very scalable. In the first phase of the algorithm we consider a reduced lock graph based on program locations. We filter out certain locks that cannot participate in a deadlock by analyzing the lock graph created in the first phase. In the second phase of the algorithm we create an even smaller lock graph considering only those locks that were not filtered in the first phase. Finally, the second phase lock graph is analyzed for cycles to find potential deadlocks in the application. We present results from various open-source and commercial software, and also compare the performance of our algorithm with traditional approach.