B. CONTRACT TEST PROBLEMS (Part 2)
B.2.4 DYNAMIC PICTURES
An exercise to show how a graphic display of a dynamic situation can be programmed.
On a display screen a rectangular pattern of e.g. 10 horizontal and 10 vertical lines shall be
drawn. (One might also imagine that the background is a simplified map.)
Within this grid two movable objects shall be shown. They shall be
discriminated either by color or by shape.
The speed and direction of each object shall be controlled by an input-output device,
e.g., a joystick.
There shall be a reset-button, which allows to bring the object into some predefined
position, and a start-button, which causes them to move. If the
objects collide, they shall start to blink and, after some seconds, return
to their homing-position. This shall be equivalent to a RESET.
The 'START' and the 'RESET' button shall be connected to the interrupt-handling mechanism of the
underlying system in a way that different interrupts occur when different buttons are
The controlling input devices shall be purely passive, i.e., the position of the stick (left, right,
forward, reverse) and its deviation from 'position zero', controlling the speed of the objects,
have to be read in explicitly by the program. The position of the input-device
shall be accessible to the program via two 16-bit registers (two bytes), one for each coordinate.
Each byte shall contain a six-bit integer number (right adjusted) which represents the
deflection in this particular direction in the moment of read-in. There exist
all kinds of 'reasonable combinations' of these values, e.g., 15right-60 forward, 56left-10reverse.
The construction of the hardware shall be such that 'unreasonable combinations' cannot occur, like e.g.,
The hardware characteristics of the display-device were mainly left out to prevent
the solutions from becoming too lengthy.
The algorithms shall be independent of the actual characteristics of the display device, e.g.,
it shall not matter whether the display device has a vector generator, or whether it is
just able to plot random points; whether the objects can be created by a pattern
generator, or whether they have to be put together from points and/or lines.
The necessary hardware dependencies should, nevertheless, be clearly identified and as well
localized as possible.
The program shall be written and structured in a way that it will work with the
most primitive display-hardware, e.g. A random-point display, which has
a precision of 10 bits for each coordinate, but that the routines necessary for simulating
more complex display capabilities can be easily removed.
To simply matters, it can be assumed that the lowest level of output-routines need not be
included in the example, i.e., as far as the problem is concerned, the output shall
be regarded as completed, as soon as the coordinates of points (lines, objects, etc.)
have been deposited as integer numbers in the appropriate buffers.
It is left to the designer how he choses to implement the graphic representation, e.g.,
by formatting procedures (similar to character formats) operating on built-in
data types or by special data structures. It is also left to him how he wants to implement the
emergency reaction, e.g., by a software-interrupt or by exceptions.
This problem shows the use of RED in real—time graphics. Information about
each object is kept in a record of TYPE OBJECT. This information includes the
location and current velocity of the object. The velocity information is also given
as a record. The REP (representation) construction of the RED language is used to
map the hardware representation of this velocity information into a record that is
easily manipulable with RED language constructions. The routine READ_JOY_STICK uses
the LOW_IO primitives of RED to effect the input without recourse to machine
The input of the velocity information from the joy stick(s) is poll driven. A
separate task for each object reads the joy stick every so often, redisplays the
figure, updates the information in the record associated with the object, and checks
for a crash. When a crash occurs, a message is sent to the CRASH_MAILBOX.
The main task, SIMULATE_OBJECTS, does a multi-way wait, waiting for any of
three events: the reset button is pushed, the start button is pushed, or a crash is
detected. When one of these events occurs, the appropriate actions are taken. This
may include suspending the objects, which we accomplish by exterminating the tasks.
[It could also be done less drastically by, for example, sending a message to the
B.2.5 A DATABASE PROTECTION MODULE
An exercise to demonstrate how complex synchronization mechanisms can be constructed
on user level.
A DBMS shall contain a module which controls access to given data areas.
The user (or a running process) shall be able to indicate whether he requires
exclusive access to a certain part of a data base ('data-set') or whether
he is willing to share this resource with other users (e.g., for reading).
The respective operations shall look like the following:
By the following operation, the user shall be able to indicate that he no longer
wants to use the data-set:
It shall be possible to specify, either by an executable statement at any time,
or by a kind of declaration at scope entry, or at compile-time:
- whether an exclusive reservation has priority over a shared reservation
- how many users may share a resource (this number be, e.g., be limited by the
length of some waiting queues)
- which users may execute which kind of access
- whether preemption is possible and, if not, whether an exception shall be
raised in case of an attempt to use the preemption parameter
- whether different users have different priorities and, if so, which ones
- whether the demanding process shall just wait for the availability of the desired
resouce or whether, in this case, an exception shall be raised to allow for
Note that 'user' may, in this example, also always mean :'running process'.
The module shall be coded in the complete form it would require to be put in
Proper procedures for cleanups shall be provided in case of preemption.
No specific assumptions as far as the hardware is concerned.
It is the implementor's option whether he prefers to provide one very general
module with all these capabilities, or whether he wants to use generic
facilities to create modules with a proper subset of the
functionalities dependent of the actual requirements at the point of
Our solution illustrates how to get the kind of facilities desired. A dataset
is defined as a record, the fields of which are indicate the kinds of access that
are permitted, and what is presently occurring. This information is:
- The dataset name (type DATASET_NAME)
- PREEMPTION: this indicates whether or not it is permitted to have an
exclusive reservation preempt shared reservations already in progress.
- EXCLUSIVELY: this indicates whether or not someone has exclusively reserved
- MAXIMUM_USERS: how many users, at most, can access the dataset.
- ALLOWED_USERS, ALLOWED_NUM: which users (and how many) are permitted use of
the dataset, if not all users can do so.
- CURRENT_USERS, CURRENT_NUM: which users (and how many) are currently using
The solution illustrates the use of regions, and record processing.
Overloading of procedure names is illustrated in that the names EXCLUSIVE and SHARED
are each given two definitions, depending logically on the information that the user
wants to give about the reservation requested.
In addition, the handling of exceptions is illustrated by the EXCLUSIVE and
SHARED procedures. The GUARD construction is used to trap the raising of exceptions
from procedures called. If the exception raised indicates that the dataset is
presently unavailable, and if the user requested that he would like to wait for its
use, then the procedure WAITs for DELAY_TIME, and then tries again. Other
exceptions -- such as the non-existence of the dataset named -- are RERAISEd and
thus passed back to the user.
B.2.6 A PROCESS CONTROL EXAMPLE
An exercise to test interactions between parallel processing and exception handling.
Assume four processes:
- process b which processes the data it finds in the buffer area
according to some algorithm, and stores them in a 'result area'.
- process c which produces output as a consequence of these data (either in human-oriented
form, or as control-output for the process to be controlled).
- process d monitors and controls these three (and possibly other) processes
and interacts with the operator via a keyboard console.
It shall further be assumed that process a and process b interact in the following
- The buffer is organized as a 'double-buffer', i.e., after one of its two areas
has been filled by process a, b is notified and starts to read out of the buffer,
process a continues by depositing data in the second buffer area. If this is full, process a tries to deposition data in the
first area again. Process b, in turn, notifies process a after having read one data area.
- It is illegal to read a buffer area which has not previously been filled,
and to write into a buffer area which has ot been completely read (except in the initialization
- The program shall be structured in a way that it is possible to replace process a
by appropriate hardware without having to change the program parts for processes
b, c, and d.
It shall also be possible to terminate process a and b at any time without
losing data, i.e., before termination, a cleanup operation shall be invoked
which causes processing of any remaining data in either of the two buffer areas.
No particular assumptions as far as hardware is concerned.
The buffers and the 'result area' can be organized as arrays.
To simplify matters, it can be assumed that actual input-output, i.e., the
communication with the hardware, as well as the processing of the data in process b,
is done by given library routines.
The routine in process d may also be described in a highly
summarized form, because this is not what the example is to test.
The purpose of this example is to show interactions between processes. Two key
features of the example are: (a) double buffering of input, and (b) being able to
stop the processing, on user command, without losing any of the work. We have used
the RED message passing facility to solve these problems.
TASKs A and B are essentially producer and consumer in a double buffering
relationship. The availability of buffers is indicated, in our solution, by passing
messages back and forth. To be precise, when A has a buffer ready for B, A sends a
message that says, "buffer O is ready". When B has finished reading the buffer, B
sends a message back that says "buffer O is free now". The use of the message
facility to solve this problem results in much simpler code than the usual double-
buffering solutions without loss of efficiency.
When task D, which monitors the user, (has received the user command to
terminate the processing that A and B are doing, task D sends a message to A that
says to quit. A then passes this along to B, and A terminates. When B reads this
message (which follows the information that A has already read), then B terminates
as well. Thus, the processing terminates in an orderly manner.
We have chosen to implement process C as a TASK that waits for a message. The
message is in fact the output of TASK B, i.e., the entire "result area" referred to
in the problem text is copied into the message buffer. This illustrates the power
of the RED message passing facility. Alternatively, one could use a signalling
scheme between B and C as already demonstrated between A and B.