L. Gunaseelan, and Richard J. LeBlanc, Jr.
College of Computing
Georgia Institute of Technology
Atlanta, GA 30332-0280
A debugging system itself cannot locate the bugs in a program or fix them for a programmer. A debugger, however, can help the programmer to formulate various fault hypotheses and identify the source of a bug by offering facilities for controlled execution, ability to observe program state, and support for setting breakpoints, watchpoints, etc. In a parallel or distributed system, since a program execution involves multiple processors, it is not possible to start and stop all the processors at a given instant and it is not possible to set global breakpoints on-the-fly without severely interfering with the execution; also, if breakpointing is achieved somehow, the global state presented to the programmer, though consistent, may not be very useful, as it happens to be an arbitrary snapshot of the computation, due to differing execution rates of various processors. System builders, for these reasons, traditionally resort to a post-mortem style of execution replay that provides for controlled reexecution (with the same inputs) and presents meaningful global states at breakpoints. During replay, a programmer can observe program execution at a user-controlled pace. In this paper, we present the design and the implementation of such a replay- oriented debugging tool for a shared object system: a system where applications are modeled as a collection of threads that access and modify a system of shared objects.
Execution replay involves recording the order of the computation events (a partial-order) and using the order to obtain a reproducible, deterministic re-execution. Our event capture scheme maintains only the ``causal-links'' during the original execution and captures such causality in the event-records generated. The replay system time-stamps the execution events post-mortem using vector clocks (indexed by threads), and uses the time-stamps for determining the event precedences during replay. The replay tool can, given a set of breakpoints, determine which will happen first by comparing the vector time-stamps. The post-mortem approach to time-stamping avoids the need to maintain costly vector clocks during the original execution.
The interesting aspect of our replay tool is that it executes the various threads in a demand-driven fashion on a single processor -- an appropriate setting for debugging (e.g. a workstation) -- while providing an exact replay of the original execution. The replay tool need not manage several processors during replay. The replay algorithm is control driven and is based on a previously known time-stamping technique~as space efficient as the instant replay approach~it is more fundamental in that it allows direct determination of event precedences and provides a meaningful, causally related global state at a breakpoint. We discuss this in Section 4. The causal-link maintenance scheme we use is appropriate for a system based on persistent objects, where the objects live longer than the threads of a computation.
Our notion of objects corresponds to encapsulated abstract data types that are globally visible in a parallel/distributed system; data in such objects can be accessed/modified only through welldefined methods. We use the term threads rather than processes to indicate that threads of execution may span object and machine boundaries. Each computation (application) starts as a top-level thread and may spawn multiple threads of control that access and modify a set of shared objects. Applications are expected to conform to this programming model. The model is supported by an extended version of the Eiffel programming language, implemented by the authors~ We have implemented our debugging tool on two different shared object platforms: the Clouds distributed operating system that supports large-grained objects using remote procedure calls (RPCs) on top of a distributed shared memory (DSM) layer, and the KSR-1 shared memory multiprocessor that provides for object sharing by means of a tightly coupled, hardware implementation of DSM. In the Clouds implementation, each object is an address space and thus an object invocation is implemented by a procedure call that involves a change of address space and possibly transfer of the execution of the thread to a new machine. In the KSR implementation, all objects reside in a single shared address space and an invocation is a simple procedure call. However, the programming model and language supported on both platforms are identical. In a previous work~we have discussed the basis for a shared memory view of an RPC-based distributed object system for event-ordering purposes. We discuss this briefly in on 2 of this paper.
One aspect of debugging that is often mentioned but not effectively addressed in the literature is the issue of debugging programs that involve a large number of objects and threads. There have been attempts to provide separate, debugging-specific higher level abstractions to handle such complexity, such as providing event oriented abstractions~oriented abstractions~In this paper, we describe our experiences in tracing and replaying applications that involve a large number of threads and objects. We observe that additional debugging abstractions are not needed in the context of the object/thread model; the abstractions provided by the object/thread model are powerful enough to debug complex applications.
In section 2 of this paper, we describe our object/thread model. In section 3, we define the notion of an enabling event and show how causal links are maintained during the execution. We also show how the execution events can be time-stamped using such causal-link information and used for determining event precedences during replay. In section 4, we describe our replay algorithm and discuss its merits compared to other debugging/replay schemes. We also discuss the implementation and the facilities offered by our replay tool. In section 5, we describe our efforts to trace and replay applications involving a large number of threads and objects. In Section 6, we discuss the abstraction ability of the object model in simplifying the debugging complexity. Section 7 discusses the lessons learned from our work.
The lessons learned from this work are: (1) Using a uni-processor replay tool that faithfully and repeatedly reproduces the original parallel/distributed computation is a useful debugging approach, as it simplifies the task of managing multiple processors. (2) Maintaining the causal-links during the original execution is a cheap way of maintaining the causality and avoids the costly vector-clock maintenance necessary for breakpoint-oriented debugging. With our replay scheme, we are able to provide a causally related global state at a breakpoint. (3) The object/thread approach to distributed system construction simplifies both programming and debugging, as well as eliminates the need for other higher level debugging-oriented abstractions for managing complexity.
To Become a USENIX Member, please see our Membership Information.