B.   CONTRACT TEST PROBLEMS (Part 1)


B.1  INTRODUCTON

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


EX 1

PURPOSE:
An exercise to program a device and interrupt handler relying primarily upon polling techniques.

PROBLEM:

1. A channel handler will expect input by the function procedure call

         'read(DEVICE-NUMBER)'

   and return a character from that device's input-stream.

2. 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 good response-time.)

3. No input shall be lost.

ASSUMPTIONS:

1. A 16-bit, byte-addressable machine

2. At least 10 asynchronous input devices (keyboards) sharing I/O channels.

3. A hard-wired circular buffer of 128 bytes located at byte-location 500(8). Two pointers are provided in conjunction with the circular buffer:

   headpointer - A pointer to the most recent input
   tailpointer - A pointer to the tail of the circular input queue

4. The I/O channel will initialize both the head- and the tail-pointer to the same location when the system is reset.

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

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

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

8. The interrupt location for Channel 0 is 440(8) and is two bytes in length to specify the location of the interrupt handling routine.

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

10. To simplify matters, assume
    1. the context of the interrupted process is automatically saved and restored, that

    2. no priority interrupt levels need be considered; and

    3. no clearing of the interrupt is required.

       3.5(REMARK)
       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

GUIDELINES:

It should be tried to formulate the program as hardware-independent as possible, and clearly separate the interface to the hardware-dependent information.

DISCUSSION:

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


EX 2

PURPOSE:
An exercise to program an interrupt kernel supporting four levels of priority.

PROBLEM:
An interrupt handling mechanism shall be described with the following functional capabilities:

1. Higher priority interrupts should be able to preempt lower priority interrupt processes.

2. 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.)

3. A proper mechanism for the resumption of processing of preempted lower level interrupt (handler)s must be provided.

4. To simplify matters, the body of each interrupt handler may be simulated, e.g., by a count of the interrupts for that priority level.

ASSUMPTIONS:

1. There are four interrupt priority levels: 0, 1, 2, 3. The lower the number, the higher the priority.

2. 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 priority level.

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

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

6. Interrupts are enabled and disabled with a 'set interrupt instruction':

         SIN <operand>

   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

7. No clearing of the interrupts is required.

GUIDELINES:

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

DISCUSSION:

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

B.2.3  A SMALL FILE-HANDLING PACKAGE


EX 3

PURPOSE:
An exercise to show how higher-level I/O functions can be constructed and used.

PROBLEM:
Program a file system according to the following specifications:

1. Files are built by producers who can perform the following operations:

   CREATE	(filename, estimated size)
   WRITE	(filename, data-area)
   ENDWRITE	(filename)

   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 of writing.

2. 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'.

3. Once all reading is complete, the file may be destroyed by calling:

         DESTROY (filename)

   Exceptions shall be raised in at least the following cases:

   1. If a producer wants to create a file with an already existing filename.

   2. If a user wants to write on a nonexistent file.

   3. If a consumer wants to read from a nonexistent file, or from an existing file with a nonexistent record number.

   4. If a file shall be destroyed while it is still used by somebody else.

ASSUMPTIONS:
Assume a disk as storage medium.

GUIDELINES:

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.

DISCUSSION:

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.