Disk Scheduling (OS)

operating-systems io scheduling

Definition

Disk Scheduling

Disk scheduling manages the order in which pending I/O requests are serviced on a magnetic disk. The primary goal is to minimise seek time, the most significant component of disk latency.

Access Time

The Average Access Time ($T_A$) for a disk operation is:

$$T_A=T_S+T_{RD}+T_{TF}$$

Component	Symbol	Description
Seek Time	$T_S$	Time to move the disk arm to the correct track
Rotational Delay	$T_{RD}$	Average: $\frac{1}{2r}$ where $r$ is rotation speed
Transfer Time	$T_{TF}$	$\frac{b}{rN}$ where $b$ = bytes, $N$ = bytes per track

Algorithms

FIFO

Requests processed in arrival order. Fair and simple, but may cause high head movement if requests are scattered.

SSTF (Shortest Service Time First)

Services the request closest to the current head position. Reduces average seek time but may cause starvation of edge requests.

SCAN (Elevator Algorithm)

Head moves in one direction servicing requests, then reverses at the disk edge. Prevents starvation with predictable wait times.

C-SCAN (Circular SCAN)

Like SCAN, but only services in one direction. Returns to the beginning without servicing on the return. Provides more uniform wait times.

N-step-SCAN

Segments request queue into batches of size $N$. Processes each batch with SCAN before moving to the next. Addresses head stickiness (many requests for a single track).

FSCAN

Uses two queues. While one is serviced, new requests enter the second. Switches queues when the current one empties. Also addresses head stickiness.