Chapter 9, Sequential Input/Output

Lecture notes for 22C:116 Introduction to System Software, by Douglas W. Jones, University of Iowa Department of Computer Science

Problems Posed by Sequential Input/Output Devices

The simple computer system used in the previous chapter had a number of input/output devices, all of which can be classified as sequential devices, that is, devices where data is read or written as a sequence, and where the chronological order of input/output operations or the position of the data on a linear recording medium dominates the structure of the data.

Support for such devices is simple only for the most basic devices, and only if performance is not a primary consideration. If the system attempts to isolate the user from the details of the particular device being used, as is the case in the example system, further complexity is introduced. This chapter describes the hardware and software typically used to support two important classes of sequential devices, and it describes a framework for implementing device independent input/output.

File Variable Implementation -- Polymorphism

In Chapter 8, we assumed that any open files f could be operated on by operations such as write(f,c) or f.write(c), with the particular form depending on whether an object oriented or a procedural worldview is adopted. This requires that there be read and write operations applicable to each device in the system that have an identical user interface.

As a first draft, we might just write functions like read-keyboard() and read-tape1(), one function to read each device, where we approximate polymorphism by giving all functions identical return types and identical parameter lists. Having done this, reconfiguring a program to run on a different device involves making a global substitution on a file name and then recompiling. This is better than nothing, but hardly convenient.

A next step might be to code a universal read routine, taking a device number as a parameter and using a switch/select/case statement to call the appropriate device specific routine. This is the direciton systems were evolving in the early 1960's when the first glimmerings of object-oriented thinking began to emerge in the computer industry.

The next step is to move the device specific storage areas from the statically allocated memory of the routines to access a particular device to the file variable. This allows, for example, one read-tape routine to be used to read form any tape. A mature interface using this approach might be constructed using an oper-file description variable as described in Figure 9.1.

In Pascal
type deviceclass = (keyboard, display, tape ... );

     { device specific data records, one per device class }
     keyboardrec = ...
     displayrec = ...
     taperec = ...

     filevariable = record case class: deviceclass of
                         keyboard: ( keyfile: keyboardrec);
                          display: (dispfile: displayrec);
                             tape: (tapefile: taperec);
                    end { record case }
In C
enum deviceclass {keyboard, display, tape ... };

/* device specific structures, one per device class */
struct keyboardrec { ...
struct displayrec { ...
struct taperec { ...

struct filevariable {
     enum deviceclass class;
     union {
          keyboardrec keyfile;
          displayrec dispfile;
          taperec tapefile;
     } variant;

Figure 9.1. A data structure for file variables.

Whatever programming language is involved, the data structure we need is polymorphic -- that is, it involves a different representation for each device class. In Pascal or Ada, this is accomplished with variant records, while in C and C++, it can be accomplished with a union. Given the basic data structure shown in Figure 9.1, each of the device independent input/output routines can be reduced to a case statement which passes appropriate parameters to the appropriate device dependent input/output routine, as illustrated in Figure 9.2.

In Pascal
procedure write( var f: filevariable; ch: char );
     case f.class of
          keyboard:  keywrite( f.keyfile,  ch );
           display: dispwrite( f.dispfile, ch );
              tape: tapewrite( f.tapefile, ch );
     end { case };
end { write };
In C
void write( struct filevariable * f, char c )
     switch (f->class) {
     case keyboard: keywrite( &(f->variant.keyfile), c ); break;
     case display:  dispwrite( &(f->variant.dispfile), c ); break;
     case tape:     tapewrite( &(f->variant.tapefile), c ); break;

Figure 9.2. The device independent write routine.

Following the pattern suggested in Figures 9.1 and 9.2, each device class must provide a class specific record type, and a set of class specific input/output routines which correspond directly to the device independent input/output routines defined in Figures 8.3 and 8.4. The device specific routines for a given device are sometimes referred to as its input/output device driver.

Although this approach to implementing file variables is quite effective, it imposes an avoidable overhead on each call to an input/output service routine; it was a search for a way to handle such calls that led to the first full implementation of the object oriented model of polymorphism in the mid 1960's.

The key idea in object-oriented polymorphism is that each object, or in C and Pascal terminology, each record or structure, begins with pointers to the functions or procedures that are used to implement the operations on that object. Thus, a call to the read operation on an open file is done by calling the function pointed to by the read pointer of the record describing that open file. This way, a read operation on one file will be automatically done by the function that matches the device used for that file, without requiring any complex decoding operations.

Object oriented languages such as C++ and Java implement all polymorphic operations in essentially this way. Non object-oriented languages such as Pascal do not support pointers to functions. Languages such as C provide no built-in support for object orientation, but they allow pointers to functions, and as a result, these languages can be used to illustrate how object oriented languages implement polymorphism.

Figure 9.3 illustrates the data structure of this indirect approach in C.

/* the definition of the type filevariable */
struct filevariable {
     /* pointers to device specific routines */
     void (* rewind)( struct filevariable * f );
     char (* read)( struct filevariable * f );
     void (* write)( struct filevariable * f, char c );
	  .   /* pointers for other operations from Figure 8.4 */

/* functions implementing access methods */
#define REWIND(f)  (*(f->rewind))(f)
#define READ(f)    (*(f->read))(f)
#define WRITE(f,c) (*(f->write))(f,c)
	  .   /* defines for other operations from Figure 8.4 */

Figure 9.3. C code for file objects.

The declaration char (*p)() in C declares p to be a pointer to a function returning a character; and the call (*p)() calls the functiona pointed to by p. The defines following the structure declaration in Figure 9.3 allow a conventional function notation to be used to call the access functions of the object without burdening the programmer with the arcane syntax required to call the function pointed to by a field of a structure.

It is important to note that each access function for the file object requires a pointer to the structure representing that object to be passed as a parameter to the function! This parameter provides the code of the function with its access to all of the fields of the object itself, including not only the other access functions for the object, but also any data fields.

An Example Output Driver

The problem of writing a device driver to handle the display screen will be used to illustrate the basic structure of typical device drivers. In order to discuss the structure of such a driver, it will be necessary to first discuss the hardware interface to the display, since it is the device driver's responsibility to manage this interface. There are two primary ways of interfacing display hardware to a computer; one involves the use of a serial input/output port, and the other involves what is called memory mapping.

When a display or printer is connected through a serial port, data to be displayed is sent to the display one byte at a time, and in fact, each bit of each data byte is sent sequentially. It is the responsibility of the display hardware to interpret the various bytes as displayable character codes or control codes, and the input/output driver software need not be aware of the two dimensional nature of the physical display surface.

In fact, when this approach is used, the display or printer hardware generally includes a small microprocessor which interprets the control codes and handles the two dimensional layout of the display. This microprocessor usually has a memory mapped interface to the display itself. In fact, serial display hardware predates the computer age by many years. Émile Baudot developed the first serial binary data format for printing telegraphy in 1874, and by the 1920's, E. E. Kleinschmidt had reduced these ideas to practical form, introducing a line of printing telegraph equipment under the trademark Teletype. Kleinschmidt's model 15 Teletype operated at only 75 baud and used a 5-bit code, but the asynchronous serial interface hardware of many modern computers is fully capable of sending output to one of these old machines.

The input/output hardware of a typical computer is controlled through a set of device registers. Each input/output interface is typically associated with at least two of these registers. The details of how these registers are accessed varies from one computer system to another. On some systems, the device registers are accessed as if they were memory locations, while on others, special machine instructions are required to access device registers. As a result, even if the rest of an operating system is written in a high level language, the code to actually manipulate device registers is frequently written in assembly language.

On the IBM PC family of computers, special machine instructions called IN and OUT are used to move data between the device registers and the registers inside the CPU. C or C++ programmers usually access the input-output registers through the routines v=inp(a) and outp(a,v), where a is the input/output register number and v is a one-byte balue read from or written to that register.

A serial output device typically has at least two input/output registers, one for the data being output to the device and one or more to control options in the interface and to report on status from the interface. For example, the IBM PC and compatables, the COM1 port (serial port 1) uses device register 3F816 for data and register 3FD16 to report on the interface status. In fact, there are a total of 8 input/output registers associated with the COM1 port, but we will ignore this complexity. Figure 9.4 illustrates a very crude use of these registers.

/* the input/output register numbers */
#define COM1DATA 0x3F8
#define COM1STATUS 0x3FD

/* transmit buffer empty bit in status register */
#define TBE 0x20

/* test for transmit buffer empty */
int com1busy()
     return (inp( COM1STATUS ) & TBE) == 0;

/* output one character to the display device */
void com1write( char c )
     while (com1busy()) /* empty loop body */;
     outp( COM1DATA, c );

Figure 9.4. Crude C code to output a byte to the COM1 port on an IBM PC.

The code given in Figure 9.4 illustrates a very common coding pattern for primitive input/output routines. Prior to attempting to move data, the code waits for the device to be ready (or inversely, it waits for the device to be not busy), and then it transfers the data to the device. The crudest way to wait for a condition is to go into a tight loop doing nothing in the loop body; the change in the device status will terminate this loop.

The loop awaiting a change of status in a device is called a polling loop. Note that the verb "to poll" means to ask a question; from this, we get common English terms such as "public opinion polling" and "polling places," terms that refer to asking questions to people, either to determine the sentement of the population or to administer an election. Here, we use the term to refer to the software repeatedly asking the hardware "are you ready yet."

A computer system may have multiple displays; not only is it likely that there will be a memory mapped primary display screen, but there may be multiple asynchronous ports connected to display devices. Most standard PC configurations include COM1 and COM2, two identical asynchronous ports, and there are standard input/output register numbers reserved for COM3 and COM4. Other than the change in input/output register numbers, COM1 through COM4 have identical interfaces, so any well designed system will a single set of input/output routines to access all of these.

We will do this by including the input/output register numbers for the device as fields of the file object referring to that device. Consider, for example, extending the data structures given in Figure 9.3 to create a driver for the IBM PC COM port as outlined in Figure 9.5.

/* the definition of the type comportvariable based on filevariable */
struct comportvariable {
     /* pointers to device specific routines */
     void (* rewind)( struct filevariable * f );
     char (* read)( struct filevariable * f );
     void (* write)( struct filevariable * f, char c );
	  .   /* pointers to routines for other operations */

     /* device specific information */
     int comdata;   /* input/output register number of data register */
     int comstatus; /* input/output register number of status register */

/* functions implementing access methods */
void comwrite( struct filevariable * f, char c )
     struct comportvariable * cp = (struct comportvariable *) f;

     while ((inp( cp->comstatus ) & TBE) == 0) /* empty loop body */;
     outp( cp->comdata, c );
	  .   /* other functions */

/* function to open communications port n */
struct filevariable * opencomport( int n )
     /* register numbers of COM1 to COM4 */
     static int comports[] = { 0, 0x3F8, 0x2F8, 0x3E8, 0x2E8 };

     /* the new open file object */
     struct comportvariable * cp;
     cp = malloc( sizeof(struct comportvariable) );

     /* initializer */
     cp->write = comwrite;
	  .   /* initialize other access function pointers */
     cp->comdata = comports[n];
     cp->comstatus = cp->comdata + 5

     /* give the caller the initialized instance */
     return (struct filevariable *) cp;

Figure 9.5. An input/output driver for a PC COM port.

The code given in Figure 9.5 uses casting, a feature of the C family of languages, to force the compiler to allow variable of type (struct filevariable *) and (struct comportvariable *) to be interchanged.

In C, C++ and related languages, the notation (t)e is called a cast. This forces the value of the expression e to be interpreted as a value of type t. In C, casting has several different functions, depending on the context. When casting is used to convert between pointer types, as we have done here, the pointer resulting from the casting operation refers to the exact same memory location as the original, but the casting operator tells the compiler that the resulting pointer has a new type.
In the outside world, all users refer to open files using the type (struct filevariable *), but within the code to acces one of the asynchronous communication ports, it is necessary to override the type checking and use the special fields declared in the comportvariable structure. In an object oriented language such as C++ or Java, we would say that comportvariable is a subclass of filevariable, and that filevariable, because it contains no implementations of any access functions, is a virtual class or an interface specificaiton, while comportvariable, because it includes methods and an initializer (the opencomport routine) would be called a concrete class.

The driver shown in Figure 9.5 does not include code for the block or line oriented output routines dispwriteline and dispwriteblock that are natural consequences of the suggestions outlined in Figure 8.4; these can easily be written using the dispwrite service and a simple loop.

The communications ports on an IBM PC also allow input, so we should write a comread routine and add corresponding comreadblock and comreadline routines. We also need a comrewind routine, not because there is any meaningful rewind operation on an IBM PC com port or, for that matter, on any asynchronous communications port, but rather, because our standard interface to open files allows this operation, and we must provide implementations for all of the operations, whether or not they are meaningful. Perhaps the comrewind operation should just raise an exception.

When a system supports multiple serial input/output ports, all of them are sometimes connected through a single device, called a serial input/output multiplexor. When this is done, there is typically a device register which is used for port selection. Only after the port select register has been set to select a particular port can the status and data registers be used to communicate with that port.

Memory Mapped Output

Memory mapped display interfaces involve the use of a special direct-memory-access peripheral processor (the display controller) which continuously scans an array in memory called the memory image of the display in order to generate a video signal for the display. For text-only display screens, the memory image is a two dimensional array of characters, typically 24 rows by 80 columns. (The 80 column line length is a legacy from the days when punched cards were widely used for text storage; the most widely used card format stored 80 characters per card.)

For black-and-white graphics displays, the memory image is usually a two dimensional array of bits, one bit per dot on the screen, with 8 bits packed in each byte; such a display is called a bit-mapped display. For color graphics displays, the memory image is usually a two-dimensional array of pixels, and we refer to the display as a pixel-mapped display. Low resolution color displays usually use one byte per pixel, while high resolution color displays may use 16, 24 or 32 bits per pixel. For example, a high resolution color display might use 10 bits each for the red, green and blue components of the display, wasting two bits of each 32 bit pixel.

The software needed to support a memory mapped graphics display interface is quite complex, even if all that is to be done is to plot text on the display. The reason is that, to display a character, the dot pattern which represents that character must be moved to the appropriate place on the screen. Line drawing, textures, and windows, make memory mapped graphics displays attractive to users, but they add considerable complexity to the software. Memory mapped text displays are, by comparison, quite easy to support, and all of the operations required to support such displays also must be performed in supporting a graphics display.

While many IBM PC compatables contain hardware that will operate as a text-only memory mapped display, this hardware is used only during startup, and once the system is up and running, the display switches to bit-mapped or pixel-mapped operation. Macintosh computers appear to have entirely abandoned text-only display technology and rely entirely on a bitmapped display.

Fully general bit mapped or pixel mapped display software is quite complex! There is usually one basic data type used for characters, cursors and icons; a good name for such a data type is the glyph; a glyph might be represented by a bitmap or a pixmap (pixel map), plus 4 integers, the width of the glyph, the height of the glyph, the X-location of the origin of the glyph, and the Y-location of the origin. The basic operation used for displaying cursors, icons and characters would logically be "display this glyph with its origin at this X and Y coordinate on the screen."

A font, that is, a set of rules for displaying text on the screen, must then be an array of glyphs, indexed by character, and the fundimental operation for displaying text on the screen must operate in terms of a current font and a current location (the cursor position). Displaying a character must display the glyph for that character at the current position and then advance the position by the width of the character. Early display software assumed that the characters were always plotted left to right, but modern systems allow a negative width to accomodate languages such as Hebrew and Arabic that are written right to left.

A full discussion of memory mapped displays cannot be given here; the complexity of window management is beyond the purview of this chapter, and we have not yet covered a sufficient amount of material on direct-memory-access device interfaces to treat the low level interface to such devices.

Keyboard Input Drivers

The driver for a typical keyboard is noticeably more complex than that for a character oriented display device. The primary reason for this is the need to echo what is typed to the display screen. Except on very old remote terminal systems or on systems where special hardware does most of the input/output driver's work, echoing is the responsibility of software. That is, when a user hits a key on the keyboard, the display of the corresponding character on the display is the result of the interaction of system software and application software.

On old remote terminals, it was common to run the communications lines between the terminal and the computer in half-duplex mode, that is, in a mode where data could only go one way at a time. Thus, it was necessary for the terminal itself to handle the echoing of keyboard input. On remote terminal systems built since the early 1970's, however, communication has usually been done in a full-duplex mode, where data can go both ways at the same time; thus, what is typed on a terminal goes all the way to the computer, and only after it has been input is it sent back to the screen. With modern personal computers and high performance workstations, the story remains essentially the same.

Another source of complexity in keyboard drivers is the line-buffering software. When a line of input is requested, all reasonable systems allow users to erase typing mistakes; sometimes word-erase and line-erase functions are provided. In the extreme case, some systems allow a line of input to be edited arbitrarily, for example, by deleting a word from the middle of the line without requiring that the entire line be retyped.

In order to allow a full discussion of keyboard input, we need a simple keyboard interface. Modern PC keyboards are quite complex, with a local microprocessor in the keyboard and a low speed bidirectional network connection connecting the keyboard and the host computer. This is too complex for this discussion, so instead, we will consider a system where the keyboard uses an asynchronous communications port to send data to the computer.

On an IBM PC compatable, the communications ports are bidirectional. Writing data to the data register of one of the COM ports causes that data to be transmitted. Reading data from the very same data register does not give the data being transmitted, but instead, it gives the most recent character received. The status register of the COM port contains a status bit, RxRD indicating that a new character has been received since the last time the software inspected the data register. As a result, we can write code to read a character from the COM1 port by following a pattern very similar to that used in Figure 9.4 to write data to the same port. This is given in Figure 9.6

/* the input/output register numbers */
#define COM1DATA 0x3F8
#define COM1STATUS 0x3FD

/* transmit buffer empty bit in status register */
#define RxRD 0x01

/* test for receive buffer not ready */
int com1idle()
     return (inp( COM1STATUS ) & RxRD) == 0;

/* input one character to the keyboard device */
char com1read()
     while (com1idle()) /* empty loop body */;
     return inp( COM1DATA );

Figure 9.6. Crude C code to input a byte from the COM1 port on an IBM PC.

The code shown in Figure 9.6 is significantly worse than the code from Figure 9.4 that it parallels. This is because the receiver for the communications line may detect many errors, for example, parity errors. Most of the bits of the status register are reserved for reporting these errors, and the software should check these to determine whether the data received is of any value.

A complete keyboard driver on a modern machine must include a low-level interface for character-at-a-time interaction, without echoing, and it must include a high-level interface for text input that echoes characters as they are typed and supports erase functions. Figure 9.7 presents such a driver, based on the framework from Figure 9.5.

/* added functions implementing access methods */

char comread( struct filevariable * f )
     struct comportvariable * cp = (struct comportvariable *) f;

     while ((inp( cp->comstatus ) & RxRD) == 0) /* empty loop body */;
     return inp( cp->comdata );

void comreadline( struct filevariable * f, char buf[], int len );
     int p = 0;

     do {
          char ch = f->read(f);
          if (ch >= ' ') { /* character is printable */
               if (p < len) { /* space is available in buffer */
                    buf[p] = ch;      /* put it in the buffer */
                    p = p + 1;
                    f->write(f, ch);  /* echo it */
          } else if (ch == '\b') { /* character is backspace */
               if (p > 0) then begin
                    p = p - 1;
                    f->write(f, '\b');  /* erase a character */
                    f->write(f, ' ');
                    f->write(f, '\b');
     } while ((ch != '\n') && (ch != '\r'));
     if (p < len) { /* space is available in buffer */
	  buf[p] = '\0';    /* put terminator in buffer */
     f->write(f, '\r');
     f->write(f, '\n');
Figure 9.7. A keyboard device driver.

The call comreadline(f,b,l), using the routine defined in Figure 9.7 reads one line from the communications port f into the buffer b, reading no more than l characters. If fewer than l characters are read, a null will be appended to the buffer. This convention of using a null to mark the end of a string is typical of UNIX and C; it would be equally appropriate to return the number of characters read, or to return an object of type string, with the length of the string encoded in a manner that depends on the implementation of the string class.

The code of comreadline given in Figure 9.7 assumes several things that may or may not be appropriate! First, it assumes that any echoing of input should be to the same COM port that the input is being read from. This is apporpirate if the user is accessing the computer using a dial-up modem from a remote computer, and it is appropriate if the user is using an old-fashioned dumb terminal, but it would not be appropriate for a user of a serial keyboard who wanted the input to echo on a bitmapped display.

The second assumption made in the code in Figure 9.7 is that successive characters can be erased from the display screen by outputting the string "\b \b" (backspace space backspace). This is not true for ink on paper display devices such as old fashioned Teletype printers, nor is it true for displays supporting variable-width or proportionally spaced fonts. It is true for the classic "dumb terminals" that dominated the computer market from around 1970 to 1980, and it is true for software on modern PCs that emulates such terminals. All of these use a fixed-width fonts and assert the rule that outputting a space erases the previously displayed material on that part of the screen.

An important design decision was made in writing the keyboard driver shown in Figure 9.7. This involves how echoing is controlled. In this case, the decision was that "keyreadline" will echo, but "keyread" will not. Thus, software which uses "keyread" may do its own echoing but need not do so, for example, when reading a password or treating all keys on the keyboard as function keys. When "keyreadline" processes input, it does not echo any characters the user types beyond what will fit in the buffer. Many modern systems use an entirely different approach to the control of echoing, with a device mode that may be set to "echo" or "noecho". This is probably a bad choice, but it has become thoroughly embedded into UNIX and systems that borrow heavily from UNIX.

Some systems allow 'echo tables' and 'terminator tables' to be established for keyboard input. The echo table specifies, for each character in the character set, whether or not that character is to be echoed when typed; the terminator table specifies, for each character, whether or not that character is to be treated as an end of line character when typed. This approach allows a very flexible approach to input, although most applications rarely need this flexibility.

Finally, on systems with super and subscript capability in their display devices, and on those with the ability to overstrike two characters, it is useful to have the "keyreadline" routine convert input to a canonical form. Thus, if SUP and SUB are the control codes for super and subscript, and the user types "a" SUP SUB SUP "b", the input buffer should contain only "a" SUP "b". Similarly, if the user overstrikes "O" with "+", the input buffer should contain the same thing as it contains when the user overstrikes "+" with "O", typically "+" BS "O" in both cases. The result of this is that if two users type inputs which look the same but they do it in different ways, the internal representation will be the same, depending only on how the input looks and not on how it was typed.

Magnetic Tape Hardware

Magnetic tape drives usually present an interface to the system software which is quite different from terminal devices. There are two reasons for this: First, tape drives typically transfer data at a relatively high speed, thus demanding direct memory access; second, starting or stopping a tape drive cannot be done instantly, so gaps are typically left separating blocks on the tape. Each block is usually read or written with a single direct memory transfer, the interblock gap is long enough that if a new transfer is not started immediately after the first ends, the tape can be stopped. Note that blocks of data on tape are sometimes called physical data records (as opposed to the logical records dealt with by user programs), and that the interblock gaps are sometimes called interrecord gaps.

Today, 8 millimeter video cassettes are widely used as backup devices for large computer systems, and a few older computer centers maintain 9-track reel-to-reel drives in order to allow access to huge libraries of data accumulated during the 1960's and 1970's. A handful of computer centers in the country even maintain 7-track reel-to-reel drives to allow access to archival data from the 1950's and early 1960's. Whatever the tape format, these devices pose some special problems!

The first problem posed by all high performance tape recording technology is that of data rate. Even the old 7-track tapes from the late 1950's could store 200 to 400 bytes per inch, and could read and write the tape while it was running at hundreds of inches per second. This means that they were moving data at rates of over 20,000 bytes per second. The computers of that era could not execute more than 1,000,000 instructions per second, so they had about 50 machine instructions available to transfer each byte.

Today, video tape technology is widely used with computers. This allows on the order of 20,000,000 bytes per second to be stored; if we have a CPU running at 1 gigahertz, it can, just barely, execute 50 machine instructions per byte transferred, but note that the CPU is not the bottleneck! Our modern RAM technology typically runs around 50 nanoseconds per memory access, and this allows exactly 20,000,000 accesses per second! Clearly, just as the machines of 1960 required special hardware to handle high performance tape interfaces, we still require this today!

This performance problem is usually solved by building a special class of input/output interface called a direct memory access interface. Such an interface contains a small special purpose processor able to read data from a buffer in main memory and send it to the device, and able to read data from the device and store if in memory. The input/output registers for a direct memory access device are not used to transfer data to and from the device, but rather, they are used to control and monitor the transfer, while the transfer itself is done directly to RAM.

A typical direct memory access interface for a device such as a tape transport is controlled by the following device registers:

the address of the next byte (or word) to be read or written by the direct memory access interface processor. This is incremented by the size of the data item as each byte (or word) is read or written.

the number of bytes remaining to be transferred. This is decremented by the appropriate amount as each byte (or word) is read or written.

this contains a field that determines whether data should be read or written. Once the software sets the address and count registers, it can start a data transfer by setting the control register to read or write.

this contains a bit that indicates whether a direct memory access transfer is currently in progress. Typically, it also contains a number of other status indicators, so the software can determine, for example, if there is a tape in the drive, if it is moving or stopped, if the most recent read contained any errors, and if the write-protect indicator is set to allow the tape to be written.
The fact that the tape is written one block at a time poses new problems. Bringing the tape up to recording speed is not instantaneous, nor is stopping the tape. As a result, as the software records a series of blocks, there will necessarily be gaps on the tape between the blocks. These are called interrecord or interblock gaps, and once it is recognized that they are inevitable, it is common to extend the recording format to allow these gaps to serve a useful purpose.

Typically, each block recorded on the tape begins with a header, so that, when a read command is issued, the interface hardware can easily identify the start of the next block on the tape by identifying the unique header. At the end of each block, it is common to record a trailer that contains such things as a checksum of the data in the block. Checksums may be as simple as an arithmetic sum of the bytes in the block, or they may involve fairly complex computations such as the cyclic redundancy check. However a checksum is computed, it allows detection of simple errors in the recorded data when it is read.

The desire for error detection explains why, on the classic reel-to-reel computer tape formats, 7 tracks were used for recording data with 6-bit bytes, and 9 tracks were used for recording data with 8-bit bytes. In each case, an extra recording track was added to the data to allow a parity bit to be recorded with each byte. The parity bit is just the exclusive-or of all the data bits in the byte. If one track is read incorrectly, for example, because a bit of dust was caught between the tape and the record-playback head, the parity recorded on the tape will not match the parity computed from the data just read, so the error can be detected.

An example routine to output one block to tape is shown in Figure 9.8.

procedure writetapeblock( buffer: memoryaddress, length: int );
     tape_address_register := memoryaddress;
     tape_count_register := length;
     tape_control_register := write_command;
     while transfer_in_progress in tape_status_register do ;

Figure 9.8. Write one block to tape, in Pascal.

Note that tape drives frequently support a number of commands which have no relation to the commands supported by other kinds of devices. Thus, in addition to the read and write commands, there may be special commands. The following list is typical of the special tape commands associated with classic 7-track and 9-track tapes. Most modern tape drives have significantly simpler interfaces without much of this complexity:

In addition to the complexity of the underlying command set, the magnetic tape interface poses new problems because, after each read operation, it the buffer is not the only item that must be returned! It is also necessary to return such things as whether the block just read was an end-of-file mark, whether there were any errors, and so on. It would be possible to rely on exception handling mechanisms for this, but in UNIX and most other operating systems, these conditions are signalled by special return values from the basic services. Thus, for example, in addition to reading a block of data into the indicated buffer, the read-block service also typically returns the number of bytes read, with the convention that a negative return value indicates an error or end of file condition, and some secondar global variable (errno in UNIX) is used to give the details of the exceptional condition.

For now, we will ignore this complexity and look at how we can integrate the tape interface into the file model from Figure 9.3. The first problem we face is that the primitive operations of our tape interface do not operate one character-at-a-time, but rather, one block at a time, thus, the primitive operations we need are the read-block and write-block routines suggested in Figure 8.4, and not the read-character and write-character or read-line and write-line routines. From this, we arrive at the code outlined in Figure 9.9

/* the definition of the type comportvariable based on filevariable */
struct tapevariable {
     /* pointers to device specific routines */
     void (* rewind)( struct filevariable * f );
     char (* read)( struct filevariable * f );
     void (* write)( struct filevariable * f, char c );
     void (* readblock)( struct filevariable * f, char buf[], int len );
     void (* writeblock)( struct filevariable * f, char buf[], int len );
          .   /* pointers to routines for other operations */

     /* device specific information */
     int tapeaddr;   /* I/O register number of DMA address register */
     int tapecount;  /* I/O register number of DMA byte count register */
     int tapestatus; /* I/O register number of status register */
     int tapecommand;/* I/O register number of command register */

/* functions implementing access methods */
void tapewriteblock( struct filevariable * f, char buf[], int len )
     struct tapevariable * t = (struct tapevariable *) f;

     /* setup the 32 bit address */
     outp( t->tapeaddr,     ((int)buf      ) & 0xFF );
     outp( t->tapeaddr + 1, ((int)buf >>  8) & 0xFF );
     outp( t->tapeaddr + 2, ((int)buf >> 16) & 0xFF );
     outp( t->tapeaddr + 3, ((int)buf >> 24) & 0xFF );

     /* setup the 16 bit count */
     outp( t->tapecount,     ((int)len      ) & 0xFF );
     outp( t->tapecount + 1, ((int)len >>  8) & 0xFF );

     /* start operation */
     outp( t->tapecommand, TAPEWRITE );

     /* await operation complete */
     while ((inp(t->tapestatus) & TAPEDONE) == 0) ;

Figure 9.9. The core of a tape driver.

The code outlined in Figure 9.9 accounts for a troublesome characteristic of the IBM PC compatable device registers; like the device registers on many other systems, the minimal I/O bus allows only 8-bit data transfers. This is particularly annoying when the data being read or written is a 32 bit buffer address or a 16 bit block size, as suggested in the figure. This example does not rest on any real device; different real devices could have different limitations on the block size or address structure.

The code outlined in Figure 9.9 allows each block recorded on the tape to be of a different length! This allows a maximum of flexibility, but reading a tape made up of various block sizes could be quite difficult. IBM's OS 360/370/390 is one of the last systems to have been designed in the era when magnetic tape was one of the primary storage media used on computers. Under this system, when a tape drive is opened for input or output, the usual approach sets the block size once, and therefore, tape files always consist of a sequence of identical sized blocks. This requires a very complex parameter list for the open operation, both in programs and in the control language, but it eliminates many potential problems that can arise with the unconstrained scheme outlined here.

The UNIX operating system provides two sets of device drivers for magnetic tape, a 'raw' driver which requires that the user handle the blocking or deblocking of data, and a 'cooked' driver which automatically constructs 1024 byte records using a variable length record packing scheme. Finally, UNIX provides a utility called DD (an obvious pun on IBM's job control language data definition statement) which can be used with the raw tape interface to read or write 'foreign' tapes and convert them to standard UNIX text files.

Blocking and Deblocking

Users of the magnetic tape interface suggested in Figure 9.9 are likely to want to read or write some tapes as streams of characters or as sequences of lines of text. To allow this, we must provide a new layer of software that allows characters to be gathered into blocks on output or blocks to be returned to the user one character at a time on input, and on top of this, we must put a layer that breaks lines into sequences of characters for output or constructs lines from sequences of characters.

There is a similarity between this problem and that illustrated by the comreadline routine shown in Figure 9.7. This latter routine assumes, as primitives, a set of character sequential input/output routines and constructs, as a higher level routine, a line sequential routine. Our new goal is to assume, as low level primitives, block sequential operations, and use these to construct, at a higher level, a set of character sequential operations.

When we read or write blocks using character sequential primitives, we need no extra data structures, but if blocks are to be assembled from a sequence of character writes, or disassembled with the successive characters returned in a sequence of character reads, we need a place to store the block during assembly. Typically, what we will do is store the a buffer for this purpose as part of the open file descriptor. Figure 9.10 shows an appropriate extension of the basic data structures allowing this.

/* the definition of the type comportvariable based on filevariable */
struct tapevariable {
     /* pointers to device specific routines */
     void (* rewind)( struct filevariable * f );
     char (* read)( struct filevariable * f );
     void (* write)( struct filevariable * f, char c );
     void (* readblock)( struct filevariable * f, char buf[], int len );
     void (* writeblock)( struct filevariable * f, char buf[], int len );
          .   /* pointers to routines for other operations */

     /* device specific information */
     int tapeaddr;   /* I/O register number of DMA address register */
     int tapecount;  /* I/O register number of DMA byte count register */
     int tapestatus; /* I/O register number of status register */
     int tapecommand;/* I/O register number of command register */

     /* blocking and deblocking information */
     char * tapebuffer; /* pointer to buffer used for deblocking */
     int  tapebufpos;   /* position in buffer */
     int  tapebufsize;  /* size of buffer */

/* functions implementing access methods */
void tapewrite( struct filevariable * f, char c )
     struct tapevariable * t = (struct tapevariable *) f;

     /* make sure a buffer is available */
     if (t->tapebuffer == NULL) {
          t->tapebuffer = malloc( t->tapebufsize );
          t->tapebufpos = 0;

     /* put the character in the buffer */
     t->tapebuffer[t->tapebufpos] = c;
     t->tapebufpos = t->tapebufpos + 1;

     /* if the buffer is full, put it on tape */
     if (t->tapebufpos >= t->tapebufsize) {
          f->writeblock( f, t->tapebuffer, t->tapebufsize );
          t->tapebufpos = 0;
Figure 9.10. Blocking character sequential output to tape.

In Figure 9.10, we have assumed that, initially, tape files are opened without allocating space for a blocking or deblocking buffer. After opening, if a buffer is needed, it will be allocated by the character sequential input/output routines. The only piece of information provided by the open routine (the initializer) is the size of the buffer to be used for blocking or deblocking this tape.

The tapewriteline service would have a structure very similar to the comwriteline service that complements the comreadline given in the Figure 9.7, and therefore, it is left as an exercise for the reader.

An interesting puzzle comes up with the blocking and deblocking services. If all user interaction is at the block level, a user can read the blocks of a tape up to some point and then begin writing blocks, overwriting all of the remainder of the file from that point onward. We would like to construct the character sequential services to operate in the same way, so that a user can read the characters of a file up to some point and then start writing new characters. This requires that the read and write deblocking routines use the buffer and buffer position in compatable ways!

On the other hand, if the user tries to write the first few blocks of a magnetic tape and then read the remainder of the tape, we are not compelled to produce a meaningful result, since a sequence of write block operations followed by a read-block operation has no well defined meaning with variable-sized blocks on tape.

System Generation

Although the specific data structures described in this chapter are not universal, they are quite typical, and all system designers face a similar problem: How are these data structures created initially? The process of installing the 'bare hardware' of a system includes the job of assigning specific device control register addresses, so it is not hard for the user to create a list giving, for each device, the addresses of each of its device control registers. The problem is to convert this to a collection of device description records in memory and an initial directory from which the "open" system service can construct file variables.

The process of creating a set of device description records and an initial directory is often called system generation. On the smallest systems, this is simply done by building these data structures in assembly language. On larger systems, neither of these alternatives is unreasonable -- modern PC's for example, are so complex that reconfiguring the BIOS for a new device is frequently nearly impossible, and most large systems are not distributed in source form so that the user can reconfigure the system by recompiling or reassembling.

One common alternative is to have a macro package which handles the details of creating the basic I/O data structures. Typically, there is one macro for each device type, where that macro takes, as parameters, the textual name to be associated with that device and the addresses of each of its device control registers. As a result, the source program which must be assembled to generate the system closely resembles the system description which the hardware people might have scribbled on a sheet of paper when they plugged all of the pieces together.

A second approach to system generation is to have a special "sysgen" program which reads a system configuration description which is written in a system configuration language. This program can be viewed as a very special compiler which builds an object file containing the initial data structures of the operating system. The system generation programs for some systems are interactive, prompting the user for each piece of information which may be needed, and explaining how to find information which is needed.

With IBM PC compatables, the BIOS, or Basic Input/Output Subsystem, provides the most basic input/output drivers, and the problem of configuring the BIOS for a new device is typically handled by an interactive BIOS configuraiton program that prompts for the relevant details about the device. This works well only if the designers of the BIOS have anticipated the device you intend to connect.

Independently of which approach is used, the system generation process for large systems also includes the selection of the set of device drivers which are to be linked into the system. On the PC, this is true because the drivers provided by the BIOS usually offer only poor performance and only support the I/O model of the DOS system and not that of higher performance systems such as Windows or Linux. Most high performance systems are distributed with a very large set of device drivers, sometimes one for each device which has ever been widely sold for the machine in question. Clearly, there is no point to including fifteen different drivers for fifteen different makes of magnetic tape drive in the loaded operating system if only one kind of tape drive is actually attached to the machine! Typically, the selection of device drivers is done by selectively link editing the desired drivers into the object file holding the system, although nowdays, many drivers are dynamically loaded from disk only when they are first used.

The Limits of Device Independence

The original goal of using file variables which could be attached to any device was to allow programs to be written which behave the same independently of which device they are actually attached to. This goal has been met by the device drivers described above only for those services which are supported in a common way by all devices. Thus, a program which produces output using only the "writeline" service can as easily produce output on tape as on the display screen, but a program which uses the "tapeskip" operation to read the blocks on a tape in a random order cannot be run using the keyboard.

This problem is a universal problem which all operating systems must face. In the oldest operating systems, device independence was not even attempted, and users were required to consider the characteristics of the devices being used when writing any input/output code. Starting in the mid 1960's, device independence became quite important. The Pascal language and early versions of the UNIX system represent an extreme approach to device independence; few if any device dependent services were provided, so all programs could be run with any device. This extreme position can be viewed as an overreaction to the state of affairs which had existed previously. Clearly, there are times when device dependent features are desirable.

At the time of this writing, the pendulum may be swinging back from device independence to device dependence for a number of reasons: The emergence of windows and bitmapped displays has made it progressively less convenient to treat the display device in the same way as other devices. The specific properties of special hardware devices such as magnetic tape drives will always require special services. It is not convenient to treat communications lines between computer systems in the same way that communications lines to remote terminals are treated, even when the physical hardware interface is exactly the same. Finally, random access disk files support special operations which do not cleanly match those of any other class of device.

Despite the abandonment of absolute device independence, it is likely that most systems will preserve a kernel of device independent services comparable to that described here, with additional services provided for each class of device. Furthermore, most devices will fit cleanly into only one of a few large classes, for example, "display window", "tape", "disk" and "communications line". Although there will be some programs which are truly device independent, most will require that at least some of the files with which they deal exhibit the characteristics of one or more of these classes.


The reader should be familiar with the following terms after reading this section:

sequential devices             full-duplex communications
device independence            line buffering
device identifier              terminals
device class                   canonical input forms
device drivers                 nine track magnetic tape
serial input/output ports      interblock gaps
memory mapped displays         recording density
device interface registers     transfer rate
polling loops                  end-of-file mark
device description records     tape labels
device control blocks          tape operations
bit mapped displays            tape errors
control characters             blocking factor
echoing                        system generation
half-duplex communications
In addition, the reader should be familiar with the following system services of the example operating system:


  1. Using the "write" service shown in Figure 9.2, and the definitions given in Figures 8.3 and 8.4, write code for the following system services:

    a) "read" b) "readblock" c) "writeblock" d) "readline" e) "writeline"

  2. Using Figure 9.5 and Figure 9.7 as guides, write code for the following parts of the display driver from Figure 9.5:

    a) "comwriteline" b) "comwriteblock"

  3. Modify the code for "comreadline" in Figure 9.7 so that it handles a word-erase function. This function should be invoked when the user types an ASCII DEL (delete) control character ('\x7F' in C). A word is defined as follows in EBNF:
    <word> ::= ( <punc> | { <text> } ) { <space> }
    <space> ::=  -- the space character
    <punc> ::=   -- any printing character other than letters and digits
    <text> ::=   -- any letter or digit

  4. Write the "comreadblock" routine to match the other keyboard routines given in Figure 9.7 and preceeding figures, and then comment on why this routine would be very unlikely to be used for reading from the keyboard.

  5. Write the "tapereadblock" system service to match the "tapewriteblock" service defined in Figure 9.9. Assume that the device status register includes the following bits: Your routine should detect errors and take reasonable actions when they are detected. You must therefore extend the specification of the readblock routine, since no errors are mentioned in the specification that was given.

  6. Rewrite the "tapewriteblock" system service that was given, taking into account the fact that the tape must be moving at full speed in the forward direction before a read is legal. The tape control interface contains the following commands, in addition to the basic commands outlined prior to Figure 9.9. Assume the status register includes the following bits: Prior to trying to write a block, your code must first stop the tape if it is moving in the wrong direction and then restart it in the right direction, and in any case, it must not issue a write command until the tape is moving at full speed.

  7. Write the "taperead" routine to match the "tapewrite" routine given in Figure 9.10. Be careful to arrange things so that a change from reading to writing while moving the tape forward will go smoothly.

  8. Write a "tapewriteline" routine that uses the "tapewrite" routine given in Figure 9.11.


Pages 254 through 259 of

Computer System Software, the Programmer/Machine Interface by R. S. Ellzey (SRA, 1987)
provide a short introduction to many of the issues discussed here. The description in Chapter 5 of
Software Systems Principles, A Survey by P. Freeman (SRA, 1975)
is much more detailed discussion of the general principles involved, without covering any device specific information.

A general discussion of device management is given in in Section 9.4 of

Systems Programming by J. J. Donovan (McGraw Hill, 1972).
This includes a discussion and illustration of the storage of data on tape and disk.

The best source of information about the characteristics of particular devices are the manuals for the use of those devices. No particular manuals will be recommended here, but there is a large market in texts that describe the hardware device interfaces of the IBM PC. Most good bookstores will have several.

The C code shown in Figure 9.3 is based on the definition of device-independent input/output streams used in the OS6 operating system; see

OS6 - An Experimental Operating System for a Small Computer, Part 2: Input/Output and Filing Systems, by J. E. Stoy and C. Strachey, The Computer Journal 15, 2 (August 1972) 195-203.
Note that Strachey is the inventor of the CPL and BCPL languages, and that BCPL was an ancestor of the C language (through the short lived B language).

The UNIX device dependent service interface is described in Section IOCTL(2) of the

UNIX Programmer's Manual, Vol. I (Holt, Rinehart and Winston, 1983).
Sections MTIO(4) and TTY(4) in the same manual cover the magnetic tape and terminal dependent IOCTL calls. These are dismayingly complex and illustrate the oversimplification of the example services presented here.

Operating System Concepts by Peterson and Silberschatz (Addison-Wesley, 1983)
contains a reasonable discussion of system generation in Section 12.7.