B. CONTRACT TEST PROBLEMS (Part 1)
This Appendix contains the ten contract test problems supplied by the
Department of Defense. We have coded solutions to the problems in the RED language,
and have verified their syntactic correctness through the RED Test Translator.
While the problems in the sample were standard kinds of programs that one would
face in systems and applications programming, we found that there was a fair degree
of interpretation required to code the problems. We have made our interpretive
choices in such a way as to indicate the features of the RED language that would be
most useful in the kinds of programming situations indicated by the problems.
In the sequel, we give the original problem texts as they were received by us;
the sample solution, heavily annotated; and some comments about the problem and the
features of RED most highlighted by the sample solution.
B.2 SAMPLE PROBLEMS
B.2.1 POLLED ASYNCHRONOUS INTERRUPT
An exercise to program a device and interrupt handler relying primarily upon polling techniques.
- A channel handler will expect input by the function procedure call
and return a character from that device's input-stream.
There should be a minimum delay from the time a character is introduced
into the circular buffer and the time it may be accessible by a 'read'.
(The input will be displayed on the appropriate crt by the reading process.
Apparent simultaneity of hitting the key and appearance on the crt is desired, i.e.,
the system should be reasonably efficient and, thus, provide
- No input shall be lost.
- A 16-bit, byte-addressable machine
- At least 10 asynchronous input devices (keyboards) sharing I/O channels.
- A hard-wired circular buffer of 128 bytes located at byte-location
500(8). Two pointers are provided in conjunction with the
headpointer - A pointer to the most recent input
tailpointer - A pointer to the tail of the circular input queue
- The I/O channel will initialize both the head- and the tail-pointer to the same location
when the system is reset.
- A difference in the contents of the head- and the tail-pointer indicates that
input has occurred. Maintenance of the head-pointer is the province of the I/O channel.
Maintenance of the tail-pointer is the province of the channel handler.
- No interrupt shall occur whe input is cleared, except as noted in 7 below
The head-pointer is incremented, and the input stored in two bytes specified by
the address contained in the head-pointer.
- An interrupt will occur when the head pointer is pointing to the input-entry just
below the entry indicated by the tail pointer, to indicate that
processing must occur to prevent loss of input.
- The interrupt location for Channel 0 is 440(8) and is two bytes in length
to specify the location of the interrupt handling routine.
- An interrupt causes an implicit call of the specified routine. When processing
of the interrupt has been completed, a return will cause the interrupted process to resume.
- To simplify matters, assume
- the context of the interrupted process is automatically saved and restored, that
- no priority interrupt levels need be considered; and
- no clearing of the interrupt is required.
Each input consists of two bytes:
Byte 0 contains the ASCII character
Byte 1 contains the device identifier, 0-9, to
identify the sending keyboard
It should be tried to formulate the program as hardware-independent as possible,
and clearly separate the interface to the hardware-dependent information.
The following CAPSULE exports a READ routine, which is called from user—level
to read from a terminal.
READ first looks to see if a character is in the mailbox for the terminal, and
also looks through the entire hardware buffer to see if any characters are waiting
there. If this fails, then READ goes into a multi-way WAIT statement, waiting for
either a character to appear in the mailbox associated with the terminal in
question, or for a time-out on a DELAY statement. When the time-out occurs, the
hardware buffer is searched for a character belonging to the terminal in question.
Other characters are sent to the proper mailboxes.
When the hardware buffer is about to overflow, an interrupt dispatches a
message to the INTERRUPT_HANDLER task, which then removes one character from the
hardware buffer, putting it in the appropriate mailbox.
The program illustrates the use of mailboxes as queues for the characters, and
the use of the mailbox in receiving interrupts. Since the input of characters is to
be mainly poll-driven in this example, the interrupt only occurs when the hardware
buffer becomes full.
B.2.2 PRIORITY INTERRUPT SYSTEM
An exercise to program an interrupt kernel supporting four levels of priority.
An interrupt handling mechanism shall be described with the following functional capabilities:
- Higher priority interrupts should be able to preempt lower priority interrupt processes.
- As much processing as possible should be done with higher priority
interrupts enabled. (REMARK: In general, interrupts should only be disabled
for the shortest possible time.)
- A proper mechanism for the resumption of processing of preempted lower
level interrupt (handler)s must be provided.
- To simplify matters, the body of each interrupt handler may be simulated, e.g.,
by a count of the interrupts for that priority level.
- There are four interrupt priority levels: 0, 1, 2, 3. The lower the number,
the higher the priority.
- There is an interrupt vector located at 20(8) with 4 bytes for each priority level:
20(8): PRIORITY 0,24(8):P1,30(8):P2,34(8):P3
These locations specify the address of the interrupt handler for the corresponding
- The interrupt routine is invoked by an implicit call when the interrupt occurs.
At completion of the handler's processing, a return is to be performed.
- To simplify matters, assume that the interrupted processes' context is
automatically saved and restored upon CALL and RETURN. However, the information
concerning the enablement and disablement of interrupts is not part of the context.
- Interrupts are enabled and disabled with a 'set interrupt instruction':
The interrupts to be enabled/disabled are specified by bits 0-3 in the word addressed by the
operand. The bit fields are:
BIT 0(LSB) : PRIORITY 0,BIT 1 : PRIORITY 1, etc.
The values of these fields are:
0 : DISABLE 1 : ENABLE
In order to disable all interrupts, perform an instruction SIN DISABLE ALL,
where the contents of DA=0
- No clearing of the interrupts is required.
Same as for EX 1. It should also be easy to replace the
bodies of the interrupt-handlers (e.g., at runtime, to allow for flexible
reactions to an interrupt, according to circumstances).
The following CAPSULE creates a task for each level of interrupts, and sets the
priorities of those tasks_such that the higher priority the interrupt, the higher
the priority of the associated task. The RED language signals interrupts by putting
messages into mailboxes, so each of the tasks simply waits for a message to be
received. A higher priority interrupt will cause the RED task scheduler to run the
associated higher priority task, thus preempting a lower priority interrupt that may
be in progress.
In considering this problem, we should mention that we considered a more
classical solution, using explicitly manipulated queues for pending interrupts, and
so on. The solution we adopted illustrates the simplicity of using the RED mailbox
concept for interrupt processing. The need for disabling and enabling interrupts
is, of course, handled by the RED interrupt handling code to which the mailboxes are
B.2.3 A SMALL FILE-HANDLING PACKAGE
An exercise to show how higher-level I/O functions can be constructed and used.
Program a file system according to the following specifications:
- Files are built by producers who can perform the following operations:
(filename, estimated size)
The data, contained in 'data-area', are written from a single variable to an
array of structures in memory.
Files are sequential, so each write adds a record to the end. ENDWRITE signals completion
- Files are read by one or more consumers who use the following operation:
READ (filename, record-no, data-area)
Here, data are read from a given record from file 'filename'.
- Once all reading is complete, the file may be destroyed by calling:
Exceptions shall be raised in at least the following cases:
- If a producer wants to create a file with an already existing filename.
- If a user wants to write on a nonexistent file.
- If a consumer wants to read from a nonexistent file, or from an existing
file with a nonexistent record number.
- If a file shall be destroyed while it is still used by somebody else.
Assume a disk as storage medium.
The design should prevent deadlock of file storage, allow disk operations to be
scheduled according to any schedule (where the scheduler goes, should be indicated),
and prevent users from accessing anything but the above five operations.
We have implemented the file directory as an (in-core) link list, the elements
of which are records. These records contain the name, length, plus status and
allocation information. The maximum size for the file is pre—defined by the ESTSIZE
parameter given to the CREATEFILE function. [We used the name CREATEFILE since
CREATE is a reserved word in RED.]
The critical section problem that results by accessing the directory from
different processes is solved by using a DATA_LOCK variable. The RED TASK scheduler U
automatically deschedules tasks that are locked out of access to the directory. No
disk operations per se are kept within the scope of the data locks REGION
statements, so locked time should be held to a minimum.
In order to be able to give a user who is writing the file exclusive access to
the file, we store his task activation in the directory element associated with the
file. This is obtained with the RED “ME" construction, which returns the task
activation pointer for the running task.
We have made several interpretations on the problem, chiefly that there can be
as many readers as needed, but that there can be only one writer at a time [and no
readers while the writer is there].
The chief features of the RED language that this illustrates are: (a) the ease
of mutual exclusion through the REGION concept; (b) the use of exceptions, such as
those that are raised when the file is not present or when someone is already
writing it; (c) the ease of invoking the task scheduler.