Disk Scheduling Notes & Formulas

1. Definition

Disk scheduling algorithms determine the order in which disk I/O requests are serviced to minimize seek time (head movement).

2. Key Terms

• Seek Time: Time to move disk arm to required track - dominates disk access time
• Rotational Latency: Time for disk to rotate required sector under head
• Transfer Time: Time to actually transfer data
• Total Access Time = Seek Time + Rotational Latency + Transfer Time

3. Disk Scheduling Algorithms (Very Important)

FCFS (First Come First Serve)

• Service requests in order received
• Fair but high seek time - no optimization

SSTF (Shortest Seek Time First)

• Service request closest to current head position
• Reduces average seek time vs FCFS
• Problem: starvation of far requests

SCAN (Elevator Algorithm)

• Head moves in one direction, services all requests, then reverses
• No starvation. Head travels to end of disk before reversing.
• Unequal wait: requests just serviced must wait for full sweep

C-SCAN (Circular SCAN)

• Head moves in one direction, services requests, jumps back to start without servicing on return
• More uniform wait time than SCAN
• Treats disk as circular

LOOK

• Like SCAN but reverses at last request (not at disk end)
• Better than SCAN - avoids unnecessary travel

C-LOOK

• Like C-SCAN but jumps back to first request (not disk start)
• Best practical algorithm - uniform wait, no wasted movement

4. Comparison

| Algorithm | Starvation | Performance | Notes |
|---|---|---|---|
| FCFS | No | Poor | Fair only |
| SSTF | Yes | Good avg | Not optimal |
| SCAN | No | Good | Unequal wait |
| C-SCAN | No | Better | Uniform wait |
| LOOK | No | Best | Used in practice |
| C-LOOK | No | Best | Used in practice |

5. Total Head Movement Calculation

Always draw the sequence on a number line and add up absolute differences between consecutive positions.

Example: Head at 50, requests: 95,180,34,119,11,123,62
FCFS: |95−50|+|180−95|+|34−180|+... = sum all moves

6. GATE Trick

SSTF is greedy - always picks nearest, not globally optimal. LOOK/C-LOOK are preferred over SCAN/C-SCAN in practice. For numerical questions: list the service order first, then calculate total movement as sum of absolute differences. C-SCAN jump-back does NOT count as movement in most questions - verify with question.