Disk Scheduling

Introduction

Disk scheduling: technique to optimize order of disk I/O requests. Goal: minimize seek time and latency. Critical in multi-programming and multi-user OS environments. Disk head movement costly: mechanical delays dominate access time. Scheduling algorithms balance fairness and efficiency. Diverse strategies exist to address workload patterns and hardware constraints.

"Disk scheduling algorithms are fundamental in reducing I/O bottlenecks in modern operating systems." -- Abraham Silberschatz

Disk Structure and Geometry

Physical Components

Disk platter: circular magnetic surface. Tracks: concentric circles storing data. Sectors: subdivisions of tracks, smallest addressable unit. Disk head: reads/writes data by positioning over track. Actuator arm: moves head radially across platters.

Logical Addressing

Logical Block Addressing (LBA): linear mapping of sectors. OS issues requests via LBA, translated to physical track/sector. Cylinder: set of tracks aligned vertically across platters.

Access Time Components

Seek time: time to move head to target track. Rotational latency: wait for target sector under head. Transfer time: actual data read/write. Seek time dominates disk I/O latency.

Need for Disk Scheduling

Multiple Concurrent Requests

Multi-user OS: many I/O requests generated simultaneously. Serializing requests inefficient without optimization.

Reducing Seek Time

Naive servicing causes excessive head movement. Scheduling reorders requests to minimize travel distance.

Improving Throughput and Response

Optimized scheduling increases I/O throughput. Reduces average response time per request. Balances fairness and efficiency.

Performance Metrics

Seek Time

Primary metric: time to move head between tracks. Measured in milliseconds. Directly impacts overall I/O latency.

Rotational Latency

Time waiting for sector under head. Average latency is half a rotation. Fixed for given disk RPM.

Throughput

Number of requests serviced per unit time. Higher throughput indicates better performance.

Fairness

Ensures no starvation of requests. Balances efficiency with equitable service.

Response Time

Elapsed time from request issue to completion. Scheduling affects average and worst-case response.

First-Come, First-Served (FCFS) Algorithm

Mechanism

Requests served in order of arrival. Simple queue structure. No reordering.

Advantages

Fair: no starvation. Easy to implement.

Disadvantages

Poor performance if requests scattered. High average seek time possible.

Use Cases

Low load systems. Where fairness prioritized over speed.

Example

Request queue: 98, 183, 37, 122, 14, 124, 65, 67. Head starts at 53.

Order: 53→98→183→37→122→14→124→65→67Total head movement: 640 tracks

Shortest Seek Time First (SSTF) Algorithm

Mechanism

Select request closest to current head position. Minimizes immediate seek time.

Advantages

Reduces average seek time compared to FCFS.

Disadvantages

Potential starvation for distant requests. Bias towards nearby requests.

Implementation

Maintain sorted list of requests. Calculate distances dynamically.

Example

Using previous request queue and head at 53:

Order: 53→65→67→37→14→98→122→124→183Total head movement: 236 tracks

SCAN Algorithm (Elevator Algorithm)

Mechanism

Head moves in one direction servicing requests until end. Then reverses direction. Mimics elevator movement.

Advantages

Reduces variance in wait times. Avoids starvation. Efficient for high load.

Disadvantages

Longer wait for requests just behind head's current direction.

Implementation Details

Maintain sorted queue. Service all requests in direction before reversing.

Example

Head at 53, moving towards higher tracks:

Order: 53→65→67→98→122→124→183→(reverse)→37→14Total head movement: 208 tracks

C-SCAN Algorithm

Mechanism

Head moves in one direction servicing requests till end. Then jumps to start without servicing on return.

Advantages

Provides uniform wait times. Avoids starvation. Better for real-time systems.

Disadvantages

Jump back causes overhead. Slightly less efficient than SCAN in some cases.

Implementation

Sorted queue with wrap-around logic.

Example

Head at 53, moving upwards:

Order: 53→65→67→98→122→124→183→jump→14→37Total head movement: 322 tracks

LOOK and C-LOOK Algorithms

LOOK Mechanism

Like SCAN but head reverses at last request in direction rather than end of disk.

C-LOOK Mechanism

Like C-SCAN but head jumps to first request instead of start of disk.

Advantages

Reduces unnecessary travel. Improves efficiency over SCAN and C-SCAN.

Disadvantages

More complex implementation. Slightly less predictable wait times.

Example

Head at 53, requests as before:

LOOK order: 53→65→67→98→122→124→183→reverse→37→14C-LOOK order: 53→65→67→98→122→124→183→jump→14→37Head movement: LOOK < SCAN, C-LOOK < C-SCAN

Algorithm Comparison

Summary Table

Performance Insights

LOOK and C-LOOK provide best tradeoff between efficiency and fairness. FCFS simplest but worst performance. SSTF improves seek time but risks starvation. SCAN and C-SCAN balance throughput and predictability.

Implementation Issues

Request Queue Management

Efficient data structures for sorting and searching requests required. Balanced trees or priority queues common.

Real-Time Constraints

Some applications require bounded response times. Scheduling must guarantee deadlines or priorities.

Hardware Variations

Solid State Drives (SSD) lack mechanical delay; scheduling less critical. Hybrid systems complicate algorithm choice.

Preemption and Interrupts

Algorithms must handle new requests arriving during servicing. May require dynamic reordering.

Integration with OS

Disk scheduler implemented in OS kernel. Interaction with file system and I/O subsystem critical.

Future Trends in Disk Scheduling

SSD and Flash Storage Impact

Minimal seek and latency times reduce need for traditional scheduling. Focus shifts to wear leveling, parallelism.

Hybrid Storage Systems

Combined HDD/SSD systems require adaptive scheduling. Data placement and migration integrated with scheduling.

Machine Learning Approaches

Predictive scheduling using workload patterns and I/O history. Dynamic algorithm selection and parameter tuning.

Cloud and Distributed Storage

Scheduling extends to networked storage and multi-node systems. Latency and bandwidth management critical.

Energy-Aware Scheduling

Balancing performance with power consumption. Scheduling to minimize disk spin-up/spin-down cycles.

References

• A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts, 10th ed., Wiley, 2018, pp. 356–382.
• G. M. Cox, M. F. Kaashoek, R. Morris, “The Design of a Disk Scheduling Algorithm,” ACM Transactions on Computer Systems, vol. 11, no. 1, 1993, pp. 1–20.
• D. A. Patterson, J. L. Hennessy, Computer Organization and Design, 5th ed., Morgan Kaufmann, 2013, pp. 395–420.
• M. J. Bach, The Design of the UNIX Operating System, Prentice Hall, 1986, pp. 235–260.
• R. Jain, The Art of Computer Systems Performance Analysis, Wiley, 1991, pp. 175–200.