Traveler: Trace Navigator applet

This applet illustrates the use of Traveler to record/trace activity of a program and browse/navigate the records along threads and object biographies. Traveler records activities in concurrent Java programs by creating objects recording the activation ordering among activities: for each activity, what subactivities did it start, what activity started next. It can also record the entry ordering (*) of threads entering an object's synchronized regions.

Applet: If you're viewing this page in a Java Plug-in 1.2.2 capable browser (such as, on Microsoft Windows, Communicator 3.00 or later, or IE 3.02 or later, or on Solaris, Communicator 4.05 or later), you should be able to try out Jexa below. (It may take a few minutes to download the plug-in if necessary; starting the plug-in the first time also takes a few dozen seconds. Once the plug-in loads ~210KB of traveler and applet jar files over the network, the applet should run quickly.) If your browser does not yet support a Java 1.2 plug-in, you can point the Sun's JDK appletviewer at the URL of this page to run the applet button:   appletviewer http://www.ai.mit.edu/people/caroma/tools/1999-06-09/JevaESGUIApplet.html
Appletviewer won't display this surrounding text.

Future Factorial

Consider FutureFactorial, which illustrates a simple algorithm that creates a tree of threads as it computes factorial. Factorial of n (i.e., n!) is the product of all the integers from 1 to n, where n is positive integer. Rangeproduct is a recursive divide-and-conquer algorithm for computing the product of the integers from lo to hi: choose mid between lo and hi, compute the rangeproduct of each subrange, and multiply the results. Future factorial computes the two subranges concurrently by starting a thread for each. It uses a future to start the computing thread and manage the result value when it is done. (For more details, see FutureFactorial.java).

Sorry, Java 1.2.2 is needed to run Jexa.
Running factorial(100) creates dozens of concurrent threads, for each recursive call in rangeproduct. Traveler records the activation ordering and displays the recursive algorithm as a nested call trace, where expanding a call (double-click) displays its subactivities. Nested calls by the same thread are indicated with ->; calls in created threads are indicated with >>. You may note that the concurrent recursive calls do not always appear in the same order, as the threads may not reach the point that is recorded in the same order.

To learn more about how the futures work, run FutureFactorial again with the checkbox checked, to record the calls on futures as well. The rangeproduct algorithm may be less clear, but you see how futures get started, and may be able to find instances where the calling thread must wait when it tries to get the value before the computing thread has completed. You may come back to this after learning about navigating biographies next.

Shared Account

In concurrent systems, both the activation order of thread activities and the entry order at synchronized shared actors affect what happens. Traveler provides means to trace and browse both orders and navigate between them.

To see an example of these orders and learn how to navigate between them, consider browsing the trace of the interacting threads of this simulation:

Billee earns 300/week and rents a place at 1000/month.
The landlord, Lordy, directly debits Billee's account monthly.
If the rent doesn't come through, Lordy gets anxious, and calls on bill collectors, who retry weekly.
(For code, see SharedAccountBio.java).
Run the simulation, say at 12 seconds per simulated year.
Sorry, Java 1.2.2 is needed to run Jexa.
When the SharedAccountBio call outline appears: The record shows the main thread sequentially creates an account, then activates two threads for Billee and Lordy. This activation ordering is a partial ordering. Invocations and returns within each thread have a sequential activation order. Threads also activate (start) other threads which proceed concurrently. Partial ordering among concurrent activities can be found through the entry order (*) in the biographies of the actors they share.

A biography of the Account appears, highlighting the selected withdrawal within the entry order. Call targets that appear preceded by '#' are clones to capture the local state of the target as it was at the call when the record was made. Travel across space and back in time to how things happened.

(Note: you may notice in the FutureFactorial applet that calls in a future biography are not preceded by '#', and the futures are not cloned. To allow futures to be cloned to record their states, the applet must be run locally as an application. Anonymous classes, e.g., as used for futures in FutureFactorial, are not public, so their instances cannot be cloned from the applet security sandbox.)

An outline of callers appears, highlighting the selected withdrawal in the activation order via one of the Collectors.


You have now seen how to use Traveler to navigate the activation ordering of concurrent thread activities, to browse the biographies of synchronized shared objects, to navigate from activities in threads to their place in the target biography, and from a call in the biography to its place within the calling thread.

Back to Traveler. Back to Outliner. Feedback to jeva-feedback@ai.mit.edu
 
CarlManning
caroma@ai.mit.edu
This page describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for this research was provided in part by the System Development Foundation, the Advanced Research Projects Agency of the Department of Defense under contracts MDA972-95-1-0018 (North East Regional Consortium Grant) and N66001-95-C-8611 (Computer Aided Education and Training Initiative), and the MIT Department of Electrical Engineering and Computer Science. Support for this research has also been received from IBM, which has generously donated Thinkpad pen computers, and from Microsoft, which has generously donated software.