I/O scheduling: disk head movement and latency
Goals and model
Trace common disk scheduling policies, count total head movement under explicit endpoint rules, and distinguish seek, rotational, transfer and queueing time. Prerequisite: ordering numbers and absolute differences. These are mechanical-disk teaching models; SSDs do not have moving heads or rotational latency. CPU scheduling and I/O scheduling select different resources, even when policy names sound similar.
Unless stated otherwise, every request in a trace is pending initially, requests name cylinders, all are serviced once, no new requests arrive, and transfer/rotation costs are ignored when counting head movement. The head starts at 50 on cylinders 0 through 99. Stop measuring as soon as the last pending request is served. A traversal's endpoints, direction and whether wrap travel is charged must be specified.
1. An elevator for cylinders
An elevator travels between numbered floors. Serving the nearest waiting passenger can reduce the next trip but can repeatedly postpone distant passengers when new calls keep appearing. A disk arm similarly moves between cylinders. Movement from x to y is |x−y|; total movement is the sum of consecutive legs, not final position minus initial position. A path can end near its start after substantial travel.
Use the pending arrival-order list 70,10,90,20,55. FCFS preserves that list:
50→70→10→90→20→55.
The legs are 20,60,80,70,35, totaling 265 cylinders. This is a distance measure, not milliseconds; mapping it to time needs a seek model. FCFS does not promise minimal movement.
2. SSTF recomputes from the current position
Shortest seek time first, under this distance proxy, chooses the pending request closest to the current cylinder. With the same workload:
50→55→70→90→20→10.
Distances are 5+15+20+70+10=120. At 90, only 10 and 20 remain, so choose 20 even though it was not next in arrival order. For ties this lesson chooses the lower cylinder; this workload has no SSTF tie. Do not sort requests just once by their distance from the initial head position.
With a continuing arrival stream, repeated nearby arrivals can starve distant requests under SSTF. The finite all-initially-pending example will finish; its short path does not prove starvation freedom in an open system or global optimality of the greedy policy.
3. SCAN and LOOK have different reversal points
SCAN sweeps in one direction servicing requests on the way, reaches the physical endpoint, and reverses if pending work remains. Starting upward, it serves 55,70,90, travels to endpoint 99, reverses, then serves 20 and 10. We stop after 10, because no request remains. Movement=(99−50)+(99−10)=49+89=138.
LOOK reverses at the last pending request in the current direction rather than visiting an unneeded physical endpoint. Starting upward it goes 50→55→70→90→20→10, totaling (90−50)+(90−10)=40+80=120. SCAN and LOOK differ by the extra trip from 90 to 99 and back: 18 cylinders here. Calling LOOK “SCAN” without defining endpoint behavior can change the answer.
4. Circular policies: count the return trip
C-SCAN services only while moving in one direction. In our upward convention it serves 55,70,90, goes to 99, returns to 0 without servicing requests during the return, then serves 10 and 20. We charge all physical movement, including the return: (99−50)+(99−0)+(20−0)=49+99+20=168. The return is 99 cylinders, not 100: labels 0 through 99 contain 100 cylinders but endpoints are 99 apart.
C-LOOK stops the upward sweep at the largest pending request, returns directly to the smallest pending request, and resumes upward service. Here 50→55→70→90→10→20, giving 40+80+10=130. The jump from 90 to 10 is counted even though intermediate cylinders are not serviced. Some questions deliberately exclude wrap cost; if so, follow that stated convention and report it rather than silently using our charged-wrap rule.
5. Time consists of distinct parts
Queueing is the delay before a request begins service. Seek time moves the arm to the required cylinder. Rotational latency waits for the desired sector to rotate under the head. Transfer time moves the bytes once ready. Controller overhead may add another term. Do not add queueing twice when a problem's quoted response time already includes it.
Worked timing: a disk rotates at 7500 revolutions/minute. One revolution takes 60/7500 seconds=0.008 s=8 ms. If the desired angular position is uniformly distributed, average rotational latency is half a revolution=4 ms. With average seek 6 ms and transfer 0.5 ms, service time excluding queue/controller overhead is 6+4+0.5=10.5 ms. If queue delay is 3 ms, response is 13.5 ms. The half-revolution expectation needs the uniform-position assumption; it is not the latency of every request.
Exam checklist and limits
Write current position, direction, request order and cylinder endpoints. Distinguish FCFS order from sorted sweep order, recompute SSTF after every move, and record whether a reversal touches an endpoint. Sum all charged legs, including specified wrap travel. Keep head distance separate from response time and mechanical-disk assumptions separate from SSD behavior. These policies illustrate I/O scheduling; this lesson does not claim to cover every device scheduler.
Original practice: six single-correct MCQs
Choose exactly one option. Each question states its own required assumptions.
IO01. Head starts at 50. FCFS services pending requests in order 70,10,90,20,55, then stops. What is total cylinder movement?
A. 5 B. 120 C. 265 D. 315
Answer: C
A: 5 is final position minus start, not path length.
B: 120 is SSTF/LOOK for this workload.
C: 20+60+80+70+35=265.
D: This incorrectly adds extra travel not in the stated path.
IO02. Head starts at 50; pending cylinders are 70,10,90,20,55. SSTF chooses the closest pending request after each move. What service order results?
A. 70,10,90,20,55 B. 55,70,90,20,10 C. 10,20,55,70,90 D. 55,20,70,10,90
Answer: B
A: This is FCFS arrival order.
B: Nearest choices are 55, then 70, then 90, then 20, then 10.
C: Ascending order is not SSTF from 50.
D: After 55, 70 is 15 away while 20 is 35 away.
IO03. Cylinders are 0..99, head 50, pending 70,10,90,20,55. SCAN starts upward, visits endpoint 99 before reversing, and stops after the last request. What movement results?
A. 120 B. 138 C. 148 D. 168
Answer: B
A: 120 reverses at 90 and is LOOK here.
B: 50→99→10 costs 49+89=138 with requests served along the path.
C: 148 unnecessarily continues from 10 to 0 after all requests finish.
D: 168 is charged-wrap C-SCAN here.
IO04. For cylinders 0..99, head 50 and pending 70,10,90,20,55, upward C-SCAN goes to 99, wraps to 0, then serves the lower requests. Count the wrap and stop at the last request. What movement?
A. 69 B. 130 C. 168 D. 169
Answer: C
A: 69 omits the 99-cylinder wrap.
B: 130 is C-LOOK with charged jump.
C: (99−50)+(99−0)+(20−0)=168.
D: Endpoint distance 99−0 is 99, not 100.
IO05. A disk spins at 7500 rpm with uniformly distributed target angular position. Average seek is 6 ms and transfer 0.5 ms. Excluding queue/controller overhead, average service time is?
A. 6.5 ms B. 8 ms C. 10.5 ms D. 14.5 ms
Answer: C
A: This omits rotation.
B: 8 ms is one full revolution, not total service.
C: A revolution is 8 ms; average rotation is 4 ms; 6+4+0.5=10.5 ms.
D: 14.5 uses a full revolution instead of the assumed average half revolution.
IO06. Under SSTF with a continuing stream of new nearby requests, which issue can occur for a distant pending request?
A. Starvation B. Its cylinder number changes C. It is necessarily served next D. The head no longer moves physically
Answer: A
A: Repeated closer choices can indefinitely postpone it.
B: Scheduling does not change the requested cylinder.
C: SSTF favors current proximity, not this waiting request unconditionally.
D: A mechanical head still moves; the concern is unfair postponement.
Sources and scope
This original lesson extends the existing OS foundations in the GATE 2026 course. It maps to Section 8 of the official 2026 syllabus; it is not a claim of complete OS coverage or GATE 2027 completeness. Practice questions are original, not past-exam questions.
Sources checked 2026-10-14.
Sign in to keep your progress. Sign in