SCAN and C-SCAN Algorithms: Worked Example, Differences and Exam Traps

Solve the same eight-request queue with SCAN and C-SCAN, then learn how endpoints, direction, circular return, and service order change the answer.

KnowledgeGate Team

Exam prep & CS education

Updated 14 Nov 20266 min read
SCAN and C-SCAN Algorithms: Worked Example, Differences and Exam Traps

SCAN and C-SCAN sound like simple elevator rules, but one missed detail can change an entire numerical. You must know the initial direction, the physical disk boundary, and whether a circular return counts. On tracks 0-199, with head 53 and eight pending requests, the two routes total 331 and 382 tracks because their endpoint and return rules differ. File systems and disk scheduling in OS: 4 algorithms worked connects these routes to allocation, directories and seek time; Disk Scheduling in Operating Systems: 6 Algorithms with Worked Examples compares all six policies on this queue; for SCAN and C-SCAN, check every leg, count the circular return, and reverse the initial direction to expose a second pair of totals.

SCAN and C-SCAN disk scheduling: build the concept before calculating

A disk-scheduling problem specifies pending tracks, the head position, the valid range, and the initial direction. Add the absolute differences between consecutive positions on the complete route to get total head movement. The unit is tracks unless a seek-time conversion is supplied.

SCAN, the elevator algorithm, services requests in the current direction, reaches the physical end, reverses, and services the other side. C-SCAN reaches the end, returns to the opposite end without servicing, and resumes in the original direction. Count that physical circular return unless told otherwise.

SCAN and C-SCAN reach physical endpoints. LOOK turns at the last pending request, while C-LOOK wraps between pending-request limits. SCAN uses directional locality, and C-SCAN aims for more uniform waiting by track position. Neither always minimises movement. These rules sit within CS Fundamentals for Exams & Placements, alongside the operating-systems concepts that distinguish physical head movement from CPU scheduling.

Disk-track number line showing requests, head at 53, and SCAN/C-SCAN endpoint rules.

Prepare the worked example: sort once, then construct each route

Tracks are 0-199, the head is 53, the queue is 98, 183, 37, 122, 14, 124, 65, 67, and direction is upward. Standard SCAN and C-SCAN reach endpoints, and the 199 to 0 C-SCAN return counts.

Sort and partition the requests:

14, 37 | head 53 | 65, 67, 98, 122, 124, 183

Sorting is not the service order. Direction decides which partition comes first. Before calculating, construct the routes:

  • SCAN movement route: 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 37 -> 14

  • SCAN service order: 65, 67, 98, 122, 124, 183, 37, 14

  • C-SCAN movement route: 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 0 -> 14 -> 37

  • C-SCAN service order: 65, 67, 98, 122, 124, 183, 14, 37

Endpoints can appear in a movement route without being requests.

SCAN worked example: calculate every leg and cross-check the total

From

To

Absolute movement

53

65

12

65

67

2

67

98

31

98

122

24

122

124

2

124

183

59

183

199

16

199

37

162

37

14

23

The total is 12 + 2 + 31 + 24 + 2 + 59 + 16 + 162 + 23 = 331 tracks.

Geometric check: upward sweep 199 - 53 = 146; reverse sweep to the lowest request 199 - 14 = 185; total 146 + 185 = 331.

Average movement is 331 / 8 = 41.375 tracks per request, not average waiting time. Endpoint 199 is not a ninth request. With an explicit assumption of 0.2 ms per track, movement time is 331 x 0.2 = 66.2 ms.

C-SCAN worked example: include the circular return

From

To

Absolute movement

53

65

12

65

67

2

67

98

31

98

122

24

122

124

2

124

183

59

183

199

16

199

0

199

0

14

14

14

37

23

The total is 12 + 2 + 31 + 24 + 2 + 59 + 16 + 199 + 14 + 23 = 382 tracks.

Monotonic check: upward sweep 199 - 53 = 146, circular return 199 - 0 = 199, and low-side sweep 37 - 0 = 37. Therefore, 146 + 199 + 37 = 382.

Average movement is 382 / 8 = 47.75 tracks per request. C-SCAN moves 382 - 331 = 51 more here, but is not universally worse. It targets more uniform service direction, not minimum movement on every queue.

Side-by-side SCAN and C-SCAN routes show totals of 331 and 382 tracks; C-SCAN includes the unserviced 199-to-0 return.

SCAN vs C-SCAN vs LOOK: compare behaviour, not only totals

Feature

SCAN

C-SCAN

LOOK and C-LOOK

Service direction

Both, after reversal

One direction only

LOOK uses both; C-LOOK uses one

Endpoint behaviour

Reaches physical end

Reaches both physical ends

Uses last-request limits

Return-path servicing

Yes

No during circular return

LOOK yes; C-LOOK no during wrap

Running service order

65, 67, 98, 122, 124, 183, 37, 14

65, 67, 98, 122, 124, 183, 14, 37

Depends on variant

Running total

331

382

Different route and total

Waiting behaviour

Can favour the current sweep

Generally more uniform by position

Depends on request limits

Under SCAN, a request just behind the head may wait through the outward sweep. C-SCAN approaches tracks in one service direction, so waiting is generally more uniform by position. Actual waiting still depends on arrivals and implementation.

Do not import CPU-scheduling language into this numerical. CPU scheduling orders processes using time and policy. Disk scheduling orders physical head movement across track positions.

Disk-scheduling traps: fix the assumption before the arithmetic

  • Turning at request 183: The calculation becomes (183 - 53) + (183 - 14) = 130 + 169 = 299. That is LOOK, not standard SCAN, because the route never reaches 199.

  • Omitting 199 -> 0: C-SCAN incorrectly falls from 382 to 183. Count the 199-track return unless told otherwise.

  • Following written queue order: Upward movement services 65 before 37. Sort first, then apply direction.

  • Treating 183 as the disk maximum: It is only the maximum request. The physical maximum here is 199. A range of 0-499 would change endpoint-based totals.

  • Using signed differences: Every leg uses an absolute difference. Movement cannot be negative.

  • Using the wrong denominator: Divide by eight requests, not by route positions or boundaries. Duplicate requests at one track remain separate requests, with zero extra movement between them.

Write the route, calculate each leg, and finish with a monotonic-segment cross-check.

How exam-style questions test SCAN and C-SCAN

Questions may ask for service order, total or average movement, route identification, SCAN versus LOOK, circular-return servicing, or fairness. Here the quick checks are 331, 382, and a 51-track difference.

Assertion: upward C-SCAN services 14 and 37 only after reaching 199 and returning to 0. Reason: it services in one direction and not during the circular return. Both are true, and the reason explains the assertion.

Route 53 -> ... -> 183 -> 37 -> 14 is LOOK because it reverses at 183. Practise with Disk Scheduling MCQs: FCFS, SSTF and SCAN. The linked set contains 12 solved questions across FCFS, SSTF and SCAN.

SCAN and C-SCAN: the short version and next step

Use this five-step scratch method:

  1. Write the track range and head position.

  2. Mark the initial direction.

  3. Sort and partition the requests.

  4. Insert required endpoints and any circular return.

  5. Sum absolute movements, then cross-check by monotonic segments.

The anchors are simple: upward SCAN is 331, upward C-SCAN is 382, and their averages across eight requests are 41.375 and 47.75.

Reverse the direction as a check. Downward SCAN visits 37, 14, 0, then 65, 67, 98, 122, 124, 183, for (53 - 0) + (183 - 0) = 236 tracks. Downward C-SCAN follows 53 -> 37 -> 14 -> 0 -> 199 -> 183 -> 124 -> 122 -> 98 -> 67 -> 65, for 53 + 199 + (199 - 65) = 386 tracks.

For structured semester-level core CS, continue with the Zero to Hero Complete CS Course. Keep movement route and service order separate.