Disk Scheduling & Management: Algorithms, Performance & Real-World Impact

Core Concepts: How Disks Work

Disk Structure and Access Time

Disks store data on concentric circles called tracks, divided into sectors. A cylinder is a stack of tracks at the same radius. Data access involves:

1. Seek time: Time to move the disk head to the correct track (typically 5–15 ms).
2. Rotational latency: Time for the desired sector to rotate under the head (0–10 ms).
3. Transfer time: Time to read/write the sector (negligible for modern disks).

   ┌───────────────────────┐
   │       Platter         │
   │   ┌───────────────┐   │
   │   │   Track 0     │   │
   │   │   ┌───┐ ┌───┐ │   │
   │   │   │S0│ │S1│ │   │
   │   │   └───┘ └───┘ │   │
   │   │   Track 1     │   │
   │   └───────────────┘   │
   │       Head          │
   └───────────────────────┘

Real-world tie: When you load a YouTube video, the OS uses disk scheduling to minimize seek time for fetching video chunks, reducing buffering delays.

---

Disk Scheduling Algorithms

1. First-Come, First-Served (FCFS)

• How it works: Processes requests in the order they arrive.
• Example: Requests arrive at cylinders 25, 43, 60, 190, 40, 125, 15, 150.
  • Head moves: 25 → 43 (18 units) → 60 (17) → 190 (130) → 40 (150) → 125 (85) → 15 (110) → 150 (135).
  • Total seek time: 645 units.

Pros: Simple to implement. Cons: Poor performance for clustered requests (high seek time).

---

2. Shortest Seek Time First (SSTF)

• How it works: Head moves to the nearest request first.
• Example: Same requests as above.
  • Head moves: 43 → 60 (17) → 40 (20) → 125 (85) → 15 (110) → 150 (135) → 190 (40).
  • Total seek time: 537 units (better than FCFS).

Pros: Reduces average seek time. Cons: Starvation for far requests (e.g., 190 waits long).

---

3. SCAN (Elevator Algorithm)

• How it works: Head moves in one direction, servicing requests until the end, then reverses.
• Example: Head starts at 43, moving right first.
  • Path: 43 → 60 (17) → 190 (130) → 15 (175) → 150 (135) → 125 (25) → 40 (85).
  • Total seek time: 767 units (worse than SSTF but fairer).

Pros: Fairer than SSTF; avoids starvation. Cons: Higher seek time for requests at the ends.

---

4. C-SCAN (Circular SCAN)

• How it works: Head moves to the end, jumps to the start, and repeats.
• Example: Head starts at 43, moves right to 190, jumps to 0, then left to 150.
  • Path: 43 → 60 (17) → 190 (130) → 0 (190) → 150 (150) → 125 (25) → 40 (85).
  • Total seek time: 707 units.

Pros: Predictable response time for outer cylinders. Cons: Higher latency for requests near the start.

---

5. LOOK and C-LOOK

• LOOK: Like SCAN but stops at the last request in the current direction.
• C-LOOK: Like C-SCAN but jumps to the last request in the current direction.
• Example: LOOK with requests 60, 190, 40, 125, 15, 150.
  • Path: 43 → 60 (17) → 190 (130) → 150 (40) → 40 (110) → 125 (85) → 15 (110).
  • Total seek time: 592 units.

Use case: Used in eSewa servers to minimize seek time during peak transaction hours (e.g., 10 AM–12 PM).

---

Performance Metrics

---

Disk Management Techniques

1. Partitioning

• Divides disk into logical units (e.g., C:, D:).
• Types:
  • Primary: Bootable (max 4 per MBR).
  • Extended: Contains logical drives.
  • Logical: Subdivisions of extended partitions.

Real-world tie: Nepal Rastra Bank (NRB) uses disk partitioning to separate transaction logs (frequent access) from archival data (rare access).

---

2. Formatting

• Low-level: Creates sectors/tracks (done by manufacturer).
• High-level: Creates file system (FAT32, NTFS, ext4).
• Example: Formatting a 1TB disk for Daraz’s order database:
  • File system: ext4 (Linux-based servers).
  • Block size: 4KB (optimized for small transactions).

---

3. RAID (Redundant Array of Independent Disks)

Combines multiple disks for performance or reliability.

Real-world tie: NTC’s network uses RAID 10 (RAID 1 + RAID 0) for critical traffic routing data to ensure zero downtime.

---

Worked Example: Disk Scheduling for Pathao Orders

Scenario: Pathao’s server processes ride requests from 100 cylinders (0–99). Current head position: 43. Pending requests (arrival order): 60, 190, 40, 125, 15, 150. Goal: Compare FCFS vs. SSTF for average seek time.

Conclusion: SSTF reduces seek time by 16.8%, improving response time for Pathao’s real-time GPS data.

---

In the Real World

1. eSewa: Uses SCAN algorithm to minimize seek time during peak hours (e.g., 10 AM–12 PM for bill payments). The OS schedules transactions in batches to reduce head movement.
2. YouTube (Google): Employs RAID 0 for video streaming servers to maximize read speed. Critical metadata (e.g., user preferences) is stored on RAID 1 for redundancy.
3. Nepal Stock Exchange (NEPSE): Uses C-SCAN for disk scheduling in trading terminals to ensure fair access to market data feeds, preventing starvation of low-priority requests.

---

Exam Tip

1. Always draw Gantt charts for scheduling questions (FCFS, SSTF, SCAN). Label axes clearly (e.g., "Cylinder Number").
2. Memorize seek time formulas:
   • FCFS: Sum of absolute differences between consecutive requests.
   • SSTF: Greedy choice at each step (nearest request).
3. Compare algorithms in tables (like above) to show trade-offs (e.g., SSTF vs. SCAN).
4. Real-world applications:
   • Banks (RAID 1 for transactions).
   • E-commerce (SCAN for order processing).
   • Telecom (C-SCAN for call logs).
5. Disk management:
   • Partitioning: Know primary/extended/logical drives.
   • RAID: Match levels to use cases (e.g., RAID 5 for databases).

---