Disk Scheduling Algorithms

Disk Scheduling Algorithm is a crucial component of operating systems that manages and organizes input and output requests for disk access. It helps reduce disk arm movement, minimizes response time, and ensures efficient data access. Understanding these algorithms is essential as disk operations are among the slowest parts of computer systems.

Key Terms in Disk Scheduling

FCFS (First Come First Serve)

Processes requests in order of arrival, following a simple first-in-first-out (FIFO) approach. The disk head moves to fulfill requests in the exact sequence they were received.

Characteristics:

  • Simple implementation using a FIFO queue
  • No starvation as every request is guaranteed to be served
  • Higher seek times due to random head movements
  • Fair but not efficient for high-load systems

Advantages:

  • Every request gets equal opportunity
  • Perfect for low-load systems
  • Minimal overhead in request processing

Disadvantages:

  • High average seek time and response time
  • No optimization for head movement
  • Poor performance with scattered requests
Example: For head at 50 and requests (82,170,43,140,24,16,190), total seek time = 642
Calculation: |50-82| + |82-170| + |170-43| + |43-140| + |140-24| + |24-16| + |16-190| = 642

SSTF (Shortest Seek Time First)

Selects request with minimum seek time from current head position, implementing a shortest-job-first approach for disk scheduling.

Characteristics:

  • Lower disk response time compared to FCFS
  • More efficient head movement patterns
  • Possible starvation of distant requests
  • Requires continuous calculation of seek times

Advantages:

  • Significantly reduces average seek time
  • Better throughput than FCFS
  • Good for systems with varied request patterns

Disadvantages:

  • Complex implementation requiring seek time calculation
  • Potential starvation of distant cylinders
  • Overhead in finding shortest seek time
Example: For same sequence, total seek time = 208
Path: 50 → 43 → 24 → 16 → 82 → 140 → 170 → 190

SCAN (Elevator)

Head moves in one direction until end, then reverses, serving requests along the way. Similar to an elevator's movement pattern, hence the name.

Characteristics:

  • Easy implementation with directional scanning
  • No request queue starvation
  • Continuous movement to disk end
  • Better performance than FCFS and SSTF

Advantages:

  • Uniform servicing of requests
  • Good for heavy-load systems
  • Prevents starvation effectively

Disadvantages:

  • Maximum waiting time for cylinders just visited
  • Extra head movement to disk ends
  • Not optimal for light loads
Example: For same sequence, total seek time = 332
Path: 50 → 43 → 24 → 16 → 0 → 82 → 140 → 170 → 190

C-SCAN (Circular SCAN)

Similar to SCAN but serves requests only in forward direction. After reaching the disk end, it quickly returns to the beginning (0) without serving any requests, and starts serving again from the beginning. This creates a circular movement pattern.

Working:

  • Head moves toward the end of disk (199) serving requests
  • After reaching end, quickly returns to beginning (0)
  • During return journey, no requests are served
  • Starts serving again from beginning (0) onwards

Advantages:

  • Uniform waiting time distribution for all cylinders
  • Better response time than SCAN
  • Avoids starvation of requests

Disadvantages:

  • Higher seek time due to full disk traversal
  • Head always moves to disk ends
  • Unused return traversal increases total time
Example: For head at 50 and requests (82,170,43,140,24,16,190), total seek time = 391
Path: 50 → 82 → 140 → 170 → 190 → [199] → [0] → 16 → 24 → 43
Calculation: (199-50) + (199-0) + (43-0) = 149 + 199 + 43 = 391

LOOK

Similar to SCAN but only goes to last request in each direction, optimizing the head movement by avoiding unnecessary travel to disk ends.

Characteristics:

  • No starvation of requests
  • Efficient time usage with limited movement
  • Requires tracking of last requests
  • Better performance than SCAN

Advantages:

  • Reduced head movement compared to SCAN
  • Better average response time
  • More efficient for edge cylinders

Disadvantages:

  • More complex implementation than SCAN
  • Requires additional overhead for tracking
  • May not be optimal for all workloads
Example: For same sequence, total seek time = 314
Path: 50 → 43 → 24 → 16 → 82 → 140 → 170 → 190

C-LOOK

Similar to LOOK algorithm but serves requests only in one direction. After reaching the highest request, it jumps to the lowest request without serving any requests in between, then continues serving in the same direction.

Working:

  • Head moves in one direction serving requests
  • Goes only until highest request (not disk end)
  • Jumps to lowest request without serving
  • Continues serving from lowest to highest

Advantages:

  • Better average response time than C-SCAN
  • More efficient than LOOK for uniform load
  • Reduced head movement than C-SCAN

Disadvantages:

  • Complex implementation logic
  • May cause non-uniform waiting times
  • Long jumps between request ends
Example: For head at 50 and requests (82,170,43,140,24,16,190), total seek time = 341
Path: 50 → 82 → 140 → 170 → 190 → [jump to 16] → 16 → 24 → 43
Calculation: (190-50) + (190-16) + (43-16) = 140 + 174 + 27 = 341
Try Animation Demo