Disk Structure & Scheduling Algorithms

Disks are among the most important components in a computer system for data storage. Understanding how data is organized on the disk and how efficiently requests are served is essential for improving system performance. Disk management involves both how data is structured and how access to it is scheduled to minimize delays.

Disk Structure Overview

Modern storage devices like HDDs (Hard Disk Drives) store data using platters, which are circular disks coated with magnetic material. These platters spin around a central spindle, and data is read or written using a read/write head that moves across the surface.

Each platter is divided into:

• Tracks: concentric circles on the surface.
• Sectors: subdivisions of each track.
• Cylinders: groups of tracks aligned vertically across platters.

Because accessing data on a disk involves mechanical movement (moving the head and spinning the platter), it is much slower than accessing data in memory. Efficient scheduling of disk access requests is, therefore, critical.

Disk Scheduling Algorithms

When multiple read/write requests arrive, the operating system must decide the order in which they will be serviced. The goal is to minimize seek time (the time taken for the head to move to the correct track), rotational latency, and overall waiting time.

Here are the major disk scheduling algorithms:

1. FCFS (First Come First Serve)

This is the simplest approach—requests are handled in the order they arrive.

• Pros: Fair and simple to implement.

• Cons: Can be inefficient if requests are scattered widely across the disk. Seek time may be high.

It does not optimize head movement and can lead to longer average waiting times.

2. SSTF (Shortest Seek Time First)

In this method, the request closest to the current head position is served next. It reduces total head movement compared to FCFS.

• Pros: Better performance than FCFS in many cases.

• Cons: Can cause starvation for requests far from the head position if closer requests keep coming.

This algorithm favors efficiency but may delay distant requests indefinitely.

3. SCAN (Elevator Algorithm)

The disk arm moves in one direction (say inward), servicing all requests in its path, and when it reaches the end, it reverses direction and services requests on the way back.

• Pros: More uniform wait times than SSTF.

• Cons: Requests just missed on the current sweep must wait until the arm returns.

The movement of the arm is like an elevator moving up and down, which gives this method its nickname.

4. LOOK

LOOK is a variant of SCAN. Instead of going to the end of the disk, the head reverses direction as soon as there are no more requests in the current direction.

• Pros: Reduces unnecessary movement of the head.

• Cons: Still suffers from long wait times in some scenarios.

It optimizes SCAN by making head movement more intelligent.

5. C-SCAN (Circular SCAN)

This algorithm moves the head in one direction only (e.g., inward). When it reaches the end, it jumps back to the beginning and starts servicing again in the same direction.

• Pros: Provides uniform wait times and avoids starvation.

• Cons: The jump back is a performance cost, although it’s not as high as in real time due to non-servicing during the return.

This method is good for systems that want to treat all requests uniformly, regardless of location.

6. C-LOOK

C-LOOK is the optimized version of C-SCAN. The head goes only as far as the last request in one direction, then jumps back to the lowest request, instead of going all the way to the end of the disk.

• Pros: Reduces unnecessary traversal.

• Cons: Similar trade-offs as C-SCAN but slightly more efficient.

C-LOOK saves time by avoiding movement to unused disk areas.

Summary

Efficient disk scheduling can significantly enhance overall system performance. The choice of algorithm depends on the workload and system requirements:

• FCFS: Simple but inefficient.
• SSTF: Fast but unfair.
• SCAN/LOOK: Balanced but can delay requests.
• C-SCAN/C-LOOK: Uniform performance and better for large-scale systems.

An understanding of these algorithms equips students to analyze performance and design better storage strategies in real-world systems.