B.   CONTRACT TEST PROBLEMS (Part 2)


B.2.4  DYNAMIC PICTURES


EX 4

PURPOSE:
An exercise to show how a graphic display of a dynamic situation can be programmed.

PROBLEM:
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.

ASSUMPTIONS:
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 pressed.

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., 10left-20right.

GUIDELINES:
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.

DISCUSSION:
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 language.

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 task.]

B.2.5  A DATABASE PROTECTION MODULE


EX 5

PURPOSE:
An exercise to demonstrate how complex synchronization mechanisms can be constructed on user level.

PROBLEM:
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:

1. whether an exclusive reservation has priority over a shared reservation

2. how many users may share a resource (this number be, e.g., be limited by the length of some waiting queues)

3. which users may execute which kind of access

4. whether preemption is possible and, if not, whether an exception shall be raised in case of an attempt to use the preemption parameter

5. whether different users have different priorities and, if so, which ones

6. 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 evasive action

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 a library.

Proper procedures for cleanups shall be provided in case of preemption.

ASSUMPTIONS:
No specific assumptions as far as the hardware is concerned.

GUIDELINES:
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 instantiation.

DISCUSSION:
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:

1. The dataset name (type DATASET_NAME)

2. PREEMPTION: this indicates whether or not it is permitted to have an exclusive reservation preempt shared reservations already in progress.

3. EXCLUSIVELY: this indicates whether or not someone has exclusively reserved the dataset.

4. MAXIMUM_USERS: how many users, at most, can access the dataset.

5. ALLOWED_USERS, ALLOWED_NUM: which users (and how many) are permitted use of the dataset, if not all users can do so.

6. CURRENT_USERS, CURRENT_NUM: which users (and how many) are currently using the dataset.

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


EX 6

PURPOSE:
An exercise to test interactions between parallel processing and exception handling.

PROBLEM:
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 specific way:

• 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 phase).

• 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.

ASSUMPTIONS:
No particular assumptions as far as hardware is concerned.

The buffers and the 'result area' can be organized as arrays.

GUIDELINES:
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.

DISCUSSION:
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.