Disk Scheduling - SSTF, SCAN, C-SCAN

🎯

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.

Level	Interview Time	Suitable For	Risk
Basic Definition	30s	Screening call or initial rounds	Too shallow for on-site interviews; may fail follow-up questions
Mechanism Depth	2-3 minutes	On-site interviews at product companies	Requires 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. Trace the sequence of events when a memory allocation request cannot be satisfied due to external fragmentation, even though total free memory is sufficient.

easy

A. Internal fragmentation increases to accommodate the request in smaller blocks

B. The system immediately rejects the request without attempting any memory rearrangement

C. The buddy system automatically merges all free blocks regardless of their sizes to fulfill the request

D. The system performs compaction to consolidate free memory blocks before retrying allocation

Solution

1. Step 1: Identify external fragmentation effect

   External fragmentation means free memory is split into small noncontiguous blocks.

2. Step 2: Understand system response

   Compaction rearranges memory to create larger contiguous free blocks, enabling allocation.

3. Step 3: Evaluate other options

   Immediate rejection (B) ignores compaction; buddy system merges only buddies, not all blocks (C); internal fragmentation (D) is unrelated to external fragmentation.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Compaction is the standard response to external fragmentation [OK]

Hint: External fragmentation -> compaction to consolidate free space [OK]

Common Mistakes:

• Assuming buddy system merges all free blocks automatically
• Believing internal fragmentation can solve external fragmentation
• Thinking system rejects requests without compaction

2. Trace the sequence of state transitions for a process that requests I/O while running and then completes the I/O operation. What is the correct order of states the process goes through?

easy

A. Running -> Waiting -> Ready -> Running

B. Running -> Ready -> Waiting -> Running

C. Running -> Waiting -> Running -> Ready

D. Running -> Ready -> Running -> Waiting

Solution

1. Step 1: Identify the event

   The process requests I/O while Running, so it must wait for I/O completion.

2. Step 2: State transition on I/O request

   Process moves from Running to Waiting state to wait for I/O.

3. Step 3: After I/O completes

   Process moves from Waiting to Ready state, waiting for CPU scheduling.

4. Step 4: CPU scheduling

   Process moves from Ready to Running when CPU is allocated.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Running -> Waiting (I/O request), Waiting -> Ready (I/O done), Ready -> Running (CPU assigned) [OK]

Hint: I/O request moves process Running -> Waiting, then Waiting -> Ready after I/O completes [OK]

Common Mistakes:

• Confusing Ready and Waiting states order
• Assuming process goes directly from Waiting to Running
• Skipping the Ready state after I/O completion

3. Trace the sequence of events when a process's CPU burst exceeds the time quantum in Round Robin scheduling. What happens immediately after the quantum expires?

easy

A. The process is preempted and placed at the end of the ready queue

B. The process continues running until it voluntarily yields the CPU

C. The process is terminated and removed from the system

D. The process is moved to the waiting queue for I/O

Solution

1. Step 1: Recall Round Robin preemption

   When a process's time quantum expires, it is preempted to ensure fairness and allow other processes CPU access.

2. Step 2: Understand queue management

   The preempted process is placed at the end of the ready queue to wait for its next turn.

3. Step 3: Analyze incorrect options

   The process continues running until it voluntarily yields the CPU contradicts RR's preemption principle. The process is terminated and removed from the system is incorrect because process termination depends on completion, not quantum expiry. The process is moved to the waiting queue for I/O is incorrect unless the process requests I/O, which is unrelated to quantum expiration.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Quantum expiry -> preempt -> enqueue at ready queue's end.

Hint: Quantum expiry means preempt and requeue

Common Mistakes:

• Thinking process runs until completion ignoring quantum
• Confusing preemption with process termination
• Assuming process moves to waiting queue without I/O

4. Which of the following statements about the 'Mutual Exclusion' condition in deadlock is INCORRECT?

medium

A. Mutual exclusion means that at least one resource must be held in a non-shareable mode.

B. Mutual exclusion can be eliminated for all resources to prevent deadlock.

C. Mutual exclusion is necessary for deadlock but not sufficient alone.

D. Mutual exclusion applies only to resources that cannot be simultaneously used by multiple processes.

Solution

1. Step 1: Understand mutual exclusion

   It requires that some resources be non-shareable, meaning only one process can use them at a time.

2. Step 2: Analyze why eliminating mutual exclusion for all resources is impractical

   Eliminating mutual exclusion for all resources is impossible because some resources (like printers) inherently cannot be shared.

3. Step 3: Evaluate other options

   Mutual exclusion means that at least one resource must be held in a non-shareable mode correctly defines mutual exclusion. Mutual exclusion is necessary for deadlock but not sufficient alone correctly states it is necessary but not sufficient. Mutual exclusion applies only to resources that cannot be simultaneously used by multiple processes correctly limits mutual exclusion to non-shareable resources.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Mutual exclusion cannot be eliminated for all resources; some must be exclusive.

Hint: Mutual exclusion is about non-shareable resources, which can't all be made shareable [OK]

Common Mistakes:

• Thinking mutual exclusion can be removed entirely
• Confusing necessity with sufficiency
• Misapplying mutual exclusion to shareable resources

5. If a system uses segmentation with paging (paged segmentation), what is a key challenge in address translation that differs from pure paging or pure segmentation?

hard

A. The need to first translate segment number to a page table, then translate page number to frame number

B. The inability to handle variable-sized segments due to fixed page sizes

C. The elimination of external fragmentation but increased internal fragmentation

D. The requirement that all segments must be the same size

Solution

1. Step 1: Understand paged segmentation

   Address translation involves two steps: segment table lookup to get page table base, then page table lookup to get frame.

2. Step 2: Analyze The need to first translate segment number to a page table, then translate page number to frame number

   This correctly describes the two-level translation process.

3. Step 3: Analyze The inability to handle variable-sized segments due to fixed page sizes

   Variable-sized segments are handled by paging within segments; this option is incorrect.

4. Step 4: Analyze The elimination of external fragmentation but increased internal fragmentation

   Fragmentation trade-offs are more complex; this option oversimplifies and is incorrect.

5. Step 5: Analyze The requirement that all segments must be the same size

   Segments can vary in size; this option is false.

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Paged segmentation requires hierarchical translation: segment -> page table -> frame.

Hint: Paged segmentation = segment lookup + page lookup

Common Mistakes:

• Assuming paged segmentation removes variable segment sizes
• Thinking all segments must be uniform size
• Confusing fragmentation effects