Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Disk structure and disk scheduling

Disk structure defines how data is physically organised on rotating disks (platters, tracks, sectors, cylinders, heads) and disk scheduling algorithms (FCFS, SSTF, SCAN/LOOK, C-SCAN/C-LOOK) decide the order of servicing I/O requests to minimise access time.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Disk drives (and their logical abstractions) are the main persistent storage in many systems. An engineer uses knowledge of disk structure to map logical blocks to physical locations and uses disk scheduling to reduce average access time, improve throughput and prevent poor performance (e.g., long delays for some requests). These ideas are used in OS I/O subsystems, filesystems, and storage device drivers.

Key ideas

Start with definitions (define before using):

  • Platter: a circular disk coated for magnetic storage. Platter surfaces store bits in concentric rings.
  • Surface: one side of a platter that can be read/written by a head.
  • Read/write head (head): device that reads or writes data on one surface. Typically there is one head per surface.
  • Track: a concentric circle on a surface where data is written. Each track is divided into sectors.
  • Sector: the smallest physical recording unit on a track (often 512 bytes or 4096 bytes).
  • Block (or logical block): the unit used by the OS (a filesystem block); often maps to one or more sectors.
  • Cylinder: the set of tracks on all surfaces at the same radial position. If you stack platters, tracks aligned vertically form a cylinder; moving the actuator to that radial position allows all heads to access that cylinder.
  • CHS (cylinder-head-sector): an older addressing scheme using (cylinder, head, sector) coordinates.
  • LBA (Logical Block Addressing): a linear addressing scheme that numbers blocks sequentially (0,1,2…). The drive/controller maps LBA to internal physical locations; modern OSes see only LBAs (CHS is legacy).

Disk performance components and definitions:

  • Seek time: time to move the head assembly to the target track/cylinder. Seek time varies with distance. Manufacturers give: minimum, average and maximum (full-stroke) seek times.
  • Rotational latency (rotational delay): waiting time for the desired sector to rotate under the head. For uniformly random sector position the average rotational latency = half a rotation.
  • Transfer time: time to actually read/write the requested bytes while the platter rotates under the head.
  • Access time: total time to complete the requested transfer = seek time + rotational latency + command overhead (small) + transfer time.

Exact, exam-style statements and derivations:

  • Rotation period, given disk spin rate RPM (revolutions per minute): rotation_time = 60 / RPM seconds. Assumes constant RPM.
  • Average rotational latency (assume uniform distribution of sector position): average_rot_latency = rotation_time / 2. This follows because the expected wait until a uniformly random angular position reaches the head equals half the rotation period.
  • Access time (single request, ignoring controller overhead): access_time = seek_time + average_rot_latency + transfer_time. This assumes seek and rotation are independent components and that seek completes before transfer.

Disk scheduling: purpose and exact algorithm statements (assume many pending requests queued with known cylinder numbers and a current head position and direction):

  • FCFS (First-Come, First-Served): Serve requests in arrival order. Definition: no reordering. Assumption: arrival order maintained.
  • SSTF (Shortest Seek Time First): At each decision point, choose the pending request whose cylinder is nearest to the current head position. Precise: minimize |current_pos − request_cylinder|. Assumption: seeks cost roughly proportional to absolute cylinder distance.
  • SCAN (elevator): Move head in current direction, service requests in that direction in order of increasing/decreasing cylinder, when you reach the end (outermost or innermost cylinder) reverse direction and continue. Assumption: head goes to disk end before reversing.
  • LOOK: Like SCAN but reverse at the last request in the current direction (do not go to physical end if no requests beyond). More efficient than SCAN when edges are empty.
  • C-SCAN (circular SCAN): Move head in one direction only; when reaching the end, jump back to the start and continue in the same direction. Assumption: jump may be treated as unserviced movement; common implementations count the full movement for performance.
  • C-LOOK: Like C-SCAN but jump only between the last and first pending requests (no travel to physical ends unless a request exists there).

Scheduling properties and trade-offs:

  • SSTF reduces total head movement compared to FCFS but can cause starvation for distant requests.
  • SCAN/LOOK give more uniform wait times (fairness) and avoid extreme starvation; LOOK usually reduces unnecessary travel compared with SCAN.
  • C-SCAN/C-LOOK provide more uniform wait distribution for requests because each cylinder is treated more equally in one direction.

What to draw (diagrams to include in exam answers):

  1. Disk structure (top view): draw concentric circles for tracks, label ‘track 0’, ‘track 1’, etc., show sectors as small radial wedges on one track and label a sector size (e.g., 512 B). Optionally add a side sketch of multiple platters stacked; show heads aligned to form a cylinder and label ‘cylinder’. Add arrows showing actuator movement radially.
  2. Scheduling example line: draw a horizontal axis labelled 0 on left and max_cylinder on right (e.g., 0–199). Mark current head position and requested cylinder numbers as dots; show the chosen service order with arrows for FCFS, SSTF, and LOOK.

Formulas

rotation_time = 60 / RPM — rotation_time in seconds; RPM is revolutions per minute; applies for constant-speed disks. average_rot_latency = rotation_time / 2 — seconds; assumed uniform random sector position. access_time ≈ seek_time + average_rot_latency + transfer_time — seconds; applies when seek completes before transfer and controller overhead is small. transfer_time = bytes_to_transfer / transfer_rate — seconds; bytes_to_transfer in bytes, transfer_rate in bytes/second. Use when transfer rate is known and steady. total_head_movement = sum |pos_i+1 − pos_i| — cylinders moved; pos_i are successive head positions during servicing, used to measure scheduling cost. average_seek_per_request = total_head_movement / number_of_requests — cylinders per request.

Worked examples

Example 1 — single-request access time (numeric) Given: RPM = 7200 rev/min, average seek_time = 9.0 ms, transfer_rate = 100 MB/s (100 × 10^6 B/s), bytes_to_transfer = 4096 B (4 KiB).

  1. rotation_time = 60 / 7200 = 0.008333... s = 8.333 ms
  2. average_rot_latency = rotation_time / 2 = 4.167 ms
  3. transfer_time = 4096 B / (100 × 10^6 B/s) = 4.096 × 10^−5 s = 0.04096 ms
  4. access_time ≈ seek_time + average_rot_latency + transfer_time = 9.000 ms + 4.167 ms + 0.041 ms = 13.208 ms Answer: average access time = 13.208 ms (keep controller overhead separate). Note: verify transfer_rate and average seek with real device specs; values used here are for calculation example.

Example 2 — disk scheduling (classic numeric) System: cylinders 0..199, initial head position = 53. Pending requests (in arrival order): 98, 183, 37, 122, 14, 124, 65, 67 (eight requests). Compute total head movement and average per request for FCFS, SSTF and LOOK (head initially moves toward decreasing cylinder numbers for LOOK). A) FCFS Stepwise distances: |98−53|=45, |183−98|=85, |37−183|=146, |122−37|=85, |14−122|=108, |124−14|=110, |65−124|=59, |67−65|=2 Total = 45+85+146+85+108+110+59+2 = 640 cylinders Average = 640 / 8 = 80 cylinders/request

B) SSTF Choose nearest pending each step (detailed selection in order): 53→65 (12), 65→67 (2), 67→37 (30), 37→14 (23), 14→98 (84), 98→122 (24), 122→124 (2), 124→183 (59) Total = 12+2+30+23+84+24+2+59 = 236 cylinders Average = 236 / 8 = 29.5 cylinders/request

C) LOOK (head moves left first; LOOK does not go to cylinder 0 if no requests) Serve requests to the left of 53 in descending order: 37, 14. Then reverse and serve remaining in ascending order: 65, 67, 98, 122, 124, 183. Distances: 53→37=16, 37→14=23, 14→65=51, 65→67=2, 67→98=31, 98→122=24, 122→124=2, 124→183=59 Total = 16+23+51+2+31+24+2+59 = 208 cylinders Average = 208 / 8 = 26 cylinders/request

Notes: If you implemented SCAN (not LOOK) and the head continues to cylinder 0 before reversing, total will be larger (see methods). For C-SCAN count the wrap-around movement if your convention does so.

Example 3 — brief model answer (theory) Question: Explain why SSTF can lead to starvation and how LOOK mitigates it. Model answer: SSTF always picks the nearest request; if new requests keep appearing near the current head, distant requests may be postponed indefinitely — this is starvation. LOOK schedules by scanning in one direction and reversing at extremes of pending requests; every pending request in that direction will be serviced as the head passes, so starvation is avoided and wait times are more uniform.

Common mistakes

  • Omitting rotational latency when computing access time.
  • Counting the jump in C-SCAN incorrectly: state explicitly whether your implementation counts the wrap-around movement.
  • Assuming SSTF is globally optimal — it minimises immediate head movement but can produce starvation and not always minimal total movement in presence of arrivals over time.
  • Mixing up LOOK and SCAN: SCAN always goes to physical end; LOOK goes only to last request in direction.
  • Arithmetic errors in scheduling worked examples (always show each move and its absolute distance).

For your exam

Typical question types:

  • Definitions: define track/cylinder/sector/LBA, state formula for rotational latency.
  • Short notes: compare FCFS, SSTF, SCAN, LOOK, C-SCAN in fairness, throughput and starvation tendencies.
  • Derivations: derive average rotational latency = rotation_time/2 from first principles (assume uniform distribution of sector positions).
  • Numericals: compute access time given RPM, seek time and transfer rate; compute total head movement for a request sequence under FCFS/SSTF/SCAN/LOOK/C-SCAN.
  • Diagrams: draw a disk top view showing tracks, sectors, heads and mark a set of requests on the cylinder axis to illustrate scheduling choices.

What a full-marks answer includes:

  • Precise definitions and assumptions (e.g., whether you count wrap-around in C-SCAN).
  • Correct formulas with units and correct unit conversion (RPM→seconds).
  • For numericals: step-by-step head movements, absolute distances, final totals and averages with units.
  • For algorithm comparisons: state starvation and fairness properties and when each algorithm is preferred.

Quick check

  1. Define 'cylinder' in one sentence.
  2. Give the formula for average rotational latency for a disk spinning at RPM rev/min.
  3. Which scheduling algorithm gives the most uniform wait times and why: SSTF, FCFS, or SCAN?

Answers: 1) A cylinder is the set of tracks at the same radial position on all platters (one track per surface), 2) average_rot_latency = (60 / RPM) / 2 seconds, 3) SCAN gives more uniform wait times because the head sweeps across cylinders servicing requests in order and thus avoids repeatedly favouring nearby requests (reduces starvation).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?