Skip to content
Tutorials Center
My learning

Topics

Lesson 64 of 66 ยท Projects and Practice

Project: Disk Scheduling Benchmark

Build a disk scheduling benchmark in Python with seeded workloads and an online simulator, compare FCFS, SSTF, LOOK and C-LOOK on throughput, tail latency and starvation.

The disk scheduling lesson compared algorithms on one tiny batch of eight requests. Real disks face an endless stream of requests that arrive while the arm is busy, and what matters then is not only total head movement but also average response time, tail latency (the slowest few percent) and starvation. In this project you build a benchmark that measures all three on repeatable workloads, the way an OS engineer would before choosing a default scheduler.

The plan:

  1. A workload generator with a seed, so every run is repeatable.
  2. An online simulator: requests arrive at specific times, the scheduler picks the next one from whatever is pending, and the clock advances by the cost of the seek plus a fixed rotation and transfer overhead.
  3. Metrics: total arm travel, finish time, mean, 95th-percentile and worst response time.
  4. A starvation test.

Step 1: seeded workloads

Always seed the random number generator, so a result can be reproduced and discussed. Two workload shapes matter:

  • Uniform: every track equally likely (a busy multi-user file server).
  • Hot spot: most requests cluster around one region (a database with hot tables, or a log directory).
Python Step 1: a repeatable workload generator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each request is a pair (arrival time, track). Because the generator is seeded, comparing two schedulers on make_workload("uniform", 400, seed=11) means both see the identical sequence of requests.

Step 2: the online simulator and the benchmark

The simulator keeps a list of pending requests. When the disk is free it asks the policy "which of these next?", then advances the clock by seek distance x 1 + 3. A request's response time is its completion time minus its arrival time.

The four policies:

  • FCFS takes the oldest request.
  • SSTF takes the nearest request.
  • LOOK continues in the current direction to the nearest request ahead, and reverses only when nothing is ahead.
  • C-LOOK always moves upward; when nothing is above the head it jumps to the lowest pending track.
Python Step 2: benchmark four schedulers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the tables:

  • On the uniform workload, FCFS is overwhelmed. Each request costs about a 67-track seek on average, which is longer than the gap between arrivals, so the queue grows and responses reach thousands of time units. The three seek-aware policies keep up and cut arm travel by a third.
  • SSTF has the best average, but LOOK has the lower 95th-percentile and worst-case response. SSTF is greedy and sometimes leaves distant requests waiting; the elevator's sweep bounds the wait.
  • C-LOOK pays for its long return jump but treats all tracks alike.
  • On the hot spot workload the disk is lightly loaded and FCFS recovers, yet SSTF and LOOK still help. Under light load all schedulers look alike, so you only see big differences when a queue builds up.

Step 3: starvation test

Average numbers can hide unfairness. Build a worst-case scenario: a steady stream of requests near the middle of the disk (tracks 90 to 110), plus one request for track 190 arriving at time 8. How long does it wait under each policy?

Python Step 3: does the far request ever get served?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

FCFS serves the far request in its turn. SSTF ignores it for over a thousand time units, until the stream dries up. That is starvation. LOOK serves it as soon as the sweep has passed the busy region, because it is then the only request ahead. This is why mainstream systems use elevator-style or deadline-based schedulers rather than pure SSTF.

Extensions

  1. Aging SSTF. Subtract 0.1 from a request's distance for each time unit it has waited, then repeat the starvation test.
  2. Deadline scheduler. Serve by LOOK order, but if any request is older than 200 units, serve it first.
  3. SCAN and C-SCAN. Add the versions that go to the physical edge, and measure how much the extra travel costs.
  4. SSD model. Set the seek cost to zero and a constant 1-unit service time. Which scheduler wins now? (See disk structure for why.)
  5. Read/write mix. Make writes cost 2 more units and let reads jump ahead of writes (as Linux does), then measure write latency.
  6. Plot it. Collect response times and print a text histogram per policy.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why should a benchmark use a fixed random seed?

    Comparing policies is only fair if they face the same requests, and reproducibility lets others verify your numbers.
  2. 2. Why is the 95th-percentile response time reported along with the average?

    Users notice slow outliers. Tail latency exposes unfairness that the mean smooths over.
  3. 3. In the starvation test, why is the far request served late under SSTF?

    SSTF always picks the closest request, so the distant one waits as long as closer ones keep appearing.
  4. 4. Under a very light load, how do the schedulers compare?

    Scheduling needs a queue to choose from. With one request at a time every policy serves it immediately.

Summary

  • A disk scheduler should be judged on throughput, mean response, tail latency and starvation, using repeatable workloads and an online simulation.
  • Seek-aware policies (SSTF, LOOK, C-LOOK) beat FCFS dramatically when a queue builds up; light load hides the differences.
  • SSTF wins averages but can starve; LOOK-style sweeps bound the worst case; C-LOOK gives uniform treatment at the cost of long returns.
  • Aging and deadlines are the usual fixes for starvation.

Next: Project: A Tiny Shell with Pipes