---
title: I/O System
date: 2024-05-14
excerpt: "I/O controllers, channels, and control modes (polling, interrupt, DMA); device data structures; disk scheduling (FCFS, SSTF, SCAN, CSCAN); buffering."
tags: [OS]
cover: https://assets.vluv.space/cover/OS/Ch5-IOSystem.webp
updated: 2026-07-08 21:17:39
lang: en
i18n:
  cn: /Ch5-IOSystem
  translation: 2
---

## Introduction to the I/O System

In a computer system, **device management** refers to controlling data transfers and managing all devices other than the CPU and main memory.

The part of the operating system responsible for managing input and output devices is called the **I/O system**, an important component of any computer system.

This system includes the devices used for information input, output, and storage, along with their device controllers.
Some large and mid-range machines also have I/O channels or I/O processors.

### Device Management

I/O devices come in many kinds, and their characteristics and modes of operation often differ greatly. This makes device management the most intricate part of the operating system and the part most tightly coupled to hardware.

- Objects of device management: mainly I/O devices, and possibly device controllers and I/O channels as well.
- Basic tasks of device management: fulfill users' I/O requests, improve I/O throughput, and improve I/O device utilization.
- Main functions of device management: buffer management, device allocation and device mapping, device driving, device handling, virtual devices, and device independence.

I/O software is closely related to many parts of the operating system, including hardware devices, the file system, the virtual memory system, and sometimes even direct user interaction.
To give this complex I/O software a clear structure, better portability, and adaptability, I/O systems today generally adopt a layered structure.
The device management modules are divided into layers; each layer uses the services of the layer below it to implement certain sub-functions of input/output, hides the details of how those functions are implemented, and provides services to the layer above.

I/O software is usually organized into four layers:

1. **User-level I/O software**, which implements the interface for user interaction. Users can directly call the library functions this layer provides for I/O operations on devices.
2. **Device-independent software**, which provides a uniform interface between user programs and device drivers, and handles device naming, device protection, and device allocation and release, while providing the storage space needed for device management and data transfer.
3. **Device drivers**, which are directly tied to the hardware. They implement the operational commands the system issues to devices and drive the I/O devices to work.
4. **Interrupt handlers**, which save the CPU context of the interrupted process, transfer control to the corresponding interrupt handling routine, and after processing restore the interrupted process's context and return to it.

### The I/O System

#### Basic Functions

1. Device allocation
2. Device mapping
3. Device driving
4. I/O buffer management

**Device allocation** is the basic task of device management. Based on a user process's I/O request, the system's currently available resources, and some allocation policy, the system allocates the required devices.
Allocation should use different strategies for different device types. For dedicated devices, which are critical resources, the system must also consider whether allocating the device leaves the system in a safe state.
Once a device is no longer in use, the system should reclaim it immediately.

To improve application software's adaptability across platforms and make I/O redirection easy, most modern operating systems support device independence for applications, often called device independence or device-independent I/O.
The operating system hides device-specific details, presents abstract logical devices to higher layers, and performs the **mapping** between logical devices and concrete physical devices. As a result, the devices that applications reference for I/O operations have no fixed binding to the devices actually installed in the physical I/O system.

A **device driver**, also called a device handler, is the communication program between the upper layers of the I/O system and the device controller. It controls the physical device and performs the actual I/O operations.
Device drivers are closely tied to hardware, and each class of device needs its own driver. Because I/O devices come in so many kinds
with widely differing characteristics and modes of operation, driver code accounts for a large share of a general-purpose operating system.

I/O buffering means setting aside regions of memory to hold data received from user input or destined for computer output.
I/O buffering eases the speed mismatch between the processor and peripherals, and increases parallelism between them, reducing system overhead and improving peripheral efficiency.
The task of **I/O buffer management** is to organize the I/O buffers and provide the means for users to obtain and release them.

#### Components

The I/O system consists mainly of I/O devices, device controllers and their interfaces, and buses; large mainframes also include I/O channels.
An **I/O device** is the mechanical part of an I/O operation, or a device used directly for I/O and information storage.
A **device controller** is the interface between the CPU and I/O devices. It receives commands from the CPU and controls the I/O devices. Its main duty is to control one or more I/O devices to realize data exchange between the devices and the computer.
Usually a device does not communicate with the CPU directly. It communicates with its device controller, so devices talk to the CPU indirectly through the controller.
Between a device and its controller there is an interface, connected by dedicated cables carrying three kinds of signals:

1. Data signal lines: bidirectional (input and output), carrying data signals between the device and the controller.
2. Control signal lines: sent from the controller to the device, requesting the device to perform operations such as read or write.
3. Status signal lines: sent from the device to the controller, indicating the device's current state, such as reading (writing) or ready for a new data transfer.

A device controller is an addressable unit. When it controls a single device, it has one unique device address; if it can connect multiple devices, it must hold multiple device addresses, one per device.

##### Device Controllers

Most controllers consist of the following three parts:

1. The interface between the device controller and the processor: used for communication between the CPU and the controller.
   It includes data lines, address lines, control lines, data registers (holding data coming from the device or the CPU), and control/status registers (holding control information from the CPU or the device's status information).
2. The interface between the device controller and the devices: a controller can connect one or more devices, so it contains one or more device interfaces, one per device.
3. I/O logic: implements control over the devices. The I/O logic decodes received addresses and, based on the decoded command, controls the selected device.

![Device controller](https://assets.vluv.space/UESTC/OS/Ch5-IOSystem/Ch5-IOSystem-2024-06-18-20-18-35.webp)

##### I/O Channels

Adding device controllers between the CPU and I/O devices relieved the CPU of controlling data input and output, markedly improving CPU efficiency.
Channels improved CPU efficiency even further. A channel is a special-purpose processor with its own instructions and programs dedicated to controlling data transfers.
Once the CPU hands the "transfer control" role down to the channel, it only handles "data processing". The channel and the CPU time-share memory, so CPU computation and I/O device operation proceed in parallel.

A channel is a special processor that executes I/O instructions. Its instruction set is limited, and it has no memory of its own, sharing memory with the CPU.

Using channels has the following characteristics:

1. DMA (direct memory access) significantly reduces CPU intervention.
2. With channels, I/O operations can run independently, freeing the CPU from organizing and managing I/O. The CPU only needs to send an I/O command to the channel; by invoking the corresponding channel program in memory, the channel completes a group of related read (or write) operations and the associated control.
3. The CPU, channels, and I/O devices can operate in parallel, further improving overall resource utilization.

A channel is a special processor that executes I/O instructions. A host can connect several channels, each channel can connect several device controllers, and each controller can connect one or more peripheral devices.
![Channels](https://assets.vluv.space/UESTC/OS/Ch5-IOSystem/Ch5-IOSystem-2024-06-18-20-32-58.webp)

> [!example] Quick quiz
>
> 1. A virtual device is a device used alternately by multiple users or processes, appearing macroscopically as if multiple users were using it simultaneously. ( )
>    False. It refers to using some I/O technique to turn a dedicated device into one shared by multiple users, improving resource utilization.
> 2. Channel technology fundamentally solves the operating system's control of I/O operations in software. ( )
>    False. Channel technology fundamentally solves it in hardware.
> 3. A logical device is a representation of physical device attributes, used to designate one specific device. ( )
>    False. It does not designate a specific device; it corresponds to a class of devices.
> 4. Classified by resource attributes, devices can be divided into dedicated devices, shared devices, and virtual devices. ( )
>    True.
> 5. When using I/O devices, users usually use physical device names to specify a concrete device. ( )
>    False. Users usually use logical device names, specifying the device type.

## Interrupt Handlers and Device Drivers

### Interrupts in Brief

Interrupts hold a special and important place in operating systems. Without them, multiprogramming would be impossible; switching between processes is accomplished through interrupts.
Interrupts are the lowest layer of the I/O system and the foundation of device management.

**Interrupt source**: the event that causes an interrupt.
**Interrupt request**: the signal an interrupt source sends to the CPU requesting interrupt handling.
**Interrupt response**: the process by which the CPU, upon receiving an interrupt request, transfers to the corresponding event handler.
**Disabling/enabling interrupts**: clearing/setting the interrupt-enable bit in the CPU's PSW, disallowing/allowing the CPU to respond to interrupts. Used to guarantee atomic execution of a code section.
**Interrupt masking**: after interrupt requests arise, the system selectively blocks some interrupts while allowing others to be serviced. Some interrupts with the highest priority cannot be masked.

By signal origin, interrupts are divided into external and internal interrupts.
An **external interrupt**, usually just called an interrupt, is the CPU's response to an interrupt signal from an I/O device. The CPU suspends the current process, handles the process that raised the interrupt, and afterwards returns to the original process and continues. 
The I/O device can be a character device (keyboard), a block device (disk), or a communication device (network). Because the cause is external, it is called an external interrupt.
An **internal interrupt**, called a trap in some textbooks, is caused by events inside the CPU's running process, hence trap or internal interrupt. It usually arises from a runtime exception in the process itself, such as arithmetic overflow, or a program error such as an illegal instruction.

The interrupt identification code produced by hardware is called the **interrupt type number** (it can also be produced in other ways, e.g. given directly in an instruction, or formed automatically by the CPU).
The **interrupt vector table** maps interrupt type numbers to the entry addresses of the corresponding interrupt handlers.
80x86 systems collect all interrupt vectors and store them in a memory region ordered by interrupt type number from small to large. This region is the interrupt vector table, i.e. the table of interrupt service routine entry addresses.

How should multiple interrupt sources be handled? For example, while the processor is handling an interrupt raised by the keyboard, a higher-priority disk interrupt arrives. What should happen?
One approach is masking interrupts, also called disabling interrupts: while the current interrupt is being handled, other incoming interrupts are ignored until the current one completes, i.e. first-come, first-served.
The second approach is nested interrupts: interrupt handlers are also processes, and when a higher-priority interrupt handler arrives it can preempt the current interrupt-handling process — an interrupt of an interrupt.

### Interrupt Handlers

Because interrupt handling is tightly coupled to hardware, it should be hidden from users and user programs as much as possible. Interrupt handling therefore belongs in the lowest layers of the operating system, with the rest of the system interacting with it as little as possible.
When a process requests an I/O operation, it is suspended until the I/O device completes the operation, at which point the device controller sends an interrupt request to the CPU.
The CPU responds by transferring to the interrupt handler, which performs the needed processing and then unblocks the corresponding process.
The interrupt handling layer's main work therefore covers three aspects:

- switching process contexts,
- testing the interrupt signal sources,
- reading device status and modifying process states.

For the device handling approach that sets up one I/O process per device class, the interrupt handling procedure breaks into the following steps:

1. Test whether there is an unserviced interrupt signal
   - After completing the current instruction, the program tests whether there is an unserviced interrupt signal.
     If not, it continues with the next instruction.
     If so, it stops executing the current process and prepares to run the interrupt handler, getting ready to hand control of the processor to it.
   - Usually the hardware automatically saves the processor status word (PSW) and the program counter (PC) in the interrupt save area (stack).
   - Then the interrupted process's CPU context (all CPU registers, including general-purpose registers, segment registers, and so on) is pushed onto the interrupt stack.
2. Transfer to the corresponding device handler
   - The processor tests each interrupt source to determine which I/O device caused this interrupt, and sends an acknowledgment to the process that raised the request so it clears the interrupt request signal.
   - Then the entry address of the corresponding device interrupt handler is loaded into the program counter, and the processor transfers to the interrupt handler.
3. Interrupt processing
   - The handler first reads the device status from the device controller to determine whether this interrupt signals normal completion or abnormal termination.
   - If the former, the handler performs completion processing; if there are further commands, it can send a new command to the controller and start a new round of data transfer.
   - If the interrupt signals abnormal termination, the handler responds according to the cause of the exception.
4. Restore the interrupted process's context
   - After interrupt handling completes, the interrupted process's context saved on the interrupt stack is retrieved and loaded into the corresponding registers, including the address N+1 of the next instruction to execute, the PSW, and the contents of the general-purpose and segment registers.
   - Thus, when the processor resumes the program, it starts from N+1 and ultimately returns to the interrupted program.

### Device Drivers

The functions and characteristics of device drivers were covered earlier.
Device handling generally falls into three approaches:

1. First: set up one process per device class, dedicated to I/O operations for that class.
2. Second: set up a single I/O process for the whole system, dedicated to performing the I/O operations of every device class.
3. Third: set up no dedicated device-handling processes at all, providing only device drivers for each device class, which user or system processes access via calls. This third approach is the most common today.

As computer technology has developed, I/O control methods have kept evolving.

1. Early computer systems used programmed I/O.
2. Once interrupt mechanisms were introduced, I/O evolved into the interrupt-driven approach.
3. Later, the appearance of DMA controllers changed the unit of transfer, from byte-by-byte transfers to block-by-block transfers, greatly improving block device I/O performance.
4. The introduction of channels then allowed both the organization of I/O operations and the data transfers to proceed independently, without CPU intervention.

Throughout the evolution of I/O control methods runs one guiding principle: minimize the host CPU's involvement in I/O control, freeing it from tedious I/O control work so it can do more data processing.

#### I/O Device Control Methods

![I/O control methods](https://assets.vluv.space/UESTC/OS/Ch5-IOSystem/Ch5-IOSystem-2024-06-18-21-35-34.webp)

##### Programmed I/O with Polling

In early computer systems, with no interrupt mechanism, the processor controlled I/O devices using programmed I/O, also called busy waiting.

The processor issues an I/O instruction to the controller to start the input device, sets busy to 1, and then loops testing busy.
When busy = 0, the input is complete; the processor reads the data into the designated location, completing one I/O.
Control is achieved by checking the busy/idle flag in the status register.

With programmed I/O, because the CPU is fast and I/O devices are slow, the CPU spends the vast majority of its time in the polling loop waiting for the device to finish,
a huge waste of CPU time. The reason the CPU must keep testing the device's status is precisely that, without an interrupt mechanism,
the I/O device has no way to report to the CPU that it has finished inputting a character.

##### Interrupt-Driven Programmed I/O

Modern computer systems all include interrupt mechanisms, so I/O device control widely adopts the interrupt-driven approach:
when a process wants to start an I/O device, the CPU issues an I/O command to the device controller and immediately returns to its original task.
The device controller then controls the specified I/O device per the command. Meanwhile, the CPU and the I/O device operate in parallel.

For input, when the device controller receives a read command from the CPU, it directs the input device to read data.
Once the data enters the data register, the controller sends an interrupt signal to the CPU over the control line. The CPU checks whether the input had errors;
if not, it signals the controller to hand over the data, which is then written via the controller and data lines to the designated memory location.

While the I/O device inputs each datum, no CPU intervention is needed, so the CPU and the device work in parallel.
Only when a datum finishes does the CPU spend a very short time on interrupt handling. This keeps both the CPU and I/O devices busy, raising overall resource utilization and throughput.

##### Direct Memory Access

Although interrupt-driven I/O beats programmed I/O, note that it still performs I/O one word (byte) at a time; each completed word (byte) triggers an interrupt request to the CPU.
In other words, with interrupt-driven I/O the CPU intervenes at the granularity of a word (byte). Applying this to block devices would clearly be extremely inefficient.
For example, reading a 1 KB block from disk would interrupt the CPU 1K times. To further reduce CPU involvement in I/O, direct memory access was introduced.
If I/O devices could exchange data with main memory directly without occupying the CPU, CPU utilization could rise further — hence the direct memory access (DMA) approach.
Characteristics of DMA control:

- The basic unit of transfer is the data block; each transfer between the CPU and the I/O device moves at least one block.
- Data goes directly from the device into memory, or vice versa.
- The CPU intervenes only at the start and end of transferring one or more blocks; the whole block transfer is done under the controller's control.

Advantage: CPU utilization improves further (greater parallelism).
Disadvantage: the transfer direction, byte count, memory address, etc. must be set up by the CPU, and each device needs its own DMA controller — uneconomical as devices multiply.

Compared with interrupt-driven I/O, DMA reduces CPU involvement in I/O by another factor of hundreds, further increasing CPU–device parallelism.

1. The process needing data issues instructions via the CPU, writing to the DMA controller the starting memory address for the data and the byte count, setting the interrupt and start bits, starting the I/O device to input data, and enabling interrupts.
2. The process gives up the processor to wait for input to finish; the processor is taken by other processes.
3. The DMA controller steals CPU cycles and writes a batch of data into memory.
4. When the transfer finishes, the DMA controller sends an interrupt request to the CPU. The CPU responds, runs the interrupt service routine, wakes the process, and returns to the interrupted process.
5. At some later time, the process is scheduled again and fetches the data from memory for processing.

> [!tip] Components of a DMA controller
>
> - Memory address register (MAR): on input, holds the starting destination address for data going from device to memory; on output, holds the source address in memory for data going to the device.
> - Data register (DR): temporarily holds data moving from device to memory or from memory to device.
> - Command/status register (CR): receives I/O commands or control information from the CPU, or the device's status.
> - Data counter (DC): holds the number of words (bytes) the CPU wants to read or write this time.
>
> ![DMA controller](https://assets.vluv.space/UESTC/OS/Ch5-IOSystem/Ch5-IOSystem-2024-06-18-21-34-19.webp)

##### I/O Channel Control

To achieve greater parallelism between the CPU and peripherals, and to let peripherals of many kinds and differing physical characteristics connect to the system through standard interfaces, computer systems introduced the channel — an independent subsystem of its own.

The I/O channel approach is an evolution of DMA. It further reduces CPU intervention: instead of intervening per data block read (or written),
the CPU intervenes per group of data blocks read (or written) plus the associated control and management.

With channels managing and controlling I/O operations, the logical coupling between peripherals and the CPU shrinks, freeing the CPU from tedious I/O work.
The CPU, channels, and I/O devices can operate in parallel, more effectively improving overall system resource utilization.

> [!example] Quick exercise
>
> 1. What is an interrupt? What is the difference between internal and external interrupts?
>    Answer: An interrupt means the processor stops its current work, saves all current data and state parameters, turns to handle a more urgent matter, and afterwards restores the original data and parameters and resumes. Internal interrupts are caused by the operating system's own internal operation; external interrupts are caused by running user applications.
> 2. What is the main difference between a page fault and an ordinary interrupt?
>    Answer: A page fault is a special kind of interrupt. Its interrupt signal is raised and handled during instruction execution, and one instruction may trigger multiple page faults during its execution.
> 3. In I/O control, how does interrupt-driven control differ from DMA?
>    Answer: With interrupt-driven I/O, the CPU and the I/O device operate in parallel; when a data I/O operation completes, the device controller sends an interrupt signal to the CPU over the control line, and the CPU spends a very short time on interrupt handling. CPU utilization rises markedly, but I/O proceeds word (byte) at a time, which is inefficient for block devices. With direct memory access (DMA), data transfers use the data block as the basic unit and complete under the controller's control, with data going directly into memory; the CPU intervenes only at the start and end of transferring one or more blocks.

## Device-Independent I/O Software

### Device Independence

**Device independence** means the operating system treats all peripheral devices uniformly as files. As long as their drivers are installed, any user can manipulate and use these devices just like files, without knowing their concrete form. Its essential meaning: applications are independent of the specific physical devices they use.

Implementing device independence brings two benefits:

1. Greater flexibility in device allocation, and better system adaptability and extensibility.
   When a process requests a class of device by logical device name, the system can immediately allocate any unit of that class; the process blocks only when all devices of that class are already allocated.
2. Easy I/O redirection.
   I/O redirection means the device used for I/O operations can be swapped (redirected) without changing the application.

**How to implement device independence**
To implement device independence, two concepts are introduced: logical devices and physical devices. Applications use logical device names to request a class of device, while the system uses physical device names at execution time. Since drivers are software tightly coupled to hardware (devices), a layer of software must be placed above the drivers, called device-independent software. It performs the operations common to all devices, maps logical device names to physical device names (requiring a logical device table), and provides a uniform interface to user-level (or file-level) software, thereby achieving device independence.

**Device-independent software**

As covered earlier, the I/O system is managed in layers. Today the most common overall structure of OS device management divides it into a hardware-independent layer and a hardware-dependent layer.
The rationale for this split lies mainly in portability and extensibility.

A driver is software tightly coupled to hardware (devices). To achieve device independence, a software layer must be placed above the drivers: the device-independent software.
The boundary between device-independent software and device drivers varies by operating system and device. It depends on trade-offs among the operating system, device independence, and driver efficiency,
because some functions that in principle belong in device-independent software end up designed into drivers for efficiency and other reasons.

The main functions of device-independent software fall into two areas:

1. Performing operations common to all devices, including:
   - allocation and reclamation of dedicated devices;
   - mapping logical device names to physical device names, and from there locating the corresponding physical device's driver;
   - protecting devices, forbidding users from accessing them directly;
   - buffer management;
   - error control;
   - providing device-independent logical blocks.
2. Providing a uniform interface to user-level (or file-level) software:
   - Whatever the device, the interface offered to users should be the same.
   - For example, reads on all kinds of devices use read in applications, and writes on all kinds of devices use write.

### Virtual Devices and SPOOLing

#### Common Device Allocation Techniques

**By the nature of device usage**

- Dedicated device: a device that cannot be shared; during a period of time it is used exclusively by one process. Example: a printer.
- Shared device: a device that several processes can share simultaneously. Example: a disk drive.
- Virtual device: a dedicated device transformed by some technique into one shareable by multiple processes.

**Three allocation techniques for the three device types**

- Dedicated allocation: assigns a dedicated device to one process until that process finishes its I/O operations and releases it.
- Shared allocation: usually applies to high-speed, large-capacity direct-access storage devices. Multiple processes share one device, each using only part of it.
- Virtual allocation: uses a shared device to simulate dedicated devices, turning a dedicated device into a shareable, fast I/O device. The best-known virtual allocation technique is SPOOLing, also called simultaneous peripheral operations on-line.

## Buffering

### The Concept of a Buffer

A buffer is a storage area. It can consist of dedicated hardware registers, or memory can be used as the buffer.
Hardware buffers are expensive and small, and are generally used only where speed matters greatly (such as the associative registers used in memory management: because page tables are accessed extremely frequently, very fast associative registers hold copies of page table entries).
Usually, memory serves as the buffer, and the buffer management of the "device-independent software" is about organizing and managing these buffers.

### Purpose of Introducing Buffers

- Ease the speed mismatch between the CPU and peripherals
- Increase parallelism between the CPU and peripherals
- Reduce the number of CPU interrupts
- Ease the data-granularity mismatch between the CPU and peripherals

### Single Buffer

![Single buffer](https://assets.vluv.space/UESTC/OS/Ch5-IOSystem/Ch5-IOSystem-2024-06-19-15-41-14.webp)

### Double Buffer

![Double buffer](https://assets.vluv.space/UESTC/OS/Ch5-IOSystem/Ch5-IOSystem-2024-06-19-15-41-41.webp)

## Disk Systems and Disk Scheduling

Disk storage is the most important storage device in a computer system, holding a large number of files. Modern computer systems all include disk storage as the primary place to keep files.

Reading and writing files involves accessing the disk. Disk I/O speed and disk system reliability directly affect system performance.
Improving disk system performance has become one of the important tasks of modern operating systems.

Main routes to higher disk I/O speed:

- Choose disks with good performance
- Use a good disk scheduling algorithm
- Set up a disk cache
- Use highly reliable, fast, high-capacity disk systems — redundant arrays of disks (RAID)
- Other methods

Hard drives come in mechanical (HDD) and solid-state (SSD) varieties. Only mechanical drives are covered here.
A mechanical hard drive is the traditional hard disk, composed mainly of platters, heads, the spindle and drive motor, the head controller, the data converter, the interface, and cache.

### Disk Data Organization and Format

- Surface
- Track
- Cylinder
- Sectors

A disk device may include one or more physical platters; each platter has one or two surfaces. Each surface is organized into concentric rings called tracks, with necessary gaps between tracks.
Each track is logically divided into sectors — roughly 8 to 32 on a floppy disk, and up to several hundred on a hard disk. One sector is called a disk block (or data block), commonly called a disk sector. Gaps are kept between sectors.
Tracks are numbered from the outer edge starting at 0, increasing inward. Tracks with the same number form a cylinder, called a disk cylinder.

![Disk data organization and format](https://assets.vluv.space/UESTC/OS/Ch5-IOSystem/Ch5-IOSystem-2024-06-19-11-41-34.webp)

**Disk access time** breaks into three parts:

1. Seek time $T_s$
   The time to move the arm (head) to the specified track.
   $T_s = m \times n + s$
   s: arm startup time
   n: the head moves n tracks
   m: time to cross each track
2. Rotational latency $T_\tau$
   The time for the specified sector to rotate under the head. The average rotational latency is the average time the head waits for the needed data sector to rotate beneath it, usually taken as half a disk revolution, i.e. $\frac{1}{2r}$.
   For example:
   A floppy spins at 300 r/min or 600 r/min, so average $T_\tau$ is 50–100 ms. (At 5–10 r/s, half a revolution takes $\frac{0.5r}{10r/s} - \frac{0.5r}{5r/s} = 0.05s - 0.1s$.)
   A hard disk spins at 15,000 r/min, 4 ms per revolution, so average rotational latency $T_\tau$ is 2 ms.
3. Transfer time $T_t$
   The time to read data from or write data to the disk.
   $T_t$ depends on the number of bytes b read/written each time and the rotational speed:
   $T_t=\frac{b}{rN}$
   r is the disk's revolutions per second; N is the number of bytes per track.

Thus, the access time $T_a$ is: $T_a = T_s + \frac{1}{2r}+\frac{b}{rN}$

Within access time, seek time and rotational latency are essentially independent of how much data is read/written, and they usually dominate.
For example, assume seek time plus rotational latency averages 20 ms and the disk's transfer rate is 10 MB/s. Transferring 10 KB gives a total access time of 21 ms — the transfer time is a tiny fraction.
Transferring 100 KB only takes 30 ms: a tenfold increase in data raises access time by only about 50%.
Disk transfer rates now exceed 80 MB/s, making the data transfer share even smaller. Clearly, batching data transfers appropriately (avoiding fragmentation) helps transfer efficiency.

### Disk Scheduling

The disk is a device shared by multiple processes. When several processes request disk access, an optimal scheduling algorithm should be used **to minimize the average disk access time across processes**. Common disk scheduling algorithms are:

1. First-come, first-served (FCFS)
2. Shortest seek time first (SSTF)
3. SCAN
4. Circular SCAN (CSCAN)

#### First-Come, First-Served (FCFS)

Schedules by the order in which processes request disk access. Its advantages are fairness and simplicity: every process's request gets handled in turn, and no process's request goes unsatisfied indefinitely.

#### Shortest Seek Time First (SSTF)

This algorithm picks the process whose requested track is nearest the head's current track, minimizing each seek. SSTF is essentially shortest-job-first (SJF) scheduling, and likewise cannot guarantee minimal average seek time.
Although SSTF achieves good seek performance, it may cause a process to suffer starvation.

#### SCAN

Although SSTF achieves good seek performance, it may starve a process: as long as new requests keep arriving for tracks near the head's current position, those new I/O requests get satisfied first. A slight modification of SSTF yields the SCAN algorithm, which prevents old processes from starving.

SCAN considers not only the distance between the requested track and the current track, but first and foremost the head's current direction of motion. For example, while the head moves outward, the next request SCAN considers must be on a track farther out than the current one and nearest to it. It keeps serving outward requests until there are no more tracks farther out to visit, and only then reverses the arm to move inward. It then again picks, at each step, the request nearest the current position on the inward side, moving the head step by step inward until no more inner tracks need visiting, thus avoiding starvation. Because the head's motion resembles an elevator — finishing requests in one direction before serving the opposite direction — this is often called the elevator algorithm.

#### CSCAN

CSCAN mandates one-way head movement. For example, the head moves only outward; once it reaches and services the outermost track, it immediately returns to the innermost requested track, so the smallest track number follows the largest, forming a loop, and scanning proceeds circularly.

SCAN achieves good seek performance while preventing starvation, so it is widely used.
But SCAN has a problem: if the head has just moved outward past some track when a process requests that track, the process must wait until the head continues outward and finishes scanning all outer requests before turning back inward — greatly delaying that request.
To reduce this delay, CSCAN mandates one-way head movement.

For example, moving only outward: once the head reaches and services the outermost track, it immediately returns to the innermost requested track, forming a loop from the largest track number back to the smallest, scanning circularly.
With circular scanning, the delayed request's wait drops from 2T to T + Smax,
where T is the seek time for one full one-way scan of the requested tracks, and Smax is the seek time to move the head directly from the outermost visited track to the innermost requested track.

#### LOOK Scheduling

SCAN and C-SCAN move the arm across the disk's full width. In practice, neither algorithm is usually implemented this way. More commonly, the arm goes only as far as the final request in each direction.

SCAN and C-SCAN following this pattern are called LOOK and C-LOOK scheduling, because they look for a request before continuing to move in a given direction.