A scheduler sorts every block request by logical block address because that reduced seek distance on a magnetic disk. The same policy is deployed on an NVMe SSD. Requests from one latency-sensitive process wait behind a long adjacent run, while the SSD’s independent internal channels remain underfilled. “Sequential is faster” was promoted from a device-specific observation to a universal rule.
Storage scheduling sits between workload intent and a device whose service function may be mechanical, solid-state, virtualized, or remote. A policy is defensible only when its cost model matches the medium and its objective includes more than aggregate throughput.
Media-aware scheduling contract. Request order must be justified by measured or specified device behavior, queue semantics, fairness boundaries, and durability constraints. Logical address proximity alone is not a universal service-time metric.
The block layer does not erase the medium
Applications and filesystems issue operations on logical byte or block ranges. The storage stack may merge, split, queue, prioritize, and dispatch them. A controller or device can reorder again, serve requests in parallel, cache writes, or translate logical addresses internally.
The observable latency of request can be decomposed as
The decomposition prevents one useful optimization—such as reducing seek—from being mistaken for the entire response time.
Retrieval — identify hidden reordering. A filesystem submits writes A then B, and the driver rings one queue doorbell. Name two lower layers that may still reorder work and the interface feature needed when A must become durable before B.
Reveal the diagnostic answerExpandCollapse
Controller firmware and the medium’s internal scheduler/translation layer may reorder. The host needs an ordering/durability mechanism defined by the device protocol, such as an ordered dependency, flush, or force-unit-access semantics as appropriate. Submission order alone is not a durability proof. Exact commands are protocol-specific and are outside the assessed filesystem-recovery scope.
Magnetic disks pay mechanical positioning cost
A simplified magnetic-disk access has
followed by transfer. Seek moves the actuator to the target track/cylinder; rotational latency waits for the desired sector to pass under the head. With rotation rate revolutions/minute and uniformly distributed angular position,
At 7,200 RPM, one revolution is 8.33 ms and average rotational latency under the uniform-angle model is 4.17 ms.
Worked trace: service-time estimate
Assume a magnetic disk with measured 8 ms seek for a particular distance, 7,200 RPM, sustained transfer 200 MB/s, no queueing, and no controller-cache hit. A 64 KiB request has
The estimate is
This is not a constant per-request law. Seek is nonlinear in distance, rotational position is not always uniform, adjacent sectors can stream, controller caches can satisfy a request, and zone geometry changes transfer rates.
Cylinder movement is a proxy, not time
Classical scheduling traces use total cylinder movement because nearby requests often reduce mechanical positioning. For initial head 53 and queue
98, 183, 37, 122, 14, 124, 65, 67
the supplied model produces:
| Policy | Service path | Movement |
|---|---|---|
| FCFS | 53→98→183→37→122→14→124→65→67 | 640 cylinders |
| SSTF | 53→65→67→37→14→98→122→124→183 | 236 cylinders |
| SCAN upward | 53→65→67→98→122→124→183→199→37→14 | 331 cylinders |
SSTF wins this movement total, but repeatedly arriving nearby requests can postpone a distant request indefinitely. SCAN trades some movement for directional progress. The model’s SCAN travels to cylinder 199 before reversing; LOOK would reverse at the final request in the direction, producing a different path.
Application — expose starvation. The head starts at 50. A request at 190 waits while one request arrives every service interval, alternating between cylinders 49 and 51. Trace the first six SSTF choices and state whether any finite waiting bound follows from the policy.
Reveal the adversarial traceExpandCollapse
At each choice, a newly arrived request one cylinder away is closer than 190, so SSTF can alternate around 50 and postpone 190 for all six choices—and indefinitely if arrivals continue. No finite waiting bound follows from pure nearest-request selection. Adding an age/deadline rule changes the policy and can bound postponement under stated dispatch assumptions.
Storage device characteristics and scheduling invariants
Evaluate each statement regarding magnetic hard drives, solid-state drives, and IO scheduling algorithms:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Experiment: compare movement and fairness
The simulator uses cylinders 0..199, a single magnetic head, a fixed request batch, and movement equal to absolute cylinder-distance sums. FCFS preserves listed arrival order. SSTF chooses the nearest pending cylinder, breaking equal distances by the workload’s current list order. SCAN moves upward, reaches cylinder 199 when lower requests remain, then reverses. It omits rotation, transfer length, deadlines, writes, caches, and new arrivals.
Prediction — choose an objective before a policy. On the mixed queue above, which policy has the least movement? Which policy gives the strongest service-order argument to the oldest request from the information provided?
Move the disk head under competing queue policies
Change the initial head position, request distribution, and policy. The path makes throughput improvements and starvation risk visible instead of reducing the choice to a slogan.
Head path: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183. This model isolates seek distance on a magnetic disk; SSDs have no mechanical head, and real storage stacks also merge requests, respect deadlines, and account for caches and device-internal scheduling.
Static state: SSTF starts at cylinder 53 and travels 236 cylinders. It minimizes the next seek greedily but can postpone distant requests indefinitely.
Transfer — change the medium. Reinterpret the same request numbers as SSD logical block addresses. Identify every visual quantity that loses physical meaning, then name three measurements that would replace cylinder movement in an SSD scheduler evaluation.
Reveal the media-model boundaryExpandCollapse
For the prediction, SSTF has the least movement on the fixed mixed batch, while FCFS gives the strongest argument about the oldest request because it preserves listed arrival order. After changing the medium, head position, path slope, cylinder distance, direction, and endpoint reversal lose their mechanical meaning. Logical adjacency may still help merging or sequential prefetch, but it does not reveal flash-channel placement or FTL physical location. Useful SSD measurements include throughput/IOPS, mean and tail completion latency, queue occupancy, device utilization, read/write mix, write amplification or bytes written, fairness, and per-queue/core contention.
FCFS, SSTF, SCAN, and deadlines optimize different contracts
| Policy | Useful property | Failure boundary | Repair direction |
|---|---|---|---|
| FCFS | transparent arrival order | long seeks and convoy effects | merge/batch without erasing age |
| SSTF | low next seek under cylinder proxy | starvation of distant requests | age or deadline override |
| SCAN | directional progress | endpoint travel; unequal waiting by position | LOOK/C-SCAN or deadlines |
| deadline hybrid | limits age while batching locality | tuning couples throughput and latency | measure read/write classes and tails |
A deadline scheduler can keep requests in both address order and age order. It dispatches batches by address for locality but checks whether an old request must be served. The guarantee is only as strong as the precise timer, batch, and lower-layer assumptions. Linux’s documented deadline scheduler, for example, exposes separate expiration and batch controls rather than claiming exact completion deadlines.
Worked policy decision: interactive reads and bulk writes
A magnetic drive receives 4 KiB interactive reads with a 20 ms start-service objective and 1 MiB sequential background writes. Pure FCFS lets a long write run delay reads. Pure read priority can starve writeback and eventually block the filesystem. A hybrid may:
- merge adjacent writes into bounded batches;
- dispatch reads preferentially;
- force any request whose age exceeds its class threshold;
- cap consecutive reads so dirty writeback progresses; and
- measure start-service and completion separately.
The design is incomplete without queue-depth and arrival assumptions. A deadline cannot be guaranteed if admitted work exceeds device capacity and no request can be rejected or degraded.
SSDs replace a head with translation and parallelism
NAND flash cannot overwrite a programmed page in place. A flash translation layer (FTL) maps host logical blocks to physical flash pages, writes updates out of place, and reclaims erase blocks through garbage collection. Thus consecutive logical addresses need not remain physically adjacent, and background firmware work can produce variable latency.
An NVMe interface exposes memory-based submission and completion queues and supports substantial parallelism. Host software can map queues to CPUs and keep multiple commands outstanding. The important scheduling dimensions shift toward:
- enough queue depth to expose device parallelism without unbounded waiting;
- avoiding one global software lock or queue bottleneck;
- read/write and latency-class isolation;
- merge/split overhead and transfer size;
- firmware garbage-collection tail latency;
- flush/order semantics; and
- fairness across processes, cgroups, or virtual machines.
Linux’s blk-mq documentation explicitly contrasts mechanical disks—where head-position ordering addressed random-access cost—with solid-state devices that have no mechanical parts and can process requests in parallel.
Counterexample: LBA sorting can reduce parallelism
Suppose SSD requests at LBAs 100–107 map internally across eight channels, while LBAs 108–115 happen to contend on one flash die after FTL remapping. A host policy that assumes the second run is “more sequential” has no evidence for physical service cost. Issuing enough independent work and observing completions may exploit parallelism better than serializing by LBA. The exact mapping is usually controller-private, so the claim must be measurement-driven.
Queue depth, throughput, and latency obey a conservation relation
For a stable observed system, Little’s law relates long-run average outstanding requests effective completion rate and average time in the system
At 100,000 completed operations/s and 400 µs mean end-to-end storage time,
requests are outstanding on average. A queue cap of 16 cannot coexist with both measured values in a stable closed domain; at least one of rate, latency, scope, or measurement is different. Little’s law does not say that setting queue depth to 40 will cause 100,000 IOPS. Service capacity and arrival behavior determine whether that operating point is reachable.
Mean latency does not protect the tail
Two devices can both average 400 µs while one completes every request near 400 µs and the other pauses during garbage collection. Report p50, p95/p99, maximum within a defined run, and the full workload conditions. A scheduler that improves mean throughput while multiplying p99 latency may violate an interactive-service objective.
Application — audit a benchmark. A report claims 150,000 IOPS at 600 µs mean latency with “queue depth 32.” Use Little’s law to identify the inconsistency and list two possible scope explanations.
Reveal the auditExpandCollapse
The two measured values imply average outstanding work 150,000 × 0.0006 = 90, not 32. Possible explanations include 32 queues each with more than one outstanding request, a per-thread queue-depth label while 90 requests exist system-wide, latency measured over a broader layer than the reported queue, or throughput and latency taken from different intervals. The result may be valid, but the term “queue depth 32” is underspecified.
Boundary cases that defeat one-number policies
Writes have ordering and durability semantics
A scheduler may reorder independent writes but must preserve barriers and dependencies expressed by upper layers and supported by the device. Completion to software can mean accepted, cached, or durable depending on the protocol and flags. A filesystem cannot infer power-loss durability from queue order alone.
Virtual disks conceal another scheduler
A guest sees logical blocks presented by a virtual device. The host may map them to a file, network store, SSD, or thin-provisioned volume. Guest cylinder optimization can fight host scheduling. The guest should rely on advertised features and measurement rather than inventing physical geometry.
Shingled and zoned media alter random-write rules
Some magnetic and solid-state devices expose zones with sequential-write constraints. They are not modeled as ordinary random-write disks. Naming zoned storage without teaching its command/state model would not establish mastery, so it remains outside scope.
Queue merging can violate latency isolation
Merging adjacent requests lowers per-command overhead, but waiting to form a large merge can delay a small urgent request. Merge windows need bounds tied to service objectives.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 5.2.1: Decomposing Hard Disk Drive Access Latency and Service Time
A magnetic disk operates with the following parameters:
- Rotational speed: 10,000 RPM.
- Average seek time:
- Sustained media transfer rate:
- Controller and bus overhead:
- Calculate the rotational period and the expected rotational latency assuming uniform angular arrival.
- Calculate the transfer time for a 64 KiB block request.
- Compute the total expected service time for an isolated random 64 KiB read request.
HintExpandCollapse
One revolution at 10,000 RPM is 60 / 10000 seconds. Expected rotational delay is half a revolution.
Worked solutionExpandCollapse
- Rotational latency: The duration of one complete revolution is: Assuming uniform angular position of the desired sector upon head arrival at the cylinder:
- Transfer time:
- Total expected service time: Notice that mechanical positioning (seek + rotation = accounts for over 93% of the total access time.
Exercise 5.2.2: Comparing FCFS, SSTF, and SCAN Traversal Distances
A disk queue holds requests for cylinders in arrival order. The read/write head is currently positioned at cylinder 50 and moved from cylinder 40 (moving upward toward higher cylinders).
- Trace the head movement sequence and compute the total cylinder distance for First-Come First-Served (FCFS).
- Trace the sequence and total cylinder distance for Shortest Seek Time First (SSTF).
- Trace the sequence and total cylinder distance for SCAN (Elevator algorithm, reversing at cylinder 199).
HintExpandCollapse
SSTF selects the closest pending cylinder; SCAN sweeps upward to the boundary then sweeps downward.
Worked solutionExpandCollapse
-
FCFS: Path: Distances:
-
SSTF: Starting at 50, find nearest remaining:
- Nearest to 50 is 62
- Nearest to 62 is 64
- Nearest to 64 is 34 vs 95 which is 31).
- Nearest to 34 is 11
- Nearest to 11 is 95
- Nearest to 95 is 119
- Nearest to 119 is 123
- Nearest to 123 is 180 Path: Total distance:
-
SCAN (Elevator upward): Services all higher cylinders in ascending order up to 199, then reverses downward:
- Upward pass:
- Reversal downward: Total distance:
Exercise 5.2.3: Applying Little's Law to Storage Queue Depth Sizing
An enterprise NVMe SSD benchmark reports a sustained random read throughput of at an average request latency of
- Use Little’s law to calculate the average number of concurrent requests in flight across the host driver and SSD controller queues.
- If the host application uses a single submission queue with a maximum depth limit of 32, what is the maximum achievable throughput if latency remains at
- What happens to request latency if the application increases queue depth to 256 while device service capacity is capped at 500,000 IOPS?
HintExpandCollapse
L = lambda * W. If L is capped, lambda = L / W. If lambda is capped, W = L / lambda.
Worked solutionExpandCollapse
- Average in-flight requests
- Throughput at queue depth limit 32: With and mean service latency A queue depth of 32 leaves the SSD under-utilized, achieving only 40% of its rated 500,000 IOPS capacity.
- Queue inflation and latency explosion: Once device throughput saturates at raising queue depth to cannot increase throughput. Instead, requests accumulate in queues: Average latency increases by more than solely due to queueing delay (bufferbloat).
Exercise 5.2.4: Internal Flash Hierarchy and Multi-Queue NVMe Concurrency
Contrast the physical architecture of an NVMe solid-state drive with a magnetic hard drive. Explain why traditional single-queue elevator schedulers degrade SSD performance, whereas NVMe multi-queue (blk-mq) architectures optimize it.
HintExpandCollapse
Consider mechanical actuators versus multiple parallel flash channels, chips, dies, and planes.
Worked solutionExpandCollapse
- Physical contrast:
- Hard disk drives have a single mechanical arm with heads that can read or write only one cylinder/track at any given millisecond. Performance depends strictly on minimizing physical seek distance and rotational delay.
- Solid-state drives contain no moving parts. Flash storage is organized into multiple independent flash channels (e.g., 8–16 channels), each connected to multiple flash chips, dies, and planes. A modern SSD can execute 32–64 flash page reads simultaneously in parallel across independent dies.
- Why elevator scheduling degrades SSDs: Sorting block requests by LBA in an elevator queue serializes requests into a single bottlenecked thread, pays CPU lock contention overhead, and suppresses the queue depth needed to keep multiple internal flash channels active simultaneously. Furthermore, logical block addresses do not correspond to physical flash die locations due to Flash Translation Layer (FTL) wear-leveling mappings.
- NVMe Multi-Queue (blk-mq) architecture: NVMe provides up to 64,000 separate submission/completion queues, each supporting 64,000 commands. By dedicating per-CPU-core queues that bypass cross-core lock synchronization, the OS dispatches deep concurrent streams of requests directly to controller hardware, maximizing internal flash die parallelism.
Exercise 5.2.5: Proving Write Ordering Failures Under Reordered Storage Caches
A database system appends a transaction record to block and then updates user balance in block
- Prove that if the drive controller possesses a volatile write cache and reorders writes, a power failure can produce unrecoverable database corruption unless an explicit cache flush or FUA command is issued.
- Contrast the semantics of
REQ_PREFLUSHandREQ_FUAin modern operating system block layers.
HintExpandCollapse
Show an interleaving where data reaches stable flash before log data is persisted.
Worked solutionExpandCollapse
-
Proof of corruption under cache reordering:
- The database relies on the Write-Ahead Logging (WAL) invariant:
- The operating system submits followed by
- The disk controller acknowledges both writes immediately upon placing them into its volatile write-back DRAM cache.
- The disk controller firmware’s internal scheduler writes to persistent magnetic platters or NAND flash first, because is closer to the current head or open flash block.
- Before is drained from the volatile cache, a power failure occurs.
- Upon recovery, contains the committed transaction modifications, but has vanished. The recovery engine cannot undo or redo the transaction, leaving database state permanently inconsistent. Hence, software submission order alone is insufficient; explicit hardware barriers are strictly required.
-
PREFLUSH versus FUA semantics:
REQ_PREFLUSH: Instructs the storage controller to synchronously flush all dirty blocks currently resident in its volatile write-back cache to non-volatile media before executing the current command.REQ_FUA(Force Unit Access): Instructs the controller that the specific I/O block carried by this command must be written directly to persistent non-volatile media before completing and returning success to the host, bypassing or write-through flushing the volatile cache for this request.
References & Further Reading
- Linux kernel: Multi-Queue Block I/O Queueing Mechanism
- Linux kernel: Deadline I/O scheduler tunables
- NVM Express Base Specification landing page and current ratified revision
- NVM Express Base Specification, Revision 2.3 (archived primary specification)
- H. Kim et al., “BPLRU: A Buffer Management Scheme for Improving Random Writes in Flash Storage” (FAST 2008)
- Seagate Savvio 15K.2 SAS Product Manual, seek and access-time definitions
- John D. C. Little, “A Proof for the Queuing Formula: L = λW” (1961)