1.2.3 I/O Structure

 A large portion of operation system code is dedicated to managing I/O, both because of its importance to the reliability and performance of a system and because of the varying nature of the devices.

Recall from the begining of this section that a general-purpose computer system consists of multiple devices, all of which exchange data via a common bus. The form of interrupt-driven I/O described in Section 1.2.1 is fine for moving small amounts of data but can produce high overhead when used for bulk data movement such as NVS I/O. To solve this problem, direct memory access(DMA) is used. After setting up buffers, pointers, and counters for the I/O device, the device controller transfers an entire block of data directly to or from the device and main memory, with no intervention by the CPU. Only one interrupt is generated per block, to tell the device driver that the operation has completed, rather than the one interrupt per byte generated for low-speed devices. While the device controller is performing these operations, the CPU is available to accomplish other work.

Some high-end systems use switch rather than bus architecture. On these systems, multiple components can talk to other components concurrently, rather than ompeting for cycles on a shared bus, In this case, DMA is even more effective. Figure 1.7 shows the interplay of all components of a computer system.

STORAGE DEFINITIONS AND NOTATION

 The basic u nit of computer storage is the bit. A bit can contain one of two values, 0 and 1. All other storage in a computer is based on collections of bits. Given enough bits, it is amazing how many things a computer can represent: numbers, letters, images, movies, sounds, documents, and programs, to name a few. A byte is 8 bits, and on most computers it is the smallest convenient chunk of storage. For example, most computers don't have an instruction to move a bit but do have one to move a byte.  A less common term is word, which is a given computer architecture's native unit of data. A word is made up of one or more bytes. For example, a computer that has 64-bit registers and 64-bit memory addressing typically has 64-bit (8-byte) words. A computer executes many operations in its native word size rather than a byte at a time.

Computer storage, along with most computer throughput, is generally measured and manipulated in byutes and collections of bytes. A kilobyte, or KB, is 1,024bytes; a megabyte, or MB, is 1,024(2) bytes; a gigabyte, or GB, is 1,024(3) bytes; a terabyte, or TB, is 1,024(4) bytes; a  petabyte, or PB, is 1,024(5) bytes. Computer manufactures often round off these numbers and say that a megabyte is 1 million bytes and a gigabyte is 1 billion bytes. Networking measurements are an exceptioni to this general rule; they are given in bits(Because networks move data a bit at a time).

1.2.2 Storage Structure

 The CPU can load instructions only from memory, so any programs must first be loaded into memory to run. General-purpose computers run most of their programs from rewritable memory, called main memory (also called random-access memory, or RAM). Main memory commonly is implemented in a semiconductor technology called dynamic random-access memory(DRAM).

Computers use other forms of memory as well. For example, the first program to run on computer power-on is a bootstrap program, which then loads the operating system. Since RAM is volatile-loses its content when power is turned off or otherwise lost-we cannot trust it to hold the bootstrap program. Instead, for this and some other purposes, the computer uses electrically erasable programmable read-only memory (EEPROM) and other forms of firmwar - storage that is infrequently written to and is nonvolatile. EEPROM can be changed but cannot be changed frequently. In addition, it is low speed, and so it contains mostly static programs and data that aren't frequently used. For example, the iPhone uses EEPROM to store serial numbers and hardware information about the device.

All forms of memory provide an array of bytes. Each byte has its own address. Interaction is achieved through a sequence of load or store instructions to specific memory addresses. The load instruction moves a byte or word from main memory to an internal register within the CPU, whereas the store instruction moves the content of a register to main memory. Aside from explicit load and stores, the CPU automatically loads instructions from main memory for execution from the location stored in the program counter.

A typical instruction-execution cycle, as executed on a system with a von Neumann architecture, first fetches an instruction from memory and stores that instruction in the instruction register. The instruction is then decoded and may cause operands to be fetched from memory and stored in some internal register. After the instruction on the operands has been executed, the result may be stored back in memory. Notice that the memory unit sees only a stream of memory addresses. It does not know how they are generated (by the instruction counter, indexing, indirection, literal addresses, or some other means) or what they are for (instructions or data). Accordingly, we can ignore how a memory address is generated by a program. We are interested only in the sequence of memory addresses generated by the running program.

Ideally, we want the programs and data to reside in main memory permanently. This arrangement usually is not possible on most systems for two reasons:

1. Main memory is usually too small to store all needed programs and data permanently.

2. Main memory, as mentioned, is volatile-it loses its contents when power is turned off or otherwise lost.

Thus, most computer systems provide secondary storage as an extension of main memory. The main requirement for secondary storage is that it be able to hold large quantities of data permanently.

The most common secondary-storage device are hard-disk drivers(HDDs) and nonvolatile memory (NVM) devices, which provide storage for both programs and data. Most programs (system and application) are stored in secoundary storage untile they are loaded into memory. Many programs then use secondary storage as both the loaded into memory. Many programs then use secondary storage as both the source and the destination of their processing. Secondary storage is also much slower then main memory. Hence, the proper management of secondary storage is of central importance to a computer system, as we discuss in Chapter 11.

In a larger sence, however, the storage structure that we have described - consisting of registers, main memory, and secondary storage - is only one of many possible storage system designs. Other possible components include cach memory, CD-ROM or blu-ray, magnetic tapes, and so on. Those that are slow enough and large enough that they are used only for special purposes - to store backup copies of material stored on other devices, for example - are called tertiary storage. Each storage system provides the basic functions of storing a datum and holding that datum until it is retrieved at a later time. The main differences among the various storage system lie in speed, size, and volatility.

The wide variety of storage systems can be organized in a hierarchy(Figure 1.6) according to storage capacity and access time. As a general rule, there is a trade-off between size and speed, with smaller and faster memory closer to the CPU. As shown in the figure, in addition to differing in speed and capacity, the various storage systems are either volatile or nonvolatile. Volatile storage, as mentioned earlier, loses its contents when the power to the device is removed, so data must be written to nunvolatile storage for safekeeping.

The top four levels of memory in the figure are constructed using semiconductor memory, which consists of semiconductor-based electronic circuits. NVM devices, at the fourth level, have several variants but in general are faster than hard disks. The most common form of NVM device is flash memory, which is popular in mobile devices such as smartphones and tablets. Increasingly, flash memory is being used for long-term storage on laptops, desktops, and servers as well.

Since storage plays an important role in operating-system structure, we will refer to it frequently in the text. In general, we will use the following terminology:

- Volatile storage will be referred to simply as memory. If we need to emphasize a particular type of storage device (for example, a register), we will do so explicity.

- Nonvolatile storage retains its contents when power is lost. It will be referred to as NVS. The vast majority of the itme we spend on NVS will be on secondary storage. This type of storage can be classified into two distinct types:

1) Mechanical. A few examples of such storage systems are HDDs, optical disks, holographic storage, and magnetic tape. If we need to emphasize a particular type of mechanical storage device (for example, magnetic tape), we will do so explicitly.

2) Electrical. A few examples of such storage systems are flash memory, FRAM, NRAM, and SSD. Electrical storage will be referred to as NVM. if we need to emphasize a particular type of electrical storage device(for example, SSD), we will do so explicitly.

Mechanical storage is generally larger and less expensive per byte than selectrical storage. Conversely, electrical storage is typically costly, smaller, and faster than mechanical storage.

The design of a complete storage system must balance all the factors just discussed: it must use only as much expensive memory as necessary while providing as much inexpensive, nonvolatile storage as possible. Caches can be installed to improve performance where a large disparity in access time or transfer rate exists between two components.

Intel processor event-vector table

 vector number    :     description

0: divide error

1: debug exception

2: null interrupt

3: breakpoint

4: INTO-detected overflow

5: bound range exception

6: invalid opcode

7: device not available

8: double fault

9: coprocessor segment overrun (reserved)

10: invalid task state segment

11: segment not present

12: stack fault

13: general protection

14: page fault

15: (Intel reserved, do not use)

16: floating-point error

17: alignment check

18: machine check

19-31: (Intel reserved, do not use)

32-255: maskable interrupts

1.2.1.2 Implementation

 The basic interrupt mechanism works as follows. The CPU hardware has a wire called the interrupt-request line that the CPU sense after executing every instruction. When the CPU detects that a controller has asserted a signal on the interrupt-request line, it reads the interrupts number and jumps to the interrupt-handler routline by using that interrupt number as an index into the interrupt vector, It then starts execution at the address associated with that index. Then interrupt handler save any state it will be changing during its operating, determines the cause of the interrupts, performs the necessary processing, performs a state restore, and executes a return from interrupt instruction to return the CPU to the execution state prior to the interrupt. We say that the device controller raises an interrupt by asserting a signal on the interrupt request line, the CPU catches the interrupt and dispatches it to the interrupt, and the handler clears the interrupt by servicing the device. Figure 1.4 summarizes the interrupt-driven I/O cycle.

The basic interrupt mechanism just described enables the SPU to respond to an asynchronous event, as when a device controller becomes ready for service. In a modern operating system, however, we need more sophisticated interrupthandling features.

1. We need the ability to defer interrupt handling during critical processing.

2. We need an efficient way to dispatch to the proper interrupt handler for a device.

3. We need multilevel interrupts, so that the operating system can distinguish between high-and low-priority interrupts and can respond with the appropriate degree of urgency.

In modern computer hardware, these three features are provided by the CPU and the interrupt-controller hardware.

Most CPUs have two interrupt request lines. One is the nonmaskable interrupt, which is reserved for events such as unrecoverable memory errors. The second interrupt line is maskable: it can be turned off by the CPU before the execution of critical instruction sequences that must not be interrupted. The maskable interrupt is used by device controllers to request service.

Recall that the purpose of a vectored interrupt mechanism is to reduce the need for a single interrupt handler to search all possible sources of interrupts to determine which one needs service. In practice, however, computers have more devices (and, hence, interrupt handlers) than they have address elements in the interrupt vector. A common way to solve this problem is to use interrupt chaining, in which each element in the interrupt vector points to the head of a list of interrupt handlers. When an interrupt is raised, the handlers on the corresponding list are called one by one, until one is found that can service the request. This structure is a compromise between the overhead of a huge interrupt table and the inefficiency of dispatching to a single interrupt handler.

Figure 1.5 illustrates the design of the interrupt vector for Intel processors. The events from 0 to 31, which are nonmaskable, are used to signal various error conditions. The events from 32 to 255, which are maskable, are used for purposes such as device-generated interrupts.

The interrupt mechanism also implements a system of interrupt priority levels. These levels enable the CPU to defer the handling of low-priority interrupts without masking all interrupts and makes it possible for a high-priority interrupt to preempt the execution of a low-priority interrupt.

In summary, interrupts are used thoroughout modern operating system to handle asynchronous events(and for other purposes we will discuss throughout the text). Device controllers and hardware faults raise interrupts. To enable the most urgent work to be done first, modern computers use a system of interrupt priorities. Because interrupts are used so heavily for time-sensitive processing. efficient interrupt handling is required for good system performance.

1.2.1.1 Overview

 Hardware may trigger an interrupt at any time by sending a signal to the CPU, usually by way of the system bus. (There may be many buses within a computer system, but thesystem bus is the main communications path between the major components.) Interrupts are used for many other purposes as well and are key part of how operating systems and hardware interact.

When the CPU is interrupted, it stops what it is doing and immediately transfers execution to a fized location. The fized location usually contains the starting address where the service routine for the interrupts is located. 

The interrupt service routine executes; on completion, the CPU resumes the interrupted omputation. A timeline of this operation is shown in Figure 1.3.

To run the animation assicated with this figure please click here.

Inerrupts are an important part of a computer architecture. Each computer design has its own interrupt machanism, but serveral funtions are common. The interrupts must transfer control to the appropriate interrupts service routine. The straightforward method for managing this transfer would be to invoke a generic routine to examine the interrupt information. The routine, in turn, would call the interrupt0specific handler. However, interrupts must be handled quickly, as they occur very frequently: A table of pointers to interrupt routine is called indirectly through the table, with no intermediate routine needed.

Generally, the table of pointers is stored in mow memory(the first hundred or so locations). These location hold the addresses of the interrupts service routines of the various devices. This array, or interrupt vector, of addresses is then indexed by a unique number, given with the interrupt request, to provide the address of the interrupt service routine for the interrupting device. Operating system as different as Windows and UNIX dispatch interrupts in this manner.

The interrupt architecture must also svae tghe state information of whatever was  interrupted, so that it can resotre this information after servicing the instance, by modifying register values-it must explicityl save the current state and then resotre that state before retuning. After the interrupt is serviced, the saved return address is loaded into the program counter, and the interrupted computation resumes as though the interrupt had not occurred.

1.2.1 Interrupts

 Consider a typical computer operation performing I/O. To start an I/O operation, the device driver loads the appropriate registers in the device controller, in turn, examines the contents of these registers to determine what action to take (such as "read a character from the keyboard"). The controller starts the transfer of data from the device to its local buffer. Once the transfer of data is complete, the device controller informs the device driver that it has finished its operation. The device driver then gives control to other parts of the operating system, possibly returning the data or a pointer to the data if the operation was a read. For other operations, the device driver returns statrus information such as "write completed successfully" or "device busy". But how does the controller inform the device dirver that it has finished its operation? This is accomplished via an interrupt.