22C:116, Lecture 14, Spring 2002

Douglas W. Jones
University of Iowa Department of Computer Science

  1. Input/Output

    This lecture focuses on a review of three different aspects of input output:

    The term virtual device is not standard, but it is realistic! The device interface presented to applications running under an operating system is usually quite different from the actual device interface, at least as different as the virtual memory abstraction is from the actual physical memory resources, and therefore, it seems quite reasonable to use the adjective virtual to distinguish the view of the device supported by the system from the actual resources provided by the device.

  2. Physical Device Interfaces

    The physical device interface of a real system typically consists of a number of device registers. For example, on a typical IBM PC compatable, parallel port zero is addressed by the hardware as follows:

      I/O  Register
      Addr Function
                    __ __ __ __ __ __ __ __ 
      0378 data    |D7|D6|D5|D4|D3|D2|D1|D0| input/output
                   |__|__|__|__|__|__|__|__|
                    __ __ __ __ __ __ __ __ 
      0379 status  |BS|AK|PE|OL|ER|x |x |x | input only
                   |__|__|__|__|__|__|__|__|
    	BS = 1 when printer not busy
    	AK = 1 when data transfer in progress
    	PE = 1 when printer is out of paper
    	OL = 1 when printer is on line
    	ER = 1 when there is no error
                    __ __ __ __ __ __ __ __ 
      0379 control |x |x |x |IE|SL|IN|LF|ST| output only
                   |__|__|__|__|__|__|__|__|
            IE = 1 to enable printer interrupt
            SL = 1 to select printer
            IN = 1 for normal operation (zero causes printer reset)
            LF = 1 to force printer to advance paper
            ST = 1 to transfer data into printer
    	
    
    All of the printer specific bits documented above are there because the PC parallel port was designed for compatability with the older Centronics parallel printer interface. If the device you have is not a printer, these printer-specific bits may be used (or abused) for entirely different purposes.

    Note that the data port has a special characteristic. Output from the CPU to the parallel port data register writes that register, and the value written in the register is visible on the output pins of the parallel port connector. Input from the parallel port data register does not come directly from the register, it comes from the pins themselves. There is a resistor between the register's output and the pin, and as a result, if the register holds a one but some external device tries to write a zero to the same wire, input from the parallel port will read zero (the value provided by the external device) instead of one (the value stored in the register). This allows the use of the parallel port data register for input!

    The protocol for printing one character using this interface was established by Centronics Corp for their line of low-cost dot-matrix printers in the early 1970's, years before the IBM PC came to market, so the IBM PC compatable parallel port is also somtimes known as the Centronics port.

    To print one character, the software must load the character in the parallel port data register and then send out a positive pulse on the ST (strobe) line. The printer acknowledges the strobe pulse with a positive pulse on the AK (acknowledge) line and a negative pulse on the BS (busy) line. The contents of the data register must remain valid until the end of the AK pulse, and no new transfer is legal until the end of the BS pulse. Usually, these two pulses will be coincident. (note that the sign of these pulses is described here as seen from the perspective of software -- the interface hardware inverts some of these signals!)

    The parallel port output protocol:
    
    outputs
              ___________          __________
    DATA-----<___________>--------<__________>--------
                  _____               ______
    ST___________|     |_____________|      |____________
    
    inputs
                      ______              ______
    AK_______________|      |____________|      |_____
      __________________          __________        ___
    BS                  |________|          |______|
    
    notes        |-a-|               |-a-|
                     |-----b-----|       |----b----|
    
      a) the data may not change here because this is when
         the device actually reads it.  The read begins when
         the device notices the strobe signal, and the read
         must have ended before the device acknowledges.
      b) no new strobe pulse may begin between the time the
         device acknowledges the stgrobe and the time the
         declares that it is no longer busy.
    
      !! The signals are shown with the values seen by software!
         many of these values are inverted by the hardware, so
         the voltages on the I/O pins of the parallel port
         connectors may be inverted from the signals shown here.
    

    If interrupts are enabled (IE = 1), the printer interface will request an interrupt when AK (acknowledge) goes from 1 to zero. The particular interrupt requested may depend on the settings of jumpers or option switches on the parallel port interface, but it is traditionally IRQ7, the lowest priority hardware interrupt supported on the original PC.

    The SL, IN, LF and ST lines from the control register correspond directly to corresponding output pins in the parallel port connector, and all of the status lines correspond to input pins in the parallel port connector. Aside from the IE (interrupt enable) bit and the interrupt logic attached to AK (acknowledge), the parallel port hardware makes no assumptions about the use made of the control, status and data lines. The meanings of those lines are established by the hardware connected to the printer port. The meanings suggested in the documentation above apply to classical printers, but many other devices use (or abuse) these signals in a variety of ways.

    Input from the PC's parallel port is a bit more complex, so we'll ignore the possibility here.

  3. Virtual Device Interfaces

    The Stream is a typical (but by no means universal) input/output abstraction. Typical stream operations are get(ch) and put(ch). These get a character from a stream or put it to a stream, where the streams these commands operate on are either passed explicitly to the access procedure, or they are implicitly passed as in the case of standard input and standard output.

    These are abstractions in the sense that they don't necessarily map directly to the actual input/output operations on any particular physical device.

    These abstractions do relate naturally to the character-at-a-time operations on some simple devices such as keyboards, asynchronous communications lines, and a few other devices.

    The UNIX stream abstraction is somewhat more complex. In UNIX, the operations are:

    	len = read( f, buffer, length )
    	len = write( f, buffer, length )
    
    Where f names the stream to be read or written, and data is transferred to or from a named buffer that is able to hold length characters. There is no requirement that the size of the buffer have any relationship to the size of the blocks transferred to or from the underlying device.

    The read operation reads up to length consecutive characters from the stream and places them in the buffer, returning len, the number of characters actually read, while the write operation appends up to length characters from the buffer to the stream, returning len, the number of characters actually transferred.

    Note that most C programmers know of other stream primitives, fputc(ch) and fgetc(); these are C abstractions that are not part of the UNIX user interface and are implemented in terms of the read and write kernel calls. These abstractions exist both because programmers prefer character sequential streams to buffer sequential streams, and because the cost of kernel calls is sufficiently high that we cannot afford a new kernel call for each character transferred to a high performance device (we can easily afford one call per character on low performance devices such as keyboards).

    It is important to emphasize that both the UNIX file and the C stream abstractions are conceptually objects with methods to operate on them. The fact that the UNIX system call interface and the C standard library interfaces are procedural can hide this, but logically, the operations on an open UNIX file should be thought of as references to methods of a file object. Thus, for example, it is constructive to think of read(f,buf,len) as f.read(buf,len).

    Also note that the there are undefined and device dependent characteristics associated with UNIX style streams: For example, under what circumstances will the read and write calls return values other than the user's specified byte count? The answer for a disk file is quite different than the answer for an asynchronous communications line!

    A fundamental issue here is how the system should respond to exceptions raised while an I/O operation is in progress. Asynchronous events such as the expiration of a timer or a user striking the control C character on a terminal send signals to the process. If the process is blocked awaiting I/O completion, what should the system do? In UNIX, a very simple answer was adopted. When a signal is delivered to a process that is currently executing a kernel call, the kernel call returns immediately and then the signal is delivered. If a read operation was in progress, for example, and it had read only 13 bytes of a 45 byte buffer, the delivery of the signal will terminate the read, and the return value will be 13 instead of the expected 45.

  4. Other Abstractions

    Another typical abstraction is block-oriented random-access I/O, where the typical primitives might be:

      SectorRead( memory_buffer, device_address )
      SectorWrite( memory_buffer, device_address )
    
    Here, the buffer is a block of consecutive memory locations in the caller's address space, and the address names a block of consecutive locations in the random-access I/O abstraction, perhaps a relative address in a disk file. The block size in this scheme is fixed and therefore is not passed as an explicit parameter!

    This abstraction maps naturally to disk devices in the case where the block size is one sector and the device_address is the sector number It maps poorly to almost all other real devices, but disks are so important that it is frequently used.

    Aside: UNIX files are a generally successful attempt to generalize streams to include block I/O. The operations are:

      Read( f, buffer, length )
      Write( f, buffer, length )
      Seek( f, offset, base )
    
    The seek() operation (or lseek(), where the l prefix indicates the use of a long int offset, typically at least 32 bits), is used to position the read-write pointer in the indicated stream. The offset may be relative to the start of the stream, to the end of the stream, or to the current position in the stream, depending on the value specified for the base. Obviously, seeking in some streams is meaningless (consider seeking relative to the end of the stream of characters being read from a communications line), and seek operations are not always supported (seeking in the stream from the keyboard would require storing the entire history of what was typed, and this is not worth doing), but on those file types where seeking is useful and can be efficiently implemented, for example, on disks and tapes, this interface works quite well.

    With a buffer size of one byte and no seek operations, this interface exactly emulates a pure stream. With a buffer size of one disk sector, with a seek offset that is a multiple of the sector size prior to each read or write, this interface exactly emulates a conventional random-access model. If the sector size is not matched to the buffer size or if seeks are made to device addresses that are not sector aligned, intermediate buffers and possibly extra input-output transfers must be used to reblock the data between the user and the device.

    Of course, if the underlying device is incapable of a seek operation, for example, if it is a printer or a keyboard, the seek operation in the user interface is meaningless.

  5. Class Hierarchy for Streams

    One of the very first uses of object oriented programming can be found in Christopher Strachey's stream implementation in his OS-6 project in the late 1960's. Strachey, the primary developer of the CPL programming language, naturally chose to write this system in BCPL (Basic CPL, the ancestor of C; C++ and Java added the notion of classes from Simulat 67 to this), but he wrote his code in clearly object oriented form, and today, we would say that he used a class hierarchy something like the following:

                    Write Only Stream
                         write(c)
                            |
                    Read/Write Stream
                          read(c)
                         write(c)
                            |
                   Random-Access Stream
                          read(c)
                         write(c)
                          seek(c)
    
    In fact, the whole notion of having the class hierarchy have any relationship to the implementation hierarchy fails for I/O, because, for some devices, random block access is the primitive, while stream access is a higher level abstraction. For other devices, the situation is reversed; stream access is primitive, and blocks must be introduced as a high level abstraction. Thus, one of the original inspirations for object oriented programming remains a good test of the methodology!

  6. Implementation of Streams

    A device driver is the component of an operating system that supports input or output operations to some device. Conceptually, this bridges the gap between the abstractions presented to the user, but in many systems, the front-end interface to user code (for example, the read(), write() and seek() kernel functions in UNIX) include standard code that applies to all devices, and the input/output drivers themselves have a different user interface, designed specifically to be used only from within the code of the standard front-end code and sometimes also used from within other points in the system.

    Stream input/output provides an excellent example of the implementation of an input/output driver. The driver is usually subdivided into two halves, one half deals with the hardware interface and includes the interrupt service routines for the device, and the other half deals with the user interface. It is quite common to include a FIFO queue between the two in order to allow computation and input/output activity to overlap. The following diagram illustrates this overall structure you would expect for a parallel port printer handler under an operating system for the IBM PC:

           ||                              ||
          put( ch ) ---> FIFO  ---> Interrupt Handler
           ||                              ||
     user  ||        device driver         ||  hardware
           ||  (in the operating system)   ||
    
    Note that the user interface suggested here only includes the operation to write one character. This is the primitive for this character sequential output device, and any other primitives desired can clearly be implemented using sequences of write-character operations.

    For input stream devices, such as the receiver for an asynchronous communications line, we can draw a similar picture:

           ||                              ||
        ch = get() <--- FIFO  <--- Interrupt Handler
           ||                              ||
     user  ||        device driver         ||  hardware
           ||  (in the operating system)   ||
    
    The only difference is that the queue is now fed by the device and emptied by the user.

    On first generation machines, programs usually were limited to synchronous I/O, where the application program stopped to read input, and where input was lost if the program wasn't ready for it when it arrived. Interrupts were not used, and the user interface routines directly manipulated the device registers to perform read and write operations.

    The IBM PC BIOS and most of the MS/DOS operating systems are typical of first-generation systems, making little or no use of interrupts (although these do support a simplified interface to the interrupt hardware for applications that require it). Modern operating systems for PC compatables generally bypass the BIOS in order to use interrupts.

    The use of a FIFO queue to separate the application code from the interrupt service routine allows fully asynchronous operation, where computation and input/output overlap, and no data is lost except in the case of input devices, when input data arrives so quickly that the input queue fills up.

  7. Echoing of Interactive Input

    There are at several different paths that may be followed by characters that a user types when they are echoed to the display:

         put( ch ) <---  FIFO <---  Interrupt Handler
    	 |                    /    |
    	B|              ----- A  FIFO C
    	 V            /            V
        ch = get() ----> FIFO  ---> Interrupt Handler
    

    In path A the input interrupt routine enqueues character to be echoed in output queue. Things echo soon after they are typed, but they get mixed randomly into the output if you type ahead of the prompt from the applications program.

    In path B the read routine enqueues character to be echoed as it dequeues it from the input queue. The output always looks the same whether or not you type ahead of the prompt, but echoing is delayed.

    In path C an additional (short) queue is introduced. The output interrupt driver must check both queues, with the queue of characters to be echoed taking priority over normal output. This leads to the fastest possible echoing of input, but in addition to allowing input to be mixed arbitrarily with output, it also makes the output driver more complex.

    Other paths are possible; for example, the hardware may handle the job of echoing input. At the other extreme, application programs may handle echoing. On UNIX, the user of a terminal device may select the echoing mode using some of the less common system calls, stty and ioctl. These calls allow nonstandard and device dependent options to be set, and the set of options they allow is huge.

  8. Block I/O Implementation

    As with stream I/O, there are two interfaces that concern us, and the system provides a mapping between these, as well as providing for buffering to improve performance.

           ||                                   ||
        Write( buf, add )      Queue            ||
           ||  or         --->  of   ---> Interrupt Driver
        Read( buf, add )      Requests          ||
           ||          ( buf, add, sem, dir )   ||
           ||                                   ||
     user  ||           device driver           ||  hardware
           ||     (in the operating system)     ||
    
    
     buf - address of buffer matched to device's block size
     add - address of block within storage device
     sem - address of a semaphore with which to signal transfer complete
     dir - direction of data transfer
    
    

    Read and Write operate on the same queue, placing requests for block I/O in it, instead of data. Each time the device issues an interrupt, it signals that it is ready to begin a new transfer, at which point, driver removes an entry from the queue and gives it to the device, starting the next transfer.

    The queue entries consist of a buffer (main memory address) and a device address, along with a semaphore used by the interrupt service routine to signal when the transfer is complete and a code indicating the direction of the transfer.

    If user-level I/O is synchronous (that is, if the user process always waits for I/O completion), the Read and Write routines take care of waiting on this semaphore, and only one semaphore is needed per process for this purpose.

    If user-level I/O is asynchronous (that is, user processes may explicitly overlap computation and I/O), then the user process must have one semaphore allocated per buffer. This gives the user the option of starting multiple reads and writes in parallel, something the traditional UNIX interface, for example, does not allow.

  9. Device Independence

    Consider this device interface

      put( ch )                   Arbitrary software
      ch = get()         <----->  that performs actions
      Read( buf, len, add )       that look like I/O to
      Write( buf, len, add )      the user, and may even
    			      involve I/O
      Used for disk files,
      windows, network ports,
      and similar abstractions.
    
    The advantages of using a standard software interface for every device, whether disk or terminal or printer or network port have been known since the days of FORTRAN. To achieve this, it is necessary to have a user-level device interface that is sufficiently flexible to operate with both random access and sequential devices, supporting both stream and block modes of operation on any device. The low level Unix interface (read, write, seek) is one good example of such an interface.

    This interface may be considered a virtual device interface, with the input output software serving the function of virtual to physical input output operation translation.

    The virtual device may also be considered as an object, in the sense used in object-oriented programming. In fact, the first clear description of how objects in this sense can be implemented came from the field of operating systems, in a paper by Christopher Strachey in his OS 6 system from the mid 1960's. In this system, he used the following implementation:

            An open file descriptor
                 (a file object)      Code for the methods
    		________         
     F ----------->|     o--|--------> Put( F, ch )
    	       |     o--|--------> ch = Get( F )
    	       |________|    
     Data specific |        | <-- Pointers to code
     to this file  |        |     to do device dependant
     and device    |        |     part of the I/O operation
    	       |________|     (the private variables)
    
    
      Put( F, ch ) <------ the device independant read
      {                     routine called by the user.
        (*F).Put( F, ch )
      }                     It simply calls the device
    			specific routine, passing
    			the pointer to the data
    			needed to do the operation.
    			The parameter F to the function
    			that implements a method is
    			needed so the function can use
    			the private variables of the
    			object
    

    This was originally implemented in BCPL (the Basic Computer Programming Language), a predecessor of C based on CPL. Christopher Strachey invented CPL while at Cambridge; CPL stood either for Christopher's Programming Language, the Combined Programming Language, or the Cambridge Programming Language, depending on who you talk to.

    In systems with no protection, a file variable can be as simple as a pointer to the descriptor for the open file. This descriptor is typically created by the Open system service. If there is protection, the descriptor must be protected from the user program, so F, the file varialbe, is more complex than just a pointer. On Unix, for example, F is an integer index into a system maintained array of pointers to descriptors (the array is called the file table of the current process).

    This approach to implementing device independance is strongly related to object oriented programming. A file is an object. The abstract data type "file" is amenable to multiple implementations, each requiring different code. Such a type is called a polymorphic type, and one requirement of the operating system context is that multiple implementations of the abstraction coexist, so that, for example, a user can have one open file refer to a file on disk, while another represents the keyboard.

    In object oriented programming languages, the same approach described here is commonly used to implement polymorphic objects. The data structure representing the object contains pointers to the action routines that implement the abstract operations on the object.

  10. File Systems

    An open disk file is an example of a virtual device just as much as a disk or a printer interface is, when presented through a device independent interface. Thus, we might see the following structure emerging in a modern file system implementation:

                    ________
             F --->|     o--|--------> File System 
                   |     o--|--------> Code
                   |________|    
                   |        |              ________
                   |     o--|------------>|     o--|------> Disk I/O
                   |        |             |     o--|------> Code
                   |________|             |________|
                 Descriptor of            |        |
                 open disk file           |        | Data needed to
                                          |        | access the disk
                 (disk file object)       |________|
                                         Descriptor of
                                         the disk itself.
    
    				     (disk object)
    

            Code to read and write an open disk file
    
            * May convert block size to that of disk.
            * Translates address of block in file
              to disk address on the real disk.
    
            The latter is Virtual Address Translation
    

    The descriptor of the open disk file will typically contain buffers for block size conversions, and it will contain the data structure needed to convert addresses from file-relative form to absolute disk addresses.

    The descriptor of the disk device itself will typically contain the information needed for disk scheduling, the queue needed to communicate with the disk interrupt service routines, and other information specific to the actual disk being used.

    The read and write routines for the open disk file can be written in such a way that they call the standard, device independant read and write routines of the disk itself -- in effect, the read and write routines that implement the open disk file can be written as if they were user-level code.