CHAPTER 3
RELATED WORK
This chapter describes the tools found in the literature for debugging and monitoring concurrent programs. They were selected for discussion because they represent, in terms of their capacity, the approach used by most of the related research. Some of them are also related to the research issue of helping novice concurrent programmers to understand concurrency. A number of debuggers and monitors for concurrent programs are presented first. Many of these systems employ the concepts used in sequential debugging. That is, these tools attempt to reduce the data and allow the extraction of useful information. Departing from this approach is the idea of providing the user with both explanations on possibly faulty constructs and guidance for correcting the faults. The last section of this chapter describes one such system which is used for debugging sequential programs.
Steven M. German was among the first to work with algorithms for monitoring Ada tasks [Germ84]. His work focused on a deadlock monitoring algorithm for Ada tasking programs. The source program is transformed. A new task, named monitor, is attached to the program together with modifications in the other tasks so they communicate to the monitor their tasking activities. The resulting program allows the monitoring of arbitrary task types, conditional entry calls, selective wait and timed entry calls. Terminate statements used in selective wait constructs and exceptions are not transformed by Greman's algorithms. Luckham and Helmbold implemented this work as described below.
The work of David Luckham and David Helmbolt work focused on task deadness errors [Luck85]. MON, a prototype monitor and pre-processor, was designed and implemented to detect deadness errors, making it an intrusive monitor. According to Luckham and Helmbolt,
Task sequencing errors result when a program's tasks interact in a different order than anticipated. Deadness is simply the inability of some or all of the active tasks to continue, and is perhaps the most evident kind of error.
Luckham and Helmbolt concluded that
Because of the capricious nature of tasking errors (now you see them, now you don't), debuggers in the classical sense of "providers of information upon request" are inadequate. Detection of errors, as well as the gathering of information, must be automated.
The user is allowed to print snapshots of the program's state, trace task interactions and single-step. To demonstrate MON's output, Luckham and Helmbolt used an automated gas station. The basic components of their gas station were: one operator, a set of pumps and a set of customers. Each of these components were programmed as Ada tasks. Figure 3.1 shows the declaration of task specifications for these components.
TASK Operator IS
ENTRY Pre_Pay(Amount, Pump_Id, Customer_Id : IN Integer);
ENTRY Charge(Amount : IN Integer; Pump_Id : Integer);
END Operator;
TASK TYPE Pump IS
ENTRY Activate(Limit : IN Integer);
ENTRY Start_Pumping;
ENTRY Finish_Pumping(Amount_Charged : OUT Integer);
END Pump;
TASK TYPE Customer IS
ENTRY Change(Amount : IN Integer);
END Customer;
Figure 3.1 - Tasks Specifications for the Gas Station
The task operator contains two entries: Pre_pay and Charge. These entries contain formal parameters, all of which have call-by-value mode. These entries are used to establish communication with tasks of type Pump and Customer. Task Pump, which is defined as a type, contains three entries. The entry Start_Pumping does not contain any parameter. The entry Finish_Pumping contains one parameter, with call-by-result mode. Task Customer contains only one entry, Change. The following objects were defined and declared by Luckham and Helmbolt:
TYPE Collection_Of_Pumps IS ARRAY(1..N) OF Pump;
TYPE Collection_Of_Customers IS ARRAY(1..N') OF Customer;
Pumps : Collection_Of_Pumps;
Customers : Collection_Of_Customers;
The Operator task works as follows: its body frame is enclosed by an infinite loop; within this loop two accept statements (for entries Pre_pay and Charge) are specified through a selective wait construct. The code to the Pre_Pay accept issues the entry call Pumps(Pump_Id).Activate(Amount) which allows the task Pump to establish a rendezvous with Customers(Customer_Number) at entry Start_Pumping. It also associates a customer with a pump. The code for the Charge accept retrieves the customer's charges for a pump and issues entry calls to task Customers at entry Change and then to task Pumps at entry Activate. In other words, the operator task is programmed to receive pre-payments, which releases a pump for a customer and also returns to the customer any change due.
Any task of the Pump type works as follows: it contains three accept statements, one after the other. These accept statements are enclosed by an infinite loop. The first accept statement, for entry Activate, receives a signal from the task operator, meaning that the pump is now free and a pre-payment (Limit) has been received from a customer. It then waits for the customer that selected the pump to start pumping. This is accomplished when the rendezvous with the matching Customers task is completed (entry Start_Pumping). The last accept statement for entry Finish_Pumping calculates how much gas was consumed and communicates the charge to the operator task.
Any task of the Customer type works as follows: an entry call to Operator.Pre_pay is issued to tell the operator the amount pre-paid (AP), the pump (P) selected and the customer identification. It then waits until the pump selected is ready (the entry call Pumps(P).Start_Pumping is completed). After the desired quantity of gas has been "pumped," it lets Pump(P) know this by issuing the entry call Pumps(P).Finish_Pumping(A). After this entry call has been completed, the customer knows that the amount due is given by (AP - A). The task will then wait (through the ACCEPT Change statement) for the operator to return any change that may be due.
Figures 3.2, 3.3, and 3.4 show the task bodies for tasks Operator, Pump, and Customer, respectively.
WITH TTY_IO, Computer, Random; USE TTY_IO;
TASK BODY Operator IS
Amount_Paid,
Customer_Number : Integer;
BEGIN
LOOP
SELECT
ACCEPT Pre_Pay(Amount, Pump_Id, Customer_Id : IN Integer) DO
-- if no previous customer is
-- waiting,
-- activate this pump.
IF Computer.Empty_Queue(Pump_Id) THEN
Pumps(Pump_Id).Activate(Amount);
END IF;
-- enter a record of
-- prepayment; records for
-- each pump are serviced
-- in FIFO order.
Computer.Enter(Pump_Id,Amount,Customer_Id);
END Pre_Pay;
OR
ACCEPT Charge(Amount, Pump_Id : IN Integer) DO
-- retrieve current
-- record for this pump
--(i.e., the caller).
Computer.Retrieve(Pump_Id, Amount_paid,
Customer_Number);
-- give change to the
-- customer.
Customers(Customer_Number).Change(Amount_Paid
- Amount);
-- if another customer is
-- waiting for this
-- pump, activate it.
IF NOT Computer_Empty_Queue(Pump_Id) THEN
Pumps(Pump_Id).Activate
(Computer.Top_Amount(Pump_id));
END IF;
END Charge;
END SELECT;
END LOOP;
END Operator;
Figure 3.2 - Operator Task Body
TASK BODY Pump IS
My_Number : Integer;
Current_Charges : Integer;
Amount_Limit : Integer;
BEGIN
... -- My_Number is initialized to a unique pump id.
LOOP
ACCEPT Activate(Limit : IN Integer) DO
Amount_Limit := Limit;
END Activate;
ACCEPT Start_Pumping;
ACCEPT Finish_Pumping(Amount_Charged : OUT Integer) DO
-- compute actual charge as a random number less
-- than the limit.
Current_Charges := Random.Get_Charges(Amount_Limit);
Amount_Charged := Current_Charges;
Operator.Charge(Current_Charges, My_Number);
END Finish_Pumping;
END LOOP;
END Pump;
Figure 3.3 - Pump Task Body
-- Each customer task will model a sequence of customers
-- entering and leaving the gas station;
TASK BODY Customer IS
My_Number : Integer;
My_Money : Integer;
Pump_Number : Integer;
Amount_Pumped : Integer;
BEGIN
... -- My_Number is initialized to a unique customer id.
LOOP
-- Randomly decide amount of gas needed and
-- choice of pump.
Random.Drive_In(My_Money,Pump_Number);
Operator.Pre_pay(My_Money, Pump_Number, My_Number);
Pumps(Pump_Number).Start_Pumping;
Pumps(Pump_Number).Finish_Pumping(Amount_Pumped);
ACCEPT Change(Amount : IN Integer) DO
...
-- compare Amount with My_Money less the
-- Amount_Pumped; output a complaint to the
-- programmer's console if not equal.
END Change;
END LOOP;
END Customer;
Figure 3.4 - Customer Task Body
MON will first detect a circular deadlock by reporting:
**MON** A circular deadlock has occurred.
task Operator calls Customers.Change,
task Customers calls Pumps.Finish_Pumping, and
task Pumps calls task Operator.Charge.
MON will conclude this report with the message:
**MON** thus forming a closed loop of tasks.
Following this stage, MON will issue the following message:
**MON** GLOBAL DEADLOCK HAS BEEN DETECTED
and a representation of the dead state is output, as shown in Figure 3.5. The number enclosed in the parenthesis specifies the entry's queue length. The entry call Operator.Charge within task Pumps(13) will cause, within entry Charge, the entry call Customers(2).Change. The accept statement for entry Change can only be executed after the rendezvous involving task Customers and task Pumps(13) at entry Finish_Pumping is completed. The circular deadlock was identified by MON, which then presented the information that is shown in Figure 3.5.
Figure 3.5 - MON's Snapshot
DbxTool [Adam86] is an interactive debugger for the C, Pascal, and FORTRAN programming languages which runs on the Sun Operating System Kernel. Several processes may be debugged, each with its own debugging window. Each window is divided into five sub-windows: status, source, buttons, command, and display. This debugger provides a comprehensive view of the state of the program being executed. Figure 3.6 shows a DbxTool screen dump. The user, operating a mouse, can select which process to debug, and activate the buttons within the button window, as well as set breakpoints within the source window. The buttons window allows the selection of following commands: print, next, step, stop at, cont, stop in, and redo.
The command window provides another interface with the user. Figure 3.7 shows an instance of a debugging section. The command toolenv displines 7 caused the size of the display window to be set to 7. The command display exam displayed the contents of the structure exam. The command cont was used to make the execution resume until a breakpoint was found. The command window showed the contents of the exam structure (through the print exam command) one iteration before the same structure contents is displayed within the display window.
Figure 3.6 - DbxTool Screen Dump
DbxTool is an example of a low-level debugger. The user is responsible for the analysis of the program's behavior. It allows several processes to be debugged individually. There are no facilities to show process interactions.
3.7 - DbxTool Debugging Section
LeDoux and Parker used a trace database model for debugging concurrent Ada programs [LeDo85]. A prototype debugger, YODA, was implemented in Prolog. YODA contains a pre-processor that inserts diagnostic output statements into a copy of the source program. At run-time, these statements activate the YODA monitor that updates the trace database. The monitor is enclosed in an Ada package. A symbol table is also produced. After the execution of the program, trace queries can be expressed in Prolog. According to the authors, YODA can be used as an "aid in debugging a restricted class of runtime errors associated with concurrency [LeDo85]." The debugger focuses on concurrency, exception handling and dynamic storage allocation. Static and dynamic program information is stored in the database. The preprocessor also generates a symbol table. Each symbol table entry has the following Prolog definition:
symbol(Name,Declarative_Context,Usage).
An entry stores the name of an identifier, the identifier's declarative context, and the identifier's base type. Figure 3.8 shows a program example which is used to demonstrate YODA's output for a shared data problem.
Figure 3.9 shows the symbol table contents for the program presented in Figure 3.8. For instance, the second symbol table entry (symbol(e,[t1,main],entry_name).) represents:
-the identifier e;
-e declared within t1, which is within main; and
-the base type of e, which is entry_name (meaning an entry).
The trace database will contain the program's history regarding variable declaration and use, task synchronization, and change in task status. The structures that represent these events, in Prolog notation, are shown in Figure 3.10.
At run-time, the monitor updates the trace database. A global clock is also used. Each update within the database causes the clock to advance by one unit. Figure 3.11 shows the trace database originated from the program shown in Figure 3.8. Each record within the trace database has the following structure:
<event> ( <description> , Timestamp ).
WITH Text_IO; USE Text_IO;
PROCEDURE Main IS
X : Integer := 0;
TASK T1 IS
ENTRY E(A_While : Duration);
END T1;
TASK T2 IS
ENTRY E;
END T2;
TASK C1;
TASK C2;
TASK BODY T1 IS
BEGIN
LOOP
SELECT
ACCEPT E(A_While : Duration) DO
IF X < 1 THEN
DELAY A_While;
X := X + 1;
Put_Line("X = " & Integer'IMAGE(X));
END IF;
END E;
OR
TERMINATE;
END SELECT;
END LOOP;
END T1;
TASK BODY T2 IS
BEGIN
ACCEPT E DO
IF X < 1 THEN
X := X + 1;
Put_Line("X = " & Integer'IMAGE(X));
END IF;
END E;
END T2;
TASK BODY C1 IS
BEGIN
T1.E(50.0);
END C1;
TASK BODY C2 IS
BEGIN
T2.E;
END C2;
BEGIN
NULL;
END Main;
Figure 3.8 - Ada Program with Shared Data Problem
symbol(main,[].subprogram_name).
symbol(e,[t1,main],entry_name).
symbol(c1,[main],object_name(task_type,anonymous,[main]).
symbol(a_while,[e,loop_name1,t1,main],object_name
(real_type_definition,duration,[])).
symbol(c2,[main],object_name(task_type,anonymous,[main])).
symbol(e,[t2,main],entry_name).
symbol(loop_name1,[t1,main],loop_name).
symbol(t1,[main],object_name(task_type,anonymous,[main])).
symbol(t2,[main],object_name(task_type,anonymous,[main])).
symbol(x,[main],object_name(integer_type_definition,integer,[])).
Figure 3.9 - YODA's Generated Symbol Table
entry_called(Caller,Callee,Entry,Time).
call_canceled(Caller,Callee,Entry,Time).
entry_queue_lengthened(Caller,Callee,Entry,Time).
entry_queue_shortened(Caller,Callee,Entry,Time).
rendezvous_started(Caller,Callee,Entry,Time).
rendezvous_completed(Caller,Callee,Entry,Time).
var_read(Variable,Location,Value,Time).
var_updated(Variable,Location,Value,Time).
entry_parm_set(Caller,Callee,Entry,Parm,Mode,Value,Time).
task_activated(Task,Time).
task_completed(Task,Time).
ready_to_terminate(Task,Time).
abnormally_terminated(Task,Time).
program_ended(Program,Time).
Figure 3.10 - Type of Events within the Trace Database
The first four records show the activation of four tasks: C2, T2, T1, T1 at clocks 1, 2, 3, and 4 respectively. Unfortunately, YODA was not able to record the activation of another task which is the main Ada program. The output of this program should be X = 1, but as a result of a faulty use of shared data, it outputs X = 2. A very simple solution for this problem would be to remove tasks C1 and C2 and place the entry calls T1.E(50.0) and T2.E in sequence within the main program. After the execution of a monitored program, Prolog queries can be issued by the user in order to confirm or reject hypotheses about program behavior.
task_activated(task(c2,[main]),1).
task_activated(task(t2,[main]),2).
task_activated(task(t1,[main]),3).
task_activated(task(c1,[main]),4).
entry_called(task(c2,[main]),callee(t2,[main]),e,5).
ready_to_terminate(task(t1,[main]),6).
entry_queue_lengthened(caller(c2,[main]),callee(t2,[main]),e,5).
entry_called(task(c1,[main]),callee(t1,[main]),e,7).
entry_queue_lengthened(caller(c1,[main]),callee(t1,[main]),e,7).
rendezvous_started(caller(c2,[main]),callee(t2,[main]),e,8).
entry_queue_shortened(caller(c2,[main]),callee(t2,[main]),e,8).
rendezvous_started(caller(c1,[main]),callee(t1,[main]),e,9).
entry_queue_shortened(caller(c1,[main]),callee(t1,[main]),e,9).
var_read(variable(x,[main]),[e,t2,main],0,10).
var_read(variable(x,[main]),[e,loop_name1,t1,main],0,11).
var_read(variable(x,[main]),[e,t2,main],0,12).
var_update(variable(x,[main]),[e,t2,main],1,13).
rendezvous_completed(caller(c2,[main]),callee(t2,[main]),e,14).
var_read(variable(x,[main]),[e,loop_name1,t1,main],1,15).
task_completed(task(c2,[main]),16).
task_completed(task(t2,[main]),17).
var_updated(variable(x,[main]),[e,loop_name1,t1,main],0,18).
rendezvous_completed(caller(c1,[main]),callee(t1,[main]),e,19).
task_completed(task(c1,[main]),20).
ready_to_terminate(task(t1,[main]),21).
program_ended(main,22).
Figure 3.11 - Sample Trace Database
YODA allows the identification of a larger spectrum of errors when compared with MON [Luck85]. This improvement is a result of passing the responsibility to the user to program queries which may, if correctly programmed, detect the presence of intertask communication, exception handling, and dynamic storage allocation errors. MON focused on deadness errors only.
Moran [Mora85] used an iconic representation of inter task activities to monitor and visualize Ada task entry calls. Ada source programs are embedded, manually, with monitoring calls. Because another image of the original program is used (with the monitoring calls), Moran's monitor is also an intrusive monitor. Figure 3.12 shows a view of a typical iconic representation. It shows four tasks: Driver1, Driver2, walker and teller. The Driver1 and Teller tasks are in rendezvous. In her work, Moran proposed an Optimal Graphical Debugger as follows:
...each task could be defined by its own window. Each window would possess a shaded border and a unique name (as in the conceptual model proposed by Weiderman). At the highest level, the task window would contain a graphical view (utilizing the conventions proposed by Buhr for showing relationships between entries, showing guards, etc.) of the entries within a task. Entry calls and rendezvous would be animated with tokens and flashing outlines of tasks just as in the graphical debugger used in this research. (See figure 3.12a) ... Supporting the next level of error localization, that of isolating the specific offending code in the suspected tasks, would be a selectable textual view for the task window which would replace the graphical view of entries with the actual textual code of the task. (See figure 3.12b)... supporting the need for a history of events would be a third selectable view of each task window which would contain a textual chronology of events for that task (See figure 3.12c). ... Also, available would be a selectable program window containing a textual time-stamped message chronology of the interleaved sequence of events in the overall flow of control of the program. (See Figure 3.12.)
Figure 3.13 shows a view of the suggested chronology of events. It allows the visualization of the interleaved sequence of events in the overall flow of program control. A textual time-stamped message contains the type of event and the tasks and entry involved.
Figure 3.12 - Moran's Selectable Task Window Views
Figure 3.13 - Chronology of Events
Maleknasri [Male88] worked with a "Prototype and Experimental Comparison of Graphical and Textual Multi-process UNIX/C Monitors" in his dissertation. CPEM (Concurrent Program Environment Monitor) is a comprehensive concurrent debugging tool. It allows the monitoring of the following:
- process creation and termination
- process relationships
- process status
- process communications and interactions
- process resource utilization and control
CPEM uses the approach of software monitoring. Figure 3.14 shows the CPEM pre-monitoring components. A pre-processor is used to adapt a set of programs for the monitoring process. The source code of each program is augmented with function calls to the event generation library, which contains the functions necessary for the monitoring process. The pre-processor analyzes the source code to locate the C constructs which are relevant for monitoring. The programs are then compiled and linked with this library.
Figure 3.14 - CPEM Pre-monitoring Components
Figure 3.15 shows the CPEM monitoring components. An event queue is used to store the events passed through the event generation function calls. The monitoring and display subsystem dequeue these events from the queue and present them on the graphic or text display terminal.
Figure 3.15 - CPEM Monitoring Components
Figure 3.16 - Basic Symbols Used in CPEM
Figure 3.16 shows the basic symbols used in CPEM. There are 30 distinct images. To take advantage of the CPEM views, one must master another level of abstraction. For teaching purposes, this approach leads to more difficulty for beginning concurrent programmers. CPEM also does not perform any sort of high-level debugging. It is merely a monitoring system.
EDEN, an event-driven monitor for Ada tasking programs, presented by Cheng, Araki and Ushijima [Chen87], collects and reports run-time information concerning inter-task actions. Histories are saved in files. EDEN detects and reports task communication deadlocks in the program while it is being executed. It uses a pre-processor that inserts calls into the original program so that a history of program activity may be recorded and analyzed. The user may interact with the monitor to request snapshots, insert breaks (in which case recompilation is required) and traces, and to perform timing analysis. It is implemented as an Ada package. The package and the altered program are then compiled and linked. Figure 3.17 shows the monitoring process with EDEN.
(a) Processing target program (b) Run-time monitoring
Figure 3.17 - Monitoring process with EDEN
The pre-processor adds to the source program monitoring calls. Source code constructs (patterns) that match the pattern shown in Figure 3.18 are transformed into the code constructs (replacements) shown in Figure 3.19.
begin
<statements-1>
accept <entry simple name> (<index>) [ <formal part> ] [do
<statements>
end [ <entry simple name> ] ] ;
Figure 3.18 - Source Pattern
begin
<statements-1>
Tasking_Information_Collector.ACCEPTABLE(TASK_ID,CLOCK,
(GET_SIMPLE_NAME("<entry simple name>"),
NATURAL( <index> )));
accept <entry simple name> ( <index> ) [ <formal part> ] do
Tasking_Information_Collector.RENDEZVOUS(TASK_ID,CLOCK,
(GET_SIMPLE_NAME("<entry simple name>"),
NATURAL(<index> )));
[ <statements> ]
Tasking_Information_Collector.CONTINUE(TASK_ID,CLOCK,
(GET_SIMPLE_NAME("<entry simple name>"),
NATURAL( <index> )));
end [ <entry simple name> ] ;
Figure 3.19 - Replacement Pattern
Figure 3.22 shows an EDEN snapshot of two instances of the execution of the program shown in Figure 3.20. At time 1.29x, the states of the tasks are as follows: the main task is performing its block activation; Task T1 is waiting for a rendezvous with Task T2 at entry E2; Task T2 is also waiting for a rendezvous, but with Task T3 at entry E3; and Task T3 is being executed. At time 2.5, the states of the tasks are as follows: the main task is in a completed state, waiting for its children tasks to terminate; Task T1 is still waiting for a rendezvous with Task T2 at entry E2; Task T2 is in rendezvous with Task T3 at entry E3; and Task T3, which is accepting the entry call from Task T2, is executing a statement. The next state described by EDEN will report that a circular entry call will arise. This state will then be followed by a global blocking report in which Task T3 is attempting a rendezvous with Task T1 at entry E1. After detecting the deadlock, EDEN will output the contents of all entry call queues, as shown in Figure 3.21.
procedure CEC is
task T1 is entry E1; end;
task T2 is entry E2; end;
task T3 is entry E3; end;
task body T1 is
begin
T2.E2;
accept E1;
end T1;
task body T2 is
begin
T3.E3;
accept E2;
end T2;
task body T3 is
begin
accept E3 do
T1.E1;
end T3;
begin
null;
end CEC;
Figure 3.20 - A Sample Program
Figure 3.20 shows an Ada program which was submitted to EDEN. It demonstrates a case of the circular deadlock problem. Task T1 issues the entry call T2.E2, accepts a call to its entry, E1, and then terminates. Task T2 has the same behavior as Task T1 but issues an entry call to Task T3. Task T3 closes the loop by first accepting a call to its entry E3 and within this entry the entry call T1.E1 is issued.
Figure 3.21 - State of All Queues
Figure 3.22 - EDEN SnapShot
Belvedere [Houg89] is a pattern-oriented parallel debugger for highly parallel programs that allows the specification of user-defined abstract communication events. Abstract events are defined through the use of an Event Definition Language [Bate83, 89]. These abstractions are then animated. Belvedere operates on post-mortem traces which are produced by a multiprocessor simulator. A post-mortem trace is treated as a relational database(db). The db is then queried and selected tuples are animated. Each tuple is time stamped. According to Hough and Cuny [Houg89],
...to debug highly parallel programs, we believe that the programmer must be able to determine the extent to which these intended logical patterns of communication actually occur during execution.
Belvedere is a prototype debugger designed to reduce the efforts related to the specification, manipulation and animation of logically structured patterns of task interactions [Houg89].
Figure 3.23 shows an example in which a user selects a portion of the trace for animation with database queries.
Figure 3.23 - Selecting Events
Figure 3.24a: Snapshot of message traffic animation during the initial phase of an iteration of the travelling salesman program. Activity is depicted with highlighting: the associated port is highlighted for a receive and the associated channel for a send (the arrowhead indicates directionality; multiple arrowheads indicate more than one message buffered).
Figure 3.24b: Snapshot of the traveling salesman message traffic showing the traced animation of the movement of a token during the second phase of an iteration.
Figure 3.24 - Belvedere Snapshots
Houg and Cony [Houg87] performed a simulated annealing [Felt86] of the traveling salesman problem on a hypercube [Felt86]. The above queries were used to produce the data that generated the animation that is shown in Figure 3.24. According to Hough and Cony [Houg87],
. . . [since] many errors in parallel programs are communication related, we believe that the identification of these patterns will form the basis for highly parallel debugging paradigms.
This approach is exploited by ADAT which is discussed within Chapters Two and Four. Of the three types of programming errors defined below the first two have been initially implemented in ADAT.
Hough and Cony [Houg89] defined three types of programming errors that disturb interprocess communication patterns:
1. sequencing errors: expected communication patterns occur, in the wrong
sequence;
2. missing communication errors: expected patterns do not occur because
some or all of their constituent events do not happen; and
3. extraneous communication errors: expected patterns occur, along
with additional, unintended communications.
PPD is an integrated debugger for parallel programs [Mill88]. It runs on shared memory multi-processors. PPD was designed to allow the easy detection of race conditions as well as deadlocks. The debugging process in PPD contains three phases: preparatory, execution, and debugging. Figure 3.25 shows the preparatory phase components.
Figure 3.25 - PPD Preparatory Phase Components
Figure 3.26 shows the execution phase components. The dynamic information gathered during the program's execution is stored in a log file. The log is used in the debugging phase.
Figure 3.27 shows the debugging phase components. To help the programmer, both static and dynamic information are supplied via the static program dependance graph, the dynamic graph and the parallel dynamic program dependance graph.
Figure 3.26 - PPD Execution Phase Components
Figure 3.28 shows an example of a dynamic program dependance graph which is used to show the run-time dependance among the components of a program.
Figure 3.27 - PPD Debugging Phase Components
Figure 3.28 - PPD Dynamic Program Dependance Graph
Figure 3.29 shows an example of a parallel dynamic program dependance graph. It is used to show the interactions between processes. Information about local events do not appear in the view.
Figure 3.29 - PPD Parallel Dynamic Program Dependance Graph
Figure 3.30 shows an example in which a subroutine accesses a shared variable, together with a simplified static program dependance graph.
Figure 3.30 - PPD Static Program Dependance Graph
MAD (Monitoring, Animating, Debugging) is a tool designed to debug PARC programs in parallel [Rubi89]. It integrates a monitor, debugger and an animation device. MAD is an interactive, event-driven, non-intrusive monitor. Its user interface allows the user to tie events to graphical views. Figure 3.31 shows the MAD architecture.
Figure 3.31 - The MAD Architecture
Figure 3.32 shows a task state view which displays the view of any task history aspect.
Figure 3.32 - Task State View
Figure 3.33 shows the task tree view which is used to show the several layers of parallel structures. MAD also provides several other views which give comprehensive visual information about the "interesting events."
Figure 3.33 - The Work Tree
VESTAL was designed as an instructional tool for animating, debugging and monitoring Ada concurrent programs [Toma91]. It provides a graphical representation for intertask interaction in Ada. The execution of an Ada program can be observed through graphical animation either continuously or in a step by step mode. Breakpoints are also allowed. Figure 3.34 shows the task state examination screen.
Figure 3.34 - Task State Examination
Another feature of VESTAL is the Trace Examination. It shows information concerning time, type of event and related tasks. Figure 3.35 shows the trace examination screen.
Figure 3.35 - Trace Examination
VESTAL is a pre-processor. For an Ada program to be animated by VESTAL, it must issue procedure and function calls to the VESTAL package. These calls are inserted into the Ada program by the VESTAL pre-processor. Figure 3.36 shows the VESTAL scheme of operation.
Figure 3.36 - VESTAL Scheme of Operation