22C:116, Lecture Notes, Lecture 2, Fall 1999

Douglas W. Jones
University of Iowa Department of Computer Science

  1. REVIEW:

    This lecture begins an intensive review of operating systems. Everyone in this class should have had a fair amount of this material, but I do not expect everyone to have prior exposure to the same subset of this material, and I hope to cover the material quickly enough that everyone is exposed to at least some new material in every lecture.

    The hardware on which we run an operating system is itself a system; as such, it is composed of several subsystems; here is a crude diagram of part of such a system:

    
     |-------|
     |  CPU  | CPU   CPU     -- CPUs
     |   |   |   \   /
     |  MEM  |    MEM        -- memory units
     |   |   |     |
     |  IOP  |    IOP        -- I/O processors
     |   |\  |     |\
     |   | \_______|_\____   -- a network
     |   |         |
     | other |   other       -- other I/O devices
     |  I/O  |    I/O
     |-------|
    Traditional
    Single--CPU
     Operating
      System.
    
    \_________  _________/
              \/
            Modern
       Operating System!
    
    
    The focus of a traditional operating system course is on a system with one CPU and no network. In this course, as suggested by the above figure, we will concentrate on systems that may include multiple CPUs, and indeed, systems that may include many computers interconnected by a network.

  2. The CPU or CPUs are complex subsystems in their own right. Although CPU structures vary wildly, we will generally simplify the model, treating the CPU as a control unit, arithmetic unit, and a set of registers, including a program counter:
     Control      Registers
      Unit         _______
     _______      |  PC   | The program counter
    |_______|     |       |
          |       |       | Some operand registers
      ALU |       |  etc  | (details vary immensely)
     _____|_      |       |
    |_______|<--->|_______|
    
    Within the CPU, we will be concerned with the set of registers visible to the programmer, and not such details as the presence or absence of pipeline stage registers, microprogram support registers, or other registers hidden inside the CPU.

    The most important operation on the registers that will concerns us is that of context switching. This involves first saving all registers of one context and then restoring all registers to build a new context.

    Context switching is accomplished in different ways on different processors. Some CPUs support single ``context switch'' or ``exchange jump'' instructions that save and restore the entire CPU state in a single instruction. Such instructions generally take, as operands, the address of a data structure in memory to be used for saving or restoring the CPU state.

    Another approach to context switching is to first push all of the registers on the CPU stack, pushing the program counter first (usually as part of the execution of a procedure call or interrupt). Once all the registers are on the stack, changing the stack pointer to the stack of the new context, followed by popping the registers and then returning from interrupt or returning from the procedure will complete the context switch.

    Within a typical operating system, there will be a data structure used to store the context of a process. At minimum, this contains a program counter and at least one other register. The details of this data structure depend on both the hardware resources of the machine and on how the context switching is done.

    Context switching software is always quirky, with strong machine dependencies. It can sometimes be written in a type-unsafe higher level language such as C or some versions of Pascal, but when this is so, the code must make strong assumptions about how the compiler and underlying hardware operate. The context switching code on most operating systems is still written in assembly language. If the operating system is to be portable, this code is typically in the form of a procedure that takes, as parameters, pointers to two context description records, one in which the old context is to be stored and one from which the new context is to be loaded.

    Exercise: Design a context data structure and a context switching routine for any machine for which you can get adequate documentation. A worked example for the fictional Hawk architecture is included in http://homepage.cs.uiowa.edu/~dwjones/arch/hawk/trap.html

  3. Memory is sometimes a very simple resource, but sometimes, this apparent simplicity is misleading. Compiler writers, for example, must be very sensitive to addressability. On some systems, memory is byte addressed. On others, it is word addressed, and on most, there is some combination. For example, on most CISC architectures of the 1970's (the IBM 370, DEC VAX, Motorola 680x0, Intel 80x86, byte addressing was allowed but with a significant performance penalty. On some modern RISC systems such as the DEC Alpha, hardware support for byte addressing has been sharply reduced.

    Operating systems must frequently contend with a different source of complexity in memory management, virtual addressing.

    Virtual Memory     Lens       Real Memory
      _________                    _________
     |         |       ----       |         |
     |         |       \  /       |         |
     |         |        )(        |         |
     |         |       /  \       |         |
     |_________|       ----       |_________|
        CPU's         Memory      What a Logic
      Viewpoint     Management   Analyzer on the
    	           Unit       bus would see
    
    A Memory Management Unit (or MMU) is present in most larger computer systems, sometimes as a component of the CPU, and sometimes as a separate component. The Motorola 680x0 and Intel 80x86 (for x > 2 in both cases) have quite complex memory management units. The memory management units on modern RISC architectures such as the Power PC, the SGI MIPS processor and the HP PA architecture are generally much simpler, relying on system software to perform many of the more complex MMU functions.

    The memory management unit serves as the "lens" through which programs operating on the CPU observe the memory. As with any lens, we can talk about the real world and the image of the world as seen by an observer looking through the the lens, the virtual image. This metaphore is the basis of the term virtual memory.

    The memory management unit contains registers that may or may not be viewed as part of the context of a running program:

    If the MMU registers are saved and restored as part of the context switching operation, the operation takes longer and the operation changes the memory address space. If the switch does not save and restore MMU registers, it is fast, but both the old and new contexts must share the same address space.

    This is why we see systems with two levels of software parallelism -- lightweight or easy to switch threads that share address spaces with each other, and heavyweight and difficult to switch processes each of which has its own address space. This allows multiple parallel threads of control acting on behalf of a single application to coexist at very low cost, while allowing separate address spaces to be allocated to each application.

  4. Register input-output is the simplest form of input-output. In order to avoid the complexity of references to a particular machine language, we can describe this using high level language procedure call syntax to describe the instructions:
     * send( data, device )         -- output
     * data = get( device )         -- input
     * repeat until ready( device ) -- wait for transfer complete
    

    Typically, the hardware interface for a simple device using register I/O consists of two I/O registers, a data register and a status-control register. The send() operation suggested above should write data to the data register, from which the hardware will copy the data to the outside world. The get() operation should read data from the data register after the hardware has loaded the data register with information from the outside world.

    The status-control register typically has a bit that the hardware sets to one whenever the device is ready for a send() or get() operation. Other bits may be used, for example, to signal that errors have been detected, or to control the device function (for example, a bit the software can set to indicate whether the device should read or write, and a bit the software can set to force the device to reset itself).

    On some machines, the I/O registers are addressed as if they are memory locations (memory mapped I/O). On others, there are special opcodes used to access I/O registers in a distinct I/O address space. Typically, I/O registers are the same size as the machine word, but on some machines, they are smaller.

    Code for directly manipulating I/O devices is always quirky and highly machine and device dependant. It is frequently written in assembly language, although on machines that use memory-mapped I/O, use of assembly language is not needed. Even when device access code is written in a high level lanugage, however, it is rarely portable to different architectures!

    Exercise: Write a routine to read a character from the keyboard input port or from an asynchronous input port of some machine -- do this with no use of operating system routines.

  5. Direct memory access input-output is more complex. Here, the device had direct access to memory, and may transfer data to or from memory while the CPU executes instructions. A simple DMA device might be pictured as follows:
       _____   MEMORY BUS   ______
      |     | ____________ |      |
      | CPU |<_____   ____>|Memory|
      |_____|      | |     |______|
                   | |
                  __v___
                 |      |
                 | DMA  |
                 |Device|
                 |______|
    
    The simplest DMA devices, for example, some of the simpler video interfaces, need no additional data paths.

    Today's video interfaces, on the other hand, have many registers that the software must load before the display can be used, these include such things as the memory address used for the screen memory, the number of pixels per line, the number of lines, and so on. Register I/O is used to access such control registers, so the picture for modern video interfaces, as well as for several other modern devices, would look something like the following:

       _____   MEMORY BUS   ______
      |     | ____________ |      |
      | CPU |<_____   ____>|Memory|
      |_____|      | |     |______|
         ^         | |
         |        __v___
         |       |      |
          ------>| DMA  |
      Register   |Device|
        I/O      |______|
    
    For typical I/O devices, the register I/O data path allows the CPU to inspect a status register, set a control register, and to inspect and set the address and word-count registers that are used to determine what memory addresses are the targets of DMA I/O operations.

    Typically, but not always, things are more complex than illustrated above. DMA I/O controllers are complex, so it is common to separate the DMA function from the actual device interface so that one DMA controller may be shared by multiple devices. For example, you may find multiple disks on one disk controller, or multiple SCSI devices (disks, tapes, and other widgits) on one SCSI controller. The latter case is illustrated below:

       _____    MAIN BUS    ______
      |     | ____________ |      |
      | CPU |<_____   ____>|Memory|
      |_____|      | |     |______|
                   | |
                  __v__       SCSI BUS
                 |     | ___________________
                 |SCSI |<____   ______   ___>
                 |_____|     | |      | |
                             | |      | |
                            __v__    __v__
                           |     |  |     |
                           | DISK|  | TAPE|
                           |_____|  |_____|
    
    In such a system, the SCSI controller can transfer data between the disk or the tape and main memory, under the direction of the CPU. To do this, the CPU must inform the controller of the memory address to be used and the operation to be performed, and through the controller, it must inform the disk or the tape drive of the device address (for example, the sector, track and cylinder) to be referenced and the operation to be performed.

    Thus, a single DMA I/O transfer involves the following steps:

    1. select device
    2. select address of data on device
    3. select buffer in main memory
    4. start transfer in or out
    5. await transfer complete
    When direct memory access I/O hardware is employed, data is transferred one block at a time, generally in parallel with program execution. I/O is initiated by a program running on the CPU, and then it takes place in parallel with program execution. When done, a signal is sent to the CPU indicating that the transfer is complete.

    In modern systems, the hierarchy of busses is frequently even more complex, with a peripheral bus such as the EISA bus quite distinct from the main CPU to memory bus, but this distinction is generally hidden from the system software, so it will not be discussed here.

  6. A USER PERSPECTIVE

    Users typically rely on operating systems to provide the following:

  7. The word ``file'' is frequently used rather carelessly to refer to any of the following items, even though they are quite different things:

    These three meanings of the word "file" are usually used without any clarifying comment, and you have to figure out, from context which meaning is intended.

    Generally, operating systems support an operation, such as open(f,name), that takes a file name and interprets it in a directory structure to deliver an open file object. This object may refer to a file on disk, or it may refer to something else such as a terminal, a communications line, or a window.

    It should be noted that on some systems, a file on disk need not have any name in any directory structure!

  8. Command Languages come in a great variety, from limited function Window-Icon-Mouse-Pointer interfaces to general purpose programming languages.

    Before UNIX, command language interpreters were generally integral parts of the operating system, and many people mistakenly asserted that, quite naturally, each command language operation was identical to a call to an operating system routine.

    In UNIX and most later systems, the command language interpreter, called a shell on UNIX, is merely an application program. If you don't like it, you can write your own. Most commands in the command language are merely names of programs, and the user of the command language interprets the commands as if they were parameterized procedure calls, where the programs themselves are the procedures being called.

    Most users view the command language interpreter as part of the system, but for most purposes, the system views the command language interpreter as if it was a user program.

    As an aside, note that in later versions of the UNIX, the system has a special relationship to the Bourne shell (the original UNIX shell) through the system() call, but this is not formally a system call; rather, it is a library routine that passes its argument to the Bourne shell.

    exercise: Write a C program under UNIX that executes the standard ls program (the program that runs when you type the ls command at a UNIX shell prompt).