Notes for CSC 2/456, Wednesday 12 January 2000 Survey familiarity with OSes DOS/Windows/NT BSD/Linux/Solaris/etc. MacOS, BeOS others: VMS, VM, OS370, Amiga, OS9, OS/2, MVS, Exec8, RMS, ... What is an operating system? Virtual machine above assembler level that provides nicer abstractions Resource manager facilitating sharing of hardware resources for efficiency and security Concept of a virtual machine layered organization program language run-time user-level services (GUI, www, ftp client, file sharing,...) kernel hardware (macroarchitecture) microarchitecture Four main kinds of resources: processors, memory, communications, devices kernel and user mode kernel runs in priviledged mode runs all the time system utilities run in user mode formerly it was easy to equate the kernel and the OS; with the proliferation of user-level services it isn't this clear-cut. The Microsoft case in federal court right now is largely about whether Internet Explorer is a part of the OS Microsoft NT (among other systems) can support multiple OS "personalities" why put something into the kernel? need to access hardware using priviledged instructions need to implement protection for users need to capitalize on global knowledge to improve performance -------------------------- Course Information Prof. Michael Scott Last taught the course in 1995, mainly because I was department chair, and had the spring off from teaching. OS is my main area of research; it's nice to be back. Thesis work at language/OS boundary, 1985. Helped build two research OSes (Charlotte and Psyche) from the ground up. email scott@cs.rochester.edu Office hours 2-3 on Friday or by appt. T.A. Grigoris Magklis 2nd yr grad student in systems, working with me on OS issues for clusters. From Crete; worked there with Evangelos Markatos, a URCS alum. e-mail maglis@cs.rochester.edu (note difference in spelling) Office hours TBA. Lectures on Monday and Wednesday from 2:00 to 3:15 PM, CSB 632 Course material (lecture notes, schedule, and much much more) are available at www.cs.rochester.edu/u/scott/456/ Also read ur.cs456 (even if you're in 256) We'll be using CS lab machines. See Marty if you need an account. Prerequisites CSC 252 or equivalent Topics to be covered: History of Operating Systems Development: OS requirements Hardware as seen by the OS Concurrency and Processes: Co-routines and processes Contention and synchronization Appropriate locking constructs for various OS functions Scheduling Resource management; deadlock Memory Management: Address translation Translation Look-aside Buffers (TLB) Segmentation and paging Virtual memory Linking Device Management: Device drivers File systems Access control protection authorization Networks and Distributed Systems: Communication protocols Implementation of message passing Distributed file systems Web Programming: Java programming language and runtime system Just-in-time compilation Assignments / Labs Extensive Lab work required; You will design and code synchronization mechanisms design and code file systems design and code memory management systems perform web programming These are not last night "all nighter" assignments -- start them immediately when assigned! Collaboration encouraged; individual writeups required C++ code built on NachOS You will need an account -- see Marty Guenter (marty@cs.rochester.edu) for this. Grading Policy 50% exams 20% midterm 30% final 50% labs 10% "trivia" assignments 20% design 20% implementation working and tested NO LATE ASSIGNMENTS no incompletes reading EXPECTED class participation crucial, expect interaction Main Text Book "Operating System Concepts", fifth edition - Silberschatz, Galvin available at bookstore? Reading assignment: chapters 1 and 2 Today's Agenda What is an operating system? History of Operating Systems -------------------------- History of Operating Systems non-existent systems batch systems multi-programmed time-sharing systems personal systems parallel systems distributed systems real-time systems early single-user systems no OS early computers did not store programs electronically programs were hard-wired before the machine started first computers tediously and carefully programmed simple batch systems von Neumann computer - programs and data stored in memory punched cards -> read-> execute -> print results problem: card readers and printers much slower than central processing unit (CPU) "batch" refers to (usually manual) sorting of jobs into "batches" -- card stacks or tape runs spooled batch systems solution is to overlap input/output (I/O) with processing separate elements so they can be asynchronous need queues (on disk) to handle synchronization spool: Simultaneous Peripheral Operation On-Line card reader reads ahead CPU stores printer output ahead punched cards -> read -> queue -> execute -> queue -> print results OS role in spooled batch systems select program from input queue, load into memory ensure that output queue does not overflow manage disk files more peripherals adding peripherals (disks, mag tape) makes more programs available how does OS select next program? not necessary to select programs FIFO OS needs to track, select, load, execute programs OS needs to do accounting, authorization, authentication OS needs to protect itself from programs file systems for storage of programs, inputs, outputs, intermediate results multi-programmed batch systems single program typically I/O bound solution is to run a program until it needs to wait, then run another round robin, prioritized multiple programs need to be ready to run (in memory) MORE memory driving concern is CPU utilization OS role in multi-programmed batch systems now OS must protect programs from each other must keep track of what programs are waiting for resources problem - users still have to anticipate all possible results how to keep track of device status without polling? interrupts - asynchronous notification OS needs to manage peripherals time-sharing or multi-tasking systems (some authors use "multi-tasking" as a synonym for "multiprogrammed") switch jobs frequently regardless of I/O/compute status; provide quick response to interactive users OS has to manage more peripherals (terminals) MORE memory introduction of inter-process communication (think Unix pipes) multi-processor (parallel) systems objectives improve speed (occasionally) improve reliability through redundancy usually multiprocessors have LOWER reliability tightly coupled - share components memory peripherals symmetric v. asymmetric multiprocessing performance does not scale with number of processors contention for shared resources, overhead for synchronization, communication decomposition of problem immensely important to avoid imbalance OS must manage contention, synchronization, communication, task assignment cache coherence personal computers technology reduced cost of CPU no longer care as much if CPU idles have seen a compressed version of evolution of "mainframe" OSs MSDOS, Windows 1-2, Apple II single task no security, authorization, authentication, accounting Windows 3 - 3.11, MAC OS multi-programmed - slow switching (on window demand) no security programs can easily crash OS and each other Win 95/98, OS2 multi-tasking for 32-bit apps NT, MacOS X multi-tasking (threads) for all apps security OS protects itself OS protects programs from each other movement toward multi-user (due to admin costs, not computer costs) distributed systems do not share memory or clock signal use some form of network for communication may be heterogeneous objectives resource sharing speed-up reliability communication real-time algorithms (process control, e.g. in high-end copier) real-time systems response time as well as results are important examples - control systems - power systems, reactors, aircraft, vehicles, robotics real-time is not just "fast" - it's predictable Hard real-time late results are worthless failure to deliver results on time may be catastrophic many approaches; many implications for OS often coupled with high reliability and availability requirements difficult to implement - requires that all operations have predictable and known latency requires design for "worst case" scenario analysis (expensive - but necessary) Soft real-time results still have some value if late critical tasks get priority most OSs have some provision for soft real-time -------------------------------- What does a typical modern computer look like from the OS point of view? (Quick review of the stuff you need from computer organization, and should have seen in 2/452.) bus address (physical) data attached to cpu memory devices -- often via additional bus(es) From the point of view of the bus, processors are just devices (There is the question of who is bus master, but we'll ignore that). Everything on the bus has an address, and devices communicate by sending bus messages to each other. To write memory, for example, the processor dumps the memory address on the address bus and the data to be written on the data bus and asserts a write; the memory responds. In old machines, there were often special instructions for I/O. That's very inflexible because the design of the processor instruction set fixes for all time the sorts of I/O you can support. Nowadays almost all devices are "memory-mapped," meaning that they sit on the bus and have physical addresses just like memory does. They respond to reads and writes, but not the *way* memory does. devices busy wait interrupt-driven transfer devices are passive except in their generation of interrupts data has to be moved between memory and devices by the processor. DMA devices are active; they transfer their own information to and from memory, and interrupt the processor when they're done. < The following contains examples from the MIPS I Instruction Set Architecture (ISA). This is the instruction set implemented by the MIPS R2000 and R3000 processors, and a subset of the instruction set implemented by the MIPS R4000, R6000 and R10000 processors. It is perhaps the "cleanest" of the RISC instruction sets. The R3000 is basically a faster, more heavily integrated implementation of the R2000. The R6000 came next. It added a few instructions, but is mainly intended for "embedded" applications (e.g. carberators), which don't need features like virtual memory. The R4000 introduced a backward-compatible 64-bit extension to the architecture: the MIPS II ISA. There are now MIPS III and MIPS IV ISAs. NachOS uses user-level programs written in (compiled into) MIPS I assembler, so you'll need to know a little bit about it. The MIPS I ISA *per se* includes only user-mode instructions. Because I'm talking about kernels, I've added the kernel-mode instructions of the R2/3000. > processor The MIPS I ISA has 32 general-purpose registers and 32 floating-point registers. Register $0 always contains a 0. Register $31 is used by the subroutine call (jal) instruction. There are conventions for usage of most of the other registers, but nothing special about them in the hardware. The instruction set includes the usual set of arithmetic, logical, and control-transfer operations. R2/3000 privileged instructions (not part of the user-mode ISA) mfc0 move from control register to general register mtc0 move from general register to control register tlbr read indexed TLB entry tlbwi write indexed TLB entry tlbwr write random TLB entry tlbp probe TLB for matching entry rfe return from exception Special registers memory management Index Random EntryLO EntryHI exception handling Context pointer to kernel virtual PTE table BadVAddr bad virtual address that caused exception Status interrupt mask and enable bits Cause exception type and pending interrupt bits EPC address of instruction that caused exception PRid processor revision ID Special registers vary a LOT from machine to machine. Some machines have special registers, or bits in special registers, that can be set or read in user mode (e.g. condition codes, which the MIPS ISA doesn't have). Machines with messier interrupt state have special registers to hold information about partially-completed instructions. interrupts Transitions from user mode to kernel (supervisor) mode happen in response to interrupts. Interrupts ideally occur "between" instructions, though some machines (including several RISC machines) don't always provide a clean break. An interrupt is said to be *precise* if when the HW traps into the OS every instruction before the interrupt has completed and no instruction after the interrupt has had any noticable effect. An interrupt is said to be *restartable* if the HW provides the OS with enough information to tell which instructions have completed, to complete those that haven't completed, and to get the pipeline going again in user mode. Interrupts occur due to - explicit trap or syscall instructions - "bad" events in user space (e.g. arithmetic overflow, bad addresses, unimplemented/privileged instructions) - external hardware interrupts Transitions from kernel to user mode are performed explicitly by the operating system, generally at the end of an interrupt handler or kernel call, using an RFE instruction. There are two instructions in the MIPS I ISA to transfer to kernel mode: 'trap' and 'syscall'. The first is meant for debugging and error checking, the second for requests for service from the kernel. Syscall instructions are littered through /usr/lib/clib.a. User programs don't generally execute them in-line. The stuff in section 2 of the Unix manual consists of routines that package stuff up, maybe do some error checking, execute a syscall instruction, and then re-package results from the kernel for return to the user program. Communication of parameters to and from the kernel is usually done in registers. Interrupts generally come in several *levels*, sorted according to urgency. Generally urgency means how quickly you have to handle them in order not to lose any. There is no fixed convention on whether larger numbers are more or less urgent; for purposes of this lecture let's say they're more urgent. When an interrupt at "level N" occurs, the hardware changes to a state in which all interrupts at level N or lower are *masked*. That means the hardware remembers whether one (or more!) has occurred, but doesn't deliver it until the current priority level drops. If two interrupts at level k can occur closer together in time than the time it takes (worst case) for the level-k handler to execute, then we can lose interrupts -- we only have one bit of memory. It is therefore imperative that handlers execute quickly. Hardware reset and power fail are generally the highest priority (power generally doesn't die instantaneously; you can execute a lot of instructions before you run out of steam, often enough to reach a clean state for crash recovery). Slow devices like serial lines (one character every 180us at 56K baud, or almost 100,000 cycles per character) are low priority. Fast devices like disks and Ethernet are in-between. terminology: 'interrupt', 'exception', 'fault', 'trap', and 'syscall' are very similar terms, without completely consistent usage. Some authors use 'interrupt' for anything that drops you into kernel mode; others use it just for the cases triggered by external devices. Some authors use 'trap' for any internally-generated drop to kernel mode; others use it only for explicit instructions. 'Syscall' is always used for explicit instructions only. 'Fault' and 'exception' are generally used only for internally-generated events other than explicit instructions. what does the hardware do when an interrupt occurs? For 'bad' events in user space, the CPU aborts the current instruction. The CPU aborts any subsequent instructions that have started down the pipeline(s). Interrupts are disabled, at least at or below the level of the one that's occurring. The HW switches to kernel mode. induces change of address space -- see below A special register gets the address at which execution can resume. The PC gets a pre-defined address. On the R2/3000, there is one address for reset, a second for TLB refill, and a third for everything else (see below for list). All of this happens atomically. CISC machines generally put interrupt state (which can be quite complicated for things like page fauts in the middle of instructions with multiple operands in main memory) onto a stack in the kernel. To do this they need a special stack pointer register that is distinct from the user-mode stack pointer. RISC machines have a lot less user-level state to save. On the other hand, most RISC machines are agressively pipelined, and may have a lot of implementation-specific pipeline state to save. The MIPS chips are about the simplest in this respect. The Intel i860 was about the worst. classes of interrupts on the R2/3000 reset TLB refill TLB invalid TLB modified bus error (bad alignment, or non-existent memory) address error (access to address w/out a valid translation) integer overflow syscall breakpoint coprocessor unusable (includes attempts to execute privileged instructions) other interrupt (e.g. devices) interrupt handlers The code located at the pre-defined address is called an 'interrupt handler'. (On a machine that sends lots of different kinds of interrupts to the same location, that location holds a switch statement that causes control to jump to an interrupt-specific location, and we reserve the name 'interrupt handler' for the code at that second location.) On some machines, the locations to which we jump on an interrupt are specified in a kernel-writable "interrupt vector table." The R2/3000 does not have a vector table. In any case, we often talk about "vectoring" to a handler on an interrupt. It is helpful to remember that processors don't "work" the way people do. They execute madly along at a steady, furious rate, never slowing, stopping, or "noticing" whether they're executing user programs, the kernel, or the idle loop -- or for that matter processing an interrupt. Seen in this light, interrupts are a "normal" event. The processor's instruction fetch unit *polls* for interrupts. If something unusual is happening in the machine, it inserts an interrupt pseudo-instruction into the pipeline instead of the normal instruction. address translation for protection notion of multiple address spaces. processor generates physical addresses for the bus. without memory management, those are the only addresses there are. With MM in place, translation from virtual addresses to physical addresses occurs. User program generates virtual addresses which the HW, under OS control, translates into physical addresses. Impossible to address things not in the current address space. In the R2/3000, translation happens via the TLB (translation lookaside buffer), which appears in several of the lists above. In other machines, the translation mechanism is much more complicated. Lots more on this subject later (and on devices and I/O, too!) bootstrapping How does all this get started? The processor powers-up in privileged mode, in the hardware-reset interrupt handler, with memory mapping turned off, at an address hardwired into the processor. Computer manufacturers arrange for that address to lie in ROM. The code in the ROM constitutes a "bootstrap loader". It runs some diagnostics, pokes around to see what memory and devices are attached to the machine, chooses one of those devices (typically the lowest-numbered disk) as the expected location of the operating system, and proceeds to load the OS into some of the memory it found while poking around. It then jumps into the OS proper. The OS continues initialization, making sure devices are all in the right state, setting up memory mapping tables, turning memory mapping on, creating any needed daemon processes, and creating the first user-level process(es). Typically several of those processes are login shells attached to the console, serial lines, etc. They all initialize themselves and then trap back into the OS waiting for keyboard input. Often one or more user-level processes are also daemons; they do whatever they need to do and then (typically) go to sleep for a while. Eventually, if nothing happens, the kernel starts running its idle loop.