FCFS and SSTF Disk Scheduling: Worked Examples and Exam Traps

Trace FCFS and SSTF on the same queue, compare 640 with 236 cylinders, and learn how to handle ties, arrivals, starvation and common traps.

KnowledgeGate Team

Exam prep & CS education

Updated 3 Nov 20265 min read
FCFS and SSTF Disk Scheduling: Worked Examples and Exam Traps

FCFS and SSTF can start from the same head position and queue but produce different service orders and totals. Learners often copy the queue into SSTF, sort it once, or add cylinder numbers instead of absolute movements. The same eight requests produce 640 cylinders under FCFS and 236 under SSTF. The earlier Disk Scheduling in Operating Systems: 6 Algorithms with Worked Examples compares all six algorithms on this queue; tie rules, dynamic arrivals, starvation, and a counterexample to SSTF optimality expose the narrower FCFS/SSTF edge cases.

FCFS and SSTF solve a disk-head ordering problem

A request identifies a cylinder. From head h to request r, movement is |r-h|; add these consecutive movements for the total. Seek time, rotational latency and transfer time are separate. Convert only under a supplied model.

FCFS, or First Come, First Served, follows queue order. It prevents later arrivals from bypassing waiting work but may cause large reversals. SSTF, or Shortest Seek Time First, selects the nearest pending request and recomputes from the new head. This greedy rule need not find the globally shortest route.

Point

FCFS

SSTF

Selection rule

Queue order

Nearest pending request

Recompute after service

No

Yes

Uses arrival order

Yes

Only for a stated tie

Needs a tie rule

No

Sometimes

Starvation risk

No later-arrival bypass

Possible

Needs initial direction

No

No

Neither needs the initial direction used by SCAN-family questions. CPU FCFS instead schedules bursts and measures waiting time.

Work FCFS from the request queue without reordering it

Cylinders range from 0 to 199, the head starts at 53, and all requests are pending in order 98, 183, 37, 122, 14, 124, 65, 67. The endpoints are context only and are not visited.

FCFS path: 53 -> 98 -> 183 -> 37 -> 122 -> 14 -> 124 -> 65 -> 67

Leg

Movement

53 -> 98

|98-53|=45

98 -> 183

|183-98|=85

183 -> 37

|37-183|=146

37 -> 122

|122-37|=85

122 -> 14

|14-122|=108

14 -> 124

|124-14|=110

124 -> 65

|65-124|=59

65 -> 67

|67-65|=2

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

Average movement is 640/8 = 80 cylinders per request, not 640 ms without a conversion.

Recompute the nearest pending request at every SSTF step

Start again at 53, measuring every distance from the current head.

Current

Choice

Movement

53

65

12

65

67

2

67

37

30

37

14

23

14

98

84

98

122

24

122

124

2

124

183

59

At 67, the shrinking pending set puts 37 at distance 30, narrowly ahead of 98 at 31. Recomputing produces:

53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183

12+2+30+23+84+24+2+59 = 236 cylinders; average 236/8 = 29.5. All eight requests appear once, giving eight terms because the initial head is not a request.

Compare the answers without claiming SSTF is always best

Policy

Path

Total

Average

FCFS

53 -> 98 -> 183 -> 37 -> 122 -> 14 -> 124 -> 65 -> 67

640

80

SSTF

53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183

236

29.5

The difference is 640-236 = 404 cylinders. FCFS reverses 183 -> 37 = 146 and 14 -> 124 = 110; SSTF first clears 65 and 67.

SSTF is not globally optimal. For head=50, queue {40,0,51,100}, it takes 50 -> 51 -> 40 -> 0 -> 100 for 1+11+40+100=152. The valid route 50 -> 40 -> 0 -> 51 -> 100 gives 10+40+51+49=150.

If a question assumes 0.2 ms per cylinder and ignores other delays, FCFS is 640 x 0.2 = 128 ms and SSTF 236 x 0.2 = 47.2 ms. This linear model is not a physical law.

A two-row cylinder-axis diagram compares FCFS and SSTF scheduling, showing totals of 640 and 236 cylinders and a 404-cylinder difference.

Handle SSTF ties, dynamic arrivals and starvation explicitly

For head=50 with requests 40, 60, 61, both 40 and 60 are 10 away. SSTF alone cannot choose. A lower-cylinder rule gives 50 -> 40 -> 60 -> 61, totalling 10+20+1=31. If earlier arrival wins and 60 arrived first, 50 -> 60 -> 61 -> 40 totals 10+1+21=32. Follow the supplied rule, state an allowed assumption, or call the answer underdetermined.

With timed arrivals, FCFS appends behind waiting requests. SSTF considers only arrived, pending requests. A closer future request is unavailable.

Now start at 50 with 180 and 49 pending. Before later decisions, nearby requests arrive: 51, 48, 52, 47, 53. SSTF serves 50 -> 49 -> 51 -> 48 -> 52 -> 47 -> 53 for 1+2+3+4+5+6=21; 180 remains pending through six choices. If arrivals stop, 53 -> 180=127. If nearer arrivals continue indefinitely, 180 can starve. Six choices alone do not prove infinite starvation.

A six-decision SSTF starvation strip shows request 180 pending while the head moves from 50 to 53 with 21 cylinders of near-request movement.

How exam-style questions test FCFS and SSTF

Tasks may derive a path and total, choose the next request, compare policies, apply ties or arrivals, convert under a stated model, or judge fairness, starvation, optimality and direction.

Use this routine:

  1. Copy the head and requests; identify a static or timed queue.

  2. State the policy and build the sequence first.

  3. For SSTF, shrink the pending set and recompute each time.

  4. Add one absolute movement per request; check each appears once.

Practise with Disk Scheduling MCQs. These examples are illustrative, not official items. Check current requirements on the examination's official site.

Avoid the mistakes that change the service path

  • Smallest cylinder first for FCFS: Preserve queue order.

  • Sort once for SSTF: Recompute each time.

  • Measure SSTF from 53: Use the current head.

  • Add destinations: Add consecutive absolute differences.

  • Choose 98 from 67: Choose 37, distance 30 versus 31.

  • Drop a reversal: 183 -> 37=146; 14 -> 124=110.

  • SSTF is always optimal: The 152 versus 150 example disproves it.

  • Starvation is inevitable: It needs continued nearer arrivals.

  • Visit 0 or 199: Do so only under an explicit rule.

  • Call 640 cylinders time: Convert only when instructed.

Eight requests require eight movement terms, a quick check for incomplete paths.

FCFS and SSTF: the short version and next step

Recall: current head, pending set, policy, full path, absolute movements, fairness. FCFS begins 53 -> 98 and totals 640; SSTF begins 53 -> 65 -> 67 and totals 236.

Reverse only the queue to 67, 65, 124, 14, 122, 37, 183, 98. FCFS gives 14+2+59+110+108+85+146+85 = 609 cylinders. SSTF keeps its path and 236 total because the static pending set is unchanged. Thus order matters to FCFS, not SSTF here.

Continue at CS Fundamentals. Zero to Hero Complete CS Course is an optional broader route; CS Fundamentals for Placements by Sanchit Sir is the placement-focused option.

Go deeper with the full courseOperating System

Keep learning

Discussion