Chapter 2.0 Interrupts and Multiprocessing 2.0.0 Why interrupts? The I/O code introduced so far repeatedly check the done-bit of the CS-register until it indicates "last I/O command completed". "Polling", as this technique is called, is simple and easily mastered by the programmer. You can achive concurrent execution of the I/O command (done by the device) and some useful computation (done by the CPU), but often the CPU spends a lot of time waiting for I/O completion. This is OK for simple operating systems that support only one CPU-process at a time, like the PC-BIOS, PC-DOS, early versions of Apple's Macintosh Operating System or Microsoft's Windows. But the programmers and designers of bigger computers felt a need to better exploit the CPU by loading multiple programs at once, so the CPU can switch to another program, when one program needs to wait for I/O completion. This is what hardware interrupts were designed for. Interrupting hardware introduces a new challenge to the programmer: The CPU jumps out of the program to the interrupt service routine (ISR). Even worse, this may happen any time during the execution of the program. 2.0.1 Rules observed by the interrupting hardware If interrupts were to occure any time any place, the design of programs that employ interrupts would be impossible. So there are some rules bounding the undeterministic nature of interrupts. When the interrupt causes the CPU to jump out of the current process to the ISR, the PC and the Processor Status Word (PSW) are changed to the values from the interrupt vector entry. To continue the interrupted process, both of these values need to be restored, this is done by the RTI instruction. Exercise: When the ISR consists of an RTI instruction only, the state of the interrupted process is not changed by the interrupt -- with one exception-- namely? The machine instructions are "atomic" with respect to interrupts, that is, an instruction is completed by the CPU before transfering to the ISR. Exercise: Which values are affected by the instruction "mov (r0)+,(r1)+"? A device will issue an interrupt request, only if the "interrupt enable" bit in its CSR is set. After reset, this bit is unset. An interrupt request is honored by the CPU only if the IPL is less than the BR. Since the greatest possible BR is 7, no interrupts will be served if the IPL equals 7. After reset, the IPL is set to 7. Exercise: The entry of sum1 is carefully chosen at 0400 so its code would be out of the interrupt vector. For two reasons this is unnecessary. Namely? 2.0.2 Process control in Unix. A process is a program in the middle of execution. The same process can run in one of two operation modes, the kernel mode and the user mode. The memory addressed in kernel mode is disjunct from the memory addressed in user mode. This protects kernel code, data and device registers from processes running in user mode. A process in user mode switches to kernel mode when executing a "SYS" instruction. It switches back from kernel mode to user mode when issuing the corresponding "RTI"-instruction. Exercise: After reset, the PDP-11 runs in kernel mode. So, when the first process switches to user mode, the RTI instruction was not preceeded by a SYS instruction. What needs to be done to make the RTI switch to user mode? Exercise: The PDP11 makes it impossible to switch from user mode to kernel mode by means of an RTI instruction. Why? When in kernel mode a process may initiate an I/O instruction. Instead of waiting for completion, it marks itself in a global process table as waiting for this event and then transfers control to some other process which is runnable. This is called a "context switch". The ISR called on completion of the I/O searches the process table for processes waiting for this event and marks them as runnable. When the interrupted process is in kernel mode, the ISR continues this process by means of an RTI instruction. When the interrupted process was in user mode, the ISR consults the process table for another process that is runnable and performs a switch to that process. Note that the context might be switched by an ISR only if the current process is in user mode, never if it is in kernel mode. This rule solves the synchronization problem with respect to data structures shared by kernel mode processes since an asynchronous process switch won't occur. The process table is an example of a shared data structure that is modified from processes (in kernel mode) and ISRs. To make this modification atomic, a process protects itself from being interrupted by setting the IPL accordingly. The ISR itself usually runs at an IPL set to the BR of the device, thus protecting itself from being interrupted by the device it is serving. By prohibiting interrupts it is guaranteed that processes and ISR see the protected data structures in a consistent state, that is a state satisfying structural invariants. It is very hard to decide if a change of a data structure needs to be atomic, i. e. protected by raising the IPL. To decide, the programmer needs to know every detail of every code possible to be executed by an ISR interrupting a process in kernel mode. If you protect too much, chances increase, that you will lose interrupts. If you protect too little, you might break data structures. This synchronization problem is lessened by a rule governing the kernel design: Minimize access to shared state if the ISR interrupted a process in kernel mode. Compare this to the rule imposed on the Java Swing library: After initialization, access to any Swing class is confined exclusively to one thread, the Event Dispatcher Thread. This rule holds with the exception of four methods that may be called from other threads to enable interthread communication. When the ISR returns to a kernel process (i. e. a process running in kernel mode), it is its duty to restore the state of the process. From the stack of the interrupted process, the ISR restores the R1, R0, PSW and PC, the latter two by the RTI instruction. The general registers R2 to R5 are not touched by the part of the ISR written in assembler. Most of the ISR is written in C which makes heavy use of these registers. But the subroutine calling and returning sequence emitted by the C compiler guarantees, that the caller's registers R2 to R5 are restored on return from a C routine. Since the ISR obeys the C calling sequence, it does not explicitly restore these registers. The SP is restored implicitly since each push is balanced by a pull. Things are slightly more complicated when the ISR interrupts a user process and needs to do a context switch before returning. This is necessary to protect the whole system from looping user processes holding the CPU for ever. In Unix, a process has two stacks, one active in kernel mode and one active in user mode. This is dictated by the fact that the addressable memory, which includes the stack area, is disjoint in user and kernel mode. The PDP 11 supports two stacks by suppling two stack pointers, the kernel stack pointer (KSP) and the user stack pointer (USP). To prepare for a context switch, the ISR pushes the USP onto the kernel stack. Part of the context switched at the end of the ISR is the kernel stack, where the state of the user process including the USP is saved. When the ISR restores the state from this other stack, it effectively returns to a process different from the interrupted one. Exercise: During a context switch, the ISR accesses a lot of global data which are modified by kernel processes without raising the IPL. Why does this not crash the system?