Disk Scheduling with SCAN vs. C-SCAN

🤖 Smarter Hard Drives: Disk Scheduling with SCAN vs. C-SCAN

Hello, CSE students! Let's talk about one of the slowest parts of a computer: the hard drive. A physical hard drive (HDD) has a read/write arm that has to physically move across the disk's surface (platter) to find data. This movement is called seek time, and it's a major bottleneck.

To make this faster, the Operating System doesn't just process I/O requests in the order they arrive. Instead, it uses Disk Scheduling Algorithms to optimize the arm's movement.

Today, we'll solve a problem using two of the most popular algorithms: SCAN (Elevator) and C-SCAN (Circular SCAN).

The Problem

We have a queue of requests for different disk tracks, and we know where the read/write arm is right now.

• Request Queue: 82, 170, 43, 140, 24, 16, 190
• Initial Head Position: 50
• Initial Direction: Moving "towards the larger value" (i.e., moving up)
• Disk Size Assumption: For these algorithms, we must know the disk's boundaries. We'll assume a standard disk range of 0 to 199.

For clarity, let's look at the requests in sorted order: 16, 24, 43, 82, 140, 170, 190.

---

1. SCAN (The Elevator Algorithm)

The Logic: The SCAN algorithm works just like an elevator. The disk arm moves in one direction, servicing all requests in its path until it hits the end of the disk. Then, it reverses direction and services all remaining requests on its way back.

Step-by-Step Solution:

1. Start: The head is at 50, moving UP (towards 199).
2. Move Up: It services all requests in its path: 82, 140, 170, 190.
3. Hit the End: After servicing 190, it continues to the end of the disk, 199.
4. Reverse: The arm reverses direction (now moving DOWN, towards 0).
5. Move Down: It services all remaining requests in its path: 43, 24, 16.
6. Stop: It stops at 16, the last request.

Here is a visual graph of the head's movement for SCAN:

(Remember to create and upload your graph here!)

• Full Path: 50 -> 82 -> 140 -> 170 -> 190 -> 199 -> 43 -> 24 -> 16
• Calculating Total Head Movement:

  We can calculate this in two parts:
  1. The entire move up: (199 - 50) = 149
  2. The entire move back down: (199 - 16) = 183

• Total = 149 + 183 = 332

---

2. C-SCAN (Circular SCAN)

The Logic: C-SCAN is a variation designed to be "fairer" and provide a more uniform wait time. It also moves in one direction, servicing requests. However, when it hits the end (199), it does not service requests on the way back. Instead, it jumps all the way back to the beginning (0) and then starts scanning in the same (UP) direction again.

Step-by-Step Solution:

1. Start: The head is at 50, moving UP.
2. Move Up: It services all requests in its path: 82, 140, 170, 190.
3. Hit the End: It continues to the end of the disk, 199.
4. Circular Jump: The arm immediately jumps from 199 to the other end of the disk, 0, without servicing anything.
5. Move Up (Again): From 0, it continues moving UP and services all remaining requests: 16, 24, 43.
6. Stop: It stops at 43, the last request in this sweep.

Here is a visual graph of the head's movement for C-SCAN:

(Remember to create and upload your graph here!)

• Full Path: 50 -> 82 -> 140 -> 170 -> 190 -> 199 -> 0 -> 16 -> 24 -> 43
• Calculating Total Head Movement:

  We calculate this in three parts:
  1. Initial move up to the end: (199 - 50) = 149
  2. The circular jump: (199 - 0) = 199
  3. The move from the start to the last request: (43 - 0) = 43

• Total = 149 + 199 + 43 = 391

---

💻 Dynamic Example: Try It Yourself!

Enter your own values to see how the algorithms adjust. The simulator will now draw a graph of the head's movement in addition to the text output.

Request Queue (e.g., 82, 170, 43): Head Start Position: Max Disk Track (e.g., 199): Initial Direction: Towards Larger Value Towards Smaller Value

Simulation Log:

Click a button to run a simulation...

Graphical Presentation (Track vs. Step): Your browser does not support the canvas element.

---

🧠 Check Your Knowledge: Quick Quiz

Test your understanding! Click a button to see the answer.

Question 1:

What is the common nickname for the SCAN algorithm?

Question 2:

In our C-SCAN problem, what track did the head visit immediately after hitting the end (track 199)?

Question 3:

Why is C-SCAN often considered "fairer" than SCAN?

---

Final Thoughts

• SCAN is efficient, but requests that just missed the elevator have to wait for the arm to go all the way to the end and come all the way back.
• C-SCAN prevents this "starvation" of requests at the extremes by always sweeping in one direction. This leads to a more predictable and fair wait time for all requests.

Happy scheduling!