A visual execution model for Ada tasking.
A visual execution model for Ada tasking can help programmers attain a deeper understanding of the tasking semantics. It can illustrate subtleties in semantic definitions that are not apparent in natural language design. We describe a contour model of Ada tasking that depicts asynchronous tasks (threads of control), relationships between the environments in which tasks execute, and the manner in which tasks interact. The use of this high-level execution model makes it possible to see what happens during execution of a program. The paper provides an introduction to the contour model of Ada tasking and demonstrates its use.
Introduction
The Ada programming language is intended for use in real-time applications
such as flight navigation or process control software. For this reason, tasking
figures prominently in the language design. The semantics of tasking, however,
is extremely complex. At the same time that tasking provides the flexibility and
control required for the implementation of real-time and embedded software, it
is undoubtedly the most difficult of all the Ada language features to understand
and to learn to use effectively.
This paper describes a visual execution model designed to help software
practitioners attain a deeper understanding of the semantics of Ada tasking.
Derived from Johnston's contour model for block-structured languages [17], our
model helps a programmer visualize the effects of executing tasking statements.
It illustrates subtleties in the semantics of tasking that are not apparent in
Copyright 1993 c
by ACM, Inc. Permission to copy and distribute this document is
hereby granted provided that this notice is retained on all copies, that copies are not altered,
and that ACM is credited when the material is used to form other copyright policies
standard natural language descriptions of Ada and the motivation for nuances
in the definitions of tasking primitives.
The Ada Language Reference Manual (ALRM) [21] is the definitive reference
for all Ada language features, including tasking. A variety of Ada language text
books, e.g. [3] and [10], describe the language in a more tutorial format, and
at least one specializes in Ada tasking [11]. These descriptions, however, lack
concreteness, being purposely vague to allow for variations in language imple-
mentations. Textual descriptions typically group language constructs according
to general features (e.g., declarations, statements, subprograms, packages,
exception handling, tasking) and combine informal explanation with example
program fragments. Such descriptions tend to be incomplete and ambiguous.
Moreover, the style of presentation obscures subtleties in the interaction of different
language features, making it difficult to recognize inconsistencies among
the definitions of separate language features. The existence of Ada Issues [1],
and the hundreds of requests for clarifications of the tasking semantics alone,
attest to the inadequacy of these natural language descriptions.
Formal semantic specifications based on axiomatic or denotational techniques
[7] address many of the shortcomings of natural language descriptions.
The use of rigorous mathematical notations results in specifications that are precise
and unambiguous, and that can be analyzed for consistency and complete-
ness. However, it also results in highly abstract mathematical specifications,
which ordinary programmers may find difficult to understand. The notations
are chosen for their mathematical properties, not their visual clarity, and are
typically of little help in visualizing the execution of programs. Moreover, axiomatic
and denotational specifications are poorly suited to describing programs
that should not terminate, such as operating systems or process control systems.
In any such function-based semantic techniques, a nonterminating program is
equivalent to the trivial program while true do null; endwhile.
We have found Johnston's contour model to be very effective in teaching
the semantics of block-structured languages. The model employs data structure
diagrams to depict program states. An executing program is represented visually
as a series of evolving diagrams. Johnston's model uses natural and simple data
structures, which are easily interpreted by programmers. An automated version
of the model supplies a visual semantics for ALGOL programs [20]. The model
also forms the basis for a textbook on programming language structures [18]
and for a description of multitasking in PL/1 [4]. The contour model is used to
illustrate and clarify the semantics of parameter passing in a paper on axiomatic
semantics of the same [6].
Section 2 gives a brief overview of Ada tasking. Section 3 presents a program
for calculating prime numbers that illustrates the use of the major tasking fea-
tures. We give an overview of our contour model in Section 4 and illustrate the
concepts introduced in the overview more concretely in the next two sections
using the example program from Section 3. Section 5 shows how we encode the
program as a collection of nested contour diagrams and Section 6 describes a
particular program execution. We compare our model to Johnston's model and
to more common stack-based execution models in Section 7. Finally, we discuss
conclusions and future work in Section 8.
Tasking in Ada
We restrict our attention to a subset of Ada in order to focus on the parallel
execution of tasks. In particular, we do not consider packages, generics and
exception handling, which are largely independent of tasking anyway, in this
work.
A discussion of the semantics of Ada tasking requires an understanding of the
distinction between the scope units, or declarative regions, defined by a program
and their run-time instances. A scope unit is a static portion of program text,
such as a block, function, procedure, or task, that encapsulates a computation
and the local data required for the computation. Virtually all block-structured
programming languages make use of blocks, functions and procedures; we therefore
limit our discussion of these constructs to their relationship to tasking.
In the case of a task, a task type determines the task's interface and its
computation. The declaration for a task type consists of a specification and
body. The specification defines a set of entries, which can be called from within
other scope units to establish a rendezvous with tasks of the type. The body
consists of a declarative part and the sequence of statements to be executed by
tasks of the type. Accept statements within the body define remote procedures
that tasks of the type execute in response to calls on their entries. We discuss
the semantics of task execution, including the call and accept statements, in
more detail below.
Instances of the scope units in a program are dynamic objects that, unlike
the scope units themselves, exist only at run-time. Execution of a program
begins with a single thread of control, which creates an instance of the top level
procedure and executes its body. While executing the body of a scope unit, a
thread of control may create new instances of procedures, functions and block
statements and spawn new threads of control to execute instances of task types.
The task instances that exist at some point during execution of a program and
the root instance of the main procedure determine the active threads of control
at that point. We view the top level procedure as defining a special root task
type with no entries. This permits us to identify threads of control with task
instances.
An instance of a task type can be created in one of two ways: by elaborating
a task declaration or by evaluating a task allocator expression of the form "new
TT ", where TT designates a task type, called the designated type. In the latter
case, the task allocator returns an access, or pointer, value designating the new
task instance and this task instance is said to belong to the collection of task
instances associated with the corresponding access type. We refer to an instance
of a task type as elaborated if it is created by elaborating an object declaration
and allocated if it is created by a task allocator. The classification of a task
instance as elaborated or allocated affects the manner in which it synchronizes
with other instances during its creation and termination, as described below.
While each instance of a given scope unit performs the same computation,
the referencing environment, or binding of identifiers to program objects, may
differ from instance to instance. The lifetimes of such instances may be disjoint,
as when an instance nonrecursively invokes the same procedure more than once,
or they may overlap, as when an instance spawns several tasks of the same task
type. If execution of an instance p causes the creation of an instance i, we refer
to p as the parent of i and to i as a child of p.
At various points during execution of a program an instance, or more pre-
cisely, the thread of control executing the instance, may have to wait for the
occurrence of certain events in order to make progress. The instance is said to
be blocked at such points. For example, when an instance issues an entry call it
blocks until the task instance that owns the entry accepts the call and executes
the rendezvous.
An instance of a task type can be regarded as passing through several different
phases during its lifetime [2, 14]. We distinguish five such phases, referring
to a task instance as activating, running, completed, terminated, or abnormal,
depending on the phase it is in. An instance of a task type begins activating
when it is created. This first phase in the lifetime of a task instance consists
of the elaboration of its declarative part. Once activated, the instance normally
begins running, which roughly corresponds to executing the sequence of
statements that appear in the body of the task type. The instance becomes
completed upon finishing execution of the task body. A completed instance
does not perform any further processing, but simply waits to terminate. The
instance can be blocked or it can be ready to execute in any of these first three
phases.
The final phase in the lifetime of a task instance begins with its termination.
The semantics of termination in Ada ensure that an implementation can deallocate
the local data associated with an instance of a block, function, procedure
or task upon terminating it. 1 The lifetime of a task instance, however, extends
past its termination so that other instances can interrogate attributes associated
with the task instance and invoke its entries. We regard the lifetime of a task
instance that is elaborated as ending when execution leaves the instance and
the lifetime of a task instance that is allocated as ending when execution leaves
the scope of the associated access type, which coincides with deallocation of the
collection that contains the instance. Under normal circumstances, therefore, a
task instance progresses through four phases, as it activates, runs its algorithm,
1 The ALRM requires all instances to pass through a completion phase, during which
the instance may be temporarily blocked, before terminating. It also talks about leaving
functions, procedures and blocks, rather than terminating them. We view leaving an instance
as equivalent to terminating it.
completes, and terminates. Its lifetime begins with its creation and ends with
its deallocation, sometime after termination.
The exception to this normal progression occurs when some instance explicitly
aborts a concurrent task instance. Aborting a task instance that is
activating or running causes it to enter the abnormal phase. A task instance
that is abnormal may continue executing statements until it reaches its next
synchronization point, at which point it must complete. If an instance of a task
type is already completed or terminated, then aborting it has no effect.
The Ada semantics require that an instance i of a task type synchronize with
its parent at the beginning and ending of i's activation. A task instance that is
elaborated blocks immediately upon being created while the parent continues
elaborating its declarative part. The parent blocks when it finishes elaborating,
at which time all child instances that it elaborated are unblocked and begin activating
in parallel. The parent remains blocked until the last of its child instances
finishes activating, at which point the parent is unblocked. A task instance that
is allocated synchronizes with its parent in a slightly different fashion. The allocated
instance does not block upon creation, but begins activating immediately,
as part of evaluation of the allocator. The parent of an allocated instance blocks
on the call to the task allocator until the instance finishes activating.
The rules that determine when instances terminate make use of certain master
and dependence relations. Each instance of a task type depends on one or
more concurrent instances, which are collectively referred to as its masters. The
ALRM defines a direct dependence between an elaborated instance of a task
type and the instance's parent and between an allocated instance of a task type
and the instance that elaborates the declaration for the associated access type,
which could be the parent or could be an instance of a global scope unit. This
direct dependence identifies a direct master for each task instance. All other
dependences are indirect. The ALRM defines indirect dependences between a
task instance and each instance on the dynamic chain (reverse of the call chain)
from one of the task instance's masters and between a task instance and each
master of one of the task instance's masters.
The dependents of an instance may need access to the instance's local data or
their execution may (logically) constitute part of its algorithm. Thus, the ALRM
extends the notion of completion to arbitrary scope units, so that all instances
complete upon finishing execution of their bodies, and further stipulates that
an instance that is completed cannot terminate until all of its dependents are
terminated. This rule ensures that an implementation can safely deallocate the
data associated with an instance upon terminating it. The ALRM further states
that, if an instance declares an access type, then the collection associated with
the access type can be deallocated when the instance terminates. In this case,
the rule for termination also guarantees that the task instances in the collection
terminate prior to being deallocated.
Although instances may communicate through shared environments, the preferred
method for synchronization and communication is through rendezvous on
entries associated with task instances. In Ada, an instance requests a rendezvous
by calling an entry belonging to some concurrent task instance. The entry call
has the semantics of a remote procedure call. The caller blocks until the task
instance that owns the entry accepts the call, by executing an accept statement
designating the entry. The accept statement specifies the modes and types of
the formal parameters and the sequence of statements, which can be null, that
the called instance executes on behalf of the caller. When the rendezvous is
finished, the caller resumes execution with the statement following the call.
An entry can be called asynchronously by multiple threads of control. In
such situations, the Ada semantics require that the called instance service the
entry calls on a first-come-first-served basis. An implementation must therefore
provide entry queues on which to place callers until their calls are accepted. An
instance that executes an accept statement blocks if there are no calls pending
for the entry.
For brevity, we restrict our attention in this paper to a single version of the
Ada select statement: the selective wait statement with a terminate alternative.
This version of the select statement allows an instance to selectively accept a
call on one of a set of entries or, under the conditions described below, to ter-
minate. In the sequel, therefore, we assume that all but one of the branches
of a select statement designate potential accept alternatives, and that the one
distinguished branch designates a terminate alternative. In this context, any
sequence of statements that begins with an accept statement constitutes an
accept alternative, while a terminate alternative consists of a single terminate
statement. An accept alternative or a terminate alternative may also be preceded
by a boolean guard, which determines if the alternative is a candidate for
execution.
The first step in executing a select statement consists of evaluating the guards
and determining the set of open alternatives, consisting of those alternatives that
have no guards and those alternatives whose guards are satisfied. We treat the
absence of any open alternative as a run-time error. 2 The instance executing a
select statement then nondeterministically selects some open alternative that is
also passable and executes it. If there are no passable alternatives, the instance
blocks until some open alternative becomes passable and, upon unblocking, selects
one open passable alternative to execute. An accept alternative is passable
if some caller is waiting for a rendezvous on the entry named by the accept
statement at the beginning of the accept alternative. Thus, the leading accept
statement in a passable accept alternative is non-blocking. A terminate alternative
is passable if the instance executing the select statement depends on some
master that is completed and every dependent of this master is either terminated
or blocked at an open terminate alternative. These conditions ensure
that no caller is waiting to engage in a rendezvous with the instance [21]. Thus,
In Ada, executing a select statement with no open alternatives raises an exception. Our
treatment is consistent with the semantics of the propagation of exceptions.
the terminate alternative in a select statement can be passed only if the select
statement does not have any passable accept alternatives.
We say a master is asleep if it is completed and if all of its dependents are
either terminated or at open terminate alternatives. 3 Being asleep is stable, in
the sense that a sleeping master remains asleep until it terminates; the master
and its dependents are finished executing their algorithms and are waiting to
terminate. The ALRM states that executing the terminate alternative of any
one of the dependents of a sleeping master results in the termination of all
dependents. We prefer, however, to view the execution of a passable terminate
alternative as completing all dependents. Ultimately, completing the dependents
has the same effect as terminating them but it does not require us to treat
distributed termination as a special case. The dependents can terminate in
the usual orderly fashion, starting with those at the bottom of the dependency
hierarchy and working upwards to the sleeping master.
The abort statement in Ada allows an instance to abort a concurrent task
instance. Aborting a task instance causes it and all of its dependents to either
complete or become abnormal, unless they are already completed or terminated.
An abnormal task instance completes on reaching its next synchronization point,
and so cannot engage in any further rendezvous.
3 An Example Tasking Program
An example program from [13] illustrates the major tasking features of Ada.
The program implements an algorithm for generating prime numbers using a
dynamically created pipeline of checker task instances: The instance at stage
n in the pipeline checks numbers for relative primeness with the nth prime
sending those numbers that pass the check to the instance at stage
Positive numbers are fed into the pipeline in order. Thus, a number
moves down the pipeline until it either fails some check or reaches the end of
the pipeline. A number that passes the relative primeness check at the final
stage of the pipeline is accepted as prime and results in a new stage being
added to the pipeline.
The procedure PRIMES implements this algorithm. The statement labels (p1,
p2, etc.) are used for reference below, and are not part of the program. For
readability, we show the procedure and task bodies separately.
p1 procedure PRIMES is
p2 task FDR; - feeds the pipeline
checks VALues for
p4 entry GET NUM(NUM: in INTEGER); - divisibility by NUM
3 This terminology is borrowed from [2]. Their definition, however, does not not require
that the master be completed.
p5 entry CHK IT(VAL: in INTEGER);
p6 end CHKR;
type CHKR PTR is access CHKR;
p8 procedure MAKE CHKR(NEW PRI: in INTEGER;
NEW CHKR: out CHKR PTR);
- creates a NEW CHKR to check
- relative primeness with NEW PRI
p9 FRONT: CHKR PTR; - the front of the pipeline
- procedure and task bodies are shown separately below
The static task FDR declared in PRIMES feeds the pipeline with positive num-
bers. Because we require only a single instance of this task, we declare FDR
directly, without first introducing a task type. However, the direct declaration
for FDR is equivalent to first declaring an anonymous task type and then
declaring a single object of that type.
The pipeline is composed of task instances of type CHKR, which are created
dynamically by the procedure MAKE CHKR. An instance of type CHKR receives the
prime number it should use through its GET NUM entry and receives numbers to
check for relative primeness through its CHK IT entry. The access type CHKR PTR
provides values for designating instances of type CHKR. The collection associated
with CHKR PTR contains instances of type CHKR.
FRONT designates the first task instance in the pipeline. Each instance of
type CHKR contains a CHKR PTR variable linking it to the next task instance in
the pipeline. We show the procedure and task bodies below. For simplicity,
we assume primitive operations, called get and put, for performing input and
output.
m1 procedure MAKE CHKR(NEW PRI: in INTEGER;
NEW CHKR: out CHKR PTR) is
m3 NEW CHKR := new CHKR; - make a new CHKR task
m4 NEW CHKR.GET NUM(NEW PRI); - tell the task its number
print the prime number
f1 task body FDR is
f2 MAX: INTEGER; - maximum prime to test
generate the first prime
f6 for CTR in 3.MAX loop
feed the pipeline
c1 task body CHKR is
c2 MY NUM, NEW VAL: INTEGER;
c3 NXT CHKR; CHKR PTR;
c4 begin
c5 accept GET NUM(NUM: in INTEGER) do
c6 MY NUM := NUM;
c8 loop
select
c10 accept CHK IT(VAL: in INTEGER) do
c13 or
c17 if NXT CHKR /= null then
pass NEW VALUE on
else
- it's prime
c22 end if;
Sections 5 and 6 show how the contour model describes a particular execution
of this program. First, however, we give a brief overview of the model itself.
4 Overview of the Contour Model
The contour model defines a simple interpreter for generating sequences of snap-shots
representing the progression of a computation through a series of instantaneous
machine states. Every sequence of snapshots generated from an initial
snapshot for a given program and a given set of inputs describes a potential
execution of the program. The interpreter is nondeterministic, in the sense that
it can produce different snapshot sequences from the same program and set of
inputs to model nondeterminism in the program.
A snapshot consists of an algorithm, which remains fixed throughout exe-
cution, and a record of execution, which changes dynamically. The algorithm
is a representation of an Ada program. It consists of a collection of algorithm
contours representing the scope units in the program. The algorithm contour
for a scope unit u contains a declaration array, which describes the local data
required by instances of u, a flow chart-like network of instructions, which defines
the computation that instances of u perform, and a successor link, which
designates the algorithm contour of the scope unit that lexically encloses u. The
algorithm encodes all the information required to execute a program. Execution
does not affect the algorithm, which is therefore the same in all snapshots.
The record of execution describes the contents of memory cells and registers.
It consists of a collection of execution contours, which represent the instances
of the scope units that exist at a some point during execution, and a collection
of processors, which depict the active threads of control. An execution contour
c for a scope unit u contains a data array in which to store c's local data and a
successor link. The interpreter uses the declaration array within the algorithm
contour for u as a template for generating the data array for c. The successor
link, also called the static link, designates the execution contour of the instance
that defines the global referencing environment for c. Thus, an instance finds
local data in its own execution contour and global data in the execution contours
on the static chain formed by following static links.
A processor is an abstraction of a hardware CPU. We associate a processor
with each task instance in a program, including the root instance of the top-level
procedure. Each processor has an associated state, which indicates the
current phase of the instance's lifetime. The values act , run, com, term, and
abn, represent the activating, running, completed, terminated and abnormal
phases, respectively. Various other components of a processor encode information
required to execute the task instance. In particular, an instruction pointer
describes the instance's locus of control, an environment pointer determines its
referencing environment, an expression stack provides temporary storage for
intermediate values and for the values of actual parameters, and an execution
status indicates if the instance is blocked or eligible to execute. We describe
additional components, which are used primarily for task management, in Section
6.
We identify scope units with their algorithm contours, instances of the scope
units with their execution contours, and task instances with processors below.
The machine cycle of the contour model interpreter consists of
Nondeterministically selecting a processor from among those processors in
the current snapshot that are not blocked and are not terminated
Fetching the instruction designated by the processor's instruction pointer
Updating the processor's instruction pointer so that it references the next
instruction in the algorithm
Executing the fetched instruction to produce a new snapshot
The processor selected in a particular machine cycle is said to be executing.
The contour model is an Information Structure Model [23]. As such, it uses
storage cells to represent units of memory in an abstract machine. Storage cells
have two important features: They may contain any number of components and
their components may reference other storage cells. The concept of a storage
cell can be used to give a precise specification for the contour model, similar to
that described in [17].
We do not describe the contour model at the level of manipulation of individual
storage cells in this paper. Instead, we use diagrams, as in [17, 18],
which describe snapshots at a higher level of abstraction, and explain how executing
instructions transforms the diagrams. A snapshot contains two main
contour diagrams, corresponding to the algorithm and record of execution, and
several additional diagrams, which show information associated with processors
and which describe the environment in which the program executes. Because
the algorithm for a program remains constant, however, we adopt Johnston's
convention of presenting the algorithm in a separate diagram and then omitting
it from individual snapshot diagrams.
The next two sections illustrate these concepts more concretely and highlight
other important aspects of the model. We describe the algorithm for PRIMES in
Section 5 and the record of executions that simulate a particular execution of
PRIMES in Section 6.
5 The Algorithm for PRIMES
The contour diagrams in Figures 1-3 express the PRIMES program from Section 3
as an algorithm. The figures illustrate notational conventions used throughout
the example. We attach lower-case italic labels to contours and to instruction
boxes for reference purposes; the labels are not part of the algorithm. We do
not show explicit successor links on contours, but instead represent successor
links implicitly by the nesting of contours. Thus, the nesting of algorithm
contours mirrors the nesting of scope units in a program. The declaration array
for each contour is shown in its upper left hand corner. We write contour
model instructions in lower-case and program names (identifiers) in upper-case.
As described below, the contour model may extend a scope unit with certain
implicit declarations; we choose names that begin with a percent sign (e.g.,
%RET, %FDR) for all implicitly declared data. Arrows connecting instruction
boxes describe control flow.
The outermost contour primes in Figure 1 represents the top-level procedure
PRIMES. We regard the direct declaration for FDR as implicitly declaring a task
type, called %FDR, and then declaring FDR to be of this type. Thus, the declarative
part of PRIMES determines six declarations, represented by the six rows of
the declaration array in the contour primes. Each row of the declaration array
specifies the name of the declared object and gives a descriptive tag. The table

Figure

Figure
primes
make chkr
chkr
fdr
return
put NEW PRI
ecall NEW CHKR.GET NUM
activate NEW CHKR
CHKR:CHKR PTR
create NEW CHKR:
out
ACC
in
INT
in
task enter
task enter
terminate
task complete
null
activate FDR
elaborate
task enter
FDR
CHKR
CHKR PTR
FRONT
ACC
fg
proc enter

Figure

1: Algorithm Contour for PRIMES
@R
\Gamma\Psi
oe?
for
fdr
terminate
exit
in
INT
in
INT
CTR INT
ecall
compare
for enter 3 . MAX
call MAKE CHKR(2,FRONT)
get MAX
activation
elaborate
task enter
INT

Figure

2: Algorithm Contour for FDR
@
@ @R
\Gamma\Psi
\Phi- c19
c6
chk it
get num
chkr
in
INT
rend exit
rend enter CHK IT
select TRUE:c10, TRUE:c14
loop
rend enter GET NUM
accept GET NUM
activation
elaborate
task enter
MY NUM:=NUM
rend exit
NUM INT in
MY NUM
INT
INT
terminate
call MAKE CHKR
ecall NXT CHKR.CHK IT
compare
compare

Figure

3: Algorithm Contour for CHKR
Tag Associated Object
ACC Access Object
ATYPE Access Type
INT Integer
LAB Label
PROC Procedure
TTYPE Task Type

Figure

4: Descriptive Tags used in the PRIMES Example
in

Figure

4 summarizes the meanings of the tags that appear in the example.
The declaration array also contains information required for initializing data
objects, as shown in the rows for %FDR, FDR, CHKR, and MAKE CHKR.
Instructions p1-p12:1 describe the algorithm performed by primes. Every
algorithm begins with an enter instruction. In the case of the top level proce-
dure, we use the task enter instruction for entering the scope of a task type.
The elaborate instruction p2 elaborates the declaration array in primes. An
elaborate instruction with no arguments is an abbreviation for a series of
elaborate instructions: one for each row in the declaration array of the enclosing
algorithm contour. The activate instruction p10 activates an instance
of FDR. The remaining instructions in the algorithm for primes correspond to
executing the body of primes (p11), completing the instance of primes (p12:0)
and, finally, terminating the instance of primes (p12:1).
The contour make chkr represents the procedure MAKE CHKR. As in John-
ston's model, we extend each procedure with an implicit formal input param-
eter, called %RET, which is used as a label when transferring control back to
the caller. The first row of the declaration array in make chkr represents the
implicit declaration for %RET, and the last two rows represent the declarations
of the formal parameters NEW PRI and NEW CHKR, which appear in the specification
for MAKE CHKR. Rows representing formal parameter declarations specify
the parameter passing mode.
The algorithm for make chkr begins with the proc enter instruction for
entering the scope of a procedure (m1). It does not require an elaborate
instruction, as the declarative part of MAKE CHKR is empty. The next four instructions
model the statements in the body of MAKE CHKR. The create instruction
m3:0 creates a new task instance of type CHKR for the collection associated
with CHKR PTR, and assigns a reference to the new instance to NEW CHKR. Instruction
m3:1 activates the new instance. Instructions m4 and m5 implement
the entry call statement and the output statement in the body of make chkr.
The algorithm for make chkr does not require a complete instruction, since

\Pi run
@ @task information blocks
dependencies
I/O
no entries
ready
Snapshot 1: An initial snapshot
make chkr has no dependents. Hence, the final instruction returns control to
the caller.

Figures

2 and 3 show the algorithm contours for FDR and CHKR. The contours
in these figures are actually nested within the contour primes in Figure 1, but are
shown separately for readability. Both algorithms require an end activation
instruction, which signals the parent when a child instance is done activating.
The for-loop in the body of FDR produces a for-block, represented by the contour
for in Figure 2. The for-block contains three local data objects: the loop
parameter and two implicit parameters, which are used to initialize the loop
parameter and determine when the loop is to be left.
The contours get num and chk it in Figure 3 represent the accept statements
in the body of CHKR. We refer to such contours as rendezvous-blocks. A
rend exit instruction terminates a rendezvous and leaves the rendezvous-block.
The select instruction c9 models the select statement in the body of CHKR.
Each selective wait alternative produces a pair of arguments specifying the associated
guard and flow of control.
6 Executing the Algorithm for PRIMES
Snapshot 1 shows an initial record of execution for the program PRIMES. It
contains a single processor, denoted by the Greek symbol \Pi. The subscript on
the processor provides a unique name, which we use as a notational convenience
to identify the processor. The superscript gives its state. The horizontal arrow
from the processor represents the instruction pointer. The bent arrow represents
the environment pointer, which is null. The dashed boxes to the left of the
processor show the program inputs (top left box) and outputs (bottom left box),
direct dependences (middle box), and task information blocks (right box), which
identify the entry queues associated with tasks (top half of the task information
blocks) and their execution status (bottom half). 4 For the example execution,
we hypothesize a single input value: 10. Initially, there is no output and there
are no direct dependences. The task instance pri-1 has no entries and it is ready
to execute.
Snapshot 2 shows the record of execution produced from Snapshot 1 by
executing the task enter instruction p1 and the elaborate instruction p2 in the
computation for primes. The task enter instruction allocates and initializes
an execution contour for primes, and moves the executing processor into the
new contour; the elaborate instruction then assigns initial values to the local
data of the new contour, as described below.
The contour created by the task enter instruction defines the base contour
for the executing processor. By convention, we use the name of the processor
as the label for a base contour. The data array is shown in the upper left
corner of the execution contour. The interpreter copies the program names in
the first column of the data array from the declaration array in the algorithm
contour as part of the initialization of the new execution contour. It initializes
the static link of a new contour with the environment pointer of the executing
processor. Thus, the referencing environment of the executing processor determines
the global environment for a new instance. The interpreter then sets the
environment pointer of the executing processor to reference the new contour,
completing execution of the task enter instruction.
The interpreter next executes the elaborate instruction p2, which elaborates
each row in the declaration array of primes. Elaboration of the row for
%FDR initializes the value of the task type %FDR in the data array of contour
pri-1. Task types in Ada are local constants with implicit initial values. The
value of a task type identifies its computation, the global environment required
for the computation, and the names of the entries declared by the task type.
The first two components of the value for a task type form a completed label,
which binds the first instruction in the algorithm of the task type to the environment
in which it is to be executed. 5 The interpreter completes the instruction
pointer given in the declaration array of the algorithm contour, binding it to
the environment pointer of the executing processor. It then copies the set of
entry names declared by the task type from the declaration array, to obtain the
In fact, the contour model extends processors with special components that describe the
information shown in the dependencies diagram and the task information blocks. We display
this information in separate diagrams to help organize the snapshot and make it easier to
read.
5 We also use completed labels to represent procedure values, even though the full generality
of a completed label is not actually needed for representing either task types or procedure
values. Because Ada does not permit assignment to procedures or to task types and does
not allow them to be passed as parameters, the environment pointer in the completed label
that represents a procedure or a task type always references the execution contour in which
it is found. We use completed labels, instead of simple instruction pointers, because of their
generality and for consistency with Johnston's model.
pri-1fdr-1task information blocks
dependencies
I/O
no entries
ready
no entries
"!
#/
act
\Pi run
@
@R
f GET NUM, CHK IT g
NULL
FRONT
CHKR PTR
CHKR
FDR
Snapshot 2: Processor pri-1 executes instructions p1 and p2
Code Indication
ACT The task instance is activating the designated children
COM The task instance is completed and is awaiting termination
of the designated dependents
CRE The task instance has just been created and is waiting to
activate
ECALL The task instance is waiting on the designated entry queue
for its call to be accepted
REND The task instance is in rendezvous with the designated task
SACC The task instance is at a select/accept statement and the
designated alternatives are open

Figure

5: Blocked-waiting codes
initial value for the task type.
Elaboration of the row for FDR creates and initializes a new processor, and
then assigns to FDR a pointer to the new processor. The interpreter uses the
label associated with the task type to initialize the instruction pointer and
environment pointer of the new processor and creates a task information block
containing the entry queues needed for the new task instance. The interpreter
starts the new processor in its activating state but blocks it, since activation of
the new instance must await elaboration of its parent. We circle a processor
that is blocked and maintain information about the conditions upon which it is
blocked in the bottom half of the task information block. Figure 5 summarizes
the blocked-waiting codes used for this purpose. Upon creating a new processor,
the interpreter must also establish a dependency between the new processor and
its direct master. The environment pointer of the executing processor designates
the direct master for a task instance that is elaborated. Finally, a pointer to
the new processor is assigned to FDR. We use a broken arrow to represent a task
value.
Elaboration of the remaining rows of the declaration array in primes is
straightforward. Elaboration of the row for CHKR associates a completed label
and set of entry names to CHKR, as described above. Elaboration of the row
for CHKR PTR assigns an empty collection (set) of CHKR tasks to CHKR PTR. Elaboration
of the row for MAKE CHKR creates a completed label to associate with
MAKE CHKR. Finally, elaboration of the row for FRONT assigns to FRONT the null
access value, which is the default initial value for access objects in Ada.
Snapshot 2 depicts two independent threads of control, represented by the
processors pri-1 and fdr-1. Nevertheless, execution must continue with pri-1,
as fdr-1 is blocked. Snapshot 3 shows the result of executing the activate
instruction p10, which blocks the executing processor and unblocks the proces-
pri-1fdr-1task information blocks
dependencies
I/O
no entries
no entries
ready
act
\Pi run
"!
#/
@
@R
f GET NUM, CHK IT g
NULL
FRONT
CHKR PTR
CHKR
FDR
Snapshot 3: Processor pri-1 executes instruction p10
sor designated by its argument. Thus, fdr-1 is ready to execute, while pri-1
is blocked. The task information block for pri-1 associates the ACT blocked-
waiting code and an activation-waiting set with pri-1, which identifies the tasks
that must finish activating before the blocked processor can proceed with its
computation.
Processor fdr-1 is the only processor that is ready to execute in the next
three machine cycles. Executing instructions f 1-f3 produces Snapshot 4. The
task enter instruction f1 creates the base contour fdr-1 and updates the environment
pointer of the executing processor. The elaborate instruction f2
then elaborates the row for MAX in the declaration array of fdr, which has no
effect as MAX has no initial value. Finally, the end activation instruction f3
changes the state of the executing processor from activating to running and removes
the processor from the activation-waiting set associated with its parent.
As this produces an empty activation-waiting set, the interpreter also unblocks
the parent.
The snapshots presented above show the conventions that govern the placement
of contours and processor symbols and enhance the visual utility of the
diagrams. In particular, we nest an execution contour directly inside the contour
designated by its static link and place a processor symbol immediately within
the contour referenced by its environment pointer. These conventions imply
that the referencing environment of a processor can be determined visually. A
processor can access the data in the execution contours that enclose the processor
but cannot see data in non-enclosing contours. Thus, the static
chain for a processor consists of the contours that enclose the processor symbol,
beginning with the innermost enclosing contour and moving outward to enclosing
contours. The conventions also eliminate the need for explicit static links
and environment pointers, which we therefore omit in subsequent diagrams.
Either of the processors pri-1 or fdr-1 can be selected to execute in Snap-shot
4. We assume that the interpreter selects pri-1 to execute on its next two
machine cycles, producing Snapshot 5. Execution of the complete instruction
for a task completes both the executing processor and its base contour. 6 As
shown in the snapshot, we complete the processor by changing its state and we
complete an execution contour by attaching the superscript com to the contour
name in the dependency diagram. A complete instruction also blocks the executing
processor if, as in the case of pri-1, the contour to be completed has
dependents that have not yet terminated.
On its next machine cycle, the interpreter selects processor fdr-1. Snapshot 6
shows the record of execution produced by executing instructions f4, f5, and
m1. The get instruction f4 assigns the first input value to the variable MAX
and removes the input value from the input diagram. The call instruction f5
first pushes the data required by the called procedure (values of actual input
6 The state of the processor does not change on execution of the complete instruction for
a procedure or block.
fdr-1task information blocks
dependencies
I/O
no entries
ready
no entries
ready
fGET NUM, CHK ITg
fg
NULL
FRONT
CHKR PTR
CHKR
FDR
\Pi run
@ @R
\Pi run
@ @R
Snapshot 4: Processor fdr-1 executes instruction f3
pri-1 comfdr-1task information blocks
dependencies
I/O
no entries
COM
no entries
ready
fGET NUM, CHK ITg
fg
NULL
FRONT
CHKR PTR
CHKR
FDR
"!
#/
\Pi com
\Pi run
Snapshot 5: Processor pri-1 executes instructions p11 and p12:0
task information blocks
dependencies
I/O
no entries
COM
no entries
ready
fGET NUM, CHK ITg
fg
NULL
FRONT
CHKR PTR
CHKR
FDR
"!
#/
\Pi com
\Pi run
pri-1.front
Snapshot executes instruction m1
parameters, references to actual output parameters, return label, etc.) onto the
expression stack of the executing processor. It then retrieves the label value
associated with the procedure and transfers control to the label, by assigning
the instruction pointer and environment pointer in the label to the instruction
pointer and environment pointer of the executing processor. This effectively
moves the processor into the global environment (contour pri-1) required for
the new procedure instance and transfers control to the proc enter instruction
in the algorithm for the procedure. The proc enter instruction, like a task
enter instruction, allocates and initializes a new execution contour and moves
the processor into the new contour. However, the proc enter instruction also
transmits the parameter values that were pushed onto the expression stack of the
executing processor by the call instruction and assigns default initial values to
any parameters that require them (e.g., the second component of NEW CHKR). The
first component of NEW CHKR illustrates the notation for designating a reference
to a cell within a data array: pri-1:front denotes the cell for FRONT in the contour
pri-1. The contour created by the proc enter instruction is not a base contour,
and so we construct a new label for it.
At this point, fdr-1 is once again the only processor ready to execute. Snap-shot
7 shows the result of executing instructions m3:0 and m3:1, which simulate
a call to the task allocator. The create instruction m3:0 creates and initializes
a new processor for a task of type CHKR, adds the new processor to the
collection associated with CHKR PTR, and assigns to NEW CHKR a reference to the
new processor, represented by the solid arrow that points to the processor sym-
bol. Initialization of the processor chkr-1 follows the steps outlined above, in
the discussion of the initialization of processor fdr-1. This time, however, the
new task instance requires two entry queues: one for queuing tasks that call its
GET NUM entry and the other for queuing tasks that call its CHK IT entry. The
entry queues are maintained as ordered lists of processor names. Additionally,
the direct master of an allocated task instance is the contour that elaborates
the access type (CHKR PTR). The activate instruction m3:1 blocks the executing
processor and unblocks the processor designated by NEW CHKR, producing
the snapshot.
In Snapshot 8, the interpreter has gone on to execute the task enter instruction
c1, the elaborate instruction c2, and the end activation instruction
c4. Both processors chkr-1 and fdr-1 are now ready to execute.
We assume that the interpreter selects processor fdr-1 and executes the
ecall instruction m4 on its next machine cycle, producing Snapshot 9. Like
a call instruction, the ecall instruction first pushes the data required by
the accept statement (the remote procedure) onto the expression stack of the
executing processor. However, it then places the executing processor on the
designated entry queue and blocks the processor on the ECALL blocked-waiting
code. We note the entry queue on which the processor is suspended beside the
blocked-waiting code. We also extend the task information block with a stack
diagram in cases where the expression stack of a processor is nonempty. Thus,
s
GET NUM:hi
ready
fGET NUM, CHK ITg
fg
NULL
FRONT
CHKR PTR
CHKR
FDR
"!
#/
\Pi com
"!
#/
\Pi run
pri-1.front
act
Snapshot 7: Processor fdr-1 executes instruction m3:1
s
ready
GET NUM:hi
ready
fGET NUM, CHK ITg
fg
NULL
FRONT
CHKR PTR
CHKR
FDR
"!
#/
\Pi com
\Pi run
pri-1.front
\Pi run
NULL
MY NUM
Snapshot 8: Processor chkr-1 executes instructions c1, c2, and c4
s
ECALL:
chkr-1.GET NUM
GET NUM:hfdr-1i
ready
fGET NUM, CHK ITg
fg
NULL
FRONT
CHKR PTR
CHKR
FDR
"!
#/
\Pi com
"!
#/
\Pi run
pri-1.front
\Pi run
NULL
MY NUM
Snapshot 9: Processor fdr-1 executes instruction m4
the stack diagram in the task information block for fdr-1 shows the value to be
passed in for the rendezvous on GET NUM.
We show a rendezvous in progress between the processors fdr-1 and chkr-1
in Snapshot 10. The snapshot is obtained by selecting processor chkr-1 on
the next three machine cycles, and executing instructions c5:0-c6. The accept
instruction c5:0 checks the entry queue associated with GET NUM. In this case the
presence of a processor on the entry queue shows that there are calls pending
on the entry, so that chkr-1 does not block. Execution of the rend enter
instruction c5:1 then proceeds as follows. The interpreter first creates a new
contour (get num-1) and moves the processor into the new contour, as when
executing a proc enter instruction. It then removes processor fdr-1 from the
entry queue associated with GET NUM, retrieves the value for the formal input
parameter NUM from the expression stack of fdr-1, and updates the blocked-
waiting status for processor fdr-1. Finally, instruction c6 assigns the current
value of NUM to MY NUM, producing the snapshot.
At this point, we assume the interpreter selects processor chkr-1 for three
machines cycles, executing instructions c7-c9, and then selects processor fdr-1
for four machine cycles, executing instructions m5, m6, and f6:0-f6:2. Snap-shot
11 shows the resulting record of execution. The rend exit instruction c7
deallocates the contour get num-1, which was created for the rendezvous; moves
processor chkr-1 into the contour chkr-1, which held the deallocated contour;
and unblocks processor fdr-1, which was engaged in the rendezvous with processor
chkr-1. The select instruction c9 blocks processor chkr-1 on the SACC
blocked-waiting code and associates a select-waiting set with the processor. Although
both of the selective wait alternatives represented by the arguments to
the select instruction are open (the guards are trivially satisfied), neither of the
alternatives is passable. The accept alternative cannot be passed because there
is no call pending on CHK IT and the terminate alternative cannot be passed because
no master of chkr-1 is asleep. The select-waiting set encodes information
about the open selective wait alternatives needed to complete execution of the
select statement. The first element of the select-waiting set for chkr-1 indicates
the presence of an open accept alternative at instruction c10 that begins with
an accept statement for the entry CHK IT, and the second element signals the
presence of an open terminate alternative at instruction c14. The next instruction
that processor chkr-1 will execute is not known at this point, but depends
on which of the open alternatives becomes passable. We reflect this uncertainty
in the snapshot by listing the statements that the processor may next execute
beside its instruction pointer.
Execution of processor fdr-1 now commences at the put instruction m5.
The output diagram shows the value printed by this instruction. The return
instruction m6 simulates the return from the procedure call. The interpreter
first copies the value of NEW CHKR back to the location pri-1.front. It then uses
the label stored at %RET to reset the instruction pointer and environment pointer
of the executing processor and deallocates the contour make-1. The for enter
s
GET NUM:hi
ready
fGET NUM, CHK ITg
fg
NULL
FRONT
CHKR PTR
CHKR
FDR
"!
#/
\Pi com
"!
#/
\Pi run
pri-1.front
NULL
get
\Pi run
Snapshot 10: Processor chkr-1 executes instructions c5:0, c5:1, and c6
s
ready
GET NUM:hi
fGET NUM, CHK ITg
fg
FRONT
CHKR PTR
CHKR
FDR
"!
#/
\Pi com
fdr-110CTR
\Pi run
"!
#/
\Pi run
NULL
Snapshot 11: Processor chkr-1 executes instructions c7, c8 and c9;
and processor fdr-1 executes instructions m5, m6, f6:0, f6:1 and
instruction f6:0 produces the contour for-1, moves the executing processor into
the new contour, and passes in values for %X and %LIM. Instruction f6:1 then
assigns the value of %X to CTR and the compare instruction f6:1 transfers control
to instruction f7.
Snapshot 12 shows the record of execution produced by executing the ecall
instruction f7 for fdr-1. As described above, the interpreter pushes a value for
the formal input parameter on the expression stack of the executing processor,
places the processor on the designated entry queue and blocks the processor.
This time, however since the task information block of the called processor,
chkr-1, indicates that chkr-1 is wating to accept a call on CHK IT, the interpreter
updates chkr-1's instruction pointer and unblocks it.
Having illustrated the main tasking features of our model, we now speed
up execution. Snapshot 13 shows processor fdr-1 after it passes the number 3
to processor chkr-1 in the rendezvous on CHK IT, completes another iteration
of the for-loop, and again calls FRONT.CHK IT, this time to check 4. Processor
chkr-1 has tested 3 for relative primeness with 2 and is in a call to MAKE CHKR to
create a new CHKR task for 3. Processor chkr-2, which was created to execute the
new CHKR task, has activated and executed the accept instruction c5:0, which
blocks chkr-2. As shown in the snapshot, we treat an accept statement as a
select statement with two alternatives: an unguarded accept alternative and a
terminate alternative that is guarded by false.
The ensuing rendezvous with chkr-1 on chkr-2's GET NUM entry assigns a 3 to
the cell for MY NUM in contour chkr-2. When the rendezvous completes, processor
chkr-1 outputs the new prime number and returns from the call to MAKE CHKR.
The return instruction copies the value of NEW CHKR into the cell for NXT CHKR
in contour chkr-1.
The next snapshot shows the effect of passing first 4 and then 5 down the
pipeline. The number 4 fails the check for relative primeness with 2, while 5
passes the checks for relative primeness with both 2 and 3, and so results in the
creation of a new instance of a CHKR task. Similar snapshots can be constructed
to show the results of passing the numbers 6, 7 and 8 down the pipeline. Both
6 and 8 fail the relative primeness check in the first stage of the pipeline, while
7 passes the checks in all three stages, and so adds a new CHKR task.
Snapshot 15 shows the record of execution that is produced if fdr-1 feeds a 9
to chkr-1, which passes the 9 on to chkr-2, and then fdr-1 feeds a 10 to chkr-1,
exits the for-block and terminates. The exit instruction f8:1 deallocates the
contour for-1 and moves the processor into the enclosing contour fdr-1. The
terminate instruction f9 then deallocates processor fdr-1's base contour and
changes the state of the processor to terminated. Note that we do not deallocate
the processor, so that FRONT still designates a task, albeit a terminated
one. Thus, other tasks may call entries belonging to a terminated task and
evaluate its attributes (e.g., its TERMINATED attribute). We also place the
superscript term on the name of the terminated processor in the dependency
diagram to make it evident which dependents of pri-1 must terminate before it
\Omega \Omega \Omega OE
task information blocks
dependencies
I/O
no entries
no entries
ECALL:
GET NUM:hi
ready
fGET NUM, CHK ITg
fg
FRONT
CHKR PTR
CHKR
FDR
"!
#/
\Pi com
fdr-110CTR
"!
#/
\Pi run
\Pi run
NULL
Snapshot 12: Processor fdr-1 executes instruction f7
@
@
chkr-2
task information blocks
dependencies
I/O
no entries
no entries
ECALL:
GET NUM:hi
ready
chkr-2
GET NUM:hi
fGET NUM, CHK ITg
fg
FRONT
CHKR PTR
CHKR
FDR
"!
#/
\Pi com
fdr-110CTR
"!
#/
\Pi run
make-2
\Pi run
chkr-1.nxt chkr
NULL
chkr-2
"!
#/
\Pi run
chkr-2
NULL
MY NUM
Snapshot 13: Processor chkr-1 executes instructions c10-c12, c16,
c17, c19 and m1-m3:1; processor chkr-2 executes instructions c1,
c2, c4 and c5:0; and processor fdr-1 executes instructions f8:0, f6:1
and f7
chkr-2
pri-1 com
no entries
COM
no entries
ready
ready
GET NUM:hi
chkr-2
ready
GET NUM:hi
chkr-3
ready
GET NUM:hi
fGET NUM, CHK ITg
fg
FRONT
CHKR PTR
CHKR
FDR
fdr-110CTR
\Pi run
\Pi run
chkr-15
MY NUM
chkr-2
\Pi run
chkr-25
MY NUM
chkr-3
\Pi run
MY NUM
"!
#/
\Pi com
Snapshot 14: Result of passing 4 and then 5 down the pipeline
chkr-3
chkr-2
pri-1 com
no entries
COM
no entries
ready
GET NUM:hi
chkr-2
ready
GET NUM:hi
chkr-3
ready
GET NUM:hi
chkr-4
ready
GET NUM:hi
fGET NUM, CHK ITg
fg
FRONT
CHKR PTR
CHKR
FDR
\Pi run
MY NUM
chkr-2
\Pi run
chkr-29
MY NUM
chkr-3
\Pi run
chkr-37
MY NUM
chkr-4
\Pi run
MY NUM
\Pi com
"!
#/
Snapshot 15: fdr-1 has terminated and 9 and 10 are in the pipeline
can be unblocked.
The pipeline now consists of four stages: FRONT designates the processor
implementing the first stage of the pipeline. Processors implementing the remaining
stages are found by following the references in the NXT CHKR cells. The
value of MY NUM in the base contour for a processor determines the prime used by
the processor for its relative primeness checks and the value of NEW VAL shows
the next number the processor will check, or, if the processor has completed
a check and has not yet received a request for another check, the last number
checked. The snapshot shows the pipeline with two numbers, which are being
checked concurrently: The first stage is checking 10 for relative primeness with
2 and the second stage is checking 9 for relative primeness with 3.
As both 9 and 10 fail the primeness check when execution continues, we do
not add any additional stages to the pipeline. The four CHKR tasks all eventually
execute their select instructions c9. In Snapshot 16 we show chkr-1, chkr-3
and chkr-4 after they have executed their select instructions and chkr-2 before
it executes its select instruction. The first three processors that execute their
select instructions block, as no accept alternative is passable and their master
is not asleep.
We obtain Snapshot 17 by executing the select instruction c9 for chkr-2
and then the terminate instructions for all the CHKR task instances. This time
the master pri-1 is put to sleep by execution of the select instruction. The
interpreter therefore updates the instruction pointers of the blocked dependents
and of the executing processor so that they reference the terminate instructions
and unblocks chkr-1, chkr-3 and chkr-4. The terminate instructions deallocate
the base contours of the CHKR task instances and change the state of the pro-
cessors. When the last of the CHKR task instances terminates the interpreter
unblocks pri-1.
Finally, pri-1 executes its terminate instruction, producing Snapshot 18.
When deallocating a contour, we deallocate its elaborated tasks and the allocated
tasks in any collections that it contains. In the example, therefore, the
processors fdr-1, chkr-1, chkr-2, chkr-3, and chkr-4 are all deallocated as part
of deallocation of the contour pri-1. This completes a sample execution of the
program PRIMES.
7 Relationship to Other Information Structure
Models
This section highlights the main differences between the contour model of Ada
tasking described above and Johnston's contour model of block structured languages
[17], and discusses the relationship between our model and stack-based
execution models.
While Johnston's contour model and Berry's clarifications of the model [5]
\Omega \Omega \Omega \Omega OE
HY
\Phi \Phi \Phi \Phi \Phi*chkr-4
chkr-3
chkr-2
pri-1 com
no entries
COM
no entries
GET NUM:hi
chkr-2
ready
GET NUM:hi
chkr-3
GET NUM:hi
chkr-4
GET NUM:hi
fGET NUM, CHK ITg
fg
FRONT
CHKR PTR
CHKR
FDR
"!
#/
\Pi run
MY NUM
chkr-2
\Pi run
chkr-29
MY NUM
"!
#/
chkr-3
\Pi run
chkr-37
MY NUM
"!
#/
chkr-4
\Pi run
MY NUM
\Pi com
"!
#/
Snapshot 16: chkr-1, chkr-3 and chkr-4 are blocked on their select
instructions and chkr-2 is preparing to execute its select instruction
\Omega \Omega \Omega \Omega \Omega \Omega OE
HY
\Phi \Phi \Phi \Phi \Phi*chkr-4 term
chkr-3 term
chkr-2 term
pri-1 com
no entries
ready
no entries
GET NUM:hi
chkr-2
GET NUM:hi
chkr-3
GET NUM:hi
chkr-4
GET NUM:hi
fGET NUM, CHK ITg
fg
FRONT
CHKR PTR
CHKR
FDR
chkr-2
chkr-3
chkr-4
\Pi com
Snapshot 17: All CHKR task instances are terminated and pri-1 is
ready to terminate
\Pi run
task information blocks
dependencies
I/O
no entries
Snapshot 18: A terminal snapshot
form the basis for our contour model of Ada tasking, we have altered aspects of
the basic model to accommodate the semantics of Ada tasking. For example,
we refine the notion of the state of a processor to coincide more closely with the
phases in the lifetime of a task and we associate a separate execution status with
a processor. In our model, therefore, the state of a processor does not determine
whether it is eligible to execute, and blocking a processor does not affect its
state. In contrast, the original contour model distinguishes only three processor
states and the states determine the execution status: In the Johnston's model
a processor is either awake, if it is eligible to execute, asleep, if it is blocked, or
terminated, if it has finished executing its algorithm.
We have also modified details of the protocol for subprogram call and return.
In the protocol illustrated by Berry in [5], the procedure call instruction allocates
and initializes the contour for a new procedure activation, evaluates the actual
parameters, copies the parameter values into the new contour, and transfers
control to an enter instruction, which then moves the executing processor into
the new contour. In our protocol, the procedure call instruction evaluates the
actual parameters, pushes them onto the executing processor's expression stack,
and transfers control to the appropriate enter instruction. The procedure enter
instruction then allocates the new contour, moves the executing processor into
the new contour and passes in the parameter values. These modifications allow
us to treat calls to subprograms and calls to entries more uniformly. The entry
call instruction cannot allocate the contour required for the rendezvous or pass
in the parameter values, as the called task may not be ready to execute the
rendezvous and may accept other calls before this one.
Explicit elaboration of the declarations in a program unit are required in
a model of Ada tasking to accurately model the semantics of task creation
and activation. In particular, explicit elaborations allow us to model erroneous
executions caused by race conditions that can occur during the activations of
tasks that share global variables. It also allows us to model programs for which
the activation of certain tasks must be interleaved with the activation and/or
execution of other tasks to avoid deadlock [22]. Additional data structures
and instructions for realizing specific requirements of Ada tasking have been
mentioned in the discussion above. For example, we associate a direct master,
entry queues and blocked-waiting information with each processor, and include
instructions for activating tasks, signaling the end of a task's activation to its
parent, initiating and completing rendezvous, selective acceptance of entry calls,
and so on.
The contour model is a retention model. Program objects (cells) are retained
as long as they are accessible and automatically reclaimed when they become
inaccessible. Our presentation of the model gives explicit rules for reclaiming
storage during execution because often it is not visually apparent when a complex
object, such as a processor or a contour, becomes inaccessible. In this way
deallocation can also be viewed as driven by the execution of various contour
model instructions. However, our model is designed to cause the effect of these
rules to be equivalent to the retention model.
This particular contour model is, therefore, equivalent to stack-based implementation
models, such as described in [12, 16, 19]. Each contour in a record
of execution corresponds to an activation record in the run-time stack of the
processor that creates it. The nested contours enclosing a processor determine
its static chain and the sequence of contours obtained by starting with the innermost
enclosing contour and following the environment pointers within the
contours' return labels to the processor's base contour determine its dynamic
chain. In a stack model for multiprocessing each processor has its own run-time
stack. In our model the base contour of a processor corresponds to the
activation record at the base of the run-time stack for a processor.
8 Conclusions and Future Work
A visual execution model for Ada tasking can help programmers gain a deeper
understanding of the tasking semantics. Our contour model depicts asynchronous
tasks, relationships between the environments in which tasks execute
and the manner in which tasks interact, making it possible to see what happens
during execution of a program. For example, it shows precisely when the activation
of a task instance begins and ends, how the instance synchronizes with its
parent, and when its entries can be invoked. Similarly, it shows relationships between
the referencing environments of concurrent instances. Various properties
of snapshots can be established to motivate the definitions for task dependence
and termination in Ada and demonstrate the interplay between these definitions
and basic run-time management concerns [9].
We have presented our snapshots at the level of abstraction appropriate for
a programmer trying to understand the semantics of Ada tasking. Higher-level
diagrams are required for understanding more complex tasking programs, which
might involve large numbers of interacting task instances. For example, higher-level
instructions can be defined that expand when control flows into them and
conventions can be established that allow the programmer to identify segments
of code to be treated as atomic instructions. Information within execution
contours can also be suppressed to focus attention on the data most important
to understanding how an execution unfolds. For example, references to task
instances and the key data values computed by an instance might be shown in
the data arrays, while return labels and the values of task types and procedures
might be suppressed. Similarly, the task information blocks can be shown using
icons in a circular configuration with directed edges between icons representing
blocked-waiting conditions in order to highlight the information required to
detect deadlocks. The icons can be expanded when necessary to show additional
information relating to the status of task instances.
A mechanical implementation of the contour model is essential if it is to
become a practical tool. An automated interpreter at the level described in
the paper would provide a valuable visual aid for teaching Ada tasking. A more
sophisticated interpreter with capabilities for viewing programs at more abstract
levels would allow a programmer to explore various executions of the same
program, investigate the potential for interaction among tasks, and understand
the effects of different algorithms for scheduling ready tasks. With fairly minor
extensions, an automated interpreter would provide a natural interface for a
tasking debugger [8] or an interleaving symbolic executor [15].

Acknowledgements

.I would like to thank Dan Berry for his generous advice
and thoughtful reviews of many drafts of this paper.



--R

The Approved Ada Language Commentaries
Ada tasking: From semantics to efficient implementation.
Programming in Ada.
Notes on PL/1.
Notes on the contour model.
Treatment of Ada procedures: Aliasing
Oest, editors. Towards a Formal Description of Ada
A debugger for Ada tasking.
Task dependence and termination in Ada.

Concurrent Programming.
Programming Language Concepts.
An Ada tasking demo.
Task state transitions in Ada.
An interleaving symbolic execution approach for the formal verification of Ada programs with task- ing
Fundamentals of Programming Languages.
The contour model of block structured processes.
Programming Language Structures.
Programming Languages: Design and Implementation.
Visible semantics for programming languages.
United States Department of Defense
A contour model of Ada tasking.
Programming Languages
--TR
ADA: Concurrent Programming
Ada: an advanced introduction
Programming language concepts 2/E
Programmming languages: design and implementation (2nd ed.)
Fundamentals of programming languages (2nd ed.)
An Ada tasking demo
A Debugger for Ada Tasking
Towards a formal description of Ada
Programming ADA

--CTR
Laura K. Dillon, Task dependence and termination in Ada, ACM Transactions on Software Engineering and Methodology (TOSEM), v.6 n.1, p.80-110, Jan. 1997
contour model;visual execution model