Chapter 11: Input/Output

Question 1

A device controller (device adapter) is an

Answer 1

electronic circuit capable of operating a specific I/O device using binary signals.

Question 2

A device driver is a device-specific program that

Answer 2

implements I/O operations, requested by user applications or the OS, by interacting with the device controller

Question 3

Opcode (generic I/O register)

Answer 3

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

Question 4

Operands (generic I/O register)

Answer 4

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.

Question 5

Busy (generic I/O register)

Answer 5

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

Question 6

Status (generic I/O register)

Answer 6

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

Question 7

Data buffer (generic I/O register)

Answer 7

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 8

Programmed I/O is a style of

Answer 8

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 9

Polling is a technique to

Answer 9

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

Question 10

A direct memory access (DMA) controller is

Answer 10

a hardware component that allows devices to access main memory directly, without the involvement of the CPU.

Question 11

A buffer is a register or an area of main memory used to

Answer 11

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.

Question 12

Buffer swapping is a technique that allows the operations of a producer process and a consumer process to

Answer 12

overlap by using two buffers. While the producer is filling buffer 1, the consumer is copying buffer 2.

Question 13

A circular buffer is a fixed

Answer 13

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 14

A disk block cache is a set of

Answer 14

main memory buffers that contain the most recently accessed disk blocks.

Question 15

A track is one of many

Answer 15

concentric rings on a magnetic disk surface.

Question 16

A sector is a portion of a

Answer 16

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

Question 17

The seek time is the time to

Answer 17

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.

Question 18

The rotational delay (rotational latency) is the time to

Answer 18

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.

Question 19

The data transfer time is the time to

Answer 19

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

Question 20

Peak transfer rate is the rate at which the data is streamed to or from the disk once

Answer 20

the read/write head is at the beginning of the sector to be transferred.

Question 21

Sustained data rate is the rate at which the disk can

Answer 21

transfer data continuously.

Question 22

The Shortest seek time first (SSTF) scheduling algorithm considers the list of

Answer 22

all pending requests and always selects the request that requires the shortest travel distance from the current position.

Question 23

The Scan scheduling algorithm mimics the behavior of

Answer 23

an elevator in a building. The r/w head maintains a current direction of travel and services all request sequentially in the current direction.

Question 24

The C-Scan scheduling algorithm is a variant of the Scan algorithm that services requests in only one direction. When the outermost request is reached, the r/w head

Answer 24

sweeps back to the opposite end of the disk and starts servicing requests again in the same direction.

Question 25

Data on a disk can become inconsistent for two reasons:

Answer 25

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.

Question 26

A parity bit is a

Answer 26

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 27

An error correcting code (ECC) includes multiple

Answer 27

parity bits in a string to permit the detection and automatic correction of some number of erroneous bits.

Question 28

A bad block (bad sector) is a

Answer 28

storage block that is no longer reliable for storing and retrieving data due to physical damage.

Question 29

Sector forwarding is a technique where a bad disk block b[i] is

Answer 29

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 30

Sector slipping is a technique where all blocks following a bad block b[i]

Answer 30

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 31

Stable storage is an approach to data management that uses

Answer 31

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.

Question 32

A stable read guarantees

Answer 32

to return a valid copy of any block.

Question 33

A stable write guarantees that

Answer 33

every block is updated atomically.

Question 34

Striping is a technique where

Answer 34

a sequence of data blocks, b[i], is distributed over n disks

Question 35

A RAID (Redundant Array of Independent Disks) is a set of disks viewed by the OS as a

Answer 35

single mass storage device.

Question 36

The device bandwidth is the

Answer 36

total number of bytes transferred, divided by the total time between the first request for service and the completion of the last transfer.

Question 37

The simplest form of disk scheduling is, of course, the first-come, first-served (FCFS) algorithm (or FIFO).

Answer 37

This algorithm is intrinsically fair, but it generally does not provide the fastest service.

Question 38

In the SCAN algorithm, the disk arm starts at

Answer 38

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.

Question 39

The SCAN algorithm is sometimes called the

Answer 39

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 40

Circular SCAN (C-SCAN) scheduling is 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,

Answer 40

it immediately returns to the beginning of the disk without servicing any requests on the return trip

Question 41

The deadline scheduler maintains

Answer 41

separate read and write queues, and gives reads priority because processes are more likely to block on read than write.

Question 42

The deadline I/O scheduler is the default in the Linux RedHat 7 distribution, but RHEL 7 also includes two others.

Answer 42

NOOP is preferred for CPU-bound systems using fast storage such as NVM devices, and the Completely Fair Queueing scheduler (CFQ) is the default for SATA drives. CFQ maintains three queues (with insertion sort to keep them sorted in LBA order): real time, best effort (the default), and idle.

Question 43

Completely Fair Queuing (CFQ):

Answer 43

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