This lecture focuses on a review of three different aspects of input output:
User level I/O requests
Virtual devices -- the abstractions provided by the system
I/O drivers -- the implementation of those abstractions
The Stream is a typical (but by no means universal) input/output abstraction. Typical stream operations are read(ch) and write(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.
Another typical abstraction is block-oriented random-access I/O, where the typical primitives might be:
Read( buffer, address ) Write( buffer, 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.
This abstraction maps naturally to disk devices in the case where the buffer length equals the sector size and the address is aligned on a disk sector boundary. It maps poorly to real devices in most other cases.
Aside: UNIX files are a generally successful attempt to generalize streams to include block I/O. The operations are:
Read( buffer ) Write( buffer ) Seek( address )Each Read and Write operation can operate with a different buffer size, varying from call to call over the life of a single file. The seek operation positions the file to any byte position, and the Read and Write operations start at that position and read or write the indicated number of bytes, leaving the position updated to the end of the sequence of bytes transferred.
The following diagram emphasizes that there are two input/output interfaces that concern us, that between user program and system, and that between system and the actual hardware. The system must typically map between these two interfaces, and it typically also provides FIFO buffering to improve I/O performance.
| |
Read( ch ) <--- FIFO <--- Interrupt Driver
| |
Write( ch ) ---> FIFO ---> Interrupt Driver
| |
user | system | hardware
Aside: 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.
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 if the input queue fills up.
There are at least two different paths that may be followed by characters that a user types when they are echoed to the display:
Read( ch ) <--- FIFO <--- Interrupt Driver
| /
B| ----- A
V /
Write( ch ) ---> FIFO ---> Interrupt Driver
In path A the input interrupt routine enqueues character to be echoed in output queue. Things echo as soon as 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.
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 ) |
| |
user | system | hardware
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.
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.
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.
Disk Throughput depends on the order of requests in the request queue. A bad order can cause lots of long seeks A good order minimise the time spent seeking
Disk schedulers can speed up the system by changing the order in which the pending I/O requests are handled. The most widely known scheduling algorithm is called the elevator algorithm.
The elevator algorithm is named after the algorithm used by an elevator in a tall building. Assume that each floor has only one button. The best service results in this case when the elevator sweeps up towards the top of the building, stopping at every floor where there is a pending service request. When it reaches the topmost floor where service was requested, it sweeps downward, again stopping at every floor where there is a pending request. This gives neither maximum throughput nor a minimum waiting time, but it gives a bounded value of the maximum wait along with decent throughput.
If the disk head position on a moving head disk is considered, the elevator algorithm can be used to schedule the movement of the head in and out from cylinder to cylinder.
Read( ch ) Arbitrary software Write( ch ) <-----> that performs actions Read( buf, add ) that look like I/O to Write( buf, add ) the user, and may even involve I/O Used for disk files, windows, network ports, and similar abstractions.
An open file descriptor
________
F ----------->| o--|--------> Read( F, ch )
| o--|--------> Write( F, ch )
|________|
Data specific | | Pointers to code
to this file | | to do device dependant
and device | | part of the I/O operation
|________|
Read( F, ch ) <------ the device independant read
{ routine called by the user.
F^.Read( F, ch )
} It simply calls the device
specific routine, passing
the pointer to the data
needed to do the operation.
This approach to implementing device independant I/O was invented by C. Strachey for his OS 6 operating system in the mid 1960's. Strachey invented CPL, the ancestor of BCPL which begat B which begat the C programming language.
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.
A disk file is an example of a virtual device
type file determines the structure of the
________
F --->| o--|--------> File System
| o--|--------> Code
|________|
| | ________
| o--|------------>| o--|------> Disk I/O
| | | o--|------> Code
|________| |________|
Descriptor of | |
open disk file | | Data needed to
| | access the disk
|________|
Descriptor of
the disk itself.
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.