Disk Scheduling

14 min read2,644 words

Disk Scheduling

1. What is Disk Scheduling?

Disk scheduling is the operating system technique used to decide which disk I/O request should be serviced first when multiple requests are waiting.

This is especially important for HDDs, where the disk head physically moves between tracks.

Simple example:

Pending requests: 98, 183, 37, 122, 14, 65, 67 Current head = 53

The OS must decide:

Which request should be served first? Which one next? Which order minimizes movement?

That decision is called disk scheduling.

2. Why Is Disk Scheduling Needed?

Suppose the disk head is at track 50.

Requests are:

10 20 80 90

If the OS processes them randomly:

50 → 10 → 90 → 20 → 80

The head travels a lot.

Instead, a better order might be:

50 → 80 → 90 → 20 → 10

Less unnecessary movement means:

  • lower seek time
  • better performance
  • better throughput
  • shorter waiting time

3. HDD Structure

A simplified HDD:

Disk ┌─────────────────┐ │ Track 0 │ │ Track 1 │ │ Track 2 │ │ Track 3 │ │ ... │ │ Track 199 │ └─────────────────┘ ↑ Disk Head

The head moves between tracks.

For example:

Track 20 ←──────── Head ────────→ Track 150

4. Important Disk Terms

Track

A circular path on an HDD platter.

Sector

A subdivision of a track.

Seek

Movement of the disk head to the required track.

Seek Time

Time required to move the disk head to the desired track.

Rotational Latency

Time waiting for the required sector to rotate under the head.

Transfer Time

Time required to actually transfer the data.

5. Total Disk Access Time

A simplified model is:

Disk Access Time = Seek Time + Rotational Latency + Transfer Time + Controller/queue overhead

For HDDs, seek time can be a major factor.

6. Disk Scheduling Algorithms

The major algorithms are:

Disk Scheduling │ ├── FCFS ├── SSTF ├── SCAN ├── C-SCAN ├── LOOK └── C-LOOK

Let's study each one.

7. FCFS — First Come First Serve

FCFS services requests in the order they arrive.

Example:

Requests: 98, 183, 37, 122, 14, 65, 67 Initial head = 53

FCFS order:

53 → 98 → 183 → 37 → 122 → 14 → 65 → 67

It doesn't try to optimize head movement.

8. FCFS Calculation

Calculate each movement:

53 → 98 = 45 98 → 183 = 85 183 → 37 = 146 37 → 122 = 85 122 → 14 = 108 14 → 65 = 51 65 → 67 = 2

Total:

45 + 85 + 146 + 85 + 108 + 51 + 2 = 522 tracks

Therefore:

Total head movement = 522 tracks

9. Advantages of FCFS

  • Very simple
  • Easy to implement
  • Fair in arrival order
  • No starvation caused by scheduling priority

10. Disadvantages of FCFS

  • Poor performance
  • Large head movement
  • High average waiting time
  • Does not optimize disk access

Memory trick

FCFS = Come first → Serve first

11. SSTF — Shortest Seek Time First

SSTF selects the request closest to the current head position.

Suppose:

Current = 53 Requests: 98, 183, 37, 122, 14, 65, 67

Distances:

98 → |98 - 53| = 45 183 → 130 37 → 16 122 → 69 14 → 39 65 → 12 67 → 14

Closest:

65

So:

53 → 65

Now current position is 65.

Remaining:

98, 183, 37, 122, 14, 67

Closest is:

67

So:

65 → 67

Then:

67 → 37

and so on.

One possible SSTF sequence is:

53 → 65 → 67 → 37 → 14 → 98 → 122 → 183

12. SSTF Calculation

Movement:

53 → 65 = 12 65 → 67 = 2 67 → 37 = 30 37 → 14 = 23 14 → 98 = 84 98 → 122 = 24 122 → 183 = 61

Total:

12 + 2 + 30 + 23 + 84 + 24 + 61 = 236 tracks

So SSTF is much better than the FCFS example in terms of total head movement.

13. Advantages of SSTF

  • Reduces average seek time
  • Usually better performance than FCFS
  • Simple concept

14. Disadvantages of SSTF

The biggest problem is starvation.

Suppose requests keep arriving close to the current head:

Head = 50 Requests: 51, 52, 53, 54, 55...

A request at:

180

may keep getting ignored.

So:

SSTF can cause starvation.

Memory trick

SSTF = Serve the nearest request

15. SCAN Algorithm

SCAN is also called the Elevator Algorithm.

Why?

Because the disk head behaves somewhat like an elevator:

↑ ↑ ↑ ↓ ↓ ↓

It moves in one direction, servicing requests along the way.

When it reaches the end of the disk, it reverses direction.

16. SCAN Example

Suppose:

Disk = 0–199 Head = 53 Requests: 98, 183, 37, 122, 14, 65, 67

Assume the head is moving toward higher track numbers.

Requests greater than 53:

65, 67, 98, 122, 183

Requests less than 53:

37, 14

SCAN moves:

53 ↓ 65 ↓ 67 ↓ 98 ↓ 122 ↓ 183 ↓ 199 ↓ 37 ↓ 14

The important point is:

SCAN goes all the way to the disk end before reversing.

17. SCAN Diagram

0 199 |----------------------------------------------| 14 37 53 65 67 98 122 183 ↑ Head Direction → 53 → 65 → 67 → 98 → 122 → 183 → 199 Direction ← 199 → 37 → 14

18. Advantages of SCAN

  • Better than FCFS
  • More predictable than SSTF
  • Reduces starvation
  • Provides more uniform waiting times

19. Disadvantages of SCAN

  • May travel to the disk end unnecessarily
  • Requests just behind the head may wait
  • More movement than necessary in some cases

Memory trick

SCAN = Go to end → Reverse

20. C-SCAN — Circular SCAN

C-SCAN means Circular SCAN.

Instead of reversing direction after reaching the end, the head returns to the beginning and continues in the same direction.

Example:

0 199 |----------------------------------------------| → → → → → → → → → → → →

Suppose:

Head = 53 Direction = right

It services:

65 → 67 → 98 → 122 → 183

Then reaches:

199

Instead of reversing:

199 → 0

Then continues:

0 → 14 → 37

21. C-SCAN Diagram

0 199 |----------------------------------------------| ↑ ↓ 37 14 183 122 98 ↑ 53 → 65 → 67 | └───────────────

Conceptually:

53 → 65 → 67 → 98 → 122 → 183 → 199 ↓ 0 ↓ 14 → 37

22. Why C-SCAN?

SCAN provides different waiting times depending on where the request is located.

C-SCAN provides a more uniform service pattern because it services requests in one direction.

Memory trick

C-SCAN = SCAN + Circular return

23. LOOK Algorithm

LOOK is similar to SCAN, but it does not go all the way to the physical end of the disk if there are no requests there.

This is the key difference.

Suppose:

Disk = 0–199 Head = 53 Requests: 14, 37, 65, 67, 98, 122, 183

Moving right:

53 → 65 → 67 → 98 → 122 → 183

At 183, there are no more requests in that direction.

LOOK immediately reverses:

183 → 37 → 14

It does not go to 199 first.

24. SCAN vs LOOK

SCAN

53 → ... → 183 → 199 → reverse

LOOK

53 → ... → 183 → reverse

Therefore:

LOOK looks for the last request instead of going to the physical disk end.

Memory trick

SCAN = reaches end

LOOK = looks for last request

25. C-LOOK

C-LOOK is the circular version of LOOK.

It moves in one direction.

When it reaches the highest pending request, it jumps to the lowest pending request and continues in the same direction.

Example:

53 → 65 → 67 → 98 → 122 → 183 ↓ 14 ↓ 37

Notice:

183 → 14

It does not need to travel physically through every track between them as a servicing sweep.

26. C-SCAN vs C-LOOK

C-SCAN

53 → ... → 183 → 199 ↓ 0 ↓ 14

C-LOOK

53 → ... → 183 ↓ 14

Therefore:

C-LOOK does not go to the physical ends unless required.

27. Complete Comparison

AlgorithmDirectionReverses?Goes to disk end?Starvation
FCFSArrival orderNot applicableNoNo
SSTFNearest requestVariableNoPossible
SCANBoth directionsYesYesLow
C-SCANOne directionNoYesLow
LOOKBoth directionsYesNoLow
C-LOOKOne directionNoNoLow

28. Visual Comparison

FCFS 53 → 98 → 183 → 37 → 122 → 14 → 65 → 67
SSTF 53 → nearest → nearest → nearest...
SCAN 53 → → → → → → 199 ↓ ← ← ←
C-SCAN 53 → → → → → → 199 ↓ 0 → → →
LOOK 53 → → → → → 183 ↓ ← ← ←
C-LOOK 53 → → → → → 183 ↓ 14 → → →

29. Important Numerical Problem

Let's solve one completely.

Given:

Disk range = 0–199 Initial head = 53 Request queue: 98, 183, 37, 122, 14, 65, 67

Assume initial direction is toward higher track numbers.

FCFS

Order:

53 → 98 → 183 → 37 → 122 → 14 → 65 → 67

Total:

|53-98| + |98-183| + |183-37| + |37-122| + |122-14| + |14-65| + |65-67| = 45 + 85 + 146 + 85 + 108 + 51 + 2 = 522 tracks

SSTF

One valid sequence:

53 → 65 → 67 → 37 → 14 → 98 → 122 → 183

Total:

12 + 2 + 30 + 23 + 84 + 24 + 61 = 236 tracks

SCAN

Moving right:

53 → 65 → 67 → 98 → 122 → 183 → 199

Then reverse:

199 → 37 → 14

Total:

(199 - 53) + (199 - 14)
146 + 185 = 331 tracks

LOOK

Moving right:

53 → 65 → 67 → 98 → 122 → 183

Reverse:

183 → 37 → 14

Total:

(183 - 53) + (183 - 14)
130 + 169 = 299 tracks

30. Important Point About SCAN/C-SCAN Calculations

When solving exam problems, always check:

  1. Disk range
  2. Initial head position
  3. Initial direction
  4. Request queue
  5. Whether the algorithm reaches the physical end
  6. Whether the algorithm jumps or physically traverses during circular return
  7. Whether the question counts the return movement

Different textbooks/questions can describe circular movement slightly differently, so follow the convention specified in the question.

31. Seek Time

Seek time is the time required for the head to move to the desired track.

If:

Head = 50 Request = 120

Head movement:

|120 - 50| = 70 tracks

If average movement is known:

Average seek time ≈ Average head movement × time per track

For example, if:

Average movement = 100 tracks Time per track = 0.1 ms

Then:

100 × 0.1 = 10 ms

32. Rotational Latency

After the head reaches the correct track, the required sector may not be directly under the head.

The platter must rotate.

Seek ↓ Correct track ↓ Wait for sector ↓ Data transfer

This waiting period is rotational latency.

For a disk rotating at RPM:

Time for one revolution = 60 / RPM seconds

Average rotational latency is approximately:

Average rotational latency ≈ Half of one revolution

So:

Average latency ≈ 30 / RPM seconds

or:

Average latency ≈ 30000 / RPM milliseconds

Example for 7200 RPM:

30000 / 7200 ≈ 4.17 ms

33. Total Disk Access Time

Simplified:

Disk Access Time = Seek Time + Rotational Latency + Transfer Time

For example:

Seek time = 6 ms Rotational latency = 4 ms Transfer time = 1 ms

Then:

Total = 6 + 4 + 1 = 11 ms

34. Why Disk Scheduling Is More Important for HDDs

HDD:

Mechanical movement ↓ Head movement costs time ↓ Scheduling can significantly reduce movement

SSD:

No moving head ↓ No traditional seek movement ↓ Classical disk scheduling is less important

However, SSDs still have I/O queues and scheduling mechanisms, just with different performance considerations.

35. Disk Scheduling Goals

The OS tries to:

1. Minimize seek time

Less head movement

2. Minimize waiting time

Requests should not wait unnecessarily.

3. Maximize throughput

More I/O operations per unit time

4. Provide fairness

Requests should get service.

5. Avoid starvation

A request shouldn't wait indefinitely.

36. FCFS vs SSTF vs SCAN

FeatureFCFSSSTFSCAN
SimpleExcellentGoodModerate
PerformanceLowGoodGood
StarvationNoPossibleLow
FairnessGood arrival fairnessLowerGood
Head movementHighLowerControlled
ComplexityVery lowLowModerate

37. Most Important Differences

FCFS

Arrival order

SSTF

Closest request

SCAN

Move → End → Reverse

C-SCAN

Move → End → Jump/return → Continue same direction

LOOK

Move → Last request → Reverse

C-LOOK

Move → Last request → Lowest request → Continue

🧠 Exam Revision

Definition

Disk scheduling is an operating-system technique that determines the order in which pending disk I/O requests are serviced to improve disk performance and reduce access time.

Algorithms

FCFS ↓ First request first SSTF ↓ Shortest seek first SCAN ↓ Go to end + reverse C-SCAN ↓ Go to end + circular return LOOK ↓ Go to last request + reverse C-LOOK ↓ Go to last request + circular jump

Memory trick

F-S-S-C-L-C

Think:

First → Shortest → Sweep → Circular → Look → Circular Look.

Most important formulas

Head Movement = Sum of |Current Position - Next Position|
TAT = CT − AT

That second formula is for CPU scheduling, not disk scheduling—don't mix them up.

For disk scheduling:

Total Head Movement = Σ |Current Track − Next Track|

And:

Disk Access Time ≈ Seek Time + Rotational Latency + Transfer Time

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy