Notes for CSC 2/456, Monday 17 January 2000 ff reading assignment: chapter 3; PLP chapter 12 ============================================================= PROCESSES AND KERNEL ORGANIZATION Major organizational alternatives: Monolithic Systems: Early operating systems were one big program containing all of the OS functions: process management, device management, memory management, file system, etc. This monolithic approach offers poor abstraction; the various parts of the OS are all intertwined. It may, however, be quite fast. Layered Systems: The operating system is organized as a hierarchy of layers, each one constructed using the virtual machine implemented by the next lower layer. Basically just a design aid in most systems, since there are no mechanisms at runtime that preclude calls across layers. Exceptions: Multics, which used special hardware support to enforce a seven-layer organization; VMS, which uses similar (but simpler) hardware to enforce a 4-layer organization (3 OS layers). The x86 HW supports 3 layers. Micro-Kernel Systems: Kernel is as small as possible; only things that (a) access kernel memory, (b) span address space boundaries, (c) manipulate physical devices, or (d) require privileged instructions Other stuff is in user space. Advantages: Bugs in the OS that reside outside the kernel do not affect all processes. Different policies can be implemented by different processes running in user mode. (e.g. multiple file systems) Kernel is transparent (in the usual sense of the word); kernel functions can be distributed across a network. Modification/experimentation is easier (doesn't require recompile of the kernel; may not require rebooting) More detailed consideration of kernel organization requires that we talk about processes. ------------------------------------------- Terms processor - CPU (physical resource) multiprocessing - using more than one physical processor virtual processor - abstraction of a (nicer?) processor multiprogramming - multiplexing virtual processors on a physical processor process - the execution of some code. Depending on author, may or may not entail extra baggage like an address space and file descriptors thread - like a process, but definitely doesn't entail all the baggage Processes in Operating Systems Used to model user-level programs various activities within the kernel (sometimes) asynchronous devices and their interrupt routines Process States (draw transition diagram) running - the process is executing on some CPU ready - the process is able to execute, but must wait for a CPU blocked - the process is waiting for some action (eg, I/O) to occur transitions running to blocked wait for something that hasn't happened yet (synchronization) blocked to ready completion of awaited event running to ready preemption ready to running dispatch (sometimes) ready to blocked external action, e.g. by shell or debugger Processes, "lightweight" processes, and threads protection domain: address space (virtual to physical mapping) user id, group id open files signal interface (for notification of asynchronous events -- think ^C) traditionally one execution context (PC, register set) per protection domain; term "process" used to refer to combination of protection domain and execution context OSes of the mid to late 1980s added multiple contexts within the same protection domain. These are sometimes called "lightweight" processes or "kernel threads". In POSIX terminology, they're "pthreads" Note that kernel-managed processes/threads are multiplexed on top of one or more physical processors. Many user-level runtime systems multiplex multiple even-lighter threads on top of one or more kernel threads. Why? Can't run a single-protection-domain program on a multiprocessor without multiple kernel-supported threads. Can't have more than one blocking kernel operation in progress without multiple kernel-supported threads. Often nice from a SW engineering point of view to multi-thread an application, but even "lightweight" kernel-supported threads are a lot slower than user-level threads. Context-switch times: Heavyweight processes ~ 500-5000 cycles "Lightweight" kernel-supported threads ~ 50-500 cycles User-level threads ~ 10-50 cycles Every operating system divides user-level work among processes/threads the same way: one process for every logically concurrent user-level activity. Different operating systems divide kernel-level work among processes in different ways. There are lots of subtleties, but two general strategies emerge. They are often called the "process-based" and "module-based" strategies -- terminology introduced by Lauer and Needham in a famous 1979 paper. Process-based: Demos Charlotte Minix Amoeba Kernel modules implemented by kernel processes, which aren't generally the same as user processes (separate scheduler, context switch routine). Execution of a typical kernel call requires work on the part of several modules, requiring IPC within the kernel, typically by means of "message" queues. Can be slow. Is also easily understood and debugged. User processes may well be supported by a *single* kernel process, sometimes called the "envelope." The envelope has lowest priority among the kernel processes; it runs, and returns to user space, when nothing else in the kernel can. Module-based: Linux/Solaris/Irix Mach/OSF1/True64/MacOS X NT Psyche Kernel modules implemented as concurrent data structures, with explicit locking or implicit mutex via lack of context switching. User processes and kernel processes are the same. Execution of a typical kernel call consists of trap into the kernel followed by reading and writing of appropriate data structures, and then a return to user space. Tends to be faster than the process-based organization. Can easily get away from you in terms of complexity. Takes some serious discipline to build right. Warning: I will be talking mostly about the module-based organization because it's faster and appeals to me aesthetically. If you read Tanenbaum's texts he assumes a process-based organization. That's one of the reasons I switched texts. In the process-based kernel, the scheduler is not part of any process; it's "underneath" the process abstraction. When the scheduler code is executing, no process is running. In a module-based kernel, the scheduler is just a procedure. It's written in such a way that the notion of "current process" can change instantaneously about halfway through the code. Up to that point, one process is running; after that point, another is running. -------------------------- Interrupt handler details Recall that on an interrupt the hardware disables (all) interrupts switches to kernel mode puts 'return' address in a special register puts description of interrupt in miscellaneous special registers jumps to a pre-defined location What exactly does the handler do? Its priority is to get everything volatile (the contents of the regular and special registers) someplace safe before re-enabling interrupts. In the general case it does something like this: save a scratch register to a fixed location (or require that the user always leave this register unused -- convention on the MIPS) load the address of the current process context block into the scratch register save into the context block volatile regular registers (including the stack pointer and any others that may be trashed by the code we're about to call, and that won't be saved by the subroutine calling convention) the scratch register value from the fixed location the return address (from a special register) the stack pointer load the process-specific kernel stack pointer from the context block move the special registers into general registers, or into the stack do a computed goto (switch/case) on the interrupt type lower priority to the appropriate level for the interrupt Some of this work may be special-cased out for time-critical things like the TLB fill handler, or the register window overflow/underflow handler on a Sparc. -------------------------- Example: process scheduling and ready list management Suppose somebody does a V on a user-level semaphore (e.g. for synchronization of access to user-level shared memory), allowing some blocked user-level process to run. IN A PROCESS-BASED KERNEL: There are separate schedulers for kernel processes and user processes. The kernel process scheduler is underneath everything else; we're not really running any process when we're running it. The scheduler for user-level processes is itself a kernel-level process. This scheduler is the *only* kernel process that can access the (user process) ready list. It runs code that looks something like this: loop forever while notice queue is non-empty dequeue and act on notice // typically these notices block, unblock, // or change the priority of user-level processes if kernel-level ready list is non-empty yield to kernel-level scheduler continue main loop if user-level ready list is empty continue main loop // this is the idle loop figure out which user-level process P ought to run next disable interrupts if kernel-level ready list is non-empty enable interrupts yield to kernel-level scheduler continue main loop if notice queue is non-empty enable interrupts continue main loop load registers from P's context block if P was not the last user-level process to run switch address spaces return to user space (enables interrupts) To do its V on a user-level semaphore (an abstraction exported by the kernel; not to be confused with kernel-level semaphores), the user-level process executes a syscall instruction. The interrupt handler saves registers into the context block of the user-level process, puts a "syscall" notice on the input queue of the user-process scheduler, re-enables interrupts (lowers the interrupt priority level), and jumps to the user-process scheduler. In effect, this "returns" from user space into the user-process scheduler. This scheduler (kernel-level process) puts a notice on the queue of the kernel-level process responsible for semaphores. As a side effect of this notice, the semaphore manager becomes runnable, so the kernel-level ready list is non-empty. The user-process scheduler therefore yields the processor and the kernel-level scheduler runs the semaphore manager. The semaphore manager looks through its data structures and puts a notice on the input queue of the user-process scheduler, telling it which process to make runnable. At some point in the future (maybe right away if the semaphore process has nothing more to do and yields to the kernel process scheduler (NOT the user process scheduler), the user-process scheduler runs, takes the notice off its queue, and modifies the user-process ready list appropriately. When there is nothing left to do in the kernel, the user-process scheduler returns into some user-level process. The process-based organization tends to be easier to understand and debug, because everything is modularized. (The explanation above is lengthy because it's pretty much all you're going to see of the process-based organization and I wanted to make sure it was clear.) There are no critical sections in the process-based organization -- no shared data! All inter-process operations are accomplished by means of notices on queues. The module-based organization tends to be faster. The process-based organization tends to institutionalize layering; the module-based organization employs layering as a looser convention. --------------- IN A MODULE-BASED KERNEL: The ready list would be a data structure. The user process that did the V operation, and which trapped into the kernel to do so, would simply modify the ready list itself. In a simple uniprocessor OS, lack of context switching in the kernel may avoid potential race conditions by making the whole kernel, in effect, a great big critical section. On a multiprocessor or in a more sophisticated uniprocessor OS, the process doing the V would acquire a lock on the ready list before doing the insert, and would release the lock afterwards. Control enters the kernel for two reasons: when a user-level program requests that the kernel perform some service, and when the hardware requests some service. A module-based kernel handles them somewhat differently, because it makes sense to handle a user request with the user process, but it doesn't necessarily make sense to handle device interrupts the same way. Unix introduced (?) some terminology that is helpful, and widely used. It divides the kernel into the "top half" and the "bottom half" (the bottom "half" is smaller). top half executes as a result of a system call or trap executes in kernel mode using a per-process kernel stack bottom half executes asynchronously as a result of a hardware interrupt executes in kernel mode using a system-wide interrupt stack cannot be interrupted by a top half process, but can interrupt one (this can be blocked out using processor priority level) also blocks other bottom half routines by blocking interrupts [NB: Linux, sadly, gets the terminology backward: it doesn't use the term "top half", but it uses "bottom half" to mean exactly what is traditionally meant by "top half".]