Disk Management: Disk Structure & Disk Scheduling Algorithms

1. Magnetic Disk Structure & Disk Access Time

To understand how the OS schedules disk requests, let us first understand the physical geometry of a Hard Disk Drive (HDD):

3 Components of Disk Access Time (Why We Need Disk Scheduling!)

When the OS reads or writes a disk block, the total time taken consists of three parts:

1. Seek Time (Largest Delay!): The time required for the mechanical Disk Arm to move the Read/Write Head horizontally to the desired Cylinder (Track).
2. Rotational Latency: Once the head is on the right track, the additional time waiting for the spinning platter to rotate the desired Sector underneath the Read/Write Head.
3. Transfer Time: The time to actually read/write the electronic bits from the sector to RAM.

Goal of Disk Scheduling: Since mechanical Seek Time (moving the disk arm across tracks) is by far the slowest part of disk I/O, Disk Scheduling Algorithms aim to minimize total Head Movement (Seek Time)!

2. The 5 Disk Scheduling Algorithms in Your Syllabus

Let us solve all 5 Disk Scheduling Algorithms (FCFS, SSTF, SCAN, C-SCAN, LOOK) using the exact same standard textbook numerical so you can easily compare them in your exam!

Common Numerical Problem Setup:

• A disk has 200 cylinders/tracks numbered from 0 to 199.
• The Read/Write Head is currently at Track 53 (moving toward 199 for SCAN/C-SCAN/LOOK).
• Disk Request Queue: 98, 183, 37, 122, 14, 124, 65, 67

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

• How It Works: The simplest algorithm. Requests are serviced strictly in the exact order they arrive in the queue, regardless of how far the head has to jump back and forth!
• Head Movement Sequence (Starting at 53):

  Formula: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67

• Total Head Movement Calculation:

  Formula: |98-53| + |183-98| + |37-183| + |122-37| + |14-122| + |124-14| + |65-124| + |67-65| Formula: = 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 Cylinders (Tracks)

• Drawback: Wildly swings the disk arm from 183 to 37 to 122 to 14, resulting in huge seek time (640 tracks!).

2. SSTF (Shortest Seek Time First) Disk Scheduling

• How It Works: Selects the pending request that requires the minimum head movement from the CURRENT head position! (Always services the closest track next, just like Greedy SJF in CPU scheduling).
• Head Movement Sequence (Starting at 53):
  • From 53, closest request is 65 (distance 12) → then 67 → then 37 (distance 30 is closer than 98’s distance 31!) → 14 → 98 → 122 → 124 → 183.

  Formula: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183

• Total Head Movement Calculation:

  Formula: |65-53| + |67-65| + |37-67| + |14-37| + |98-14| + |122-98| + |124-122| + |183-124| Formula: = 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 Cylinders

• Advantage & Drawback: Cuts head movement down to almost one-third of FCFS (236 vs 640), but can cause Starvation of far-away tracks if requests near the current head keep arriving!

3. SCAN (Elevator Algorithm) Disk Scheduling

• How It Works: The disk arm works just like a Building Elevator (Lift)!
  1. The arm starts at 53 and moves in one direction (say, toward the end of the disk 199), servicing all requests along the way until it touches the physical end boundary (199 or 0)!
  2. Once it hits the boundary (199), it reverses direction and services all remaining requests on the way back!
• Head Movement Sequence (Starting at 53, moving toward 199):

  Formula: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 (End Boundary) → 37 → 14

• Total Head Movement Calculation:

  Formula: (199 - 53) + (199 - 14) = 146 + 185 = 331 Cylinders

• (Note: If moving toward 0 first: 53 → 37 → 14 → 0 → 65 → 67 → 98 → 122 → 124 → 183 = 53 + 183 = 236 Cylinders).

4. C-SCAN (Circular SCAN) Disk Scheduling

• Why C-SCAN? In standard SCAN, when the head reverses at 199, tracks near 199 were just serviced, while tracks at the other end (0) have been waiting the longest.
• How C-SCAN Works: Provides a more uniform waiting time!
  1. The head moves from 53 toward 199, servicing requests along the way until it reaches the end (199).
  2. It then immediately jumps back to the beginning of the disk (0) WITHOUT servicing any requests on the return trip, and starts scanning upward again from 0! (Treats the cylinders 0..199 as a circular list).
• Head Movement Sequence (Starting at 53 toward 199):

  Formula: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 → (Jump) → 0 → 14 → 37

• Total Head Movement Calculation:

  Formula: (199 - 53) + (199 - 0) + (37 - 0) = 146 + 199 + 37 = 382 Cylinders

5. LOOK (and C-LOOK) Disk Scheduling

• Why LOOK? In SCAN and C-SCAN, the disk arm foolishly travels all the way to the physical end of the disk (199 or 0), even if the last actual request is at 183 (no request exists between 183 and 199!).
• How LOOK Works: The arm “LOOKS” ahead to see if there are any more requests in the current direction! It moves only as far as the final request in each direction (183) and then immediately reverses direction without wasting time going to 199!
• Head Movement Sequence (Starting at 53 toward 199):

  Formula: 53 → 65 → 67 → 98 → 122 → 124 → 183 (Reverses here!) → 37 → 14

• Total Head Movement Calculation:

  Formula: (183 - 53) + (183 - 14) = 130 + 169 = 299 Cylinders

3. Quick Summary Table of All 5 Disk Scheduling Algorithms

💡 Exam Preparation Tips for DAVV BCA

• Remember the golden distinction between SCAN and LOOK:
  • SCAN always goes all the way to the physical boundary (0 or 199) before reversing.
  • LOOK stops and reverses at the highest/lowest requested track (183 or 14)!
• In any numerical question, you don’t need to add 8 individual subtractions for SCAN/LOOK—just calculate |End - Start| + |End - TurnEnd|!