Lecture notes for 22C:116 Introduction to System Software, by Douglas W. Jones, University of Iowa Department of Computer Science
The polled input/output routines presented in the previous chapter work, but they severely limit system performance. They make no provision for overlap of input/output activity and computation, and they make no provision for simultaneous input/output to multiple devices. This may be acceptable on small personal computers, but even on single-user systems, users are sometimes annoyed by such things as the inability of the system to respond to keyboard input at the same time it is doing disk input/output.
The basic problem is that the input/output drivers can 'capture' the CPU and and tie it up in a polling loop until the I/O is completed. Thus, to allow overlap of computation and input/output, or to allow simultaneous operations on multiple devices, the polling loops must be moved out of the input/output drivers! When this is done, input/output operations by user programs do not directly initiate data transfers to devices and then await their results. Instead, a call to a device driver by a user program simply places data in a queue or takes data from a queue; the status of the device must still be polled so that data can be transferred to or from the queue whenever the device is ready.
There are essentially three places that the polling burden can be moved:
Whenever multiple devices are supported, a second problem arises, that of buffering. If data arrives from an input device while the program is dealing with an output device, the input data must be held somewhere until the program can process it. Similarly, if a program produces more output than an output device can transfer in one operation, the excess data must be stored somewhere so that the program can continue processing. Of course, the applications program must stop and wait for input when there is nothing in the input buffer at the time data is needed, and it must stop and wait when it produces more data for output when the output buffer is full, but outside of these limiting cases, we would like the application to be able to run essentially continuously, in parallel with input/output activity.
For simple character sequential devices, it is easy to implement the input and output buffers as first-in first-out queues, with the operations documented in Figure 10.1.
- enqueue(q,c) or q.enqueue(c)
- puts the character c at the tail of the queue q, illegal if q is full.
- c = dequeue(q) or c = q.dequeue
- gets the character c from head of the queue q, illegal if q is empty. The character returned it the one that was farthest in the past.
- full(q) or q.full
- returns true if q is full.
- empty(q) or q.empty
- returns true if q is empty.
Figure 10.1. A specification of first-in first-out queues.
It should be noted that, for terminal (combined keyboard and display) devices, there are a number of possible ways of using such queues that differ in the way they handle echoing and line buffering; for the moment, we will ignore this complexity!
As with any abstract data type, we can completely divorce the question of how queues are implemented from how queues are used. There are many implementations of queues, but for our purposes, all are equivalent so long as they support operations analogous to those given in Figure 10.1.
The oldest solution to the problem of overlapping computation with input/output is to enclose the entire main program inside a single giant polling loop, the main polling loop or just the main loop. This can greatly distort the logic of the applications program but it makes it easy to see how it allows multiple devices to perform simultaneous input/output operations.
The main polling loop structure is common in some found in older real time or process control systems. A process-control system is a computer system which controls a process; as an example, consider the computer system in a chemical plant which controls the reactor in which ethylene is converted to polyethylene. A real-time system is one where there are deadlines by which certain actions must be taken; in an ethylene reactor, the computer must adjust the settings of the pumps and valves in response to the temperature and pressure every few seconds to keep the reaction under control.
This approach is also common in some transaction processing and event processing systems, not only old ones such as the CICS system that is still widely used in IBM mainframe environments, but also under many modern window managers in common use today. In such systems, each user action is represented by a transaction or event that is sent to the program's input queue. The outer loop of the program gets one event notice or transaction record per iteration, where, depending on the context, transactions may be as complex as web-server requests containing the results of filling out a form, or as simple as individual mouse clicks and keypresses.
Figure 10.2 illustrates the global structure of a main polling loop in the context of a single input device and a single output device, each with a status register and a data register.
repeat {main polling loop} if (inp( inputstatus ) = ready) and (not full( inputqueue )) then enqueue( inputqueue, inp( inputdata )); if (inp( outputstatus ) = ready) and (not empty( outputqueue )) then outp( outputdata, dequeue( outputqueue )); application; forever;Figure 10.2. The main polling loop structure, in Pascal.
In the above, the procedure call to application does all the useful work. On any given call to application, nothing might be done, for example, when an insufficient amount of information is available in the input queue or when the output queue is full, or quite a bit might be done. We must usually limit the time taken by any given call to application, however, because most devices must be checked at some minimum frequency. For example, a 9600 baud communications line can transmit 960 characters per second (8 bits data, 1 start bit, 1 stop bit), so if such a communications line is connected to our input, one call to application must not take longer than 1/960 of a second.
To see how the use of a main polling loop distorts the structure of an application, consider the rather stupid little application described in Figure 10.3.
repeat ch = read; if ch <> 'z' then begin if ch = 'x' then write( ch ); write( ch ) end; until done;Figure 10.3. A simple application, in Pascal.
The application in Figure 10.3 copies its input to its output, deleting all occurrences of 'z' from the input and doubling all occurences of 'x'. So, if the input is 'azyxzyb,' the output will be 'ayxxyb.' As is typical of many applications, the amount of output depends in part on the amount of input; in this case, so long as there are no 'x' or 'z' characters, the amount of output exactly matches the amount of input. However, for some inputs, the output will be much smaller than the input, for example, if there are many 'z' characters in the input, and for other inputs, the output will be much bigger than the input, for example, if there are many 'x' characters. As a result, sometimes, the input queue may tend to fill because the program is blocked by a full output queue, and other times, the output queue may run empty because the program is blocked awaiting for more input.
The application shown in Figure 10.3 can be embedded in the main polling loop shown in Figure 10.2 using the code in Figure 10.4.
procedure application; { ch is global, but not used elsewhere } { state is global, not used elsewhere, and has initial value 1 } begin case state of 1: if not empty( inputqueue ) then begin { read a character } dequeue( inputqueue, ch ); if ch <> 'z' then begin if ch = 'x' then state := 2 else state := 3 end; end; 2: if not full( outputqueue ) then begin { write an extra 'x' } enqueue( outputqueue, ch ); state := 3; end; 3: if not full( outputqueue ) then begin { write the character } enqueue( outputqueue, ch ); state := 1; end; end { case }; end { application };Figure 10.4. The code from Figure 10.3 changed to fit Figure 10.2.
In the code in Figure 10.4, the logical control structure of the application has been hidden in the sequence of values taken on by the variable state; thus, assignments to this variable have the effect of goto statements transferring the flow of control between the alternative cases. On any particular call to application, only one case will be executed, but because application is embedded in the main polling loop, we may read the program as if the flow of control was from one case to another as determined by the assignments to state at the end of each case.
The example used in Figures 10.3 and 10.4 was very simple, but this approach, adding state variables and converting control structures into selection among cases embedded in an outer loop is universal. Any program can be rewritten using just one outer loop plus a state variable per function called and a case selection replacing the control structure of the body of that function, with if statements used where needed to determine the assignment of values to the state variable at the end of each case.
Although the main polling loop approach is completely general, in that any program can be converted to this form, it is hardly convenient to rewrite easily understood code into strange amalgams of case selections and state variables. Programs are far more maintainable if the obvious control structures actually relate to the algorithm being implemented and not to the strange constraints of the input-output environment. This can be done by packaging the device polling operations used in the main polling loop into a subroutine, call it poll, and by replacing the requirement that the loop iterate at least n times per second with the requirement that the application must call poll at least n times per second.
Figure 10.5 illustrates the use of a polling procedure to support the application from Figure 10.3 using the device interface code from Figure 10.2 copied verbatim, with no changes at all.
procedure poll; begin if (inp( inputstatus ) = ready) and (not full( inputqueue )) then enqueue( inputqueue, inp( inputdata )); if (inp( outputstatus ) = ready) and (not empty( outputqueue )) then outp( outputdata, dequeue( outputqueue )); end { poll }; function read: char; begin while empty( inputqueue ) do poll; read := dequeue( inputqueue, ch ); end; procedure write( ch: char ); begin while full( outputqueue ) do poll; enqueue( outputqueue, ch ); end; begin { main program } repeat ch = read; if ch <> 'z' then begin if ch = 'x' then write( ch ); write( ch ); end; poll; forever; end { main program };Figure 10.5. The polling procedure approach.
Note that the main program is almost exactly the same as the code in Figure 10.3, with only the addition of a call to poll added in the body of the loop. The read, write, and poll routines, as well as the implementation of the queue abstract data type, can be viewed as the 'operating system' which is needed to support this code. Note that, within read and write, there are polling loops waiting not for the associated devices to be ready, but for space or data in the appropriate queues. Because these polling loops contain calls to poll, output can continue to be passed from the output queue to the output device while the program is blocked waiting for data to arrive in the input queue.
The polling procedure approach is not only adequate but it is reasonably easy to use. All you usually need to remember is to insert a call to poll in the body of each loop in the program. As a result, this is the recommended approach to handling multiple peripheral devices on systems where interrupt hardware is not available. The primary problem with this approach arise when an attempt is made to optimize the polling, avoiding the overhead of too many calls to poll by omitting calls from within short definite loops. This requires a careful check of the run-time of each section of code, and with modern computers, estimating the run-time of a section of code can be very difficult.
Interrupt hardware was invented to eliminate the need for explicit calls to a polling procedure from within applications code. In effect, what the basic interrupt mechanism does is check all of the relevant device status bits just after executing each and every machine instruction, inserting a call to an interrupt handler, analogous to our poll routine, whenever some device is ready. So long as no devices need service, this allows the computer to execute instructions at full speed. In general, an interrupt can be viewed as a hardware-initiated call to a procedure. In effect, the instruction execution loop of the central processor has been made to serve as the main polling loop of our application!
Although the abstract description of an interrupt as a hardware initiated procedure call applies to most interrupt hardware, the details vary considerably from machine to machine. The address of the interrupt service routine is frequently stored in a special register or dedicated memory location, called the interrupt vector. On some machines, calls to interrupt service routines parallel procedure calls to the extent that the normal procedure return can be used to return to the code which was running at the time of the interrupt, while on others, special return-from-interrupt instructions must be used. In most of this discussion, interrupt service routines will be coded as conventional procedures.
Once an interrupt service routine has been called, it is essential that the hardware request for that service be disabled or withdrawn. If it were not, an infinite (and possibly recursive) loop would result in which, after executing the first instruction of the interrupt service routine, the hardware would force a control transfer to the start of the same interrupt service routine. On some systems, the interrupt is automatically disabled by the actions of the central processor hardware when it responds to the interrupt, while on others, the first instruction of each interrupt service routine must disable the interrupt. In the examples presented here, it will be assumed that the hardware automatically disables interrupts.
Even if the hardware can disable interrupts, the software must also be able to enable or disable them. For example, on return from an interrupt service routine, after the software has done whatever the interrupt requested, the software must re-enable the interrupt as it returns to the the code which was interrupted. Furthermore, if the output queue is empty, there is no point in responding to an interrupt from the output device when it is ready to transfer more data; a similar argument can be made when the input queue is full. On most machines, there are special instructions to enable and disable interrupts; on some, these instructions apply to all interrupts at the same time, while other machines allow groups of devices to be enabled or disabled as a group. In addition, it is usual to include, in each device's control register, one or more interrupt enable bits corresponding to each condition the device can sense that might be cause for an interrupt request. If the interrupt enable bit for a condition is set, then when that condition is detected, there will be an interrupt request.
It should be noted that the disabling an output device's ability to request interrupts when the output queue is empty and enabling that device when data is put in the queue is a special purpose solution to a general problem, the producer-consumer problem. The device is the consumer, and the application is the producer, and the general problem is to prevent the consumer from attempting to use data that has not yet been produced. In any producer-consumer system, whether the system is all in hardware, all in software, or mixed between the two, there must be some synchronization mechanism to make the consumer wait until data is available!
The asynchronous communications line interface commonly used on the IBM PC compatable family of computers is a good example for illustrating the use of interrupts. Each of the asynchronous communications ports COM1 through COM4 has its own data, control and status registers. The complete specification of the registers relevant to interrupts on these machines is given in Figure 10.6:
_______________ 3F8 COM1DATA |_______________| 8 bits in/out _______________ 3F9 COM1IE interrupt enable |_______|_|_|_|_| unused | | | | RxRD - received data ready | | | RxRD TBE - transmit buffer empty | | TBE ERBK - error, overrun or break | ERBK SINP - secondary input change SINP _______________ 3FA COM1II interrupt identity |_________|___|_| unused | | | PND = 0 - interrupt pending | | PND ID ID = 00 - secondary input change ID = 01 - transmit buffer empty ID = 10 - receive data ready ID = 11 - error, overrun or break _______________ 3FD COM1STAT |_|_|_|_|_|_|_|_| unused | | | | | | | RxRD - received data ready | | | | | | RxRD OVRE - overrun error | | | | | OVRE PARE - parity error | | | | PARE FRME - frame error | | | FRME BREK - break | | BREK TBE - transmit buffer empty | TBE TXE - transmission done TXEFigure 10.6. Control and status bits for the PC COM1 port.
The data register has been amply discussed in Chapter 9. The interrupt enable register is new; the bits in this determine which sources of interrupts will cause this device to request an interrupt. For example, the COM1 port will request an interrupt when received data is ready only when the RxRD status bit is 1 and the RxRD interrupt enable bit is also 1. Similarly, the COM1 port will request an interrupt if the TBE status bit is 1 and the TBE interrupt enable bit is also 1.
After an interrupt is requested by the hardware, the interrupt identity register contains a code indicating what caused the interrupt. The hardware automatically retracts interrupt requests when the conditions that caused them are dealt with. So, reading the data register clears the RxRD status bit, writing new data to the data register clears the TBE status bit, and reading the status register clears the error indicators themselves.
The code shown in Figure 10.7 uses interrupts to implement the read and write routines required by the example application code given in Figure 10.3, using the interface from Figure 10.6.
procedure com1interrupt; { control reaches here whenever there is any interrupt request from the COM1 port } var id: integer; begin { first, find out what interrupt this is } id := inp( COM1II ) DIV 2; { second, dispatch to the appropriate routine } case id of 0: ... ; 1: com1transmit; 2: com1receive; 3: ... ; end; end { com1interrupt }; procedure com1receive; var stat: integer; data: char; begin { we know the RxRD status bit is 1, but so what } stat = inp( COM1STAT ); if testbit( stat, STATRxRD ) and not full( com1inqueue ) then begin { get the data } data := inp( COM1DATA ); enqueue( com1inqueue, data ); end; if full( com1inqueue ) then begin { disable the RxRD interrupt } stat := inp( COM1IE ); clearbit( stat, IERxRD ); outp( COM1IE, stat ); end; end { com1receive }; procedure com1transmit; var stat: integer; data: char; begin { we know the TBE status bit is 1, but so what } stat := inp( COM1STAT ); if testbit( stat, STATTBE ) and not empty( com1outqueue ) then begin { output the data } data := dequeue( com1outqueue ); outp( COM1DATA, data ); end; if empty( com1outqueue ) then begin { disable the TBE interrupt } stat := inp( COM1IE ); clearbit( stat, IETBE ); outp( COM1IE, stat ); end; end { com1transmit }; function read: char; begin { wait for data to be available } while empty( com1inqueue ) do { nothing }; { get the data } read = dequeue( com1inqueue ); { enable RxRD interrupt } stat := inp( COM1IE ); setbit( stat, IERxRD ); outp( COM1IE, stat ); end { read }; procedure write( ch: char ); begin { wait for space in queue } while full( com1outqueue ) do { nothing }; { put the data } enqueue( com1outqueue, ch ); { enable TBE interrupt } stat := inp( COM1IE ); setbit( stat, IETBE ); outp( COM1IE, stat ); end { read };Figure 10.7. Use of interrupts for the COM1 port.
The com1interrupt routine is called whenever the COM1 hardware requests any interrupt. It's job is to check to see what the cause of the interrupt was and dispatch control to subsidiary interrupt service routines. The details of how the hardware interrupt mechanism dispatches control to the com1interrupt routine are not covered here, but it is important to know that, during the execution of com1interrupt or any routines called from it, no other interrupts from any communications port are allowed. On the IBM PC, fast devices such as disks may request interrupts during the execution of interrupt service routines for slow devices like asynchronous communications ports, but we can ignore this possibility in this discussion.
There are 4 possible reasons the COM1 port may request an interrupt, including errors and secondary input changes that will be ignored here. The remaining possibilities are that the transmit buffer is empty, allowing a new character to be transmitted by the software, or that the receive buffer contains a character ready to be processed by software. In the former case, com1interrupt calls com1transmit; in the latter case, it calls com1receive.
The com1receive routine is called each time a new character of input becomes available. It begins by verifying that input is available. Assuming that the remaining code is correct, this shouldn't be required, but it seems reasonable to refuse to read the input if the RxRD bit is not set in the status register or if the input queue has no space for the new character. If all is well, we read the character from the data register and enqueue it on the input queue.
The com1receive routine finishes with a check of the queue status. If the received character did not fill the input queue, the routine returns normally, and, on return from interrupt, the interrupted program will be resumed, and perhaps later, another interrupt will signal the arrival of the next character. If, on the other hand, the input queue is full, the RxRD bit of the COM1 port's interrupt enable register is reset, thus preventing any future interrupts announcing that input data is available until the queue is no longer full.
Of course, this requires that the read routine for the COM1 port re-enable the interrupt, setting the RxRD bit of the COM1 port's interrupt enable register after it makes space in the queue. We only need to do this when the queue was full prior to the dequeue operation, but the code given in Figure 10.7 does this after each dequeue. The read routine begins with a little polling loop, waiting for space in the input queue; interrupts during this polling loop may service any device, and the polling loop will exit if an COM1 interrupt puts something in the queue.
The code shown in Figure 10.7 contains one serious flaw, specifically, in both the read and write routines, there are 3-line sequences of code that begin by reading the interrupt enable register, edit the value read, and then output that value back to the interrupt enable register. The problem is, what happens if an interrupt occurs during such a sequence of instructions, and more specifically, what if it is an input or output interrupt that, itself, makes some change to the interrupt enable register?
A sequence of instructions such as this is called a critical section. It is a section of code where it is critical that no interrupt be allowed, or more specifically, that no other activity that uses the same variable be allowed. In this case, the variable is the interrupt enable register for the COM1 port.
There are several solution to the critical section problem, depending on whether it is a long critical section or a short one, and depending on wheter the machine has just one CPU or many CPUs. The solution we will use here is one appropriate for short critical sections on uniprocessors. This is quite simple, just disable all interrupts for the duration of the critical section, as shown in Figure 10.8.
function read: char; begin { wait for data to be available } while empty( com1inqueue ) do { nothing }; { get the data } read = dequeue( com1inqueue ); { enable RxRD interrupt -- a critical section } disableints; stat := inp( COM1IE ); setbit( stat, IERxRD ); outp( COM1IE, stat ); enableints; end { read }; procedure write( ch: char ); begin { wait for space in queue } while full( com1outqueue ) do { nothing }; { put the data } enqueue( com1outqueue, ch ); { enable TBE interrupt -- a critical section } disableints; stat := inp( COM1IE ); setbit( stat, IETBE ); outp( COM1IE, stat ); enableints; end { read };Figure 10.8. Protecting critical section in code from Figure 10.7
The code shown in Figure 10.8 replaces the final to routines in Figure 10.7. The only change is the addition of a call to disableints before each critical section and a call to enableints after each critical section. In fact, most computers include a pair of machine instructions, one that globally enables all interrupts, and one that globally disables all interrupts, and the subroutine calls to disableints and enableints could be replaced directly by these two instructions, but most high level language compilers cannot do this; instead, we write these two trivial assembly language subroutines to use these special machine instructions.
The first-in, first-out queues used in the above input/output implementations provide communication between the user code and the device using the enqueue, and dequeue operations, and they provide synchronization using the tests for a full or empty queue. These operations were informally defined in Figure 10.1, but now, it is time to give implementation details. One common implementation of the queue abstract data type uses a linked list to represent each queue. The other, given in Figure 10.9, uses bounded buffers.
type queue = record head, tail, count: integer { initially zero }; buffer: array [0..size] of char; end; procedure enqueue( var q: queue; ch: char ); begin q.count := q.count + 1; q.buffer[ q.tail ] := ch; q.tail := (q.tail + 1) mod (size + 1); end { enqueue }; function dequeue( var q: queue ): char; begin q.count := q.count - 1; dequeue := q.buffer[ q.head ]; q.head := (q.head + 1) mod (size + 1); end { dequeue }; function full( var q: queue ): boolean; begin full := (q.count = (size + 1)); end { full }; function empty( var q: queue ): boolean; begin empty := q.count = 0; end { empty };Figure 10.9. A simple bounded buffer queue implementation.
In the code in Figure 10.9, it has been assumed that the head pointer always points to the next item to be dequeued from the queue (if there is one), and thus must be incremented after use; similarly, the tail pointer always points to the next free space ready to be used when new data is enqueued, so it must also be incremented after use. Variations are possible where the pointers are incremented before use or where one is incremented before and one after use. Note that this code does not prevent an attempt to dequeue from an empty queue or enqueue in a full queue. Additional code could be added to check for this, but it should be unnecessary except for debugging because the users of this code are expected to provide all necessary synchronization by testing for queue full before enqueueing, and by testing for queue empty before dequeueing.
The bounded buffer implementation shown in Figure 10.9 is entirely sufficient for use in the main polling loop and polling procedure solutions to overlapping of processing with data transfers, but it will not suffice for the interrupt solution. Again, we have a critical section problem! what would happen if, as the user program was enqueueing a character on the output queue, the output device requested an interrupt causing a character to be dequeued from the output queue. If this happens while the enqueue operation is in the middle of incrementing the count of items in the queue, the sequence of operations shown in Figure 10.10 may occur.
actions in enqueue actions in dequeue 1) register := q.count + 1; 2) interrupt 3) q.count := q.count - 1; 4) return 5) q.count := register;Figure 10.10. Interrupts in the context of Figure 10.9.
To understand Figure 10.10, note first that many modern CPUs do not include instructions to directly increment or decrement a variable in memory; instead, typical modern CPUs must load this variable in a register, then decrement it, and then store the result in memory. It is quite possible that an interrupt will occur between any pair of consecutive instructions unless this is prevented, so here we have another example of a critical section.
We could fix the code from Figure 10.10 in exactly the way the code from Figure 10.7 was fixed in Figure 10.8, by disabling all interrupts before each critical section and enabling them after each critical section, but there is another solution, the complete elimination of the count of items in the queue. The key to doing this is to note that, for both a full queue and an empty queue, the head and tail pointers will be equal! This is illustrated in Figure 10.11.
_ _ _ _ _ _ _ _ _ _ An empty queue: |_|_|_|_|_|_|_|_|_|_| | count = 0, empty head = tail After enqueue(X) _ _ _ _ _ _ _ _ _ _ enqueue(Y) |_|_|_|_|_|_|X|Y|_|_| | | count = 2 head tail After enqueue(Z) _ _ _ _ _ _ _ _ _ _ enqueue(W) |_|_|_|_|_|_|X|Y|Z|W| | | count = 4 tail head _ _ _ _ _ _ _ _ _ _ After more enqueues |A|B|C|D|E|F|X|Y|Z|W| | count = 10 tail = head _ _ _ _ _ _ _ _ _ _ After two dequeues |A|B|C|D|E|F|_|_|Z|W| | | count = 8 tail head _ _ _ _ _ _ _ _ _ _ After two more dequeues |A|B|C|D|E|F|_|_|_|_| | | | count = 6 head tail headFigure 10.11. A sequence of operations on a queue of length 10.
If enqueueing data causes the head and tail pointers to become equal, then the queue has been filled. If dequeueing data causes the head and tail pointers to become equal, then the queue has been emptied. Note that the relative order of the head and tail pointers has absolutely no bearing on whether or not the queue is full or empty! It should also be noted that only the enqueue routine modifies the value of the tail pointer and only the dequeue routine modifies the value of the head pointer; thus, there are no critical sections involving these pointers as long as there is only one producer and one consumer for data from the queue.
Using the above observation, we can detect queue full after enqueue and queue empty after dequeue, but these rules do not allow for a separate predecate to distinguish between the full and empty conditions by comparing the head and tail pointers. We can solve this if we forbid the queue from filling, reserving the condition where the pointers are equal to mean queue empty. If we do this, the queue full condition must be indicated by the fact that there is exactly one free space, or that the head pointer is one location behind the tail pointer. The code for testing for the full and empty conditions using this approach is given in Figure 10.12.
function full( var q: queue ): boolean; begin full := ((q.tail + 1) mod (size + 1)) = q.head); end { full }; function empty( var q: queue ): boolean; begin empty := (q.head = q.tail); end { empty };Figure 10.12. Eliminating the need for a count field.
It's interesting to note that the storage requirements for the queue may not have been changed by this scheme! We have eliminated the count field at the expense of one item in the queue. One character is typically only 8 bits, and if the queue size is under 256 bytes, the count field could have been an 8 bit counter! In modern practice, larger queues are quite common, so eliminating the count field at the expense of one character of queue capacity leads to a net improvement in storage utilization.
When you type on the keyboard, you usually expect to see what you typed echo on the display screen. When queues are used for terminal input/output, there are a number of possible ways of handling this echoing. These are described in Figure 10.13.
hardware | software
---------- ----------- -------------- ------
| display |--<--| interface |-<---| output queue |-<-------| |
---------- ----------- -------------- | | | |
| | | |3 | | | user |
|1 | |2 --------->---------- |4 | |
| | | | | | code |
---------- ^ ----------- ^ | -------------- ^ | |
| keyboard |-->--| interface |-->--| input queue |-->------| |
---------- ----------- -------------- ------
|
Figure 10.13. Alternate approaches to echoing.
The alternatives outlined in Figure 10.13 are:
The user will be able to distinguish between paths 1 and 2, on the one hand, and path 3, on the other hand, only if the user types while the application is sending output to the screen, and even then, the result is likely to be subtle. With paths 1 and 2, typed input will be echoed immediately, while with path 3, typed input will be delayed. In both cases, however, typed input will be jumbled into the stream of output, so it may be difficult to observe which echo path is being used.
Finally, paths 1 and 2 are usually indistinguishable, except on systems that actually lock the keyboard when the communications line is configured for output, and then unlock it when input is permitted.
It should be noted that, although queues are used with most devices on large systems, the keyboard input queue is the only queue which users are usually directly aware of. As a result, it has earned a name of its own, the type-ahead buffer. This name accurately describes the function of the keyboard input queue: It allows users to type ahead of any request from the applications program for input.
On devices such as magnetic tape, where data is transferred one block at a time instead of one character at a time, first-in first-out queues of characters are rarely used. Instead, it is common to use queues of buffers or of input/output request blocks. In both cases, the queues are usually implemented using linked lists, but the two approaches are otherwise quite distinct.
When queues of buffers are used, the interrupt service routine must have a state, either reading or writing. When it is reading, each interrupt signals that a buffer has been filled and is ready to be enqueued for later use by a user program reading from that tape. When it is writing, each interrupt signals that a buffer has been written and it is time to dequeue a new buffer and start a new write. Because the queue is implemented as a linked list of buffers, there can be a common pool of free buffers which is shared by all tape or similar block-transfer oriented devices on the system. When this is done, there is a problem: How long should each queue be allowed to get before either the device or the user program is stopped? This is an example of a load balancing problem.
Consider the problems caused when a user program opens two files attached to different tape drives, but reads many blocks from one of them while reading few blocks from the other. Both tape interrupt service routines will quickly start enqueueing buffers holding blocks which have been read from tape, but the user program will only remove blocks from one queue. If there is no provision to stop reading from the tape which is not being used much, that tape interrupt service routine will eventually claim most of the buffers, fill them with data, and enqueue them on the queue from which the user program is not taking data. As a result, very few buffers will be available for the queue which is handling most of the traffic, and the benefits of queueing will be largely lost. In effect, the input/output load has been placed on one queue while the resources have been claimed by the other.
The solution to this load balancing problem is to limit the size of each queue. A fixed limit per queue eliminates most of the advantages of sharing a pool of free buffers, so a variable limit is desirable. On some older systems, the user must specify the queue size when a file is opened, but this requires that the user understand the input/output patterns of the program. One of the most interesting solutions to this problem is to have the queue size adjusted adaptively by the system as it observes the input/output behavior of the user program. This sounds complex, but some surprisingly simple heuristics lead to excellent performance.
The DEMOS system used a heuristic where the queue size limit was initially two buffers, and was adjusted whenever the queue filled or emptied. If the queue never fills or empties, the length is assumed to be appropriate. For input queues, the fact that the interrupt service routine has successfully filled the queue suggests that the queue is bigger than needed, so the size will be reduced by one the next time a buffer is dequeued. If an input queue is ever emptied by a user program, it is assumed that the queue was too small and that it would be desirable to allow more data to be buffered. As a program runs, this allows the queue size to dynamically adapt to the needs of the program.
The use of queues of buffers is complicated if the user is allowed to switch from reading to writing on a tape. If there are I buffers in the input queue and the user requests a write, the last buffer which the user has read was I blocks prior to the current position of the read/write head, so the tape must be moved back I blocks before starting to write. The I buffers in the input queue can be discarded when this is done. Note that this means that either the input queue or the output queue will always be empty with a for a tape-based system, so there is really only a need for one queue plus a state variable indicating whether that queue is an input queue or an output queue.
The complexity of the schemes described above for managing queues of buffers is such that many older systems take an alternate approach. Instead of queueing buffers, the system queues requests to perform input/output on a particular device. Each input/output request is a record describing which input/output operations were requested and where the associated buffer is to be found. All operations will be performed in exactly the order that the user requests, but not necessarily at the time of the request. A user request for input or output specifies the buffer and the operation, and the user must explicitly wait for the operation to be completed. If the user wishes any overlap of input/output and computation, the user must maintain a queue of buffers. Few programs on such systems use more than two buffers; as a result, the term double buffering has come to be widely used to describe schemes which allow overlap of computation and input/output.
The discussion of queues and interrupts presented up to this point in this chapter has ignored all of the issues of device independent input/output, file variable structures, and device description records which were discussed in the previous chapter. In fact, it is not difficult to incorporate queues into the device description record in such a way that most of the structures discussed in Chapter 9 remain unchanged. As an example, consider the design of an interrupt driven serial port driver based on that given in Figure 9.5.
First, each open serial port record needs a new piece of information, the addresses of the input and output queues queue associated with that device. The user of the open file no longer needs to know the data register and status register for this device; those are needed only in the interrupt service routine, but the user does need to use the interrupt enable register. This leads to the design of a keyboard interface documented in Figure 10.14.
/* the definition of the type comportvariable based on filevariable */ struct comportvariable { /* pointers to device specific routines */ void (* rewind)( struct filevariable * f ); char (* read)( struct filevariable * f ); void (* write)( struct filevariable * f, char c ); . . /* pointers to routines for other operations */ . /* device specific information */ int comie; /* I/O register number of interrupt enable register */ struct queue * inq; struct queue * outq; }; /* functions implementing access methods */ void comwrite( struct filevariable * f, char c ) { struct comportvariable * cp = (struct comportvariable *) f; int ie; while (!full( cp->inq )) /* empty loop body */; enqueue( cp->enq, c ); disableints(); ie = inp( cp->comie ); ie = ie | IETBE; outp( cp->comie, ie ); enableints(); } . . /* other functions */ . void com1transmit() /* interrupt service routine for COM1 output */ { int stat; char data; /* we know the TBE status bit is 1, but so what */ stat = inp( COM1STAT ); if (((stat & STATTBE) != 0) && !empty( com1outqueue )) { /* output the data */ data = dequeue( com1outqueue ); outp( COM1DATA, data ); } if (empty( com1outqueue )) { /* disable the TBE interrupt */ stat = inp( COM1IE ); stat = stat & ~IETBE; outp( COM1IE, stat ); } }Figure 10.14. Device Independance and Interrupts, combining code from Figure 9.5 and Figure 10.7.
The key thing to note about Figure 10.14 is that, above the level of the user-callable read routine, no part of the system needs to know that there is an input queue. The linkage between the open file and the interrupt service routine is tenuous! The open routine must fill in the queue pointer field of the open file description with the same queue used by the interrupt service routine, and the open routine must fill in the same interrupt enable register number as is used in the interrupt service routine.
The reader should be familiar with the following general terms after reading this section.
main polling loop free space list polling procedure circular queues interrupts bounded buffers interrupt service routines buffering interrupt vector request queues interrupt disable or enable synchronization mechanisms producer consumer problems mutual exclusion problems echoing type ahead buffers queue load balancing heuristics double buffering
repeat
read( ch );
if ch = '('
then repeat read( ch ) until ch = ')'
else write( ch );
forever;
b) Does your solution contain any critical sections which would cause trouble if interrupts were used? If so, for each, document the problem that could occur, in the style of Figure 10.10.
c) Modify your solution to part a to support the DEMOS load balancing heuristics.
b) Does your solution contain any critical sections which would cause trouble if interrupts were used? If so, document them in the style of Figure 10.10.
Many of the references listed at the end of the previous chapter are also appropriate here. Interrupts are well covered in
Software Systems Principles by Peter Freeman (SRA, 1975);see particularly Sections 2.4.4 on interrupt hardware and 5.4.1 on interrupt handlers and polling.
There is a decent discussion of interrupt structures in Sections 9.1.6 and 9.1.7 of
Systems Programming by Donnovan (McGraw Hill, 1972)
The DEMOS approach to buffer management is discussed in
"The DEMOS File System" by M. L. Powell, in the Proceedings of the 6th Symposium on Operating Systems Principles, published as Operating Systems Review, 11, 5 (ACM SIGOPS, Nov. 1977), pages 33-41.