Disk Scheduling Algorithms | Interview Guide

Disk Scheduling Algorithms

Optimizing Disk I/O for Faster and Fairer Performance

1500+ Words | 10 MCQs | Interview Ready

This guide explains disk scheduling algorithms for interviews. Learn how operating systems decide request order, minimize seek time, and balance throughput, fairness, and response time.

"Disk scheduling is the strategy the operating system uses to choose the order in which disk I/O requests are serviced, improving performance and fairness." Use this definition to start your answer confidently.

What Is Disk Scheduling?

Disk scheduling determines the sequence in which pending I/O requests are granted access to the disk. Since disk heads must move across tracks, the order of service significantly impacts seek time, latency, and overall throughput.

In interviews, explain that disk scheduling is crucial for mechanical disks and also relevant in systems where performance, fairness, and workload patterns matter.

The main goal is to minimize head movement while avoiding starvation and providing reasonable response times for all requests.

Disk Scheduling Objectives

Minimize seek time: reduce head movement between requested tracks.
Maximize throughput: service as many requests as possible quickly.
Ensure fairness: avoid starving requests by letting all requests eventually run.
Reduce response time: keep average wait time low for users and processes.

Important Disk Scheduling Terms

Track/Cylinder: concentric circles on a platter or a collection of tracks under the same head position.
Seek time: the time it takes for the disk head to move to the requested track.
Head movement: the total travel distance of the disk head between requests.
Request queue: the pending list of disk I/O requests waiting to be serviced.

Why Disk Scheduling Matters in Interviews

Disk scheduling is a classic operating system topic that demonstrates your understanding of I/O management, performance trade-offs, and scheduling policies. It is a strong area to show both theory and practical system-level thinking.

Use the example of a disk with many pending requests to show how different algorithms affect average travel distance and response times.

Common Algorithms

FCFS (First Come, First Served)
SSTF (Shortest Seek Time First)
SCAN (Elevator Algorithm)
C-SCAN (Circular SCAN)
LOOK
C-LOOK
N-SCAN
F-SCAN

When to Use Which Algorithm

FCFS: simple systems or low load scenarios.
SSTF: best when starvation can be minimized and response time is critical.
SCAN/LOOK: general-purpose systems with balanced loads.
C-SCAN/C-LOOK: high-load systems needing uniform wait time.
N-SCAN/F-SCAN: real-time systems and workloads with bursty arrivals.

Understanding FCFS

FCFS (First Come, First Served) services requests in the order they arrive. It is easy to implement and fair in the sense that each request is eventually served, but it can result in excessive seek time if requests jump back and forth across the disk.

A typical example: if requests arrive in the order 53, 98, 183, 37, 122, 14, 124, 65, 67, the head travels exactly through each request sequentially, which may cause a lot of wasted movement.

Understanding SSTF

SSTF (Shortest Seek Time First) selects the pending request closest to the current head position. This reduces head movement and often improves response time compared to FCFS.

However, SSTF may cause starvation for requests that are far from the head if new closer requests keep arriving. In interviews, mention this trade-off clearly.

Understanding SCAN

SCAN is also known as the elevator algorithm. The disk head moves in one direction, servicing requests until it reaches the end, and then reverses direction to service requests in the opposite direction.

SCAN provides better fairness and throughput than SSTF in many workloads because it services requests in a sweeping motion.

Understanding C-SCAN

C-SCAN (Circular SCAN) moves the head in one direction only. When it reaches the end, it jumps back to the beginning without servicing requests on the return trip.

This gives more uniform wait times across the disk because each request is serviced in one direction only.

Understanding LOOK

LOOK is similar to SCAN, but the head reverses direction at the last pending request rather than going all the way to the end of the disk. This reduces unnecessary travel.

For example, if the furthest pending request in the current direction is at track 98, the head reverses there instead of going to track 199.

Understanding C-LOOK

C-LOOK is a circular variant of LOOK. The head moves in one direction to the furthest request, then jumps back to the nearest request at the other end and continues.

It preserves uniformity while avoiding the wasted distance of a full disk traversal.

Understanding N-SCAN

N-SCAN divides the request queue into batches. While one batch is being serviced in SCAN order, newly arriving requests are collected in a second batch.

This limits the amount of reordering and provides more predictable behavior under heavy load.

Understanding F-SCAN

F-SCAN extends N-SCAN by using two queues: one active batch being serviced and one secondary batch collecting new arrivals. The active batch is processed without changes.

F-SCAN avoids the starvation and unpredictability that can occur when new requests continuously alter the service order.

Disk Scheduling Comparison

Algorithm	Avg. Seek Time	Throughput	Fairness	Starvation
FCFS	Poor	Low	Fair	Possible
SSTF	Best	High	Not Fair	Possible
SCAN	Good	High	Fair	No
C-SCAN	Good	High	Fair	No
LOOK	Better	High	Fair	No
C-LOOK	Better	High	Fair	No
N-SCAN	Good	High	Fair	No
F-SCAN	Good	High	Fair	No

When to Use Each Algorithm

The best disk scheduling algorithm depends on workload characteristics. For simple systems and low load, FCFS is acceptable. When performance matters, SCAN family algorithms often provide a better balance than SSTF or FCFS.

Use C-SCAN or C-LOOK when you want uniform wait times, especially for large disks or high request rates. Use N-SCAN and F-SCAN in real-time or bursty workloads where queue stability is important.

Disk Scheduling Example

Consider a disk with cylinders numbered 0 to 199 and an initial head position at 53. A request queue contains 98, 183, 37, 122, 14, 124, 65, 67. Different algorithms produce different movement totals.

Explain the example in interviews to show how each algorithm changes the service order and total seek distance.

Batching and Real-Time Behavior

Disk scheduling algorithms like N-SCAN and F-SCAN group requests into batches to limit reordering and prevent starvation. This is especially valuable in systems that need predictable I/O behavior.

By processing one batch at a time, these algorithms reduce the risk that new arrivals will indefinitely delay existing requests.

Performance vs Fairness

Disk scheduling illustrates a classic trade-off between performance and fairness. SSTF may minimize seek time but can unfairly favor nearby requests. SCAN and LOOK sacrifice a small amount of efficiency to ensure that all requests are eventually serviced.

In interviews, emphasize that system designers choose the algorithm based on the desired balance between throughput and response fairness.

Key Takeaways for Interviews

Define disk scheduling clearly and mention why it matters for disk-based systems.
Describe FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK, N-SCAN, and F-SCAN at a high level.
Explain seek time, head movement, and the request queue.
Discuss trade-offs: performance, fairness, and starvation.
Give an example request sequence and compare outputs from different algorithms.

Best Practices

Use SCAN or LOOK for general-purpose disk scheduling to balance fairness and performance.
Use C-SCAN or C-LOOK for uniform wait times across the disk surface.
Consider SSTF only if starvation is acceptable or can be managed with aging.
Use N-SCAN or F-SCAN for systems with bursty or real-time I/O demands.
Document the expected workload and choose the algorithm accordingly.

Common Interview Mistakes

Confusing SCAN with C-SCAN — the key difference is whether the return trip services requests.
Claiming SSTF is always best; it can cause starvation without safeguards.
Not mentioning that disk scheduling is less critical for SSDs but still relevant for fairness and request ordering.

Disk Scheduling for SSDs

Solid-state drives don’t have moving heads, so traditional seek-time improvements do not apply. However, scheduling still matters for managing request ordering, write amplification, and fairness in software stacks.

In interviews, note that legacy disk scheduling topics are still important for understanding historical OS design and for systems that still use HDDs.

Related Concepts

Elevator algorithm: another name for SCAN based on how elevator cars service floors.
Aging: technique to prevent starvation by increasing priority of waiting requests.
Request reordering: the core mechanism by which scheduling algorithms improve performance.
Throughput: amount of work done per unit time.
Response time: how long requests wait before being serviced.

Interview-Ready Summary

Disk scheduling algorithms are about deciding which disk request to serve next. The simplest policy is FCFS, while more advanced policies like SCAN, LOOK, and C-SCAN reduce head movement and provide better fairness.

Good interview answers will compare algorithms, explain trade-offs, and connect the choice to workload needs and system goals.

Interview Answer Tips

Start with a strong definition, then describe the difference between head movement optimization and fairness. Mention how SCAN and C-SCAN manage the disk head like an elevator to reduce wasted travel.

If asked for examples, compare FCFS and SSTF with the full SCAN family, and explain why some algorithms are better in high-load or real-time situations.

Practical Disk Scheduling Observations

In modern systems, disk scheduling is less visible for SSDs but remains a useful concept for understanding how operating systems optimize I/O. In HDD-based environments, these algorithms directly affect performance.

The same principles apply to other queued resources: choose an order that minimizes expensive movement and prevents long wait times.

Disk Scheduling and System Load

As system load increases, the choice of scheduling policy becomes more important. Algorithms that reduce average seek time and avoid starvation help maintain stability under heavy demand.

In low-load systems, FCFS may be sufficient, but in data centers and storage servers, SCAN family algorithms usually perform better.

Disk Scheduling in Operating Systems

Operating systems implement disk scheduling in their I/O subsystem. The scheduler collects pending requests, applies the chosen policy, and orders the requests before sending them to the disk driver.

This layer is responsible for ensuring that I/O requests are serviced efficiently while respecting priorities and fairness rules.

Example Comparison

If the head is at position 53 and the request queue is [98, 183, 37, 122, 14, 124, 65, 67], FCFS follows that exact order. SSTF might choose 65 or 37 next, while SCAN services everything in one direction before reversing.

Mentioning concrete numbers in your answer makes it more compelling and shows that you understand the practical impact of each algorithm.

Key Concept: Head Movement

Head movement is the main cost in disk scheduling. The farther the head travels, the more time it spends seeking. Algorithms that minimize travel distance tend to achieve better throughput.

But minimizing travel alone is not enough; you also need to ensure requests do not wait indefinitely.

Algorithm Notes

FCFS: easiest to explain, but poor for performance-sensitive workloads.
SSTF: often best for short response times, but watch for starvation.
SCAN and LOOK: good balanced performance with increased fairness.
C-SCAN and C-LOOK: improve uniformity and reduce wait-time variation.
N-SCAN and F-SCAN: provide stability in bursty I/O environments.

Interview Summary

Disk scheduling questions test your grasp of request ordering, seek cost, and algorithm trade-offs. A strong answer defines the concept, compares the main policies, and explains why one algorithm may be chosen over another for a given workload.

Use terms like head movement, request queue, seek time, and fairness to show you understand both the mechanics and the design goals behind disk scheduling.