Abstract: Consider a multi-threaded application that occasionally fails due to non-determinism. Using the DejaVu capture/replay tool, it is possible to record the thread schedule and replay the application in a deterministic way. By systematically narrowing down the difference between a thread schedule that makes the program pass and another schedule that makes the program fail, the Delta Debugging approach can pinpoint the error location automatically---namely, the location(s) where a thread switch causes the program to fail. In a case study, Delta Debugging isolated the failure-inducing schedule difference from 3.8 billion differences in only 50 tests.

Download: PDF file (438K)

Efficient and Precise Datarace Detection for Multithreaded Object-Oriented Programs

Authors: J.-D. Choi, K. Lee, A. Loginov, R. O'Callahan, V. Sarkar, and M. Sridharan

Conference: ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation (PLDI), Berlin, Germany, June 17 - 19, 2002

Abstract: We present a novel approach to dynamic datarace detection for multithreaded object-oriented programs. Past techniques for on-the-fly dataracedetection either sacrificedprecision for performance, leading to many false positive datarace reports, or maintained precision but incurred significant overheads in the range of 3X to 30X. In contrast, our approach results in very few false positives and runtime overhead in the 13% to 42% range, making it both efficient and precise. This performance improvement is the result of a unique combination of complementary static and dynamic optimization techniques.

Download: PDF file (117K)

Record/Replay in the Presence of Benign Data Races

Authors: M. Christiaens, J.-D. Choi, M. Ronsse, and K. De Bosschere

Conference: International Conference on Parallel and Dstributed Processing Techniques and Applications (PDPTA'02)

Abstract: In this article we present our experience with the integration of record/replay in the Jalapeno virtual machine. The goal of record/replay is to be able to faithfully replay an application. Previous work in Jalapeno focused on the replay of Java applications on uni-processors. Here we describe additional work done to obtain replay with low intrusion on multi-processor systems by doing `ordering based' record/replay. During ordering based record/replay we only record the order of the synchronization operations performed. A prerequisite of this technique is that there are no data races present in the application that is to be replayed. However, we found that Jalape~ no contains many benign data races. A major contribution of this article is that we show how one can circumvent these data races and still perform a meaningful replay of the application.

Download: PDF file (180K)

Static Datarace Analysis for Multithreaded Object-Oriented Programs

Authors: J.-D. Choi, A. Loginov, and V. Sarkar

Conference: IBM Research Report 22146, 2001.

Abstract: This paper presents a novel analysis framework and algorithm for statically identifying dataraces in multithreaded object-oriented programs. The framework shows how datarace analysis can be formulated as a conjuction of interthread control flow analysis and points-to analysis of thread objects, synchronization objects and access objects. This formulation can be used to identify a spectrum of dataraces depending on the precision of points-to and control flow information received as input. The framework can be used for datarace analysis of programs written in any multithreaded object-oriented language that supports creation of thread objects, monitor-like synchronization of threads via object-based locking, and global memory accesses via static and instrance fields. Our datarace analysis algorithm operates interprocedurally over the interthread call graph (ICG) and extracts ordering information by examining the thread creation sites and the object references used for monitor synchronization. The algroithm computes two classes of data races -- potential (no false negatives) and definite (no false positives). We present experimental results obtained from a preliminary implementatoin of the datarace analysis algorithm in the Jalapeno JVM. The results show that our preliminary implementation can be effective in narrowing down the set of statement pairs that may participate in a datarace. This information could be used in a static analysis tool, or as a filter for reducing the overhead of dynamic datarace detection.

Download: PDF file (371K)

A Debugging Platform for Java Server Applications

Authors: B. Alpern, J.-D. Choi, T. Ngo, M. Sridharan, J. Vlissides, and H.-G. Yook

Conference: IBM Research Report 22036

Abstract: Development of multithreaded server applications is particularly tricky because of their nondeterministic execution behavior, availability requirements, and extended running times. New tools are needed to help programmers understand server behavior. Key to the realization of such tools is the ability to repeat nondeterministic execution behavior. This paper presents a platform for understanding and debugging Java server applications. DejaVu supports deterministic replay of nondetenninistic, multithreaded Java programs running on the Jalapeno virtual machine on unipmcessors. Jalapeno is written in Java, and its optimizing compiler combines application, virtual machine, and DejaVu instrumentation code into unified machine-code sequences. Such integration compounds the difficulty of replaying nondeterministic behavior accurately and with minimal interference from the instrumentation. DejaVu ensures deterministic replay through symmetric insrrumenration-side-effect-preserving instrumentation in both record and replay modes-and remore reflection, which exposes the state of an application without perturbing it.

Download: PDF file (1.1M)

Authors: J.-D. Choi, B. Alpern, T. Ngo, M. Sridharan, and J. Vlissides

Conference: 15th International Parallel and Distributed Processing Symposium (IPDPS'01), San Fransisco, CA, April 23-27, 2001.

Abstract: Development of multithreaded applications is particularly tricky because of their non-deterministic execution behaviors. Tools that support the debugging and performance tuning of such applications are needed. Key to the construction of such tools is the ability to repeat the non-deterministic execution behavior of a multithreaded application. A clean separation between the application and the system that runs it facilitates supporting that ability. This paper presents a platform for constructing such tools in a context in which any separation between the application and the underlying system (and between both and the platform's own instrumentation code) has been obscured.

DejaVu supports deterministic replay of non-deterministic executions of multithreaded Java programs on the Jalapeno virtual machine (running on a uniprocessor). Jalapeno is written in Java and its optimizing compiler regularly integrates application, virtual machine, and DejaVu instrumentation code into unified machine-code sequences. DejaVu ensures deterministic replay through symmetric instrumentation --- side-effect identical instrumentation in both record and replay modes --- and remote reflection which exposes the state of an application without perturbing it.

Download: PS file (139K)

Authors: B. Alpern, J.-D. Choi, T. Ngo, and M. Sridharan

Conference: 2000  ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'00), Minneapolis, Minnesota, October 15-19, 2000.

Abstract: Java applications, in particular server applications, are often multithreaded.  Their execution can be non-deterministic, making them difficult to understand and debug.  This paper presents a platform for analyzing interleaved program execution, comprising the Jalapeno VM (Virtual Machine), the replay capabilities of  DejaVu (Deterministic Java Replay Utility), and the perturbation-free reflection afforded by remote reflection. A debugger demonstrates the power and novel characteristics of the platform.

DejaVu supports understanding and debugging multithreaded Java applications through deterministic replay of non-deterministic execution. DejaVu replays the execution of the entire Jalapeno VM, including its thread and garbage collector subsystems. The debugger must not alter the execution behavior of the VM during replay, which is especially challenging on this platform because all components---from the Jalapeno VM to DejaVu and the debugger---are written in Java.  The key is remote reflection, which exposes program state by invoking the VM's internal reflection methods without perturbing the VM or the application.

Download: PDF file (90K)
Screen Shots.

A Perturbation-Free Replay Platform for Cross-Optimized Multithreaded Applications

Authors: B. Alpern, J.-D. Choi, T. Ngo, M. Sridharan, and J. Vlissides

Conference: IBM Research Report 21864

Abstract: Java applications, in particular server applications, are often multithreaded.  Their execution can be non-deterministic, making them difficult to understand and debug.  This paper presents a platform for analyzing interleaved program execution, comprising the Jalapeno VM, the replay capabilities of DejaVu, and the perturbation-free reflection afforded by remote reflection. A debugger demonstrates the power and novel characteristics of the platform.

DejaVu supports understanding and debugging multithreaded Java applications through deterministic replay of non-deterministic execution. DejaVu replays the execution of the entire Jalapenpo VM, including its thread and garbage collector subsystems. The debugger must not alter the execution behavior of the VM during replay, which is especially challenging on this platform because all components---from the Jalapeno VM to DejaVu and the debugger---are written in Java.  DejaVu ensures deterministic replay through symmetric instrumentation and remote reflection, which exposes the state of an application without perturbing it

Download: PDF file (649K)

Debugging by Remote Reflection

Authors: T. Ngo and J. Barton

Conference: Euro-Par 2000, Munich, Germany, August 27-September 1.

Abstract : Reflection in an object-oriented system allows the structure of objects and
classes to be queried at run-time and for data inside objects to be read and written using
this structure. Reflection allows ``meta-object'' programming, including, for example, program debugging. Remote Reflection allows objects in one address space to reflect upon objects in a different address space. When applied to a program debugger, remote
reflection makes available the full power of object-oriented reflection even when the object being examined is within a malfunctioning or terminated system. We have implemented remote reflection as an extension to an interpreter to create a very effective debugger for
Jalapeno, a Java Virtual Machine written in Java.

Download: PostScript file (270K)

Deterministic Replay of Distributed Java Applications

Authors: R. Konuru, H. Srinivasan, and J.-D. Choi

Conference: 14th International Parallel & Distributed Processing Symposium (IPDPS 00), Cancun, Mexico, May 1-5, 2000

Abstract: Execution behavior of a Java application can be non-deterministic due to concurrent threads of execution, thread scheduling, and variable network delays. This non-determinism in Java makes the understanding and debugging of multi-threaded distributed Java applications a difficult and a laborious process. It is well accepted that providing deterministic replay of application execution is a key step towards programmer productivity and program understanding. Towards this goal, we developed a replay framework based on logical thread schedules and logical intervals. An application of this framework was previously published in the context of  a system called DejaVu, that provides deterministic replay of  multi-threaded Java programs on a single Java Virtual Machine(JVM). In contrast, this paper focuses on distributed DejaVu that provides deterministic replay of distributed Java applications running on multiple JVMs. We describe the issues and present the design, implementation and preliminary performance results of  distributed DejaVu that supports both multi-threaded and distributed Java applications.

Download: poscript file (224K) 

Deterministic Replay of Java Multithreaded Applications

Authors:   J.-D. Choi and  H. Srinivasan

Conference: 1998  ACM SIGMETRICS SPDT98, Oregon, August 3-4

Abstract: Threads and concurrency constructs in Java introduce non-determinism to a program's execution, which makes it hard to understand and analyze the execution behavior. Non-determinism in execution behavior also makes it impossible to use execution replay for debugging, performance monitoring, or visualization. This paper discusses a record/replay tool for Java, DejaVu, that provides deterministic replay of a  program's execution. In particular, this paper describes the idea of the logical thread schedule, which makes DejaVu efficient and independent of the underlying thread scheduler. The paper also discusses how to handle the various Java synchronization operations for record and replay. DejaVu has been implemented by modifying the  Sun Microsystems' Java Virtual Machine.  

Download:  poscript file (278K) 

Java and all Java-based trademarks and logos are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries.