Disk Scheduling (OS)

operating-systems io scheduling

Definition

Disk Scheduling

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

Characteristic Times

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

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

1. Seek Time ($T_S$): The time required to move the disk arm to the correct track.

2. Rotational Delay ($T_{RD}$): The time it takes for the desired sector to rotate under the disk head. On average, this is half the rotation time: $T_{RD}=\frac{1}{2r}$ where $r$ is the rotation speed.

3. Transfer Time ($T_{TF}$): The time required to transfer the data.

   $$T_{TF}=\frac{b}{rN}$$

   where $b$ is the number of bytes to transfer, $r$ is rotation speed, and $N$ is the number of bytes per track.

Scheduling Algorithms

First-In-First-Out (FIFO)

Requests are processed in the order they arrive.

• Pros: Fair and simple.
• Cons: Can result in high head movement if requests are scattered across tracks.

Shortest Service Time First (SSTF)

The request closest to the current head position is serviced next.

• Pros: Significantly reduces average seek time.
• Cons: Can lead to starvation of requests at the edges of the disk if new requests keep arriving near the centre.

SCAN (Elevator Algorithm)

The head moves in one direction, servicing all requests until it reaches the edge of the disk, then reverses direction.

• Pros: Prevents starvation and provides a more predictable wait time.

C-SCAN (Circular SCAN)

Similar to SCAN, but the head only services requests in one direction. When it reaches the end, it immediately returns to the beginning without servicing any requests on the way back.

• Pros: Provides more uniform wait times than SCAN.

N-step-SCAN and FSCAN

These algorithms address the problem of head stickiness, where a high volume of requests for a single track prevents the head from moving.

• N-step-SCAN: Segments the request queue into batches of size $N$. The algorithm processes one batch completely using the SCAN strategy before moving to the next. New requests arriving during a scan are placed into the next batch.
• FSCAN: Uses two separate queues. While one queue is being serviced by the SCAN algorithm, all new requests are “bundled” into the second queue. Once the first queue is empty, the algorithm switches to the second.