C191-Terms-Chapter-11

Question 1

device controller (device adapter)

Answer 1

an electronic circuit capable of operating a specific I/O device using binary signals. The interface to a device controller is a set of hardware registers and flags, which may be set by and/or examined by device drivers.

Question 2

device driver

Answer 2

a device-specific program that implements I/O operations, requested by user applications or the OS, by interacting with the device controller.

Since devices vary greatly in speed, latency, and the size of data being transmitted, the ability to perform random vs sequential access, and other aspects, device drivers are supplied by the device manufacturers.

To be able to incorporate new devices into a system without modifications to the OS, the I/O system supports a small set of generic API instructions. The typical subdivision includes instructions for:

Block-oriented devices (magnetic disks, CD ROMs, FLASH disks)
Character-oriented devices (keyboards, pointing devices, cameras, media players, printers)
Network devices (modems, Ethernet adapters)
The driver of any new device must implement the generic I/O instructions of an API for the specific device.

Question 3

A generic interface to a device controller consists of a set of registers:

Answer 3

Opcode: The register specifies the type of operation requested. Ex: read or write. Storing a new value into the register starts the I/O operation.

Operands: One or more operand registers are used to describe the parameters of the requested operation. The values are written by the CPU prior to starting the operation.

Busy: The register (a 1-bit flag) is set by the controller to indicate whether the device is busy or idle.

Status: The register is set by the controller to indicate the success or failure of the last I/O operation.

Data buffer: The data buffer holds the data to be transferred between the device and main memory. Depending on the device type, the buffer may hold a single character or a block of data.

Question 4

Programmed I/O

Answer 4

a style of I/O programming where the CPU, running the device driver, performs the copying of all data between the I/O device controller and main memory.

Question 5

Polling

Answer 5

a technique to determine whether a device is busy or idle by reading a flag set and reset by the device controller.

To perform programmed input with polling, the CPU first issues an input request to the device controller by writing a new value into the opcode register. Then the CPU repeatedly polls the busy flag until the operation completes. If the operation was successful, the CPU copies the data from the controller buffer to main memory.

Programmed output with polling is analogous. When the device is not busy, the CPU copies the data from main memory to the controller buffer and issues an output request. The CPU then polls the busy flag until the operation completes. If the operation was successful, the CPU may proceed with the next output operation.

Question 6

Programmed I/O with interrupts

Answer 6

When interrupts are used for I/O processing, the interface to the controller remains the same, but the controller is equipped with the ability to issue interrupts to the CPU.

The operand and opcode registers are used to describe and start an I/O operation. The status register indicates the success or failure of the last operation. The controller buffer holds the data transferred to or from the device.

The busy flag is still present but is used only initially to determine whether the device is available to accept a new I/O request. Then, after starting the I/O operation, the current process blocks itself, instead of repeatedly polling the busy flag to detect the termination of the data transfer.

The controller issues an interrupt when the operation has terminated, which reactivates the blocked process. The process examines the status of the operation and, depending on the outcome, proceeds with the next I/O operation or takes appropriate corrective actions.

Question 7

I/O with direct memory access

Answer 7

With programmed I/O, the CPU needs to transfer all data between the controller buffer and the main memory. The resulting overhead is acceptable with slow, character-oriented devices, but to liberate the CPU from the frequent disruptions caused by fast devices, direct memory access may be used.

Question 8

direct memory access (DMA)

Answer 8

controller is a hardware component that allows devices to access main memory directly, without the involvement of the CPU. Using DMA, the CPU only initiates a data transfer, which can consists of a line of characters, a block of data, or even multiple blocks of data, as part of a single I/O operation.

The process executing the device driver then blocks itself, which frees the CPU to serve other processes in the meantime. The device controller in collaboration with the DMA controller executes the I/O operation by transferring the data directly between the device and main memory. When the operation terminates, the device controller issues an interrupt to reactivate the blocked process.

Question 9

Polling vs interrupts

Answer 9

Polling and interrupts both result in overhead during I/O processing, but the overhead sources are different. Executing a single poll requires only a few machine instructions. On the other hand, blocking and later reactivating a process using an interrupt constitutes significant CPU overhead.

Polling is a good choice in dedicated systems, where only a single process is running. The CPU can busy-wait by executing a polling loop because no other computation is available to use the CPU in the meantime.

Polling is also suitable for devices that complete an I/O operation within a few microseconds. Ex: non-volatile solid-state (flash) memories. With such very fast devices, a context switch using interrupts would be more time-consuming than a short polling loop.

In a general-purpose multi-process environment, interrupts are a better choice with most devices. Blocking a process after issuing an I/O instruction and later processing the interrupt to reactivate the process represents constant, predictable overhead for each I/O instruction.

The device is restarted immediately after completing the data transfer and CPU time is never wasted on long busy-loops when a device is slow in responding.

Question 10

buffer

Answer 10

a register or an area of main memory used to hold data generated by a producer process or an input device and removed from the buffer at a later time by a consumer process or an output device. Depending on the intended use, a single buffer can hold one character at a time or a larger block of data.

The main purpose of using a single buffer is to decouple the producer from the consumer in time. The producer can generate a data item without the consumer being active simultaneously. Similarly, the consumer can copy the item from the buffer without the producer being active simultaneously.

A buffer also permits the consumer to accumulate and act upon multiple data items generated by the producer one at a time.

Question 11

Buffer swapping

Answer 11

a technique that allows the operations of a producer process and a consumer process to overlap by using two buffers. While the producer is filling buffer 1, the consumer is copying buffer 2. When both terminate, the two buffers are swapped. The producer starts filling buffer 2 while the consumer starts copying buffer 1.

Buffer swapping improves performance by overlapping the execution of the producer and the consumer, but only when data is produced and consumed at the same constant rate.

In situations where data is produced in bursts of varying lengths or frequency and the consumer is unable to handle the incoming data at the rate of a burst, multiple buffer slots are useful to hold and process the data at the slower rate of the consumer.

Conversely, if the consumer needs to process incoming data in bursts or at a higher granularity, then multiple buffer slots can be used to accumulate the data prior to each burst.

Question 12

circular buffer

Answer 12

a fixed array of buffer slots filled by the producer and emptied by the consumer one slot at a time in ascending order, modulo the buffer size.

Question 13

disk block cache

Answer 13

To speed up access to disk blocks, modern disk controllers include an internal cache to hold the most recently accessed blocks. In addition, the OS may maintain an additional larger cache in main memory. A disk block cache is a set of main memory buffers that contain the most recently accessed disk blocks.

Since a disk block cache can contain a large number of blocks, hashing is used to organize blocks into separate lists for faster access. In addition, all blocks are divided into several categories and are linked together using separate linked lists.

Blocks critical to performance (Ex: blocks used internally by the OS) must remain resident at all times and are kept on a list of Locked blocks.

Blocks expected to be accessed again in the near future (Ex: blocks holding data from regular user files) reside on a list that implements the LRU (least recently used) policy.

Whenever a block is accessed, the block is moved to the rear of the list. Blocks not accessed again gradually migrate to the front of the list and are removed when no free buffers are available.

Blocks expected to be accessed only once or very infrequently (Ex: blocks containing file control blocks, which are accessed when a new file is opened) are added to the front of the same LRU list and thus will be removed quickly.

All free buffers are kept on a separate list, possibly segregated by buffer size, and are added to the Locked list or the LRU list whenever a new non-resident block is accessed.

Question 14

track

Answer 14

one of many concentric rings on a magnetic disk surface. To access information on a track, a read/write head, mounted on a movable arm, is mechanically positioned over the track. Information is written onto or read from the track as the disk rotates under the r/w head.

Question 15

sector

Answer 15

a portion of a track and is the smallest unit of data that can be read or written with a single r/w operation.

Question 16

The time to access any data on a disk consists of 3 components

Answer 16

The seek time is the time to move the r/w head from the current position to the track containing the desired data. The time is directly proportional to the physical distance the r/w head needs to traverse.

The rotational delay (rotational latency) is the time to wait for the desired data item to pass under the r/w head. On average, the rotational delay is one half of the time of one disk revolution. Thus the time depends on the disk’s rotational speed.

The data transfer time is the time to transfer the desired number of bits to or from the disk, and is directly proportional to the disk’s rotational speed.

Question 17

Peak transfer rate

Answer 17

The most important characteristics of a disk are the disk size in bytes and the data transfer rate. Peak transfer rate is the rate at which the data is streamed to or from the disk once the read/write head is at the beginning of the sector to be transferred. The peak transfer rate depends directly on the rotational speed of the disk and the number of sectors per track.

Question 18

Sustained data rate

Answer 18

the rate at which the disk can transfer data continuously. The sustained data rate includes the seek times over multiple tracks and other overhead in accessing the data over time.

Question 19

Disk access optimization

Answer 19

The seek time and the rotational delay involve mechanical motion of the r/w head and the physical disk rotation. Both times are in the millisecond range and thus constitute most of the access time to a disk block.

Rotational delay is easy to optimize. Given a sequence of requests for multiple blocks on a track, the requests are sorted in ascending order. Consequently, all blocks on the same track can be accessed within a single revolution of the disk.

Optimizing the seek time is a more difficult problem because the r/w head sweeps back and forth across different tracks. Thus at any point in time, the algorithm must decide in which direction the r/w head should move next. The main objective is to minimize the movement of the r/w head while also guaranteeing some measure of fairness in servicing all requests.

Question 20

The simplest approach to disk scheduling

Answer 20

The simplest approach to disk scheduling is to service all requests in FIFO order, which is the order of arrivals. For each request to access a sector on track t, the r/w head moves to the track t. The number of tracks traversed by the r/w head using FIFO scheduling can significantly be reduced when requests are reordered prior to moving the r/w head.

Question 21

Shortest seek time first (SSTF)

Answer 21

scheduling algorithm considers the list of all pending requests and always selects the request that requires the shortest travel distance from the current position.

The algorithm minimizes the travel distance of the r/w head and thus maximizes the disk’s performance but the main drawback is a lack of fairness in treating the different requests.

Since new requests for tracks close to the current position are always served before more distant tracks, the service time of any request is unpredictable. With a continuous stream of new arrivals in the vicinity of the current position, requests for distant tracks could be postponed indefinitely, leading to starvation.

Question 22

Scan scheduling algorithm

Answer 22

mimics the behavior of an elevator in a building. The r/w head maintains a current direction of travel and services all request sequentially in the current direction. When the outermost request is reached, the direction is reversed and the algorithm services all requests in the opposite direction.

The performance of the scan algorithm lies between the performance of the FIFO and the SSTF algorithms but starvation is eliminated, since each request is guaranteed to be served within one sweep of the r/w head.

However, the access time to different tracks is not uniform. Since the r/w head sweeps back and forth, tracks closer to the midrange have a greater chance to be serviced quickly than tracks at either extreme of the disk.

Question 23

C-Scan scheduling algorithm

Answer 23

a variant of the Scan algorithm that services requests in only one direction. When the outermost request is reached, the r/w head sweeps back to the opposite end of the disk and starts servicing requests again in the same direction.

Unlike Scan, C-Scan guarantees a uniform access time to all tracks, because the r/w head services all requests in only ascending order. Thus a position in the midrange of the disk conveys no advantage over any other position.

Question 24

Error detection and correction

Answer 24

Data on a disk can become inconsistent for two reasons:

A system crash during a write operation can leave a disk block in a partially updated state.

A spontaneously occurring bad block, caused by aging or physical damage to the recording medium, makes the reading or re-writing of the block impossible.

Data can also be corrupted during transmission between systems or I/O devices.

Question 25

parity bit

Answer 25

a bit added to a string of bits to ensure that the total number of 1’s in the string is even or odd. Even parity sets the parity bit such that the number of 1’s is even. Similarly, odd parity sets the parity bit such that the number of 1’s is odd. Even and odd parity are duals of each other and either can be used as the simplest form of error detecting code, able to detect a single erroneous bit in a string.

Question 26

error correcting code (ECC)

Answer 26

includes multiple parity bits in a string to permit the detection and automatic correction of some number of erroneous bits.The number of bits that can be detected and corrected depends on the number of parity bits and the encoding scheme employed.

A popular ECC is the Hamming code, which can correct a single bit error. The encoding inserts even parity bits into a string of arbitrary length at positions 1, 2, 4, 8, …,
.

Parity bit p1 covers all positions that have a 1 in the least significant bit: 1, 3, 5, 7, …

Parity bit p2 covers all positions that have a 1 in the second least significant bit: 2, 3, 6, 7, …

Parity bit p4 covers all positions that have a 1 in the third significant bit: 4, 5, 6, 7, … , etc.

A single error in a string can automatically be corrected by adding the positions of all incorrect parity bits. The sum identifies the erroneous bit.

Question 27

bad block (bad sector)

Answer 27

a storage block that is no longer reliable for storing and retrieving data due to physical damage. An ECC is associated with each block, which allows the detection and automatic correction of some number of corrupted bits in the block.

Whenever a block is written to the disk, the controller computes and stores the ECC along with the block. Whenever a block is read from the disk, the controller computes the ECC and compares the value with the stored ECC. A bad block is detected when the two values disagree.

A transient r/w error may be corrected by repeating the same r/w operation. If the error persists, the block is marked as permanently damaged. To maintain the logical sequence of blocks b[0] … b[D-1] without gaps, the disk provides some number of spare sectors on each track. The damaged block, b[i], can be remapped to a spare sector in one of two ways including sector forwarding and sector slipping.

Question 28

Sector forwarding

Answer 28

a technique where a bad disk block b[i] is mapped to one of the spare sectors. The solution is fast and simple but the drawback is that the logical blocks are no longer mapped to consecutive sectors, resulting in additional revolutions of the disk.

Question 29

Sector slipping

Answer 29

a technique where all blocks following a bad block b[i] are shifted to the right. The last block is mapped to a spare sector and b[i] is mapped to the sector occupied previously by block b[i+1]. The approach requires more work initially but maintains the sequential order of all blocks.

Question 30

Stable storage

Answer 30

an approach to data management that uses redundancy, along with a strict protocol for reading, writing, and error recovery, to guarantee that all data remains consistent in the presence of media and crash failures.

A stable storage uses two independent disks, A and B, which contain identical copies of all data. ECCs are associated with all blocks to detect inconsistent blocks. Since the two disks fail independently, one of the disks always contains a valid copy of any block, which can be used to restore the corresponding block on the other disk.

Question 31

stable read

Answer 31

guarantees to return a valid copy of any block.

Question 32

stable write

Answer 32

guarantees that every block is updated atomically. After the write, the block contains either the old or the new value but never a partially updated value.

Question 33

Striping

Answer 33

One approach to increasing the rate at which data can be extracted from or written to mass storage devices is to use multiple independent disks working in parallel.

Striping is a technique where a sequence of data blocks, b[i], is distributed over n disks, such that disk[i] contains block b[i] modulo n. Ex: With 3 disks, blocks 0, 3, 6, … are mapped to disk 0, blocks 1, 4, 7, … are mapped to disk 1, and blocks 2, 5, 8, … are mapped to disk 2. As a result, 3 blocks can be accessed concurrently, resulting in a 3-fold speedup of the storage.

Striping can also be applied at finer levels. Individual bytes or even bits can be distributed over multiple disks in a modulo n fashion, which increases access time to individual words.

Question 34

RAID (Redundant Array of Independent Disks)

Answer 34

a set of disks viewed by the OS as a single mass storage device.

Since the probability of media failures increases rapidly with the number of disks, redundancy is used to decrease the probability of data loss. Several classes of RAIDs exist, distinguished by the amount, type, and location of the redundant data provided.

The amount of redundant data can range from a single parity bit per block to a full duplication of the entire block.

The type of redundant data determines how many bit-errors can be detected and/or automatically corrected.

The redundant data can be segregated on separate disk units or distributed throughout all disk units.

Question 35

bandwidth

Answer 35

the total number of bytes transferred, divided by the total time between the first request for service and the completion of the last transfer. We can improve both the access time and the bandwidth by managing the order in which storage I/O requests are serviced.

Whenever a process needs I/O to or from the drive, it issues a system call to the operating system. The request specifies several pieces of information:

Whether this operation is input or output

The open file handle indicating the file to operate on

What the memory address for the transfer is

The amount of data to transfer

Question 36

FCFS scheduling

Answer 36

The simplest form of disk scheduling is, of course, the first-come, first-served (FCFS) algorithm (or FIFO). This algorithm is intrinsically fair, but it generally does not provide the fastest service.

Question 37

SCAN algorithm

Answer 37

the disk arm starts at one end of the disk and moves toward the other end, servicing requests as it reaches each cylinder, until it gets to the other end of the disk. At the other end, the direction of head movement is reversed, and servicing continues. The head continuously scans back and forth across the disk.

The SCAN algorithm is sometimes called the elevator algorithm, since the disk arm behaves just like an elevator in a building, first servicing all the requests going up and then reversing to service requests the other way.

Question 38

Circular SCAN (C-SCAN) scheduling

Answer 38

a variant of SCAN designed to provide a more uniform wait time. Like SCAN, C-SCAN moves the head from one end of the disk to the other, servicing requests along the way.

When the head reaches the other end, however, it immediately returns to the beginning of the disk without servicing any requests on the return trip.

Question 39

Completely Fair Queuing (CFQ)

Answer 39

In Linux, the default I/O scheduler in kernel 2.6 and later versions.