Up to this point, we have discussed traps, and mentioned occasionally that interrupts are similar. Now is the time to distinguish between these:
The best way to understand interrupts is to look at a typical simple device that can cause an interrupt. The Hawk keyboard input interface is a good example. It is worth noting that keyboard input, input from serial ports, modems and parallel ports all look very similar from a software viewpoint, so the description here is typical of all such devices.
On the Hawk, all device interface registers appear to be 32 bit registers, even if only a few bits have meaning. This simplifies programming because word addressing is easy on this machine. Well behaved interfaces will set the unused bits of these registers to zero. On the hawk, attempting to write a read-only device control register or a read-only bit of a read-write register has no effect; unless the memory management unit intervenes because the memory region is read-only, the write operation is simply ignored.
The Hawk CPU has access to the keyboard interface through a pair of device interface registers:
Keyboard Data Register
_______________________________________________________________
|_______________________________________________|_______________|
|31 8|7 0|
unused key code
On full-fledged modern machines, it is common to find input key codes that
are not encoded in ASCII; raw scan codes (3 bits to encode keyboard row and
5 bits to encode keyboard column) are fairly common, as are more complex
encodings. We will ignore these here!
The keyboard status register is more complex; some bits in it are read-only, while others can be set by writing the register. The basic layout of this register is as follows:
Keyboard Status and Control Register
_______________________________________________________________
|_______________________________________________|_|_|_________|_|
|31 8|7 6|5 4 3 2 1|0|
unused I E R
The individual bits are as follows:
The basic Hawk monitor includes the following code to read from the keyboard:
;-------------------------------
INT KBGETC
KBGETC: ; get char from keyboard
; return char in R3
; wipe out R4
; does not use R2
LIW R4,KBDSTAT
KBPOLL: ; loop awaiting input
LOADSCC R3,R4 ; test status
BZS KBPOLL
LIW R4,KBDDATA
LOADS R3,R4 ; get char
JUMPS R1 ; return
This code begins by repeatedly reading the keyboard status register looking
for the ready bit to be set, and then gets the character from the keyboard.
The code assumes that interrupts are disabled (as they are, by default),
and it assumes that no other keyboard status bits have been defined.
The loop in the above code is called a polling loop. This use of the word polling is closely related to the use of that word in public opinion polling or in describing voting as going to the polling place. When you poll someone, you ask a question. In this case, the CPU is repeatedly asking the device "are you ready yet". When someone hits a key on the keyboard, the answer is yes and execution falls through the bottom of the polling loop and reads the contents of the data register.
The following version of the polling loop tests the ready bit more carefully, allowing a more typical modern keyboard interface with other status and control bits:
KBPOLL: ; loop awaiting input
LOADSCC R3,R4 ; get status
SRU R3,1 ; shift ready bit into C bit
BCR KBPOLL
This routine ignores errors. In the context of a keyboard handler, this
is not necessarily a bad thing; other than, perhaps a beep or an unusual
keyclick, there is little that can be done about an input error other than,
possibly, to ignore the data. Even that may be unreasonable; users should
always be able to erase and retype input that was misread by the computer.
Polled input and output routines such as the above were very common in the first generation of software written for each generation of hardware. Thus, code written for the mainframes of the 1950's, the minicomputers of the 1960's and the microcomputers of the 1970's usually relied on polling.
Polling is not generally desirable! While the CPU is executing the code in a polling loop, it cannot do anything else. Usually, we prefer our computers to be able to do useful work in parallel with input or output operations. Thus, for example, we expect to have our keyboard input accepted while the computer is executing our programs (the typeahead problem) and we expect our programs to continue executing after producing output, while that output is being printed (the output spooling problem).
Both of these problems can be solved by hardware, but they are easily solved by software, using interrupts. Most modern operating systems, UNIX (born as a minicomputer operating system in the 1970's) or even MS/DOS (a marginal but widely used microcomputer operating system of the 1980's) support interrupt driven input and output.
Consider the typeahead problem. Solutions to this problem allow input data to be buffered, so that the user may type at his or her own speed without attention to whether or not the application program is ready for the typed data. All solutions to this problem have the following basic structure:
__________ ____________ _________
| | | | | |
| Keyboard |==>| FIFO Queue |==>| Program |
|__________| |____________| |_________|
The FIFO queue can be built in hardware, but using interrupts, it is possible
to solve this in software as follows:
__________ ____________
| | | Keyboard |
| Keyboard |==>| Interrupt |
|__________| |_Handler____|
|
_____V______ _________
| | | |
| FIFO Queue |==>| Program |
|____________| |_________|
With this solution, whenever a user presses a key on the keyboard, the keyboard
interface requests an interrupt. The keyboard interrupt handler then reads
the character from the interface and enqueues it. When the program wants a
character, it uses the dequeue operation. We assume here that the dequeue
operation will automatically wait when there is nothing in the queue, blocking
the user program.
Assuming that procedures named ENQUEUE and DEQUEUE handle access to the FIFO queue, the following keyboard interrupt service routine will work; this is written to conform to the conventions of the trap and interrupt dispatcher discussed in Lecture 31:
;-------------------------------
; format of AR pointed to by R2
; 0 ; return address
KEYAREA = 4 ; pointer to register save area
KEYARSZ = 8 ; size of AR
KEYBOARD: ; interrupt handler for keyboard
; assumes R3 points to register save area
; preserves R3, may wipe out others
STORES R1,R2
STORE R3,R2,KEYAREA
LIW R4,KBDDATA
ADDI R2,KEYARSZ
LOADS R3,R4 ; get character from keyboard
JSR R1,ENQUEUE ; put it on the queue
ADDI R2,-KEYARSZ
LOAD R3,R2,KEYAREA
LOADS R1,R2
JUMPS R1 ; return
Note that the above code does not inspect or modify the keyboard status
register! It assumes that interrupts are enabled and should remain enabled,
and it assumes that the interrupt itself was a sufficient signal that that
keyboard input is available, so there is no need to check the status. For
such a simple device, the only reason to check the keyboard status register
would be in order to determine if there was an error.
Given this interrupt service routine, user calls to KBGETC can be replaced with calls to DEQUEUE to create a full software implementation of the typeahead buffer. Of course, there remains the problem of writing an appropriate routines for the queue itself!
Writing the enqueue and dequeue routines is straightforward. We begin by designing a data structure for the queue:
;------------------------------- ; FIFO Queue Data Structure CAPACITY = 40 COMMON QUEUE,MAX PQUEUE W QUEUE ; offsets of fields within the queue structure HEAD = 0 TAIL = 4 DATA = 8 MAX = DATA + CAPACITY ;------------------------------- INITQUEUE: ; initialization ; wipes out R3-R4 LOAD R3,PQUEUE LEA R4,R3,DATA STORE R4,R3,HEAD ; head = tail == empty queue STORE R4,R3,TAIL JUMPS R1Here, in initializing the queue, we establish the convention that the queue is empty whenever the head pointer is equal to the tail pointer. Now, we can code the enqueue routine, called from the keyboard interrupt service routine:
;------------------------------- ENQUEUE: ; put one char, R3, into the queue ; wipes out R3-R6 LOAD R4,PQUEUE LOAD R5,R4,TAIL ; enqueued data at the tail end ADDSI R5,1 ; increment tail before storing LEA R6,R4,MAX ; get maximum tail value CMP R6,R5 ; see if at end of buffer BNE ENQOK LEA R5,R4,DATA ; wrap pointer back to start of buffer ENQOK: LOADS R6,R5 STUFFB R6,R3,R5 ; stuff byte into queue STORES R6,R5 STORE R5,R4,TAIL ; update tail pointer JUMPS R1 ; returnNote that this version of enqueue does not check for a full queue. In a real system, it would probably be wise to lock out additional input when the queue filled, or equivalently (in the case of a keyboard), it would be appropriate to simply discard input when the queue is full.
Writing a DEQUEUE routine that matches this version of ENQUEUE is not very difficult:
;------------------------------- DEQUEUE: ; get one char into R3 from the queue ; wipes out R3-R6 LOAD R4,PQUEUE LOAD R5,R4,HEAD ; enqueued data at the tail end DEQPOLL: LOAD R6,R4,TAIL ; must see if there is any data CMP R5,R6 BEQ DEQPOLL ; if equal, queue is empty. ADDSI R5,1 ; increment head before loading LEA R6,R4,MAX ; get maximum head value CMP R6,R5 ; see if at end of buffer BNE DEQOK LEA R5,R4,DATA ; wrap pointer back to start of buffer DEQOK: LOADS R6,R5 EXTB R3,R6,R5 ; get byte from queue STORES R6,R5 STORE R5,R4,HEAD ; update tail pointer JUMPS R1 ; returnNote that this version of dequeue includes a polling loop that blocks the program until the head and tail pointers differ. When these pointers are equal, the queue is empty. Once the program enters this loop, it can only break out when the interrupt service routine calls ENQUEUE; with each trip through the loop, TAIL is reloaded from memory, and ENQUEUE is the only piece of code that changes TAIL.
This code was fairly easy to write only because the ENQUEUE and DEQUEUE routines each update different variables. Had we tried to keep a counter of the number of characters in the queue where ENQUEUE incremented the counter and DEQUEUE decremented it, a new problem would have arisen. Consider adding the following code fragments to the queue access routines:
; added to ENQUEUE LOAD R3,R4,COUNT ADDSI R3,1 STORE R3,R4,COUNT ; added to DEQUEUE LOAD R3,R4,COUNT ADDSI R3,-1 STORE R3,R4,COUNTDEQUEUE is called by the user; consider what happens if, while DEQUEUE is executing, between loading COUNT and storing COUNT, there is a keyboard interrupt:
To prevent such interrupts, we can either disable interrupts by changing the LEVEL field of the PSW, or we can use the interrupt enable bit in the keyboard status word. The latter is preferable, since the only interrupt we need to disable is the keyboard interrupt -- other interrupts, for example, from a disk or a network interface, cause no problems with counting characters in the keyboard typeahead buffer. So we must replace the code to maintain COUNT with the following:
; added to ENQUEUE LOAD R3,R4,COUNT ADDSI R3,1 STORE R3,R4,COUNT ; added to DEQUEUE LIW R5,KBDSTAT STORE 0,R5 ; disable interrupts LOAD R3,R4,COUNT ADDSI R3,-1 STORE R3,R4,COUNT LIS R3,#10 STORE R3,R5 ; re-enable interrupts
The failure to correctly identify critical sections in operating system code is one of the most common causes of operating system crashes!