CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 6 of 7 · 3 min read

Linux schedulers

Scheduling on a modern Linux machine

Think of a post office that has one sorting machine for letters. The sorting machine is the part that cares about the order. If every letter is handled in the same time, no sorting is needed and the clerk just passes them in. The analogy stops in one place: a flash disk still has a queue and some limits, and the OS still makes a few useful choices.

In plain words: Linux sends block requests through a scheduler that sits between the file system and the device driver. A scheduler can merge requests for neighbouring blocks into one larger request, put them into a better order, and give old requests a deadline so that none waits too long. The kernel offers none (no reordering), mq-deadline (read and write queues with deadlines), kyber (it controls the latency) and bfq (it gives each process a fair share). A drive may also reorder requests inside its own firmware.

A worked example. The test machine reports its choice in one file.

$ cat /sys/block/vda/queue/scheduler
none [mq-deadline] kyber bfq
$ cat /sys/block/vda/queue/nr_requests
256

The brackets mark the active scheduler: mq-deadline. The queue holds up to 256 requests. The choice of scheduler is a setting of the system. A server with fast flash disks often uses none, because reordering saves almost nothing and costs processor time.

The key lines. mq-deadline keeps requests in order of sector number (so neighbours can be merged and served in order) and also in order of arrival with a deadline. If the oldest request has expired, it is served first. This is a LOOK-like rule with a bound on the wait, which fits the starvation lesson of section 2.

Block I/O scheduler

A block I/O scheduler is the part of the kernel that orders and merges the read and write requests that go to a block device. It aims at throughput, at the latency of each request, or at fairness between processes, depending on the scheduler chosen.

Example: mq-deadline merges neighbouring requests, serves them in sector order, and promotes a request that has waited past its deadline.

Interview angle

A common question is "Which disk scheduling algorithm would you use?" A good answer names the device first: a LOOK variant with deadlines for a spinning disk, and almost no reordering for flash, with fairness (bfq) where several users share the device.

Check yourself: 1. What does merging two neighbouring requests save? 2. Why is a deadline needed in a scheduler that sorts by position? 3. Which line of /sys/block/<disk>/queue/ tells you whether the device spins?

Words you will meet

Word Meaning
Cylinder The set of tracks under all heads at one arm position.
FCFS Serve in arrival order.
SSTF Serve the nearest request first.
SCAN Sweep to the end, then back.
LOOK Sweep to the farthest request, then back.
Starvation Waiting without bound.

Quick notes

  • The order of waiting requests decides the arm movement.
  • FCFS is fair and costly. SSTF is cheap and can starve a far request.
  • SCAN sweeps the whole disk and reverses. C-SCAN sweeps one way and returns without serving.
  • LOOK and C-LOOK turn at the last request and never move farther than SCAN and C-SCAN.
  • Linux offers none, mq-deadline, kyber and bfq. The active one is shown in brackets.
  • On flash disks, position-based sorting adds little.