|
USENIX 2005 Annual Technical Conference, General Track — Abstract
Pp. 31–44 of the Proceedings
Pulse: A Dynamic Deadlock Detection Mechanism Using Speculative Execution
Tong Li, Carla S. Ellis, Alvin R. Lebeck, and Daniel J. Sorin, Duke University
Abstract
Deadlock can occur wherever multiple processes interact. Most existing static and dynamic deadlock detection tools focus on simple types of deadlock, such as those caused by incorrect ordering of lock acquisitions. In this paper, we propose Pulse, a novel operating system mechanism that dynamically detects various types of deadlock in application programs. Pulse runs as a system daemon. Periodically, it scans the system for processes that have been blocked for a long time (e.g., waiting on I/O events). To determine if these processes are deadlocked, Pulse speculatively executes them ahead to discover their dependences. Based on this information, it constructs a general resource graph and detects deadlock by checking if the graph contains cycles. The ability to look into the future allows Pulse to detect deadlocks involving consumable resources, such as synchronization semaphores and pipes, which no existing tools can detect. We evaluate Pulse by showing that it can detect deadlocks in the classical dining-philosophers and smokers problems. Furthermore, we show that Pulse can detect a well-known deadlock scenario, which is widely referred to as a denial-of-service vulnerability, in the Apache web server. Our results show that Pulse can detect all these deadlocks within three seconds, and it introduces little performance overhead to normal applications that do not deadlock.
- View the full text of this paper in HTML and PDF.
Until April 2006, you will need your USENIX membership identification in order to access the full papers. The Proceedings are published as a collective work, © 2005 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.
|
Need help? Use our Contacts page.
