I/O management
Open in the Padhaiko app4.1 I/O management
Alongside process scheduling, memory management, and file management, one of the primary responsibilities of an operating system is controlling and coordinating all of the computer's Input/Output (I/O) devices. Because I/O devices vary wildly in speed, data format, and control complexity, the OS must (OS Ch4):
- Issue commands to device controllers to initiate and manage I/O operations.
- Catch and service interrupts generated by devices upon completion of work.
- Detect and handle hardware/transmission errors transparently.
- Provide a clean, uniform, device-independent interface between physical hardware and user programs.
4.1.1 Principles of I/O hardware and software
Classification of I/O Devices
From an operating system programmer's viewpoint, I/O devices are divided into two primary categories (OS Ch4):
| Aspect | Block Devices | Character Devices |
|---|---|---|
| Storage & Transfer Unit | Stores and transfers information in fixed-size blocks (typically to ) | Delivers or accepts a continuous stream of bytes/characters without block structure |
| Addressability | Block-addressable: each block has its own unique logical address and can be read or written independently | Not addressable: does not support random seeks to arbitrary positions |
| System Call Interface | read(), write(), seek() (to position the next block to be accessed) | get() (read a character) and put() (write a character) |
| Representative Examples | Hard Disk Drives (HDDs), Solid-State Drives (SSDs), NVMe drives, CD-ROMs, USB flash drives | Keyboards, mice, serial printers, network interfaces, audio streams |
Device Controllers and I/O Registers
An I/O unit consists of a mechanical/physical component (the device itself, such as a disk platter assembly) and an electronic component called the device controller (or adapter). The CPU communicates with the device controller—never directly with the raw mechanics—by reading and writing a small set of registers inside the controller:
- Control Register: Written by the CPU to issue commands (e.g., seek, read, reset) or change device operating modes.
- Status Register: Read by the CPU to check whether the current command has completed, whether a byte is available to read ( flag bit), or whether an error occurred.
- Data-In / Data-Out Buffers: Hold bytes or blocks being transferred from the device to the CPU or from the CPU to the device.
Three Hardware Techniques for I/O Handling
Data can be transferred between an I/O device and main memory using three fundamental mechanisms (OS Ch4):
Programmed I/O, Interrupt-Driven I/O, and Direct Memory Access (DMA)
- Programmed I/O (Polling / Busy Waiting): The CPU initiates every single byte/word transfer and continuously monitors (polls) the device controller's status register in a tight loop until the operation completes:
- On input, the I/O device places data on the I/O bus and asserts
data valid; the interface latches the byte into its data register and sets flag bitF = 1in the status register. - The CPU repeatedly reads the status register: if
F == 0, it keeps polling; onceF == 1, the CPU reads the data register, resetsF = 0, and stores the byte in memory. - Drawback: Ties up of the CPU waiting for slow I/O peripherals, severely degrading multiprogramming throughput.
- On input, the I/O device places data on the I/O bus and asserts
- Interrupt-Driven I/O: Eliminates busy waiting by letting the CPU do useful work while the device controller prepares or consumes data:
- The CPU issues a read/write command to the I/O module and switches to execute another ready process.
- When the I/O module is ready to exchange a word of data, it asserts an interrupt request line to the CPU.
- The CPU suspends its current process, executes the Interrupt Service Routine (ISR) to transfer the word between the controller data register and memory, and resumes normal execution.
- Drawback: Still requires active CPU intervention (and an interrupt context switch) for every single word or byte transferred, which is too slow for high-speed block devices like disks.
- Direct Memory Access (DMA): Offloads bulk block transfers to a dedicated hardware DMA Controller so data moves directly between the peripheral device and main memory without continuous CPU involvement:
- The CPU programs the DMA controller with the memory buffer address, byte count, target device, and transfer direction, then switches to other work.
- To transfer data over the system bus, the DMA controller asserts Bus Request (
BR) to the CPU. - The CPU finishes its current bus cycle, places its address, data, and control lines into a high-impedance (tri-state) state, and asserts Bus Grant (
BG). - The DMA controller takes master control of the buses and transfers data directly between memory and the I/O device. When the entire block finishes, the DMA controller drops
BR, releases the bus back to the CPU, and raises a single interrupt to notify the OS that the whole block is ready.
| Feature | Programmed I/O | Interrupt-Driven I/O | Direct Memory Access (DMA) |
|---|---|---|---|
| Wait Mechanism | CPU busy-waits (polls status flag ) | CPU executes other processes until interrupted | DMA controller handles transfer; CPU interrupted once per block |
| Data Path | directly via system bus | ||
| CPU Overhead | Extremely high ( CPU wasted during I/O wait) | Moderate (one interrupt per byte/word transferred) | Minimal (one setup + one completion interrupt per multi-KB block) |
| Best Suited For | Simple embedded systems or ultra-fast registers | Low-speed character devices (keyboards, mice, serial ports) | High-speed block devices (magnetic disks, SSDs, NVMe, network cards) |
Principles and Goals of I/O Software
Regardless of the underlying hardware, operating system I/O software is designed around six core principles (OS Ch4):
- Device Independence: Programs should be able to read or write any I/O device (hard disk, USB flash drive, SSD) without having to be rewritten or recompiled for each device type.
- Uniform Naming: Every file and device is addressed using the same uniform naming scheme (e.g., UNIX mount paths
/dev/sda), independent of the physical device. - Error Handling: Errors should be handled as close to the hardware as possible. If a disk controller detects a read error, it first attempts to correct it transparently using Error-Correcting Code (ECC); only if the controller fails does the device driver retry, and only if the driver fails is the error reported up to the OS and user application.
- Synchronous (Blocking) vs. Asynchronous (Interrupt-Driven) Transfers: Physical I/O is fundamentally asynchronous (interrupt-driven), but user programs are much easier to write if I/O calls appear blocking (synchronous). The OS bridges this gap: when a process calls
read(), the OS issues the asynchronous hardware operation, blocks the calling process, and wakes it only when the interrupt arrives. - Buffering: Data arriving from a device (such as network packets or keyboard strokes) often cannot be written directly into user space immediately; the OS maintains kernel memory buffers (single buffer, double buffer, or circular buffer) to decouple producer and consumer speeds.
- Sharable vs. Dedicated Devices: Some devices (like disks) can be shared concurrently by many users at the same time, whereas dedicated devices (such as magnetic tape drives or printers) must be allocated exclusively to one job or mediated through a spooler until finished.
4.1.2 I/O software layer
I/O software is structured into four hierarchical layers, where each layer performs a well-defined role and communicates with adjacent layers through a clean interface (OS Ch4):
+-------------------------------------------------------------------+
| 1. User-Level I/O Software (printf, scanf, spooler daemons) | ^
+-------------------------------------------------------------------+ | Reply /
| 2. Device-Independent OS Software (buffering, naming, block size) | | Data
+-------------------------------------------------------------------+ | Flow
| 3. Device Drivers (controller registers, LBA->CHS) | |
+-------------------------------------------------------------------+ |
| 4. Interrupt Handlers (save PSW/regs, ISR, unblock) | |
+===================================================================+
| Physical Hardware & Controllers |
+-------------------------------------------------------------------+1. User-Level I/O Software (Top Layer)
- Library Procedures: Standard runtime libraries linked into user programs (such as
printf(),scanf(),fopen(),read(),write()in C) format data and invoke the underlying OS I/O system calls. - Spooling Systems: Spooling (Simultaneous Peripheral Operations On-Line) manages dedicated I/O devices (such as printers) in a multiprogramming environment. Instead of letting a user process open the physical printer directly (and potentially hold it idle for hours), user processes write their output files into a special spooling directory. A privileged background process called a printer daemon is the only process permitted to access the printer special file, printing queued files one by one in order.
2. Device-Independent Operating System Software
Provides the common services needed across all devices and presents a uniform interface to user-level software (OS Ch4):
- Uniform Interfacing for Device Drivers: Defines a standard driver table interface (
open,read,write,close,ioctl) so adding a new device driver does not require modifying the kernel. - Buffering: Manages kernel buffers in both block and character I/O to absorb bursty transfers and avoid writing directly into paged-out user memory.
- Error Reporting: Translates low-level controller/driver failure codes into standard system error codes (e.g.,
EIO). - Allocating and Releasing Dedicated Devices: Accepts or rejects
openrequests on non-sharable devices. - Device-Independent Logical Block Size: Hides differences in physical sector sizes across disks/SSDs by exposing a single uniform logical block size (e.g., ) to the file system layer.
3. Device Drivers
A device driver is the device-specific kernel module (typically written by the hardware manufacturer) that understands a particular controller's register layout, command set, and timing (OS Ch4).
- Core Functions:
- Accept abstract read/write requests from the device-independent layer above it and validate input parameters.
- Translate abstract logical parameters into concrete hardware parameters—for example, converting a linear logical block number into a physical CHS (Cylinder, Head, Sector) address on a magnetic disk.
- Initialize the device, manage its power states, and queue incoming requests if the device is currently busy.
- Working Mechanism of a Device Driver:
- Determines the sequence of controller commands needed for the request and writes them into the controller's device registers.
- Verifies that the controller accepted the command.
- Blocks itself (putting the calling process or driver thread to sleep) while the hardware controller performs the physical I/O operation.
- When the operation finishes, the hardware interrupt unblocks the driver; the driver inspects the controller status register for errors, passes the transferred data up to the device-independent software, and either starts the next queued request or goes back to sleep.
4. Interrupt Handlers (Bottom Layer)
When a hardware device finishes an I/O operation and asserts an interrupt, the interrupt handler executes a precise low-level sequence (OS Ch4):
| Phase | Action Performed by Hardware / OS Kernel |
|---|---|
| 1 | Save any CPU registers (including the Program Status Word, PSW, and Program Counter) not already saved automatically by the interrupt hardware. |
| 2 | Set up the execution context for the Interrupt Service Routine (ISR), including the MMU, TLB, page table, and a kernel stack for the ISR. |
| 3 | Acknowledge the centralized interrupt controller (or re-enable interrupts if no centralized controller is used). |
| 4 | Copy the interrupted process's saved registers from the temporary stack into its Process Control Block (process table entry). |
| 5 | Run the Interrupt Service Procedure (ISR), which reads status/data from the interrupting device controller's registers and unblocks (up/wakeup) the waiting device driver. |
| 6 | Invoke the scheduler to choose which ready process to run next (potentially preempting the previous process if the interrupt just unblocked a higher-priority process). |
| 7 | Load the chosen process's MMU/TLB context, restore its registers and PSW, and resume execution. |
4.1.3 Disk technologies: Magnetic disk, SSD, NVMe storage
1. Magnetic Disks (Hard Disk Drives — HDDs)
Physical Geometry of a Magnetic Disk
A magnetic hard disk drive consists of a stack of flat circular aluminum or glass platters coated on both surfaces with a magnetizable material (OS Ch4):
- Read/Write Heads and Arm Assembly: A read/write head "flies" on a microscopic cushion of air just above each platter surface. All heads are attached to a single disk actuator arm that moves all heads radially in and out together as one unit.
- Tracks: Each platter surface is logically divided into thousands of concentric circular rings called tracks.
- Sectors: Each track is subdivided into fixed-size arcs called sectors (traditionally , or in Advanced Format drives), separated by small inter-sector gaps.
- Cylinder: The set of all tracks across all platter surfaces at a single radial arm position (i.e., equidistant from the spindle) forms a cylinder. Reading consecutive tracks within the same cylinder requires no mechanical arm movement.
Disk Access Time and Data Transfer Rate
Disk Access Time Components and Transfer Rate
Accessing a sector on a magnetic disk involves three sequential physical delays:
- Seek Time (): The mechanical time required for the disk arm to move the read/write heads radially to the target cylinder (track). Typically to , dominating overall disk access time.
- Rotational Latency / Delay (): Once the head is positioned on the target track, the time spent waiting for the spinning platter to rotate the desired sector underneath the head. For a disk spinning at (revolutions per minute), one full rotation takes , and the average rotational latency is half a revolution:
- Data Transfer Time (): The time required to magnetically read or write the sector bytes as they pass under the head. If a track contains sectors of each (), the sustained data transfer rate is:
Disk Formatting and Error Handling
Before a newly manufactured magnetic disk can store files, it undergoes three stages of formatting (OS Ch4):
- Low-Level (Physical) Formatting: Performed at the factory. Divides every track into physical sectors, where each sector consists of three fields:
+----------------------------------+------------------------+------------------+ | Preamble (Sync pattern, Cyl/Sec) | Data Area (512B / 4KB) | ECC (Error Code) | +----------------------------------+------------------------+------------------+- Preamble: Bit pattern enabling the hardware to recognize the start of the sector, followed by the cylinder and sector numbers.
- Data Area: Payload bytes ( or ).
- ECC (Error-Correcting Code): Redundant checksum (such as Reed-Solomon code) calculated across the data bytes and verified automatically by the controller on every read to detect and correct bit errors.
- Mid-Level Formatting (Partitioning): Divides the physical disk into one or more logical cylinder groups (partitions). On MBR disks, Sector 0 holds the Master Boot Record boot code and the partition table specifying the starting sector and size of each partition.
- High-Level (Logical) Formatting: Performed by the OS (
mkfs/ Format) on each partition individually. Writes the partition's boot block, superblock, free-space management structures (bitmap or free list), and an empty root directory.
Handling Bad Sectors and Seek Errors (OS Ch4):
- Bad Sectors: Manufacturing defects or wear create sectors whose ECC repeatedly fails. Either the disk controller or the OS remaps bad sectors using one of two techniques (leaving spare sectors per track or cylinder):
- Sector Sparing (Substitution): The controller replaces the defective sector pointer directly with the address of a designated spare sector.
- Sector Shifting: All sectors between the bad sector and the spare sector are shifted down by one position so sequential logical sectors remain physically adjacent.
- Seek Errors: If mechanical arm drift causes the head to land on the wrong cylinder (detected when the controller reads the cylinder number from the next sector's preamble), modern hard disk controllers automatically issue corrective step pulses to recalibrate the arm.
Disk Arm Scheduling Algorithms
Because seek time () is proportional to the number of cylinders traversed and dominates disk I/O latency, the OS reorders pending disk requests in the queue to minimize total head movement (OS Ch4):
| Algorithm | Operating Principle | Advantages | Disadvantages |
|---|---|---|---|
| 1. FCFS (First Come First Served) | Services requests strictly in the FIFO order they arrive in the queue. | Simple and fair; zero starvation. | Wild back-and-forth head swings yield high total seek distance. |
| 2. SSTF (Shortest Seek Time First) | Always selects the pending request closest to the current head position (regardless of direction). | Substantially reduces total seek distance and average response time over FCFS. | Can cause starvation for distant requests at the inner/outer edges if nearby requests keep arriving. |
| 3. SCAN (Elevator Algorithm) | Moves the head in one direction servicing all requests in its path until it hits the physical end of the disk ( or ), then reverses direction. | Eliminates starvation; bounds maximum wait time. | Wastes arm travel moving all the way to the physical disk boundary ( or ) even when no request lies near the edge. |
| 4. C-SCAN (Circular SCAN) | Sweeps in one direction to the physical boundary (), jumps straight back to the opposite boundary () without servicing requests on the return trip, and sweeps again in the same direction. | Provides more uniform waiting time than SCAN (avoids biasing recently reversed edge cylinders). | Extra seek travel to both physical ends ( and ). |
| 5. LOOK | Like SCAN, sweeps back and forth, but reverses direction immediately upon reaching the last pending request in that direction (looks ahead before moving to the physical end). | Avoids unnecessary travel to physical disk boundaries and ; no starvation. | Slight software overhead to inspect the queue for the extremal request. |
| 6. C-LOOK (Circular LOOK) | Like C-SCAN, services requests in one direction up to the last pending request, then jumps directly to the lowest pending request at the other end and sweeps again. | Eliminates wasted boundary travel at both ends while preserving uniform circular wait times. | Slight overhead of tracking extremal requests in the queue. |
2. Solid-State Drives (SSD)
Solid-State Drive (SSD) Architecture and Flash Properties
A Solid-State Drive (SSD) is a non-volatile block storage device built from NAND flash memory integrated circuits with zero moving mechanical parts (OS Ch5).
- Zero Mechanical Latency: Because data is accessed electronically rather than by moving a physical head over spinning platters, an SSD has zero seek time () and zero rotational latency (). Random block reads are nearly as fast as sequential reads, making mechanical disk-arm scheduling algorithms (SSTF, SCAN, LOOK) obsolete for SSDs.
- Read / Write / Erase Asymmetry: NAND flash memory is organized into pages (typically –) grouped into erase blocks (typically – pages, or –):
- Reads and writes are performed at the page granularity.
- However, an already-written flash page cannot be overwritten in place! Before a page can be rewritten, its entire enclosing block must first be electrically erased.
- Flash Translation Layer (FTL), Wear Leveling, and Garbage Collection: Each NAND flash block can survive only a finite number of program-erase (P/E) cycles ( to cycles) before its oxide insulation wears out. An internal controller running the Flash Translation Layer (FTL):
- Remaps logical block addresses (LBAs) dynamically to fresh physical flash pages (out-of-place writes).
- Performs wear leveling to distribute writes and erasures evenly across all physical blocks on the drive.
- Runs background garbage collection (assisted by the OS
TRIMcommand) to copy valid pages out of partially stale blocks and erase the freed blocks.
3. NVMe (Non-Volatile Memory Express) Storage
Early SSDs were connected through the legacy SATA (Serial ATA) bus using the AHCI (Advanced Host Controller Interface) protocol. Because SATA/AHCI was originally designed for slow mechanical hard disks—supporting only 1 command queue holding at most 32 commands and capped at —the bus and protocol became a severe bottleneck for high-speed flash memory.
NVMe (Non-Volatile Memory Express) Storage
NVMe (Non-Volatile Memory Express) is an open, high-performance host controller interface and storage protocol engineered from the ground up for non-volatile solid-state storage attached directly to the CPU via the high-speed PCIe (Peripheral Component Interconnect Express) bus.
Key Architectural Advantages of NVMe over Legacy SATA/AHCI:
- Direct PCIe Bus Attachment: Bypasses the legacy SATA controller and communicates directly over multi-lane PCIe ( lanes), delivering to sequential throughput.
- Massive Parallel Queueing (): Supports up to () independent I/O submission/completion queues, with up to () commands per queue (compared to AHCI's single queue of commands). Each CPU core can have its own dedicated lockless NVMe queue.
- Streamlined Command Path: Requires only one 64-byte register write per I/O request (versus 4 uncacheable register reads/writes in AHCI) and uses MSI-X interrupts and polling to reduce I/O latency to .
| Characteristic | Magnetic Disk (HDD) | SATA SSD | NVMe SSD (PCIe) |
|---|---|---|---|
| Storage Medium | Rotating magnetic platters & moving read/write heads | NAND flash memory cells (no moving parts) | NAND flash memory cells (no moving parts) |
| Host Interface & Protocol | SATA / SAS with AHCI / SCSI | SATA III () with AHCI | PCIe ( Gen 3/4/5) with NVMe protocol |
| Hardware Queues | queue commands (NCQ) | queue commands (AHCI) | Up to queues commands/queue |
| Access Latency | (seek + rotational delay) | ||
| Sequential Throughput | |||
| Random IOPS () | |||
| Arm Scheduling Needed? | Yes (SSTF, SCAN, LOOK critical) | No (handled by FTL / wear leveling) | No (parallel multi-queue dispatch) |
4.1.4 RAID
RAID (Redundant Array of Independent Disks)
Introduced by Patterson, Gibson, and Katz (1988), RAID (Redundant Array of Independent Disks)—originally Redundant Array of Inexpensive Disks—is a storage virtualization technology that combines physical disk drives into a single logical storage unit presented to the operating system.
RAID achieves two complementary objectives:
- Increased Performance (Data Striping): Splits data across multiple drives (at the bit, byte, or block level) so multiple disks service read/write requests in parallel, multiplying I/O bandwidth.
- Increased Reliability / Fault Tolerance (Redundancy): Stores redundant information—either via mirroring (full duplication) or parity / error-correcting codes (XOR parity)—so data survives physical disk failures without loss.
Standard RAID Levels ( through and )
Suppose an array contains identical disks, each of storage capacity :
| RAID Level | Organization & Redundancy Scheme | Min. Disks | Usable Capacity | Disks Tolerated Before Data Loss | Key Characteristics & Use Cases |
|---|---|---|---|---|---|
| RAID 0 | Block-level striping without parity or mirroring | () | disks (any single disk failure destroys the array) | Maximum read/write speed and full capacity; zero fault tolerance. Used for scratch/cache data. | |
| RAID 1 | Disk mirroring (exact duplicate written to pairs of disks) | () | disk per mirrored pair (up to if in separate pairs) | Fast reads (can read from either mirror), simple recovery, capacity overhead. Used for OS boot/transaction logs. | |
| RAID 2 | Bit-level striping with Hamming error-correcting code disks | disk | Obsolete in practice because modern drives already include built-in sector ECC. | ||
| RAID 3 | Byte-level striping with one dedicated parity disk (synchronized spindles) | disk | High sequential transfer rate, but dedicated parity disk and synchronized spindles limit random IOPS. | ||
| RAID 4 | Block-level striping with one dedicated parity disk | disk | Independent block reads are fast, but every write must update the single dedicated parity disk, creating a severe write bottleneck. | ||
| RAID 5 | Block-level striping with distributed single parity across all disks | disk | Eliminates RAID 4's dedicated parity bottleneck by rotating parity blocks across all disks. Standard for general-purpose servers. | ||
| RAID 6 | Block-level striping with distributed dual parity ( Reed-Solomon) | disks simultaneously | Survives a second drive failure while a failed drive is being rebuilt. Used in mission-critical storage arrays. | ||
| RAID 10 (1+0) | Stripe of mirrors: data striped (RAID 0) across mirrored pairs (RAID 1) | (even) | () | disk per mirror pair | Combines RAID 1's fast rebuild and fault tolerance with RAID 0's parallel speed, avoiding RAID 5/6 parity calculation overhead. |
4.1.5 Concept of stable storage, cost per bit comparison
Concept of Stable Storage (Lampson and Sturgis Model)
While RAID protects against a disk drive failing permanently, what happens if a power failure or OS crash occurs in the middle of writing a single disk sector? The partially written sector will have an invalid ECC checksum, corrupting both the old data and the new data.
Stable Storage and Atomic Crash-Proof Operations
Designed by Lampson and Sturgis, stable storage is an abstraction constructed using a pair of identical physical disks (Drive 1 and Drive 2) that guarantees atomic, crash-safe block writes: a write either completes successfully or leaves the previous valid data intact, even if the system crashes mid-write.
Each logical block is represented by two corresponding physical blocks—Block on Drive 1 and Block on Drive 2—operated via three protocols:
- Stable Write:
- First, write the new data block to Drive 1 () and read it back to verify its ECC checksum (retrying or remapping if bad).
- Only after Drive 1's write is verified complete, write the identical data block to Drive 2 () and verify.
- Stable Read:
- Read Block from Drive 1. If the ECC checksum is valid, return immediately.
- If fails its ECC check (corrupted sector), read Block from Drive 2 instead (since both drives cannot fail in the exact same sector simultaneously).
- Crash Recovery (After Reboot): A background recovery scan compares corresponding blocks and across both drives:
- Case 1 — Both blocks have valid ECC and : Normal state; nothing to do.
- Case 2 — One block has a bad ECC checksum and the other is valid: The crash occurred during the write to the corrupted drive. Overwrite the bad block with the good block!
- Case 3 — Both blocks have valid ECC, but : The crash occurred after Drive 1 finished writing the new data, but before Drive 2 started writing! Copy (Drive 1) onto (Drive 2) to complete the atomic write.
Cost per Bit Comparison Across the Storage Hierarchy
Computer storage technologies exhibit a fundamental economic and physical trade-off: faster access time requires more expensive circuitry per bit and lower storage density (pages="added"):
| Hierarchy Level | Technology | Typical Access Latency | Typical Capacity | Volatile? | Relative Cost per Bit |
|---|---|---|---|---|---|
| 1. CPU Registers | Flip-flops / multi-port CMOS | ( clock cycle) | Yes | Highest ( HDD) | |
| 2. Cache Memory (L1/L2/L3) | On-chip SRAM (Static RAM, 6 transistors/bit) | Yes | Very High ( HDD) | ||
| 3. Main Memory (RAM) | DRAM (Dynamic RAM, 1 transistor + 1 capacitor/bit) | Yes | Moderate ( HDD) | ||
| 4. NVMe / SATA SSD | 3D NAND Flash Memory (floating-gate / charge-trap) | No | Low ( HDD) | ||
| 5. Magnetic Disk (HDD) | Spinning magnetic platters | No | Very Low (Baseline ) | ||
| 6. Magnetic Tape / Archival | Linear magnetic tape cartridges | Seconds to minutes (sequential) | No | Lowest ( HDD) |
Worked Out Examples
4.1
A magnetic disk drive rotates at (revolutions per minute), has , and stores (OS Ch4, slide 46). Assume the disk has an average seek time of . Calculate:
- The data transfer capacity per revolution (one track).
- The sustained data transfer rate in and (using ).
- The average rotational latency in milliseconds ().
- The total average access time to read a single sector in milliseconds ().
Part 1 — Data Transfer per Revolution (Track Capacity): In one complete revolution, the read/write head passes over all sectors of a single track:
Part 2 — Sustained Data Transfer Rate: At , the platter completes revolutions per minute, or :
Part 3 — Average Rotational Latency (): Time for one full revolution:
Average rotational latency is half a revolution:
Part 4 — Total Average Time to Read One Sector: Transfer time for sector out of sectors in a revolution:
Summing the three components:
- Data per revolution: .
- Data transfer rate: or .
- Average rotational latency: .
- Total average time to read one sector: .
4.2
Suppose a disk has cylinders, numbered from to . The read/write head is currently serving a request at cylinder , and the previous request was at cylinder (OS Ch4, slides 50–70). The queue of pending requests, in FIFO order, is:
Starting from the current head position (), calculate the total head movement (in cylinders) required to satisfy all pending requests under:
- FCFS
- SSTF
- SCAN
- C-SCAN
- LOOK
- C-LOOK
1. FCFS (First Come First Served): Requests are serviced in the exact arrival sequence :
2. SSTF (Shortest Seek Time First): At each position, move to the closest pending cylinder:
- From , closest is (dist , vs at dist ) (dist ) (dist ) (dist ) (dist ) (dist ) (dist ).
- Path: .
3. SCAN (Elevator Algorithm): Since the previous cylinder was and current is , the head is moving toward higher cylinder numbers (). It services , reaches the upper disk end , reverses direction, and services :
4. C-SCAN (Circular SCAN): Moves up from through to the physical boundary , sweeps back to cylinder without servicing requests, and moves up through :
5. LOOK and 6. C-LOOK:
- LOOK: Moves up from to the highest pending request (), then immediately reverses to the lowest pending request ():
- C-LOOK: Moves up from to , jumps directly to the lowest pending request , and moves up to ():
- FCFS:
- SSTF:
- SCAN:
- C-SCAN:
- LOOK:
- C-LOOK:
4.3
Suppose a disk has tracks numbered from to . The read/write head is currently at track , and track was accessed just before (OS Ch4, slide 71). The queue of pending requests in FIFO order is:
Given that a seek takes per cylinder moved, find the total head movement (in cylinders) and the total seek time (in ) for: (a) FCFS, (b) SSTF, (c) SCAN, (d) C-SCAN, (e) LOOK, and (f) C-LOOK.
Sorting Pending Requests Relative to Head at (Moving Up Since ):
- Lower than :
- Higher than :
(a) FCFS and (b) SSTF:
- FCFS ():
- SSTF (): From , closest is (dist , vs at dist ), then , then reverses to :
(c) SCAN and (d) C-SCAN (Moving Up Toward Track ):
- SCAN ():
- C-SCAN ():
(e) LOOK and (f) C-LOOK:
- LOOK ():
- C-LOOK ():
- (a) FCFS: ,
- (b) SSTF: ,
- (c) SCAN: ,
- (d) C-SCAN: ,
- (e) LOOK: ,
- (f) C-LOOK: ,
4.4
A storage server is equipped with identical hard disks, each of capacity . Calculate the usable storage capacity, storage efficiency (percentage of raw capacity available for user data), and guaranteed simultaneous disk failure tolerance when the drives are configured as:
- RAID 0
- RAID 10 (1+0)
- RAID 5
- RAID 6
Total Raw Capacity:
1. RAID 0 (Pure Block Striping) and 2. RAID 10 (Striped Mirrors):
- RAID 0: All disks store user data with zero redundancy:
- RAID 10: mirrored pairs striped together; half the capacity holds mirrors:
3. RAID 5 (Single Distributed Parity) and 4. RAID 6 (Dual Distributed Parity):
- RAID 5: Equivalent of disk's capacity is used for distributed XOR parity across the drives:
- RAID 6: Equivalent of disks' capacity is used for dual () parity:
- RAID 0: Usable ( efficiency), tolerates disk failures.
- RAID 10: Usable ( efficiency), tolerates disk failure guaranteed (up to if in different mirrored pairs).
- RAID 5: Usable ( efficiency), tolerates disk failure.
- RAID 6: Usable ( efficiency), tolerates simultaneous disk failures.
Exercises
Practice Exercises — I/O Management, Disk Scheduling, SSD/NVMe & RAID
Compare Programmed I/O, Interrupt-Driven I/O, and Direct Memory Access (DMA). Explain how Bus Request (BR) and Bus Grant (BG) signals coordinate a DMA transfer, and distinguish between Burst Mode and Cycle Stealing.
Comparison of Programmed I/O, Interrupt-Driven I/O, and DMA:
- Programmed I/O: The CPU issues an I/O command and continuously polls the controller's status flag ( bit) in a tight loop, wasting of CPU time until each word is transferred.
- Interrupt-Driven I/O: The CPU issues an I/O command and switches to other work; the device controller interrupts the CPU when each word is ready. Avoids busy waiting, but still incurs an interrupt per word.
- Direct Memory Access (DMA): A hardware DMA controller transfers an entire block of data directly between the I/O device and main memory over the system bus, interrupting the CPU only once when the entire block completes.
Bus Request (BR) and Bus Grant (BG) Handshake: When the DMA controller is ready to transfer data, it asserts the Bus Request (BR) line to the CPU. The CPU finishes its current bus cycle, places its address, data, and read/write lines into a high-impedance state, and asserts Bus Grant (BG). The DMA controller then drives the buses directly to move data between memory and the device, dropping BR when finished.
Burst Mode vs. Cycle Stealing:
- Burst Mode: The DMA controller holds the system bus continuously until an entire block of words is transferred.
- Cycle Stealing: The DMA controller steals a single bus cycle to transfer one word and immediately returns bus control to the CPU, interleaving DMA transfers with CPU execution.
Programmed I/O busy-waits on every word; Interrupt-Driven I/O interrupts the CPU on every word; DMA transfers entire blocks directly between memory and the device with a single completion interrupt. During DMA, the DMA controller asserts BR, the CPU tri-states its bus lines and asserts BG, and the transfer proceeds either in Burst Mode (holding the bus for a whole block) or Cycle Stealing (taking one bus cycle per word).
Describe the four layers of the I/O software stack and state the major functions of the Device-Independent OS Software layer and the Device Driver layer.
Four Layers of the I/O Software Stack (Top to Bottom):
- User-Level I/O Software: Library calls (
printf,read,write) and spooling daemons. - Device-Independent Operating System Software: Common OS I/O routines shared across all devices.
- Device Drivers: Device-specific modules that issue register-level commands to hardware controllers.
- Interrupt Handlers: Low-level routines that save CPU state, run the ISR, and wake blocked drivers when an I/O operation completes.
Functions of Device-Independent OS Software vs. Device Drivers:
- Device-Independent OS Software: Provides a uniform interface for device drivers, performs kernel buffering, handles error reporting, allocates and releases dedicated devices, and presents a uniform logical block size.
- Device Drivers: Validate parameters from the layer above, translate abstract requests into concrete hardware terms (e.g., logical block number to Cylinder-Head-Sector), write command sequences into controller registers, queue requests if the device is busy, and block until the completion interrupt arrives.
The four I/O software layers are: (1) User-Level I/O Software, (2) Device-Independent OS Software, (3) Device Drivers, and (4) Interrupt Handlers. The Device-Independent layer handles uniform driver interfacing, buffering, error reporting, dedicated device allocation, and uniform block sizing, whereas the Device Driver translates logical requests into hardware controller register commands and blocks awaiting interrupt completion.
A magnetic disk drive has cylinders numbered to . The disk head is currently at cylinder and is moving toward higher-numbered cylinders (). The queue of pending requests in FIFO order is:
Calculate the total head movement (in cylinders) for: (a) FCFS, (b) SSTF, (c) SCAN, (d) C-SCAN, and (e) C-LOOK.
(a) FCFS ():
(b) SSTF (): From , closest is (dist , vs at dist ) (dist ) (dist , vs at dist ) (dist ) :
(c) SCAN, (d) C-SCAN, and (e) C-LOOK (Moving Up Toward ):
- SCAN ():
- C-SCAN ():
- C-LOOK ():
- (a) FCFS:
- (b) SSTF:
- (c) SCAN:
- (d) C-SCAN:
- (e) C-LOOK:
A magnetic hard disk rotates at , has an average seek time of , , and . Calculate:
- The average rotational latency in milliseconds ().
- The sustained data transfer rate in ().
- The total average time required to read a contiguous () block in milliseconds ().
Part 1 — Average Rotational Latency: At , one full rotation takes:
Average rotational latency (half a rotation):
Part 2 — Sustained Data Transfer Rate: Track capacity , and rotational speed :
Part 3 — Total Average Time to Read Contiguous Sectors: Transfer time for sectors out of sectors on a track:
Total average access time:
- Average rotational latency: ().
- Data transfer rate: .
- Total average time to read an -sector () block: .
Compare Magnetic Disks (HDD), SATA SSDs, and NVMe SSDs. Explain why NAND flash SSDs require wear leveling and why mechanical disk-arm scheduling algorithms are unnecessary for SSDs.
Comparison of HDD, SATA SSD, and NVMe SSD:
- Magnetic Disk (HDD): Stores data on rotating magnetic platters accessed by moving read/write heads ( seek + rotational latency, ).
- SATA SSD: Uses NAND flash memory over the legacy SATA/AHCI interface ( queue of commands, latency, capped around ).
- NVMe SSD: Attaches NAND flash directly to the PCIe bus using the NVMe protocol, supporting up to queues with commands per queue, latency, and multi-GB/s throughput.
Why SSDs Need Wear Leveling and Not Arm Scheduling:
- Wear Leveling: In NAND flash, pages cannot be overwritten in place; an entire flash block must be erased before rewriting, and each block endures only a finite number of program-erase cycles before wearing out. The Flash Translation Layer (FTL) remaps logical writes across all physical blocks (wear leveling) so no single block wears out prematurely.
- No Arm Scheduling: Because SSDs have no moving heads or rotating platters, seek time and rotational delay are zero—accessing any flash page takes the same time regardless of its address.
HDDs rely on mechanical platters and heads ( latency); SATA SSDs use flash over a single-queue legacy SATA bus (); NVMe SSDs connect flash directly to the PCIe bus with parallel queues and multi-GB/s speed. SSDs require wear leveling because flash blocks can only be erased a limited number of times, and they do not need arm scheduling because electronic flash access has zero seek or rotational latency.
Explain the concept of Stable Storage (Lampson and Sturgis model) and describe how its Crash Recovery procedure restores consistency after a power failure during a write. Also compare RAID 1, RAID 5, and RAID 6.
Lampson and Sturgis Stable Storage & Crash Recovery: Stable storage pairs two independent physical disk blocks ( on Drive 1 and on Drive 2) for each logical block. A Stable Write first writes and verifies on Drive 1, and only after succeeds does it write and verify on Drive 2. Upon reboot after a crash, Crash Recovery compares and :
- If both blocks have valid ECC and , no action is needed.
- If one block has a bad ECC checksum (crash occurred mid-sector write), the bad block is overwritten with the valid block.
- If both blocks have valid ECC but (crash occurred between finishing Drive 1 and starting Drive 2), is copied onto .
Comparison of RAID 1, RAID 5, and RAID 6 (for disks of size ):
- RAID 1 (Mirroring): Duplicates every block onto a mirror disk. Usable capacity , tolerates disk failure per pair, fast reads and no parity calculation overhead, but capacity cost.
- RAID 5 (Block Striping with Distributed Single Parity): Rotates XOR parity blocks across all disks. Usable capacity , tolerates disk failure, incurs a 4-I/O small-write penalty.
- RAID 6 (Block Striping with Distributed Dual Parity): Stores two independent parity blocks ( and ) per stripe across all disks. Usable capacity , tolerates simultaneous disk failures.
Stable storage writes sequentially to two mirrored blocks ( then ) and recovers after a crash by copying the valid block over a bad-ECC block or copying if both are valid but unequal. RAID 1 uses full mirroring ( capacity, -disk fault tolerance), RAID 5 stripes blocks with single distributed parity ( capacity, -disk fault tolerance), and RAID 6 uses dual distributed parity ( capacity, -disk fault tolerance).