Storage and I/O: Disk Scheduling, SSDs, RAID and I/O Models

Why storage and I/O matter

A CPU executes billions of instructions per second; a hard disk performs perhaps a hundred random reads per second. That gap of roughly seven orders of magnitude is the reason so much of operating-system design is about input/output (I/O): hiding slow devices behind caches and buffers, ordering requests cleverly, letting the CPU do other work while devices transfer data, and surviving device failures.

This lesson starts with the physical disk and how long one access takes, then covers disk scheduling algorithms (with one shared request queue and every total worked out), how SSDs change the picture, RAID levels, and finally the I/O system itself: polling, interrupts, DMA, buffering, device drivers and the blocking, non-blocking and asynchronous I/O models behind select, epoll and io_uring.

Interviewers commonly ask you to compute head movement for SSTF or SCAN, compare RAID 5 and RAID 10, explain DMA, and describe how a server handles ten thousand connections with epoll.

Anatomy of a hard disk

A hard disk drive (HDD) stores data magnetically on spinning platters.

        spindle
           |
   +-------+-------+  <- platter (both surfaces used)
   |   . track .   |
   |  .  +---+  .  |     sector = a slice of one track
   |  .  | o |  .  |     (512 B or 4 KiB)
   |   . ..... .   |
   +---------------+
        ^
   read/write head on an arm; all arms move together

   cylinder = the same track number on every surface

• A platter is a circular disk coated with magnetic material. A drive has one or more, stacked on a spindle that spins at a fixed speed (5400, 7200, 10,000 or 15,000 revolutions per minute, RPM).
• Each surface has a read/write head on an arm. All arms move together as one assembly.
• A track is one concentric ring on a surface.
• A sector is the smallest addressable unit on a track, traditionally 512 bytes, 4 KiB on modern "Advanced Format" drives.
• A cylinder is the set of tracks at the same arm position across all surfaces. Data in one cylinder can be read without moving the arm.

Old interfaces addressed sectors by (cylinder, head, sector), called CHS. Modern drives use logical block addressing (LBA): the disk looks like a flat array of blocks numbered from 0, and the drive firmware maps block numbers to physical locations (and quietly remaps bad sectors). Low LBAs are usually on the outer tracks, which pass under the head faster, so the start of a disk is often faster than the end.

The three parts of an access

Reading a sector takes three steps:

1. Seek time: move the arm to the right cylinder. Typically several milliseconds; the "average seek time" on a datasheet is often 4 to 10 ms.
2. Rotational latency: wait for the right sector to rotate under the head. On average, half a revolution.
3. Transfer time: read the bits as they pass under the head. Size divided by transfer rate.

access time = seek time + rotational latency + transfer time

Worked example: one random read

A 7200 RPM disk, average seek time 9 ms, sustained transfer rate 150 MB/s. Read one random 4 KiB block.

1. One revolution takes 60 s / 7200 = 8.33 ms.
2. Average rotational latency = half a revolution = 4.17 ms.
3. Transfer time = 4096 B / 150,000,000 B/s = 0.027 ms.
4. Total = 9 + 4.17 + 0.027 = 13.19 ms.

That gives about 1000 / 13.19 = 76 random reads per second, or only 76 x 4 KiB = about 0.31 MB/s of useful throughput, from a disk rated at 150 MB/s.

Now read 1 MiB sequentially from one random starting point:

1. Seek and rotation as before: 9 + 4.17 = 13.17 ms.
2. Transfer = 1,048,576 / 150,000,000 = 6.99 ms.
3. Total = 20.16 ms, giving an effective rate of about 52 MB/s.

The lesson: on an HDD, positioning (seek plus rotation) dominates. Reading big contiguous chunks and reducing arm movement matter enormously. That is the motivation for disk scheduling, extent-based file systems and sequential log writes.

Disk scheduling

Many processes issue disk requests; they wait in a queue. The OS (or the drive itself) can choose the order in which to serve them. Disk scheduling picks that order to reduce total seek distance, measured as total head movement in cylinders, while keeping waiting times fair.

The shared worked example

Use the same input for every algorithm so you can compare:

• Cylinders numbered 0 to 199.
• Head currently at 50, last moving toward higher cylinder numbers.
• Request queue in arrival order: 82, 170, 43, 140, 24, 16, 190.

FCFS (first come, first served)

Serve requests in arrival order.

50 -> 82 -> 170 -> 43 -> 140 -> 24 -> 16 -> 190

Fair (no starvation) and simple, but the head swings wildly back and forth.

SSTF (shortest seek time first)

Always serve the pending request closest to the current head position.

1. At 50: nearest is 43 (distance 7) versus 82 (32). Go to 43.
2. At 43: 24 (19) versus 82 (39). Go to 24.
3. At 24: 16 (8). Go to 16.
4. At 16: only higher requests remain; nearest is 82 (66).
5. Then 140 (58), 170 (30), 190 (20).

50 -> 43 -> 24 -> 16 -> 82 -> 140 -> 170 -> 190
 7 + 19 +  8  + 66 +  58 +  30 +   20  = 208

Total = 208. Much better than FCFS. But SSTF is greedy, not optimal in general, and it can starve requests far from the head: if new requests keep arriving near the head, a request at the far edge may wait indefinitely. It is similar in spirit to shortest-job-first CPU scheduling.

SCAN (the elevator algorithm)

The head sweeps in one direction to the end of the disk, serving requests on the way, then reverses and sweeps back. Like a lift that goes all the way up, then all the way down.

Moving toward higher numbers first:

50 -> 82 -> 140 -> 170 -> 190 -> 199 -> 43 -> 24 -> 16

1. 50 up to the end, 199: 149 cylinders (serving 82, 140, 170, 190 on the way).
2. Reverse, 199 down to 16: 183 cylinders (serving 43, 24, 16).

Total = 149 + 183 = 332.

No starvation, and bounded waiting. Its weakness: after the head reverses, the requests just behind it (near the end it just left) are served again quickly, while requests at the far end, which have waited longest, are served last. Waiting times are uneven.

C-SCAN (circular SCAN)

Sweep in one direction only. At the end, jump back to the other end without serving anything, then sweep in the same direction again. This treats the cylinders as a circular list and gives more uniform waiting times.

50 -> 82 -> 140 -> 170 -> 190 -> 199 => 0 -> 16 -> 24 -> 43
                                  (return)

1. 50 up to 199: 149.
2. Return 199 to 0: 199.
3. 0 up to 43: 43.

Total = 149 + 199 + 43 = 391 if you count the return sweep. Some textbooks and exam papers do not count the return (since it is a fast seek with no reads); then the total is 149 + 43 = 192. State which convention you use.

LOOK

Like SCAN, but the head only goes as far as the last request in each direction, not to the physical end of the disk.

50 -> 82 -> 140 -> 170 -> 190 -> 43 -> 24 -> 16

1. 50 up to 190: 140.
2. 190 down to 16: 174.

Total = 314. Saves the pointless trip from 190 to 199 and back.

C-LOOK

Like C-SCAN, but go only as far as the last request, then jump to the lowest pending request (not cylinder 0).

50 -> 82 -> 140 -> 170 -> 190 => 16 -> 24 -> 43
                            (jump)

1. 50 up to 190: 140.
2. Jump 190 to 16: 174.
3. 16 up to 43: 27.

Total = 140 + 174 + 27 = 341 counting the jump, or 167 without it.

Summary of the worked example

On this input SSTF wins on raw distance, because the three low requests are close to the starting point. On other inputs SCAN or LOOK may tie or win, and they never starve requests.

Here is a script that reproduces every number above:

def total_movement(path):
    return sum(abs(b - a) for a, b in zip(path, path[1:]))

def fcfs(head, queue, max_cyl):
    return [head] + queue

def sstf(head, queue, max_cyl):
    pending, path = list(queue), [head]
    while pending:
        nearest = min(pending, key=lambda c: (abs(c - path[-1]), c))
        pending.remove(nearest)
        path.append(nearest)
    return path

def scan(head, queue, max_cyl):      # moving toward max_cyl first
    up = sorted(c for c in queue if c >= head)
    down = sorted((c for c in queue if c < head), reverse=True)
    return [head] + up + ([max_cyl] if down else []) + down

def look(head, queue, max_cyl):
    up = sorted(c for c in queue if c >= head)
    down = sorted((c for c in queue if c < head), reverse=True)
    return [head] + up + down

def c_scan(head, queue, max_cyl):
    up = sorted(c for c in queue if c >= head)
    low = sorted(c for c in queue if c < head)
    return [head] + up + ([max_cyl, 0] if low else []) + low

def c_look(head, queue, max_cyl):
    up = sorted(c for c in queue if c >= head)
    low = sorted(c for c in queue if c < head)
    return [head] + up + low

queue, head, max_cyl = [82, 170, 43, 140, 24, 16, 190], 50, 199
for algo in (fcfs, sstf, scan, c_scan, look, c_look):
    path = algo(head, queue, max_cyl)
    print(f"{algo.__name__:7} {total_movement(path):4}  {path}")

Output:

fcfs     642  [50, 82, 170, 43, 140, 24, 16, 190]
sstf     208  [50, 43, 24, 16, 82, 140, 170, 190]
scan     332  [50, 82, 140, 170, 190, 199, 43, 24, 16]
c_scan   391  [50, 82, 140, 170, 190, 199, 0, 16, 24, 43]
look     314  [50, 82, 140, 170, 190, 43, 24, 16]
c_look   341  [50, 82, 140, 170, 190, 16, 24, 43]

Disk scheduling in real systems

• Modern drives accept many requests at once (NCQ, native command queuing, on SATA allows up to 32) and reorder them internally, because only the drive knows the exact rotational position.
• Linux uses I/O schedulers in its multi-queue block layer: mq-deadline (sorts requests and enforces deadlines so none starve), bfq (budget fair queuing, for interactive desktops), kyber, and none (no reordering, common for fast NVMe SSDs). You can see the active one with cat /sys/block/sda/queue/scheduler.
• Older Linux kernels had CFQ (completely fair queuing) as the default; it was removed when the single-queue block layer was retired.

SSDs versus HDDs

A solid-state drive (SSD) stores data in NAND flash memory chips. There are no moving parts, so there is no seek and no rotation. Random reads take tens of microseconds instead of milliseconds.

Flash has unusual rules that shape everything about SSDs:

1. Data is read and written in pages (typically 4 to 16 KiB).
2. A page cannot be overwritten in place. It must be erased first, and erasure works only on a whole erase block of many pages (often hundreds of pages, several megabytes).
3. Each block survives only a limited number of program/erase cycles before wearing out; fewer for denser cell types (TLC and QLC store 3 and 4 bits per cell).

The flash translation layer (FTL)

The SSD's controller runs firmware called the flash translation layer (FTL) that hides these rules and presents a normal block device:

• Out-of-place writes: when the OS overwrites logical block 100, the FTL writes the new data to a fresh, already-erased page and updates a mapping table (logical block to physical page). The old page is marked invalid.
• Garbage collection: in the background, the FTL picks erase blocks with many invalid pages, copies the still-valid pages elsewhere, and erases the block so it can be reused. Copying valid pages means the drive writes more than the host asked for; the ratio is called write amplification.
• Wear levelling: the FTL spreads writes across all blocks, including occasionally moving long-lived (cold) data, so no block wears out early.
• Over-provisioning: drives keep spare capacity the OS cannot see to give garbage collection room to work.

 OS writes logical block 100 three times:
   logical 100 -> page A (v1)   later invalid
   logical 100 -> page B (v2)   later invalid
   logical 100 -> page C (v3)   current mapping
 GC later copies valid pages out of A's and B's erase blocks,
 then erases them.

TRIM

When you delete a file, the file system just marks blocks free in its own bitmap; the SSD does not know they are garbage and would keep copying them during garbage collection. The TRIM command (called UNMAP in SCSI and Deallocate in NVMe) tells the SSD which logical blocks no longer hold useful data, so it can drop them. On Linux it is issued either continuously (the discard mount option) or periodically with fstrim (often run weekly by a systemd timer).

Why scheduling matters less on SSDs

• There is no head, so "distance" between blocks means nothing; access time does not depend on position.
• SSDs have many flash chips working in parallel and deep internal queues. NVMe drives support up to 65,535 queues of up to 65,536 commands each, and Linux typically gives each CPU its own queue.
• Reordering by block number gives no benefit and costs CPU, so Linux often uses none or mq-deadline for NVMe.

What still matters on SSDs: merging small adjacent requests, keeping enough requests in flight to use the parallelism, avoiding small random writes that increase write amplification, and fairness between processes.

RAID

RAID (redundant array of independent disks) combines several disks into one logical device for more performance, more reliability, or both. Three building blocks:

• Striping: split data into chunks spread across disks, so one large request uses all disks in parallel.
• Mirroring: keep identical copies on two or more disks.
• Parity: store an error-correcting value computed from data on other disks, so a lost disk can be rebuilt.

Parity with XOR

RAID 5 parity is the XOR of the data chunks in a stripe. XOR has the property that any one value can be recomputed from all the others.

Worked example, one stripe of three data chunks (4 bits each for clarity):

1. D0 = 1011, D1 = 0110, D2 = 1100.
2. P = D0 XOR D1 XOR D2 = 1011 XOR 0110 = 1101; then 1101 XOR 1100 = 0001.
3. The disk holding D1 fails. Rebuild D1 = D0 XOR D2 XOR P = 1011 XOR 1100 = 0111; 0111 XOR 0001 = 0110. Correct.

The levels

 RAID 0 (striping)        RAID 1 (mirror)
 disk0  disk1             disk0  disk1
 [A1]   [A2]              [A1]   [A1]
 [A3]   [A4]              [A2]   [A2]

 RAID 5 (rotating parity)        RAID 10 (stripe of mirrors)
 disk0  disk1  disk2  disk3      pair 1         pair 2
 [A1]   [A2]   [A3]   [Ap]       d0    d1       d2    d3
 [B1]   [B2]   [Bp]   [B3]       [A1]  [A1]     [A2]  [A2]
 [C1]   [Cp]   [C2]   [C3]       [A3]  [A3]     [A4]  [A4]

• RAID 0 (striping): data split across all disks, no redundancy. Fastest and full capacity, but any one disk failure loses the whole array. Use for scratch data you can regenerate.
• RAID 1 (mirroring): every block written to each disk. Survives the loss of all but one disk in the mirror. Reads can be served by any copy; writes go to all.
• RAID 5 (striping with distributed parity): one chunk of parity per stripe, rotated across disks so no single disk is a bottleneck. Survives one disk failure. Small writes are expensive: updating one chunk requires reading the old data and old parity, then writing new data and new parity (four I/Os, the "small write penalty").
• RAID 6 (dual parity): two independent parity chunks per stripe (the second uses a different code, not plain XOR). Survives two simultaneous failures. Higher write penalty than RAID 5.
• RAID 10 (1+0): mirror pairs, then stripe across the pairs. Survives one failure per mirror pair. Good write performance and fast rebuilds (copy from the partner), at the cost of half the raw capacity.

RAID 2, 3 and 4 exist (bit-level ECC, byte-level and block-level striping with a dedicated parity disk) but are essentially unused today; RAID 4's dedicated parity disk becomes a write bottleneck, which RAID 5 fixes by rotating parity.

Capacity and fault-tolerance table

With n disks of capacity C each:

Worked example: six 4 TB disks

Practical notes

• During a rebuild after a failure, a RAID 5 array has no redundancy left and every remaining disk is read end to end. With very large disks the rebuild takes many hours, and a second failure or an unreadable sector during that time can lose data. This is the main reason large arrays prefer RAID 6 or RAID 10.
• RAID is not a backup. It protects against disk failure, not against accidental deletion, ransomware, file-system bugs or a fire. Deleted files are deleted on every mirror instantly.
• RAID can be done in hardware (a controller card, often with a battery-backed cache), in software (Linux mdadm, Windows Storage Spaces), or inside the file system (ZFS RAID-Z, Btrfs).

The I/O system: how the CPU talks to devices

Devices connect to the computer through buses (PCI Express, USB, SATA) and are controlled by a device controller, a small processor on the device or motherboard with its own registers and buffers. The CPU talks to the controller by reading and writing those registers, in one of two ways:

• Port-mapped I/O: special CPU instructions (in and out on x86) access a separate I/O address space.
• Memory-mapped I/O: device registers appear at physical memory addresses; ordinary load and store instructions access them. This is what PCIe devices use.

A typical controller has a status register (busy, ready, error), a control (command) register, and data-in and data-out registers. There are three ways to move data.

Programmed I/O (polling)

The CPU does everything itself:

1. Repeatedly read the status register until the device is not busy (busy-waiting, also called polling).
2. Write the command and data to the device registers.
3. Poll again until the device reports completion.
4. Copy each byte or word itself.

Simple, and actually the fastest option when the device responds within a few CPU cycles. But for a slow device the CPU wastes millions of cycles spinning.

Interrupt-driven I/O

The CPU issues a command and goes off to do other work. When the device is ready, the controller raises an interrupt signal:

1. The CPU finishes the current instruction, saves state, and jumps to the interrupt handler found through the interrupt vector table.
2. The handler reads the status, moves the data, and wakes the process waiting for it.
3. The CPU returns to what it was doing.

No wasted spinning, but there is an interrupt per unit of data (each byte or word for a simple device), and each interrupt costs hundreds of cycles of overhead. For a disk transferring megabytes, that is still too much CPU work.

Linux splits interrupt handling into a fast top half (acknowledge the device, grab data, schedule more work) that runs with interrupts disabled, and a deferred bottom half (softirqs, tasklets or workqueues) that does the slower processing.

DMA (direct memory access)

For bulk transfers, a DMA controller (part of most device controllers today) moves data between the device and RAM without the CPU copying each word:

1. The CPU (driver) writes a DMA command: source, destination address in RAM, byte count, direction. Often this is a list of buffers (scatter-gather list).
2. The DMA engine transfers the whole block directly over the bus to or from memory.
3. When the transfer completes, the device raises one interrupt.

  CPU                  DMA/controller            RAM
   | program transfer        |                    |
   |------------------------>|                    |
   | (runs other processes)  |--- data words ---->|
   |                         |--- data words ---->|
   |<----- one interrupt ----|  (done)            |

The CPU is involved only at the start and end. While DMA uses the memory bus the CPU may occasionally have to wait for it (called cycle stealing), but the CPU mostly runs from its caches anyway. On systems with an IOMMU, device DMA addresses are translated and checked like virtual memory, which stops a buggy or malicious device from writing anywhere in RAM.

Interestingly, extremely fast devices bring polling back: at millions of operations per second, interrupt overhead dominates, so Linux's NAPI (for network cards) switches to polling under heavy load, and io_uring and NVMe drivers offer polling modes.

Kernel I/O subsystem: buffering, caching and spooling

Buffering

A buffer is a memory area that holds data while it moves between two parties. The kernel buffers for three reasons:

1. Speed mismatch: a network card receives a packet faster than the application reads it, or a slow modem fills a buffer the disk then writes in one go.
2. Transfer size mismatch: network packets are reassembled into one larger message; a 100-byte application write is collected into a full disk block.
3. Copy semantics: when an application calls write(fd, buf, n), the kernel copies buf immediately, so the application can reuse buf right away, even though the device writes later.

Double buffering uses two buffers: the device fills one while the consumer empties the other, then they swap. Circular (ring) buffers generalise this to many slots and are everywhere: network card receive rings, audio, io_uring.

Caching

A cache holds a copy of data that also exists elsewhere, to serve repeated access faster. The difference from a buffer: a buffer may hold the only copy of data in transit; a cache holds a duplicate.

Linux's page cache keeps recently used file blocks in otherwise free RAM. Reads that hit the cache need no disk I/O; writes go into the cache and are flushed later by kernel writeback threads (write-back caching). This is why free shows most RAM as "buff/cache" on a busy server and why that memory is still effectively available. See Linux internals for reading those numbers.

Spooling

A spool (simultaneous peripheral operations on-line) is a buffer for a device that can serve only one job at a time and cannot interleave jobs, like a printer. Each process's output is written to a separate spool file on disk; a spooler daemon sends the files to the printer one at a time. Applications finish immediately, and pages from different jobs are never mixed. Print queues (CUPS on Linux and macOS) are the classic example; batch job queues and outgoing mail queues use the same idea.

Other kernel I/O services

• I/O scheduling (as above).
• Error handling: retry failed operations, report errors via return codes (errno).
• Device reservation and protection: all I/O instructions are privileged, so user programs must go through system calls.

Device drivers

A device driver is the kernel code that knows how to operate one kind of device controller. It translates generic requests ("read 8 blocks starting at block 1000") into the specific register writes and DMA setups that particular hardware needs, and handles its interrupts.

   application:    read(fd, buf, 4096)
   ------------------------------------------- user/kernel boundary
   system call layer
   VFS and file system (ext4)
   page cache
   block layer and I/O scheduler
   device driver (NVMe driver)
   ------------------------------------------- hardware
   device controller -> flash chips

Drivers present a uniform interface upward. Unix groups devices into classes:

• Block devices (disks, SSDs): accessed in fixed-size blocks, support random access, go through the block layer and page cache. /dev/sda, /dev/nvme0n1.
• Character devices (keyboards, serial ports, /dev/null, /dev/random): a stream of bytes, no seeking in most cases.
• Network devices (eth0, wlan0): accessed through the socket interface, not through files in /dev.

Linux drivers can be built into the kernel or loaded as kernel modules at run time (lsmod, modprobe). Drivers run in kernel mode, so a buggy driver can crash the whole system; historically drivers have been one of the largest sources of kernel bugs. Some systems run drivers in user space for isolation (FUSE for file systems, DPDK and SPDK for fast networking and storage).

Blocking, non-blocking and asynchronous I/O

How does a system call behave when data is not ready yet?

• Blocking I/O: the call does not return until the operation completes. The calling thread sleeps meanwhile. Simple to program: n = read(fd, buf, 4096) gives you data or end-of-file. The default for files and sockets.
• Non-blocking I/O: the call returns immediately. If no data is ready, it fails with EAGAIN (or EWOULDBLOCK) and you try again later. Set with O_NONBLOCK. You need a way to know when to try again, which is what I/O multiplexing provides.
• Asynchronous I/O: you submit the operation and return immediately; the kernel performs the whole operation, including copying the data into your buffer, and notifies you when it is complete (by a signal, callback or completion queue).

The difference between non-blocking and asynchronous is subtle and commonly asked: non-blocking tells you "ready, now you do the read"; asynchronous tells you "done, the data is already in your buffer".

 Blocking:      read() ----sleeping until data----> returns data
 Non-blocking:  read() -> EAGAIN, read() -> EAGAIN, read() -> data
 Multiplexing:  epoll_wait() --> "fd 7 ready" --> read(7) -> data
 Async:         submit read --> do other work --> "read done" (data in buf)

Blocking I/O with one thread per connection is easy, but each thread costs memory (its stack) and scheduling overhead, which becomes a problem at tens of thousands of connections (the "C10K problem"). Event-driven servers such as nginx, Node.js and Redis use one or a few threads with non-blocking sockets and multiplexing instead.

select, poll, epoll and io_uring

I/O multiplexing lets one thread wait on many file descriptors at once and learn which are ready.

• select (POSIX): pass bit sets of descriptors to watch. The kernel scans all of them on every call, and the sets must be rebuilt each time. Limited to FD_SETSIZE descriptors (usually 1024). Cost is O(n) in the number of watched descriptors per call.
• poll (POSIX): passes an array of pollfd structures instead; no 1024 limit, but still O(n) per call, and the whole array is copied into the kernel each time.
• epoll (Linux): you register descriptors once with epoll_ctl; the kernel keeps the interest list and a ready list. epoll_wait returns only the ready descriptors, so the cost scales with the number of active descriptors, not total. Supports level-triggered (report while ready, the default) and edge-triggered (report only on a change to ready; you must drain the socket until EAGAIN) modes. BSD and macOS have the equivalent kqueue; Windows uses I/O completion ports (IOCP), which is a completion-based model.
• io_uring (Linux 5.1 and later): a truly asynchronous interface built on two ring buffers shared between the application and the kernel: a submission queue and a completion queue. The application writes requests into the submission ring and reads results from the completion ring, often with very few system calls. It works for files, sockets and many other operations, and supports polling modes. Because it is a large, complex kernel attack surface, some environments restrict it (for example some container runtimes and Android block it via seccomp policies).

Python's selectors module picks the best mechanism for the platform (epoll on Linux, kqueue on macOS). This small echo server handles many clients on one thread:

import selectors
import socket

sel = selectors.DefaultSelector()          # epoll on Linux, kqueue on macOS

server = socket.socket()
server.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
server.bind(("127.0.0.1", 9000))
server.listen()
server.setblocking(False)
sel.register(server, selectors.EVENT_READ)

while True:
    for key, _ in sel.select():            # blocks until something is ready
        if key.fileobj is server:
            conn, _ = server.accept()
            conn.setblocking(False)
            sel.register(conn, selectors.EVENT_READ)
        else:
            conn = key.fileobj
            data = conn.recv(4096)
            if data:
                conn.sendall(data)         # echo back
            else:
                sel.unregister(conn)
                conn.close()

(For brevity it uses sendall on a non-blocking socket, which is fine for a demo; a production server would buffer unsent output and wait for write-readiness.)

Interview questions

Q1. What are the components of disk access time?

Seek time to move the arm to the cylinder, rotational latency to wait for the sector (half a revolution on average), and transfer time (size divided by transfer rate). For random small reads on an HDD, seek and rotation dominate, so a 7200 RPM disk manages only around 75 to 100 random reads per second.

Q2. Compare SSTF and SCAN.

SSTF serves the nearest request next, which minimises immediate seek distance but can starve far requests. SCAN sweeps from end to end serving requests on the way, which bounds waiting time and avoids starvation at the cost of sometimes more movement. LOOK improves SCAN by reversing at the last request instead of the disk edge.

Q3. Why does C-SCAN exist when SCAN already avoids starvation?

After SCAN reverses, requests just behind the head are served again quickly while those at the far end wait for two sweeps. C-SCAN always serves in one direction and jumps back, treating the disk as circular, so waiting times are more uniform.

Q4. Why do disk scheduling algorithms matter less for SSDs?

SSDs have no moving head, so access time does not depend on the distance between blocks. They also process many requests in parallel internally. Linux often uses the none scheduler for NVMe drives and focuses on merging requests and keeping queues full.

Q5. What do the FTL, garbage collection and TRIM do?

Flash cannot be overwritten in place and erases only in large blocks, so the flash translation layer writes updates to fresh pages and remaps logical blocks. Garbage collection reclaims blocks full of stale pages by moving valid data and erasing. TRIM tells the drive which logical blocks the file system no longer uses, so GC need not preserve them, reducing write amplification.

Q6. What is wear levelling?

Each flash block tolerates a limited number of program/erase cycles. Wear levelling spreads writes evenly over all blocks, including periodically moving cold data, so that no block wears out much earlier than the others.

Q7. Compare RAID 0, 1, 5, 6 and 10.

RAID 0 stripes with no redundancy: full capacity, no fault tolerance. RAID 1 mirrors: one disk's capacity, survives all but one disk failing. RAID 5 stripes with rotating parity: n - 1 disks of capacity, survives one failure, small-write penalty. RAID 6 uses two parities: n - 2 capacity, survives two failures. RAID 10 stripes over mirror pairs: half capacity, good write performance and fast rebuilds.

Q8. Why is RAID not a backup?

RAID protects only against disk hardware failure. Deletions, corruption, ransomware and software bugs are faithfully replicated to every disk in the array instantly. Backups are separate, versioned copies, ideally off-site.

Q9. Explain DMA and why it is needed.

DMA lets a device controller transfer a whole block between the device and memory without the CPU copying each word. The CPU programs the transfer and receives one interrupt at completion. Without DMA, a disk or network card moving gigabytes per second would consume the CPU entirely with interrupts and copying.

Q10. When is polling better than interrupts?

When the device responds so fast that the overhead of an interrupt (context save, handler dispatch) exceeds the time spent waiting, or when events arrive so frequently that interrupts would flood the CPU. Linux NAPI switches network cards to polling under load, and NVMe and io_uring offer polled modes.

Q11. What is the difference between buffering, caching and spooling?

A buffer holds data in transit between two parties to handle speed or size mismatches, possibly the only copy. A cache holds a duplicate of data stored elsewhere for faster repeated access. A spool queues whole jobs on disk for a device that can serve only one job at a time, such as a printer.

Q12. What is the difference between non-blocking and asynchronous I/O?

Non-blocking I/O returns immediately with EAGAIN if the operation cannot proceed; you learn when a descriptor is ready (for example with epoll) and then perform the read yourself. Asynchronous I/O submits the whole operation and later notifies you that it is complete, with data already in your buffer, as in io_uring or Windows IOCP.

Q13. Why is epoll more scalable than select?

select copies and scans every watched descriptor on every call and is limited to 1024 descriptors by default, so the cost is proportional to the total number of connections. epoll registers interest once and maintains a ready list in the kernel, so epoll_wait costs time proportional to the number of ready descriptors. With 10,000 mostly idle connections, that difference is huge.

Q14. What is the difference between level-triggered and edge-triggered epoll?

Level-triggered reports a descriptor as long as it remains ready, so leftover data will be reported again on the next call. Edge-triggered reports only when the state changes from not ready to ready, so you must read until EAGAIN or you may never be told about the remaining data. Edge-triggered reduces repeated notifications but is easier to get wrong.

Q15. What is a device driver and why are drivers a reliability risk?

A driver is kernel code that translates generic I/O requests into the commands a specific controller understands and handles its interrupts. Drivers run in kernel mode with full privileges, so a bug can corrupt kernel memory or crash the system. That is why some systems isolate drivers in user space or behind an IOMMU.

Key takeaways

• HDD access time = seek + rotational latency (half a revolution on average) + transfer; positioning dominates random I/O.
• On the shared example (head 50, toward higher, queue 82, 170, 43, 140, 24, 16, 190): FCFS 642, SSTF 208, SCAN 332, C-SCAN 391 (192 without return), LOOK 314, C-LOOK 341 (167 without jump).
• SSTF can starve; SCAN and LOOK bound waiting; C-SCAN and C-LOOK make waits uniform.
• SSDs remap writes through an FTL, garbage-collect erase blocks, level wear and need TRIM; seek-optimising scheduling barely helps them.
• RAID 0 = speed, RAID 1 = mirroring, RAID 5 = one parity (n - 1 capacity), RAID 6 = two parities (n - 2), RAID 10 = striped mirrors (n / 2); RAID is not backup.
• Polling wastes CPU on slow devices, interrupts cost per event, DMA moves whole blocks with one interrupt.
• Buffers hold data in transit, caches hold copies, spools queue whole jobs.
• Non-blocking means "tell me when ready", asynchronous means "tell me when done"; epoll scales with ready descriptors and io_uring uses shared submission and completion rings.

Next lesson

Continue with Linux internals.