Self-Monitoring of Thread Interactions in Multithreaded Systems


March 31, 2005


Tong Li


Duke University


Multithreaded systems provide infrastructure capable of executing multiple software threads in parallel. Such systems range from the conventional multiprocessors to the recent simultaneous multithreading (SMT) and chip-multiprocessor (CMP) systems. Ideally, these systems should dynamically manage themselves such that applications always obtain the best performance. To achieve this goal, the systems must be able to self-monitor the runtime behavior of applications. In this talk, we focus on two aspects of application behavior: deadlock and synchronization.

First, we describe Pulse, an operating system mechanism that dynamically detects deadlock in user applications. Pulse runs as a system daemon. Periodically, it scans the system for processes blocked for a long time (e.g., waiting on locks or 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. If the graph contains a cycle, Pulse reports that a potential deadlock exists. The ability to look into the future allows Pulse to detect deadlocks involving consumable resources, such as synchronization semaphores and pipes, which, to the best of our knowledge, no existing tools can detect.

In the second part of this talk, we describe how to design hardware to dynamically detect spinning synchronization in user applications. Instead of relying on application instrumentation, which places a burden on programmers, we propose hardware that detects when a thread is spinning. Based on this design, we develop (1) hardware performance counters that more accurately reflect application performance than existing counters, and (2) scheduling and power control policies that more efficiently manage resources than existing policies.


Tong Li

Tong Li is a Computer Science Ph.D. candidate at Duke University, where he studies computer microarchitecture, multiprocessor architecture, and operating systems. His thesis focuses on designing hardware and OS support to enable multithreaded systems to self-monitor their runtime behavior. He received his M.S. from the University of Kentucky and B.S. from Northwestern Polytechnic University in China, both in Computer Science.