Bird
Raised Fist0
Interview Prepoperating-systemsmediumAmazonGoogleMicrosoftWipro

Disk Scheduling - SSTF, SCAN, C-SCAN

Choose your preparation mode3 modes available
🎯
Disk Scheduling - SSTF, SCAN, C-SCAN
mediumOSAmazonGoogleMicrosoft

Imagine a busy library where a librarian must fetch books from shelves scattered across a long aisle. Choosing the order to pick books can save a lot of walking time, just like disk scheduling algorithms optimize the movement of the disk arm.

💡 Beginners often confuse disk scheduling with CPU scheduling or think all disk requests are served in the order they arrive, missing how seek time optimization impacts performance.
📋
Interview Question

Explain the disk scheduling algorithms SSTF, SCAN, and C-SCAN. How do they work, and what are their trade-offs in terms of seek time and fairness?

Seek time and rotational latency in disk I/OHow SSTF selects the closest request to minimize seek timeSCAN and C-SCAN as elevator algorithms that provide fairness and reduce starvation
💡
Scenario & Trace
ScenarioA disk with pending read requests at tracks 10, 22, 20, 2, 40, and 6, and the disk arm currently at track 15.
SSTF: Picks the closest request to 15 first (20), then 22, then 10, 6, 2, and finally 40, minimizing immediate seek time but possibly causing starvation for far requests. SCAN: Moves the arm in one direction (e.g., towards higher tracks), servicing 20, 22, 40, then reverses direction to service 10, 6, 2, ensuring all requests are eventually served. C-SCAN: Moves in one direction only (e.g., upwards), servicing 20, 22, 40, then quickly returns to the lowest track without servicing requests on the return, then services 2, 6, 10, providing more uniform wait times.
  • What if two requests are equidistant from the current head position in SSTF?
  • What happens when the disk arm reaches the last track in SCAN?
  • How does C-SCAN handle requests that arrive while the arm is returning to the start?
⚠️
Common Mistakes
Confusing disk scheduling with CPU scheduling

Interviewer thinks candidate lacks clarity on OS subsystems

✅ Understand disk scheduling optimizes physical disk arm movement, unlike CPU scheduling which manages process execution

Assuming SSTF always minimizes total seek time

Interviewer notes candidate misses starvation and long-term fairness issues

✅ Explain SSTF minimizes immediate seek time but can cause starvation for far requests

Thinking SCAN and C-SCAN are identical

Interviewer doubts candidate’s understanding of algorithm differences

✅ Clarify SCAN services requests in both directions; C-SCAN services only in one direction and jumps back

Ignoring what happens when the arm reaches the disk edge

Candidate misses explaining reversal or wrap-around behavior

✅ Describe how SCAN reverses direction at the edge and C-SCAN jumps back to start

🧠
Basic Definition - What It Is
💡 This level covers the fundamental idea behind disk scheduling and the names of the algorithms.

Intuition

Disk scheduling algorithms decide the order of servicing disk I/O requests to reduce the time the disk arm spends moving between tracks.

Explanation

Disk scheduling is about optimizing the movement of the disk arm to reduce seek time, which is the time taken to move the arm to the track where data is to be read or written. SSTF (Shortest Seek Time First) picks the request closest to the current head position. SCAN moves the arm in one direction servicing all requests until it reaches the end, then reverses direction. C-SCAN is similar to SCAN but only services requests in one direction and jumps back to the start without servicing requests on the return trip.

Memory Hook

💡 Think of SSTF as always picking the closest book on the shelf, SCAN as walking to the end of the aisle and back, and C-SCAN as walking to the end and teleporting back to the start.

Illustrative Code

Interview Questions

❓ What is the main goal of disk scheduling algorithms?
  • Minimize seek time
  • Improve disk throughput
  • Reduce latency for I/O requests
⏱
Depth Level
Interview Time30 seconds
Depthbasic

Covers what the algorithms are and their high-level purpose; sufficient for screening rounds.

Interview Target: Minimum floor - never go below this

Knowing only this will get you through initial screening but not detailed technical interviews.

🧠
Mechanism Depth - How It Works
💡 This level explains the internal working and trade-offs of each algorithm, expected in product company interviews.

Intuition

Each algorithm balances seek time optimization and fairness differently by choosing how the disk arm moves and which requests it prioritizes.

Explanation

SSTF selects the pending request closest to the current head position, minimizing immediate seek time but potentially causing starvation for distant requests. SCAN moves the disk arm in one direction, servicing all requests along the way until it reaches the last track, then reverses direction, ensuring no starvation but possibly longer average seek time. C-SCAN moves the arm in one direction only, servicing requests on the way up, then quickly returns to the start without servicing requests on the return trip, providing more uniform wait times and fairness. These algorithms trade off between minimizing seek time and preventing starvation, with SCAN and C-SCAN resembling an elevator's movement pattern.

Memory Hook

💡 Imagine SSTF as a greedy shopper grabbing the nearest item, SCAN as an elevator going up and down, and C-SCAN as an elevator that only goes up and teleports down.

Illustrative Code

Interview Questions

❓ How does SSTF cause starvation and how do SCAN and C-SCAN address it?
  • SSTF may keep picking nearby requests, ignoring far ones indefinitely
  • SCAN services requests in one direction then reverses, ensuring all are served
  • C-SCAN services requests in one direction and jumps back, providing uniform wait times
⏱
Depth Level
Interview Time2-3 minutes
Depthintermediate

Demonstrates understanding of internal mechanics, trade-offs, and fairness considerations.

Interview Target: Target level for FAANG on-sites

Mastering this level distinguishes you from most candidates and prepares you for deeper system design discussions.

📊
Explanation Depth Levels
💡 Choose your explanation depth based on interview stage and role expectations.
LevelInterview TimeSuitable ForRisk
Basic Definition30sScreening call or initial roundsToo shallow for on-site interviews; may fail follow-up questions
Mechanism Depth2-3 minutesOn-site interviews at product companiesRequires good understanding; missing edge cases can still hurt
💼
Interview Strategy
💡 Use this guide to structure your explanation clearly and confidently before every mock or real interview.

How to Present

Start with a concise definition of disk scheduling and why it matters.Give a simple analogy or example to illustrate the problem.Explain each algorithm’s mechanism and how it chooses requests.Discuss edge cases and trade-offs like starvation and fairness.

Time Allocation

Definition: 30s → Example: 1min → Mechanism: 2min → Edge cases: 30s. Total ~4min

What the Interviewer Tests

Your ability to explain the purpose, workings, and trade-offs of each algorithm clearly and handle edge cases.

Common Follow-ups

  • What happens if two requests are equally close in SSTF? → Explain tie-breaking strategies.
  • How does C-SCAN improve fairness compared to SCAN? → Discuss uniform wait times and starvation prevention.
💡 These follow-ups test your depth and ability to handle nuanced scenarios.
🔍
Pattern Recognition

When to Use

When asked about optimizing disk I/O performance or explaining how OS manages disk requests.

Signature Phrases

Explain disk scheduling algorithmsCompare SSTF vs SCAN vs C-SCANWhat happens when multiple requests arrive simultaneously?

NOT This Pattern When

Similar Problems

Practice

(1/5)
1. Trace the sequence of events when all philosophers simultaneously pick up their left fork first in the Dining Philosophers problem. What is the immediate consequence?
easy
A. All philosophers eat simultaneously without conflict
B. Starvation occurs because some philosophers never get to pick up forks
C. Deadlock occurs because each philosopher holds one fork and waits for the other
D. The system recovers automatically as forks are released in order

Solution

  1. Step 1: Understand the initial action

    Each philosopher picks up their left fork simultaneously, so all forks on the left side are held.
  2. Step 2: Analyze waiting condition

    Each philosopher now waits for the right fork, which is held by their neighbor, creating a circular wait.
  3. Step 3: Identify the system state

    This circular wait with no forks released leads to deadlock.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Deadlock arises immediately due to circular wait and mutual exclusion.
Hint: All pick left fork first -> circular wait -> deadlock [OK]
Common Mistakes:
  • Assuming philosophers can eat simultaneously
  • Confusing deadlock with starvation
  • Believing system recovers automatically without intervention
2. Which of the following statements about user mode and kernel mode is INCORRECT?
medium
A. Mode switches are triggered by traps or interrupts to ensure controlled privilege escalation.
B. Kernel mode has unrestricted access to all hardware and memory.
C. User mode code cannot directly access kernel memory for protection reasons.
D. System calls execute entirely in user mode without switching to kernel mode.

Solution

  1. Step 1: Review privilege separation

    User mode is restricted; kernel mode has full privileges.
  2. Step 2: Validate each statement

    User mode code cannot directly access kernel memory for protection reasons. is true; user mode cannot access kernel memory. Kernel mode has unrestricted access to all hardware and memory. is true; kernel mode has full access. Mode switches are triggered by traps or interrupts to ensure controlled privilege escalation. is true; traps/interrupts cause mode switches.
  3. Step 3: Identify incorrect statement

    System calls execute entirely in user mode without switching to kernel mode. is false; system calls require switching to kernel mode to execute privileged operations.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    System calls always involve mode switch to kernel [OK]
Hint: System calls require kernel mode execution
Common Mistakes:
  • Believing system calls run entirely in user mode
  • Confusing hardware interrupts with system calls
  • Assuming user mode can access kernel memory
3. If a process requests resources that would keep the system in a safe state but the system is currently in an unsafe state, what does the Banker's Algorithm do and why?
hard
A. It denies the request because the system must always remain in a safe state, and starting from an unsafe state invalidates the algorithm's assumptions.
B. It restarts the system to reset resource allocations and ensure safety.
C. It preempts resources from other processes to restore a safe state before granting the request.
D. It grants the request because the immediate allocation is safe, ignoring the current unsafe state.

Solution

  1. Step 1: Recall Banker's Algorithm assumptions

    The algorithm assumes the system starts in a safe state to guarantee deadlock avoidance.
  2. Step 2: Analyze the scenario

    If the system is already unsafe, granting requests--even if individually safe--cannot guarantee overall safety.
  3. Step 3: Evaluate options

    A ignores the unsafe starting state.
    B and C describe actions outside the algorithm's scope.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Banker's Algorithm cannot recover from unsafe states; it only avoids entering them.
Hint: Banker's Algorithm requires starting safe state to function correctly [OK]
Common Mistakes:
  • Assuming safe requests can fix unsafe states
  • Believing the algorithm preempts resources
  • Thinking system restarts are part of the algorithm
4. If a system using FCFS scheduling introduces a mix of I/O-bound and CPU-bound processes arriving at different times, how does this affect the convoy effect and waiting times, and what strategy could reduce the negative impact?
hard
A. The convoy effect disappears because I/O-bound processes run first, so waiting times decrease automatically
B. The convoy effect worsens as CPU-bound processes block I/O-bound ones, increasing waiting times; introducing preemption can help
C. Waiting times remain unchanged because FCFS ignores process type and arrival time
D. The convoy effect is irrelevant in mixed workloads since I/O-bound processes do not use the CPU

Solution

  1. Step 1: Understand process types in FCFS

    FCFS schedules strictly by arrival order, regardless of process type.
  2. Step 2: Analyze impact of mixed workloads

    CPU-bound processes arriving first can delay I/O-bound processes, worsening the convoy effect and increasing waiting times.
  3. Step 3: Mitigation strategy

    Introducing preemption or priority scheduling can reduce waiting times for I/O-bound processes by allowing them to run sooner.
  4. Step 4: Evaluate options

    A is incorrect; convoy effect does not disappear automatically.
    B is correct; convoy effect worsens and preemption helps.
    C is incorrect; waiting times do change due to process mix.
    D is incorrect; convoy effect is relevant because all processes compete for CPU.
  5. Final Answer:

    Option B -> Option B
  6. Quick Check:

    Mixed workloads worsen convoy effect; preemption mitigates it.
Hint: Mixed CPU/I-O bound + FCFS -> worse convoy; preemption helps
Common Mistakes:
  • Assuming I/O-bound processes run first automatically
  • Believing waiting times don't change with process mix
  • Ignoring convoy effect in mixed workloads
5. If a system using the buddy system frequently experiences internal fragmentation, which of the following strategies would best reduce it without sacrificing allocation speed?
hard
A. Increase the minimum block size in the buddy system to reduce splitting overhead
B. Use compaction to rearrange allocated blocks and reduce fragmentation
C. Implement a slab allocator on top of the buddy system for frequently requested object sizes
D. Switch to fixed partitioning to eliminate internal fragmentation

Solution

  1. Step 1: Identify internal fragmentation cause

    Buddy system rounds allocations to power-of-two sizes, causing internal fragmentation.
  2. Step 2: Evaluate strategies

    Slab allocator efficiently manages fixed-size objects, reducing internal fragmentation without slowing allocation.
  3. Step 3: Analyze other options

    Increasing minimum block size (A) increases internal fragmentation; compaction (C) addresses external fragmentation; fixed partitioning (D) is inflexible and can worsen fragmentation.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Slab allocators complement buddy system to reduce internal fragmentation [OK]
Hint: Slab allocator + buddy system = less internal fragmentation [OK]
Common Mistakes:
  • Thinking compaction reduces internal fragmentation
  • Assuming bigger minimum block size reduces fragmentation
  • Believing fixed partitioning eliminates fragmentation
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard