Disk Scheduling Algorithms in Operating Systems

Disk Scheduling Algorithms in Operating Systems

Description: Disk scheduling algorithms are strategies used by operating systems to determine the order of servicing disk I/O requests. Since disk access speed is much slower than memory and CPU, efficient disk scheduling can significantly improve system performance. When multiple processes request access to different parts of the disk, the operating system needs to choose a reasonable order to handle these requests to reduce head movement distance, shorten average seek time, and thereby improve disk I/O bandwidth and overall system response speed.

Key Points and Problem-Solving Process:

  1. Core Problem: Seek Time

    • Background: The access time of a mechanical hard disk drive (HDD) mainly consists of three parts: seek time, rotational latency, and data transfer time. Among them, seek time (the time required for the head to move to the target track) is the primary bottleneck, usually much greater than the latter two. Therefore, the core goal of disk scheduling algorithms is to minimize the total seek distance.
    • Key Concept: We use a request queue to simulate a scenario. Assume the disk has 200 tracks (0-199), and the current head is at track 53. The request queue is: [98, 183, 37, 122, 14, 124, 65, 67]. We will use this example to explain various algorithms.

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

    • Description: This is the simplest scheduling algorithm, processing requests in the order they arrive. It is very fair but usually inefficient because the head moves back and forth without optimization.
    • Problem-Solving Process:
      1. Current head at 53.
      2. Service next request 98, head moves from 53 to 98, seek distance = |98-53| = 45.
      3. Service request 183, move distance = |183-98| = 85.
      4. Service request 37, move distance = |37-183| = 146.
      5. Service request 122, move distance = |122-37| = 85.
      6. Service request 14, move distance = |14-122| = 108.
      7. Service request 124, move distance = |124-14| = 110.
      8. Service request 65, move distance = |65-124| = 59.
      9. Service request 67, move distance = |67-65| = 2.
    • Total Seek Distance: 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640.
    • Advantages and Disadvantages: Fair, but has long average seek time and poor performance. Similar to FCFS in process scheduling.

  3. Shortest Seek Time First (SSTF)

    • Description: Selects the request closest to the current head position for service. This is a "greedy" algorithm, aiming to make each move optimal.
    • Problem-Solving Process:
      1. Current head at 53. Request queue [98, 183, 37, 122, 14, 124, 65, 67].
      2. Find the request closest to 53: 65 (distance 12) and 67 (distance 14), choose 65.
      3. Head moves to 65. Next closest is 67 (distance 2).
      4. Head moves to 67. Next closest are 37 (distance 30) and 98 (distance 31), choose 37.
      5. Head moves to 37. Next closest is 14 (distance 23).
      6. Head moves to 14. Next closest is 98 (distance 84).
      7. Head moves to 98. Next closest is 122 (distance 24).
      8. Head moves to 122. Next closest is 124 (distance 2).
      9. Head moves to 124. Finally service 183.
    • Service Order: 53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183.
    • Total Seek Distance: 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236.
    • Advantages and Disadvantages: Performance is significantly better than FCFS. However, it may cause "starvation": if new requests keep arriving near the current head position, requests far from the head may never be serviced.

  4. SCAN Algorithm (Elevator Algorithm)

    • Description: Mimics elevator operation. The head moves in one direction (e.g., from inner to outer), servicing all requests along the way until it reaches the disk end (or start), then reverses direction and moves back, servicing requests.
    • Problem-Solving Process (assuming initial head direction is towards increasing track numbers):
      1. Current head at 53, direction outward.
      2. Move in increasing direction, servicing all requests greater than 53: 65, 67, 98, 122, 124, 183.
      3. After reaching disk end (199), reverse direction to decreasing.
      4. Service all requests less than 53: 37, 14.
    • Service Order: 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> (199) -> 37 -> 14.
    • Total Seek Distance: (65-53)+(67-65)+...+(183-124)+(199-183)+(199-37)+(37-14) = 12+2+31+24+2+59+16+162+23 = 331. (Or simply calculate: from 53 to 199, then to 14).
    • Advantages and Disadvantages: Overcomes SSTF's starvation problem. But unfair to requests at both ends; areas just passed must wait for the head to traverse the entire disk again.

  5. Circular SCAN Algorithm (C-SCAN)

    • Description: An improved version of SCAN, providing more uniform waiting times. The head services requests only in one direction (e.g., from inner to outer). When it reaches the disk end, it immediately returns to the disk start (without servicing requests) and starts scanning again.
    • Problem-Solving Process (assuming direction is towards increasing track numbers):
      1. Current head at 53, direction outward.
      2. Move in increasing direction, servicing all requests greater than 53: 65, 67, 98, 122, 124, 183.
      3. After reaching disk end (199), immediately jump back to disk start (0).
      4. Starting from 0, move again in increasing direction, servicing all requests less than 53: 14, 37.
    • Service Order: 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> (199 -> 0) -> 14 -> 37.
    • Total Seek Distance: (from 53 to 183) + (jump from 183 to 199/0) + (from 0 to 37) = (183-53) + (199-0) + (37-0) = 130 + 199 + 37 = 366. (Actual head movement is (199-53) + (199-0) + (37-0) = 146 + 199 + 37 = 382, but algorithms typically only count seek distance, treating the jump as necessary overhead).
    • Advantages and Disadvantages: Provides more consistent waiting times than SCAN by treating the disk as a circular list.

  6. LOOK and C-LOOK Algorithms

    • Description: Optimized versions of SCAN and C-SCAN. The head does not need to reach the physical endpoints of the disk; it only needs to reach the last request in that direction before reversing or returning.
    • LOOK Algorithm Process (corresponding to SCAN):
      1. Current head at 53, direction outward.
      2. Move in increasing direction, servicing 65, 67, 98, 122, 124, 183. 183 is the last request in that direction, so no need to go to 199.
      3. Reverse to decreasing direction, servicing 37, 14. 14 is the last request in that direction, no need to go to 0.
    • Service Order: 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 37 -> 14.
    • Total Seek Distance: Shorter than SCAN (331).
    • C-LOOK Algorithm Process (corresponding to C-SCAN):
      1. Current head at 53, direction outward.
      2. Move in increasing direction, servicing 65, 67, 98, 122, 124, 183.
      3. Jump immediately from 183 to the first request in that direction (14), not to 0.
      4. Starting from 14, continue moving in increasing direction, servicing 37.
    • Service Order: 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 14 -> 37.
    • Total Seek Distance: Shorter than C-SCAN.
    • Advantages and Disadvantages: LOOK and C-LOOK are more commonly used in real systems because they avoid unnecessary movement to disk ends and are more efficient.

Summary: Choosing a disk scheduling algorithm involves a trade-off between fairness and performance. FCFS is fair but performs poorly; SSTF performs well but may cause starvation; SCAN/C-SCAN are fair but may have overhead; LOOK/C-LOOK are practical choices with good performance and fairness. In modern operating systems (like Linux), variants of the C-LOOK algorithm are typically used. For SSDs (solid-state drives), due to the lack of mechanical movement, these algorithms are no longer applicable, and FCFS or simpler policies are usually used.