Disk Scheduling

01 Introduction

Lesson 11.1 presented the hard disk's geometry and showed that a random read's cost is dominated by the seek and the rotational delay: the transfer itself is a tiny fraction of the access time, and the mechanical delays account for over 95% of the cost. Lesson 11.4 presented the device driver and its interface with the block layer's request queue. This lesson presents the layer between them: the disk scheduler (also called the I/O scheduler), which decides the order in which the queued requests are dispatched to the device.

The scheduling decision is one of the operating system's most consequential performance decisions. A hard disk's throughput depends on the order of the requests: a sequence of requests that are sorted by block address and issued together — so the heads move in a single sweep across the platters — is far faster than the same requests issued in random order, where the heads move back and forth. The difference can be an order of magnitude: a disk that delivers 200 IOPS with random requests can deliver 2,000 IOPS with sorted ones. The scheduler's job is to find the order that maximizes the throughput while preserving the fairness and the latency that the applications expect.

The scheduling problem has a long history. The classical algorithms — FCFS, SSTF, SCAN, C-SCAN, LOOK, and C-LOOK — were developed for the hard disks of the 1970s and 1980s, and their names are still used. The modern schedulers — mq-deadline, BFQ, Kyber, and none — are designed for the multi-queue block layer and for the modern devices: the solid-state drives whose access time is nearly uniform, the NVMe devices whose parallelism is enormous, and the virtual machines whose I/O is layered. The modern schedulers must balance the throughput (which the hard disks reward with sorted requests), the latency (which the interactive applications require), and the fairness (which the multi-tenant systems demand).

This lesson presents disk scheduling. It defines the scheduling problem and the performance measures that the schedulers optimize. It presents the hard disk's performance characteristics and the seek-time bottleneck that shapes the classical algorithms. It presents the classical algorithms one at a time, with their trade-offs and their pathologies. It presents the modern Linux schedulers and the multi-queue block layer's design, and it presents the solid-state drives' different characteristics and the schedulers' adaptation to them. It presents the I/O priority and the cgroup controllers that the multi-tenant systems use, and it closes with the scheduling's effect on the system's throughput and latency and the tuning that the administrator can perform.

02 Learning objectives

This lesson contributes to U11.5 and U11.6, and to course learning outcomes CLO1, CLO5, and CLO6.

03 Required reading

• Operating System Concepts — Chapter 11, Mass-Storage Structure, Section 11.2, Disk Scheduling. The standard treatment of the classical algorithms, with the classical examples and the comparison of the algorithms' performance.
• OSTEP — Chapter 37, Hard Disk Drives, and Chapter 38, Redundant Arrays of Inexpensive Disks (RAIDs). OSTEP's treatment of the disk's geometry and its performance is the basis for the scheduling problem, and its discussion of the disk's scheduling is the basis for the classical algorithms' analysis.
• Tanenbaum & Bos — Modern Operating Systems, Chapter 5, Section 5.4, Disks. A complementary treatment that develops the disk's hardware and the scheduling algorithms from first principles.
• Love, R. — Linux Kernel Development, 3rd ed., Chapter 16, The Block I/O Layer. The Linux kernel's block layer: the request queue, the elevator algorithms, and the multi-queue design.
• Bovet, D. P., & Cesati, M. — Understanding the Linux Kernel, 3rd ed. O'Reilly, 2005. Chapter 14, Block Device Drivers. The classical block layer's structures and its elevator algorithms.
• Axboe, J. — Linux Block IO: Introducing Multi-queue SSD Access on Multi-core Systems. Proceedings of the 6th International Systems and Storage Conference (SYSTOR), 2013. The paper that introduced the multi-queue block layer and its schedulers.
• Valente, P., & Checconi, F. — High Throughput Disk Scheduling with Fair Bandwidth Distribution. IEEE Transactions on Computers, 2010. The paper that describes the BFQ scheduler's design and its fairness guarantees.
• Linux man pages: man 1 iostat, man 1 iotop, man 1 ionice, man 1 fio, man 5 proc (for /proc/diskstats), man 2 ioprio_set, man 5 cgroups (for the blkio controller), man 8 blkdiscard, man 1 lsblk, man 8 tune2fs.

04 Core content

4.1 The disk scheduling problem

The disk scheduling problem is the problem of ordering the pending I/O requests to optimize the device's performance. The block layer maintains a queue of requests (Lesson 11.4), and the scheduler decides which request the device should serve next. The decision is made for every request, and its cumulative effect determines the device's throughput and the requests' latency.

The problem's importance comes from the hard disk's performance characteristics. A hard disk's access time has three components:

• The seek time is the time to move the heads to the correct cylinder. It is a few milliseconds on a modern disk, and it is the largest component for a random access.
• The rotational delay is the time for the platter's rotation to bring the correct sector under the head. It averages half a rotation — about 4.2 milliseconds at 7,200 RPM.
• The transfer time is the time to read or write the data. It is a few microseconds per sector at the disk's sequential bandwidth, and it is a tiny fraction of the access time.

The seek and the rotational delay are mechanical, and they dominate the access time. The seek's duration depends on the distance between the current cylinder and the target cylinder: a short seek (a few cylinders) takes a fraction of a millisecond, while a long seek (across the disk) takes several milliseconds. The observation is the scheduling problem's basis: if the requests are ordered so that the heads move in a single sweep — each request's target cylinder is close to the previous request's — the total seek distance is minimized, and the throughput is maximized.

The problem's objective is therefore to order the requests so that the head's movement is minimized. The objective has three competing components:

• The throughput. The number of requests the device serves per second. The throughput is maximized by minimizing the total head movement, which is achieved by sorting the requests by block address.
• The latency. The time an individual request waits before it is served. The latency is minimized by serving the requests in the order they arrive, which conflicts with the sorting.
• The fairness. The requests' distribution across the applications and the devices' regions. The fairness is violated when a request waits indefinitely because the scheduler always prefers the requests near the head's current position.

The three components conflict: a scheduler that maximizes the throughput (by sorting) increases the latency (the far requests wait), and a scheduler that minimizes the latency (by serving in arrival order) reduces the throughput. The scheduler's design is the balance it strikes, and the balance is the source of the classical algorithms' differences and the modern schedulers' variety.

4.2 The classical algorithms

The classical algorithms were developed for the hard disks of the 1970s and 1980s, and their names are still used. They differ in how they use the head's current position to order the requests:

FCFS (First Come, First Served)

The requests are served in the order they arrive. FCFS is the simplest algorithm, and its fairness is perfect (no request can starve). Its throughput is the worst of the classical algorithms, because the heads move back and forth across the disk: if the queue is [98, 183, 37, 122, 14, 124, 65, 67] and the head is at 53, the head moves 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67, a total of 640 cylinders. FCFS is appropriate for the devices whose access time is nearly uniform (the solid-state drives) or for the workloads whose requests are already sorted.

SSTF (Shortest Seek Time First)

The request whose cylinder is closest to the head's current position is served first. SSTF is the disk's counterpart of the CPU's shortest-job-first (SJF) algorithm, and its throughput is better than FCFS's: for the same queue, the head moves 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183, a total of 236 cylinders — less than half of FCFS's. SSTF's disadvantage is its fairness: the requests whose cylinders are far from the head's position may starve, because the scheduler always prefers the closer requests. In a system with a steady stream of requests near the head's position, the far requests wait indefinitely. SSTF is the classical example of the throughput-versus-fairness trade-off.

SCAN (the elevator algorithm)

The head moves in one direction (from the disk's inner edge to its outer edge, or vice versa), serving the requests it passes, until it reaches the disk's edge; then it reverses direction and serves the requests on the way back. SCAN's name comes from the head's sweeping motion, and its alternative name (the elevator algorithm) comes from the analogy with an elevator that serves the floors in one direction before reversing. SCAN's throughput is better than SSTF's in the long run, because the head never backtracks: each request is served at most one sweep after it arrives. SCAN's disadvantage is the requests near the disk's edges: they wait for almost two full sweeps if they arrive just after the head passes them.

C-SCAN (Circular SCAN)

The head moves in one direction only, serving the requests it passes, and when it reaches the disk's edge, it returns to the opposite edge without serving any requests on the return. The return's requests wait for the next sweep, so the waiting time is more uniform than SCAN's: a request waits at most one sweep, regardless of its position. C-SCAN's fairness is better than SCAN's, and its throughput is slightly lower (the return's sweep is wasted), but the trade-off is usually worth it. C-SCAN is the standard algorithm for the systems whose latency matters.

LOOK and C-LOOK

The variants of SCAN and C-SCAN that reverse direction (or return to the opposite edge) at the last request in the current direction, rather than at the disk's physical edge. The head does not travel to the disk's edge if no request requires it, so the wasted movement is eliminated. LOOK and C-LOOK are the practical algorithms: the modern systems use them (or their variants) rather than the classical SCAN and C-SCAN.

The classical algorithms' differences are summarized in the following table. The table's "total movement" column is the head's total travel for the classical example (the queue [98, 183, 37, 122, 14, 124, 65, 67] with the head at 53), and the "fairness" column describes the algorithm's fairness properties.

The table's numbers make the algorithms' trade-offs concrete. FCFS's movement is the worst; SSTF's is the best of the simple algorithms, but its fairness is poor. The SCAN family's movement is close to SSTF's, and its fairness is better: the sweep's bounded length means that every request is served within a bounded time. The SCAN family is therefore the classical algorithms' practical choice, and the modern schedulers' designs are its descendants.

4.3 The SCAN family's trade-offs and pathologies

The SCAN family is the classical algorithms' practical choice, but its design has several trade-offs and pathologies that the modern schedulers must address:

• The far requests' wait. A request that arrives just after the head passes its cylinder waits for almost a full sweep. On a large disk with a long sweep, the wait can be tens of milliseconds, and a latency-sensitive application (a database, an interactive program) notices.
• The arm's stickiness. If the request stream is concentrated in a narrow region of the disk, the head tends to stay in that region, and the requests elsewhere wait longer. The stickiness is the reason the classical algorithms are supplemented with the ageing mechanisms: a request's priority increases with its waiting time, so the far requests eventually become the head's target.
• The write's delay. The classical algorithms treat the reads and the writes symmetrically, but the writes are usually asynchronous (the application's write returns as soon as the data is in the page cache, and the actual write can be delayed) and the reads are usually synchronous (the application's read blocks until the data is available). A scheduler that delays the reads to batch the writes improves the throughput but increases the read latency, and the balance is the modern schedulers' central trade-off.
• The read-ahead's interference. The kernel's read-ahead (Lesson 10.4's page cache) submits the read-ahead requests before the application asks for them, so the requests arrive in bursts. The bursts' interference with the application's requests is a scheduling problem: the read-ahead's requests occupy the device while the application waits.
• The multiple devices' interference. A system with several devices (a hard disk and an SSD, or several hard disks) must schedule the requests across the devices, not just within one. The scheduling's cross-device aspects (the workload's placement, the devices' utilization) are the modern systems' additional concern.

The modern schedulers address these trade-offs with a combination of mechanisms: the deadline mechanism (each request has a deadline, and the scheduler serves the requests in the deadline order when the deadlines approach), the fairness mechanism (each application or cgroup has a weight, and the scheduler allocates the device's bandwidth proportionally), and the parallelism mechanism (the requests are submitted to the device's multiple queues concurrently, so the device's parallelism is exploited). The mechanisms' balance is the modern schedulers' design, and it is the subject of the next section.

4.4 The multi-queue block layer

The classical block layer had a single request queue per device, and its elevator algorithm ran under a single lock. The design was a bottleneck on the modern devices: the lock serialized the submissions from the multiple processor cores, and the single queue could not exploit the device's parallelism. The multi-queue block layer (introduced in Linux 3.13) replaced the design with a two-level structure:

• The software queues. One queue per processor core (or per submission context). The queue is lockless (or uses a per-queue lock), so the submissions from different cores do not contend. The software queue is where the scheduler's algorithm runs: the requests are sorted, merged, and ordered per core.
• The hardware queues. One queue per device's hardware queue (the NVMe's queue pair, the SCSI controller's queue, the AHCI controller's command slot). The hardware queue is what the driver's queue_rq method consumes. The software queues are mapped to the hardware queues, typically one per core, so the submissions and the completions do not contend.

The multi-queue block layer's design is the reason the modern devices achieve their throughput: the submissions from different cores go to different software queues, the software queues' algorithms run in parallel, and the hardware queues receive the requests without contention. The design's complexity is the scheduler's: the algorithm must run per software queue (so it cannot see the whole request stream), and the fairness must be enforced across the queues (so the scheduler must coordinate the queues' decisions). The modern schedulers' designs reflect the constraint: they use the per-queue sorting for the throughput and the cross-queue mechanisms for the fairness.

4.5 The modern Linux schedulers

The Linux kernel provides four schedulers for the multi-queue block layer, each with its own design and its own target workload:

mq-deadline

The multi-queue version of the classical deadline scheduler. The scheduler maintains three queues: a sorted queue (the requests ordered by their block address, for the throughput), a read deadline queue (the read requests ordered by their deadlines, for the latency), and a write deadline queue (the write requests ordered by their deadlines, for the fairness). The scheduler dispatches the requests from the sorted queue normally, but when a request's deadline approaches (the default is 500 ms for the reads and 5 s for the writes), it dispatches the request from the deadline queue, so the request's latency is bounded. The design balances the throughput (the sorted queue) and the latency (the deadlines), and it is the kernel's default scheduler for the general-purpose workloads.

BFQ (Budget Fair Queueing)

A scheduler that provides the strong fairness guarantees of the budget fair queueing algorithm. Each application (or cgroup) has a weight and a budget (the number of sectors it may transfer before the scheduler switches to another application), and the scheduler allocates the device's bandwidth proportionally to the weights. BFQ's fairness is its principal advantage: a low-priority application cannot starve a high-priority one, and the interactive applications' latency is bounded even under a heavy load. BFQ's disadvantage is its overhead: the scheduler's per-request bookkeeping is more expensive than mq-deadline's, and its throughput on the high-end devices is slightly lower. BFQ is the kernel's recommended scheduler for the desktop and the interactive workloads, where the fairness and the latency matter more than the raw throughput.

Kyber

A scheduler designed for the high-performance devices (the NVMe SSDs). Kyber's design is lightweight: it maintains a small number of queues per operation type (the reads and the writes), and it throttles the submissions when the device's queue's depth exceeds a target (the latency target). The throttling keeps the device's queue's depth in the range where the device's latency is bounded, so the scheduler's overhead is minimal and the device's latency is controlled. Kyber is the kernel's recommended scheduler for the high-performance SSDs, where the seek distance is irrelevant and the queue's depth is the latency's determinant.

none (noop)

The scheduler that performs no scheduling: the requests are dispatched to the device in the order they arrive (the multi-queue block layer's software queues' order, with the merging). The scheduler's overhead is zero, and its throughput is the device's raw throughput. The scheduler is the kernel's default for the devices whose access time is nearly uniform (the SSDs, the NVMe devices, the virtual devices), where the sorting's benefit is small and the scheduling's overhead is a waste. The scheduler's name reflects its design: the kernel's default for the modern devices, where the device's controller does the scheduling and the kernel's role is limited.

The four schedulers' differences are summarized in the following table:

The schedulers' selection is a per-device setting: the administrator writes the scheduler's name to /sys/block/<device>/queue/scheduler, or sets it through the kernel's boot parameters. The default is set by the distribution, and the modern distributions use mq-deadline for the hard disks and none or kyber for the SSDs. The selection can be changed at runtime, and the administrator can use it to tune the system for the workload.

4.6 Solid-state drives and the scheduling problem

The solid-state drive's characteristics change the scheduling problem's nature. An SSD has no heads to seek and no platter to rotate: its access time is dominated by the flash memory's read latency (tens of microseconds) and the controller's overhead, and the difference between the sequential and the random access is far smaller than a hard disk's. The sorting's benefit is therefore small: an SSD's random read is nearly as fast as its sequential read, so the scheduler's reordering does not improve the throughput significantly.

The SSD's scheduling problem is different:

• The parallelism. An SSD contains many flash chips, and the controller can access several of them in parallel. The device's throughput is maximized when several requests are in flight at once, so the scheduler's job is to keep the device's queue's depth high (the queue depth). The high-performance SSDs (the NVMe devices) have thousands of queue slots, and the scheduler's role is to fill them and to keep the completions flowing.
• The write amplification. The SSD's flash memory cannot be overwritten in place, so the controller's flash translation layer performs the read-modify-erase-write cycles. The write amplification depends on the write pattern: the sequential and the aligned writes cause less amplification than the random and the unaligned writes. The scheduler's job is to submit the writes in a pattern that minimizes the amplification, and the modern schedulers' designs (the merging, the batching) are shaped by it.
• The garbage collection. The SSD's controller must periodically reclaim the invalidated blocks (the garbage collection), and the reclamation competes with the applications' I/O. The scheduler's job is to pace the submissions so the garbage collection does not starve the applications, and the modern schedulers' throttling (Kyber's latency target) is designed for it.
• The latency's distribution. The SSD's average latency is low, but its tail latency (the 99th percentile, the 99.9th percentile) can be much higher, because of the garbage collection, the write amplification, and the controller's internal scheduling. The scheduler's job is to bound the tail latency, and the modern schedulers' designs (the deadlines, the throttling) are shaped by it.

The observation is the reason the modern Linux distributions use none or kyber for the SSDs: the sorting's benefit is small, and the scheduling's overhead is a waste. The device's controller does the scheduling internally (the flash translation layer's parallelism, the garbage collection's pacing), and the kernel's role is limited to the submission and the completion. The design is the modern storage stack's central trend: the device's controller is becoming a computer in its own right, and the kernel's scheduling's role is shrinking.

4.7 I/O priority and the cgroup controllers

The multi-tenant systems (the servers with several virtual machines, the containers on a shared host) need to allocate the devices' bandwidth among the tenants. The Linux kernel provides two mechanisms:

• The I/O priority. Each process has an I/O priority (a class and a level), which the ionice command sets and the ioprio_set system call sets programmatically. The classes are the real-time (the highest priority, for the processes that must not be delayed), the best-effort (the default, with the levels 0–7), and the idle (the lowest priority, for the processes that should yield to all others). The BFQ and mq-deadline schedulers honour the priorities: the higher-priority processes' requests are dispatched first, and the lower- priority processes' requests wait.
• The cgroup blkio controller. The controller lets the administrator group the processes (into the cgroups) and allocate the devices' bandwidth among the groups. The allocation is expressed in the weights (the proportional shares) or in the limits (the maximum bandwidth, the maximum IOPS). The controller's design is the multi-tenant systems' basis: a virtual machine's or a container's I/O is limited by its cgroup's allocation, and the other tenants' I/O is protected.

The two mechanisms' design reflects the modern systems' requirements. The I/O priority is the per-process mechanism: it is simple, and it is sufficient for the systems with a few processes and a well-understood priority structure. The cgroup controller is the group mechanism: it is more complex, and it is necessary for the systems with many tenants and a dynamic workload. The two mechanisms' combination (the priority within the cgroup, the weight across the cgroups) is the modern systems' standard, and the administrators of the multi-tenant systems must configure both.

4.8 The scheduling's effect on the system's performance

The scheduler's choice's effect on the system's performance is significant, and it is visible in the system's metrics:

• The throughput. The device's throughput (the IOPS and the bandwidth) is the scheduler's primary metric. On a hard disk, the sorted scheduling can improve the throughput by an order of magnitude for the random workloads; on an SSD, the difference is small, and the scheduler's overhead is the determinant.
• The latency. The requests' latency (the average and the tail) is the scheduler's fairness metric. The deadline schedulers (mq-deadline, BFQ) bound the latency; the sorting schedulers (the classical SCAN family) increase the latency for the far requests; the no-op scheduler's latency is the device's raw latency.
• The fairness. The tenants' bandwidth allocation is the scheduler's multi-tenant metric. The BFQ and the cgroup controller's design provides the strong fairness; the mq-deadline's design provides the weaker fairness (the deadlines' bound); the no-op scheduler provides the weakest fairness (the arrival order's accidental fairness).
• The CPU overhead. The scheduler's own CPU cost is the system's overhead metric. The BFQ's design is the most expensive (the per-request bookkeeping), the mq-deadline's is moderate, the Kyber's is low, and the no-op scheduler's is zero. On a high-throughput device (an NVMe SSD at millions of IOPS), the scheduler's overhead can consume a significant fraction of the processor's time, and the no-op scheduler is the right choice.

The metrics' balance is the scheduler's design decision, and it is the administrator's tuning decision. The administrator can select the scheduler per device, set its parameters (the deadlines, the weights, the latency targets), and observe the metrics (through iostat, iotop, and the /proc/diskstats interface). The tuning is the system administrator's ongoing task: the workload changes, the devices change, and the scheduler's settings must be adjusted to the new conditions.

4.9 Common misconceptions

05 Worked example

The following example traces the classical algorithms through the standard queue, computes their total head movement and their average latency, compares the modern schedulers' behaviour, and shows the scheduling's effect on a live system's metrics.

Head: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67

Movement:
  |98  - 53|  =  45
  |183 - 98|  =  85
  |37  - 183| = 146
  |122 - 37|  =  85
  |14  - 122| = 108
  |124 - 14|  = 110
  |65  - 124| =  59
  |67  - 65|  =   2
  Total       = 640 cylinders

Head at 53. The requests are [98, 183, 37, 122, 14,
124, 65, 67]. The nearest to 53 is 65 (distance 12).

Head: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183

Movement:
  |65  - 53|  =  12
  |67  - 65|  =   2
  |37  - 67|  =  30
  |14  - 37|  =  23
  |98  - 14|  =  84
  |122 - 98|  =  24
  |124 - 122| =   2
  |183 - 124| =  59
  Total       = 236 cylinders

Sweep up: 53 → 65 → 67 → 98 → 122 → 124 → 183
  (the requests at 65, 67, 98, 122, 124, 183)
Reverse:  183 → 37 → 14
  (the requests at 37, 14)

Movement:
  |65  - 53|  =  12
  |67  - 65|  =   2
  |98  - 67|  =  31
  |122 - 98|  =  24
  |124 - 122| =   2
  |183 - 124| =  59
  |37  - 183| = 146
  |14  - 37|  =  23
  Total       = 299 cylinders

# Show the device's current scheduler
cat /sys/block/sda/queue/scheduler

# Show the device's statistics
iostat -x 1 3

# The output's columns include:
#   r/s, w/s    — the read and write requests per second
#   rkB/s, wkB/s — the read and write bandwidth
#   await       — the average latency (ms)
#   r_await, w_await — the read and write latencies
#   aqu-sz      — the average queue depth
#   %util       — the device's utilization

# Change the scheduler and re-measure
echo mq-deadline | sudo tee /sys/block/sda/queue/scheduler
iostat -x 1 3

echo none | sudo tee /sys/block/sda/queue/scheduler
iostat -x 1 3

# Compare the latency and the throughput across the schedulers.

# Measure the throughput at different queue depths
# (if fio is available)
for qd in 1 2 4 8 16 32 64 128; do
    echo "=== queue depth $qd ==="
    sudo fio --name=test --filename=/tmp/fio-qd.bin \
        --size=500M --rw=randread --bs=4k --iodepth=$qd \
        --ioengine=libaio --direct=1 --runtime=3 --time_based \
        2>/dev/null | grep -E 'IOPS|bw'
done

# Clean up
rm /tmp/fio-qd.bin 2>/dev/null

06 Interactive activity

07 Knowledge check

08 Unit discussion

09 Practice exercise

10 Summary

• The disk scheduling problem is the problem of ordering the pending I/O requests to optimize the device's performance. The order matters because of the hard disk's mechanical delays — the seek and the rotational delay — which dominate the access time. The scheduler must balance the throughput, the latency, and the fairness, and the three objectives conflict.
• The classical algorithms are FCFS (arrival order; perfect fairness, worst throughput), SSTF (nearest first; good throughput, poor fairness), SCAN (the elevator algorithm; a sweep in one direction, then a reverse), C-SCAN (a sweep in one direction, then a return without serving), LOOK (SCAN to the last request), and C-LOOK (C-SCAN to the last request). The SCAN family is the practical choice: its movement is close to SSTF's, and its fairness is better.
• The SCAN family's trade-offs are the far requests' wait, the arm's stickiness, the writes' delay, the read-ahead's interference, and the multiple devices' interference. The modern schedulers address them with the deadlines, the fairness, and the parallelism.
• The multi-queue block layer (introduced in Linux 3.13) replaced the single queue with a two-level structure: the software queues (one per processor core, lockless) and the hardware queues (one per device's hardware queue). The design is the reason the modern devices achieve their throughput.
• The modern Linux schedulers are mq-deadline (a sorted queue plus the deadline queues; the general-purpose choice), BFQ (budget fair queueing; the strong fairness, the desktop and the multi-tenant choice), Kyber (the queue-depth throttling; the high-performance SSDs), and none (the arrival order, no scheduling; the fast SSDs and the virtual devices). The choice is a per-device setting, and the modern distributions use mq-deadline for the hard disks and none or kyber for the SSDs.
• The solid-state drive's characteristics change the scheduling problem: the sorting's benefit is small, and the parallelism, the write amplification, the garbage collection, and the latency's distribution are the new concerns. The no-op and Kyber schedulers are the SSD-appropriate choices.
• The I/O priority (the per-process mechanism, set by ionice) and the cgroup blkio controller (the group mechanism) allocate the devices' bandwidth among the processes and the groups. The two mechanisms are complementary, and their combination is the multi-tenant systems' standard.
• The scheduling's effect is visible in the system's metrics: the throughput, the latency, the fairness, and the scheduler's own CPU overhead. The administrator's tuning (the scheduler's selection, its parameters, the I/O priority, the cgroup's weights) is the balance among the metrics, and it must account for the device's characteristics and the workload's access pattern.

11 References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 11, Section 11.2.
• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 37 and 38. Available online at ostep.org.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 5, Section 5.4.
• Love, R. Linux Kernel Development, 3rd ed., Chapter 16, The Block I/O Layer.
• Bovet, D. P., & Cesati, M. Understanding the Linux Kernel, 3rd ed. O'Reilly, 2005. Chapter 14, Block Device Drivers.
• Axboe, J. Linux Block IO: Introducing Multi-queue SSD Access on Multi-core Systems. Proceedings of the 6th International Systems and Storage Conference (SYSTOR), 2013.
• Valente, P., & Checconi, F. High Throughput Disk Scheduling with Fair Bandwidth Distribution. IEEE Transactions on Computers, 2010.
• Linux man-pages: man 1 iostat, man 1 iotop, man 1 ionice, man 1 fio, man 5 proc, man 2 ioprio_set, man 5 cgroups, man 8 blkdiscard, man 1 lsblk.