Skills101

AdvancedOperating Systems · Lesson 13 of 17 · Updated ·

Disk Scheduling Numericals — LOOK, C-LOOK, SCAN, C-SCAN and Disk Access Time

Lesson 8 solved FCFS, SSTF, SCAN and C-SCAN. Two more algorithms appear in almost every exam — LOOK and C-LOOK — and questions often add a second part: "how long does it take?" This lesson solves all six on one queue and then converts head movement into milliseconds.

1. The question

A disk has cylinders 0 to 199. The head is at cylinder 50 and is moving towards higher cylinder numbers. The request queue (in arrival order) is:

82, 170, 43, 140, 24, 16, 190

Find the total head movement for each algorithm.

Head movement is the sum of the distances between consecutive positions: |82 − 50| + |170 − 82| + … Before you start, split the requests into two groups — this makes the "elevator" algorithms quick:

  • Above 50: 82, 140, 170, 190
  • Below 50: 43, 24, 16

2. FCFS and SSTF (quick revision)

FCFS serves in arrival order: 50 → 82 → 170 → 43 → 140 → 24 → 16 → 190. Movement = 32 + 88 + 127 + 97 + 116 + 8 + 174 = 642 cylinders.

SSTF always goes to the nearest pending request. From 50, the nearest is 43 (distance 7), then 24, then 16; from 16 the nearest is 82, then 140, 170, 190. Path: 50 → 43 → 24 → 16 → 82 → 140 → 170 → 190 = 7 + 19 + 8 + 66 + 58 + 30 + 20 = 208.

SSTF is good on average but can starve requests far from the head if new nearby requests keep arriving.

3. SCAN (elevator)

The head moves in one direction, serving requests, all the way to the last cylinder (199), then reverses.

Path: 50 → 82 → 140 → 170 → 190 → 199 → 43 → 24 → 16. Movement = (199 − 50) + (199 − 16) = 149 + 183 = 332.

Shortcut: go to the end and come back to the furthest request on the other side.

4. LOOK

LOOK is SCAN without the wasted trip: it reverses at the last request in the current direction, not at the disk's edge.

LOOK disk scheduling path from 50 up through 82, 140, 170 and 190, then reversing down to 43, 24 and 16: 314 cylinders of head movement

Path: 50 → 82 → 140 → 170 → 190 → 43 → 24 → 16. Movement = (190 − 50) + (190 − 16) = 140 + 174 = 314.

LOOK saves exactly the 2 × 9 = 18 cylinders that SCAN spent going from 190 to 199 and back.

5. C-SCAN (circular SCAN)

C-SCAN serves requests only while moving up. At cylinder 199 it jumps straight back to cylinder 0 and starts moving up again. This gives more uniform waiting times: a request just behind the head waits at most one sweep.

Path: 50 → 82 → 140 → 170 → 190 → 199 → 0 → 16 → 24 → 43. Movement = (199 − 50) + (199 − 0) + (43 − 0) = 149 + 199 + 43 = 391.

Does the return jump count? Books differ. If the question says the return is not counted (or is "very fast"), the answer is 391 − 199 = 192. Always state which convention you used.

6. C-LOOK

C-LOOK is C-SCAN without visiting the edges: go up to the last request (190), jump to the lowest pending request (16), and continue upward.

C-LOOK disk scheduling path: up from 50 to 190, a dashed jump back to 16, then up to 24 and 43: 341 cylinders including the jump

Path: 50 → 82 → 140 → 170 → 190 → 16 → 24 → 43. Movement = (190 − 50) + (190 − 16) + (43 − 16) = 140 + 174 + 27 = 341 (or 167 if the jump is not counted).

7. Check every answer with Python

def head_movement(policy, requests, head, max_cyl=199):
    up = sorted(r for r in requests if r >= head)
    down = sorted(r for r in requests if r < head)
    if policy == "FCFS":
        path = [head] + requests
    elif policy == "SSTF":
        path, left = [head], list(requests)
        while left:
            nearest = min(left, key=lambda r: abs(r - path[-1]))
            path.append(nearest)
            left.remove(nearest)
    elif policy == "SCAN":
        path = [head] + up + [max_cyl] + down[::-1]
    elif policy == "LOOK":
        path = [head] + up + down[::-1]
    elif policy == "C-SCAN":
        path = [head] + up + [max_cyl, 0] + down
    else:  # C-LOOK
        path = [head] + up + down
    return sum(abs(b - a) for a, b in zip(path, path[1:])), path

queue = [82, 170, 43, 140, 24, 16, 190]
for p in ("FCFS", "SSTF", "SCAN", "LOOK", "C-SCAN", "C-LOOK"):
    total, path = head_movement(p, queue, 50)
    print(f"{p:7}{total:4}  {path}")
FCFS    642  [50, 82, 170, 43, 140, 24, 16, 190]
SSTF    208  [50, 43, 24, 16, 82, 140, 170, 190]
SCAN    332  [50, 82, 140, 170, 190, 199, 43, 24, 16]
LOOK    314  [50, 82, 140, 170, 190, 43, 24, 16]
C-SCAN  391  [50, 82, 140, 170, 190, 199, 0, 16, 24, 43]
C-LOOK  341  [50, 82, 140, 170, 190, 16, 24, 43]

To solve a question where the head moves down first, mirror the disk: replace every cylinder c (and the head) with 199 − c, run the same code, and the totals come out right.

8. From cylinders to milliseconds

The time to read one block has three parts:

Access time = seek time + rotational latency + transfer time

PartWhat it isHow to compute
Seek timemoving the arm to the right cylindergiven, or cylinders × time per cylinder
Rotational latencywaiting for the sector to come under the headon average half a rotation
Transfer timereading the sectors as they pass(sectors to read / sectors per track) × rotation time

Worked example. A disk spins at 7200 RPM, has 500 sectors per track of 512 bytes, and an average seek time of 5 ms. How long does it take to read a 4 KB block?

  1. One rotation = 60,000 ms / 7200 = 8.33 ms.
  2. Average rotational latency = 8.33 / 2 = 4.17 ms.
  3. 4 KB = 4096 / 512 = 8 sectors → transfer = 8/500 × 8.33 = 0.13 ms.
  4. Access time = 5 + 4.17 + 0.13 ≈ 9.3 ms.

Seek and rotation dominate; the actual reading is tiny. That is exactly why disk scheduling (which reduces seeking) matters on hard disks — and why it matters much less on SSDs, which have no moving arm.

Seek time from head movement. If moving one cylinder takes 0.1 ms, SSTF's 208 cylinders cost 20.8 ms of seeking, while FCFS's 642 cylinders cost 64.2 ms — three times longer for the same seven requests.

9. Which algorithm is used when?

AlgorithmStrengthWeakness
FCFSfair, simplelots of movement
SSTFlow movementstarvation possible
SCAN / LOOKno starvation, good throughputrequests just passed wait a full sweep and back
C-SCAN / C-LOOKmost uniform waiting timethe return jump adds movement

Common mistakes

  • Going to the disk edge (199) in LOOK, or not going to it in SCAN.
  • Forgetting the head's starting direction — the answer changes completely.
  • In C-SCAN and C-LOOK, serving requests on the way back. The return trip serves nothing.
  • Not saying whether the return jump is counted.
  • Using a full rotation instead of half a rotation for average latency.

Quick recap

  • On this queue: FCFS 642, SSTF 208, SCAN 332, LOOK 314, C-SCAN 391 (192 without the jump), C-LOOK 341 (167 without the jump).
  • SCAN/C-SCAN touch the disk edge; LOOK/C-LOOK turn at the last request.
  • Circular versions serve in one direction only and give more uniform waiting.
  • Access time = seek + rotational latency (half a rotation) + transfer.

Practice what you learned

📝 Quiz: Disk Scheduling Numericals5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →