Disk scheduling: FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Average rotational latency? from Lesson 6.2.1
2. Which part of access time can request ordering reduce? from Lesson 6.2.1
3. Which CPU scheduling algorithm can starve long jobs? from Lesson 2.1.2

1 · The Hook

A lift in a tall building doesn't serve floors in the order the buttons were pressed; that would send it up and down for ever. It keeps going in one direction, stopping on the way. Disk arms work the same way, and GATE asks for the total head movement under each algorithm almost every year. One request queue is used for the whole lesson.

3 · Core Concept

Predict First — the answer

45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 cylinders.

In plain words

Every request names a cylinder. The algorithm decides the order in which the arm visits them. Total head movement = sum of the distances travelled. Less movement means less seek time.

Running queue (cylinders 0–199, head at 53): 98, 183, 37, 122, 14, 124, 65, 67.

1. FCFS

Serve in arrival order. Fair, but the arm zig-zags: 640.

2. SSTF (shortest seek time first)

Always go to the nearest pending request: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183. 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236. Like SJF, it can starve far requests.

3. SCAN (elevator)

Move in one direction to the end of the disk, serving requests on the way, then reverse.

• Moving towards 0: 53 → 37 → 14 → 0 → 65 → 67 → 98 → 122 → 124 → 183 = 53 + 183 = 236.
• Moving towards 199: 53 → … → 183 → 199 → 37 → 14 = 146 + 185 = 331.

4. LOOK

Like SCAN, but reverse at the last request, not at the disk's end.

• Towards 199: 53 → … → 183 → 37 → 14 = 130 + 169 = 299.
• Towards 0: 53 → 37 → 14 → 65 → … → 183 = 39 + 169 = 208.

5. C-SCAN (circular SCAN)

Move in one direction to the end, jump back to the other end, and continue in the same direction. Gives more uniform waiting times. Towards 199 (counting the return jump): 53 → … → 183 → 199 → 0 → 14 → 37 = 146 + 199 + 37 = 382.

6. C-LOOK

Like C-SCAN, but go only as far as the last request, then jump to the farthest request at the other side. Towards 199: 53 → … → 183 → 14 → 37 = 130 + 169 + 23 = 322.

Convention used here: the return jump of C-SCAN/C-LOOK is counted. Some questions say not to count it; read carefully.

4 · Visual

SSTF on the running queue (cylinder scale 0 ... 199)

0    14      37         53  65 67           98       122 124              183      199
|----+-------+----------+---+--+------------+--------+---+----------------+--------|
                        53 ->65->67
             37 <------------------                       (nearest after 67 is 37)
     14 <----
     ------------------------------------> 98 --> 122 -> 124 ---------> 183
total = 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236

5 · Worked Examples

Example 1 Easy

Head at 50, requests 40, 60, 10 (FCFS). Total movement?

Solution

10 + 20 + 50 = 80.

Example 2 Medium

Head at 50, requests 40, 60, 10, 90 (SSTF). Order and total?

Solution

40 and 60 are both 10 away; take the lower, 40. From 40: 60 is 20 away, 10 is 30 away → 60. From 60: 90 (30) beats 10 (50). Finally 10. Order 40, 60, 90, 10: 10 + 20 + 30 + 80 = 140.

Example 3 GATE

Running queue, head at 53, C-SCAN moving towards 199, return jump counted. Total?

Solution

146 (53 → 199) + 199 (199 → 0) + 37 (0 → 37) = 382.

6 · GATE Traps

• SCAN goes to the disk's end (0 or 199); LOOK stops at the last request.
• C-SCAN/C-LOOK serve requests in one direction only; check whether the return jump counts.
• SSTF ties: state the rule (here: the lower cylinder).
• Check the initial direction given in the question.

7 · Memory Hook

"FCFS zig-zags, SSTF grabs the nearest, SCAN is a lift to the wall, LOOK turns at the last stop, C- versions only go one way."

8 · Connect the Dots

Disk scheduling decides which request the disk serves. The last lesson looks at how data moves between devices and memory at all: polling, interrupts and DMA, plus buffering and spooling.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — SSTF

Running queue (98, 183, 37, 122, 14, 124, 65, 67), head at 53. Total head movement with SSTF?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — SCAN

Running queue, head at 53, SCAN moving towards 199 first (cylinders 0–199). Total head movement?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — LOOK

Running queue, head at 53, LOOK moving towards 0 first. Total head movement?

Numerical answer: ________

Q4 · NAT · 2 mark(s) — C-LOOK

Running queue, head at 53, C-LOOK moving towards 199, counting the jump. Total head movement?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Starvation

Which disk-scheduling algorithm can starve a request far from the head?

1. (A) SCAN
2. (B) SSTF
3. (C) FCFS
4. (D) C-SCAN

10 · Rule Card

• FCFS: arrival order. SSTF: nearest next (starvation).
• SCAN: sweep to the disk's end, reverse. LOOK: reverse at the last request.
• C-SCAN: sweep to the end, jump to the other end, continue same direction. C-LOOK: jump from last request to the farthest one.
• Running queue (head 53): FCFS 640, SSTF 236, SCAN ↓ 236 / ↑ 331, LOOK ↑ 299 / ↓ 208, C-SCAN ↑ 382, C-LOOK ↑ 322.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

disk schedulingtotal head movementFCFSshortest seek time firstSCAN (elevator)LOOKC-SCANC-LOOKdirection of the sweepcounting the return jump