Bird
Raised Fist0
Interview Prepoperating-systemsmediumAmazonGoogleMicrosoftWipro

Disk Scheduling - SSTF, SCAN, C-SCAN

Choose your preparation mode3 modes available
▶
Steps
setup

Initialize SSTF Scheduler

Initialize the SSTF scheduler with the head at position 50 and the request queue [10, 22, 20, 2, 40, 6, 38, 48]. No requests have been serviced yet.

💡 Setting up initial state is crucial to understand how the scheduler will pick requests based on shortest seek time.
Line:head = 50 requests = [10, 22, 20, 2, 40, 6, 38, 48] serviced = []
💡 The scheduler starts with a known head position and a list of pending requests.
📊
Disk Scheduling - SSTF, SCAN, C-SCAN - Watch the Algorithm Execute, Step by Step
Watching the algorithm step-by-step reveals how each scheduling strategy optimizes disk head movement differently, which is hard to grasp from code alone.
Step 1/14
·Active fill★Answer cell
Transition new → ready pid:SSTF - Initialization of SSTF scheduler
SSTF
ready
Ready Queue
empty
Waiting Queue
empty
🖥CPUSSTFt=0
Transition ready → running pid:SSTF - Calculating closest request
SSTF
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUSSTFt=1
SSTF
Transition running → running pid:SSTF - Moved head and serviced request 48
SSTF
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUSSTFt=2
SSTF
Transition running → running pid:SSTF - Calculating next closest request
SSTF
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUSSTFt=3
SSTF
Transition running → running pid:SSTF - Moved head and serviced request 40
SSTF
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUSSTFt=4
SSTF
Transition new → ready pid:SCAN - Initialization of SCAN scheduler
SCAN
ready
Ready Queue
empty
Waiting Queue
empty
🖥CPUSCANt=0
Transition ready → running pid:SCAN - Moved head and serviced request 48
SCAN
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUSCANt=1
SCAN
Transition running → running pid:SCAN - Moved head to disk end and reversed direction
SCAN
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUSCANt=2
SCAN
Transition running → running pid:SCAN - Moved head and serviced request 40
SCAN
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUSCANt=3
SCAN
Transition new → ready pid:C-SCAN - Initialization of C-SCAN scheduler
C-SCAN
ready
Ready Queue
empty
Waiting Queue
empty
🖥CPUC-SCANt=0
Transition ready → running pid:C-SCAN - Moved head and serviced request 48
C-SCAN
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUC-SCANt=1
C-SCAN
Transition running → running pid:C-SCAN - Moved head to disk end and wrapped to start
C-SCAN
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUC-SCANt=2
C-SCAN
Transition running → running pid:C-SCAN - Moved head and serviced request 2
C-SCAN
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUC-SCANt=3
C-SCAN
Transition running → terminated pid:SSTF - All requests serviced
SSTF
terminated
burst: 0
SCAN
terminated
burst: 0
C-SCAN
terminated
burst: 0
Ready Queue
empty
Waiting Queue
empty
🖥CPUidlet=14
SSTF
SCAN
C-SCAN

Key Takeaways

✓ SSTF minimizes immediate seek time by always choosing the closest request next.

This greedy approach is intuitive but can cause starvation for far requests, which is clearer when watching the head movements step-by-step.

✓ SCAN moves the head in one direction servicing all requests until it reaches the end, then reverses direction.

Visualizing SCAN shows how it reduces seek time by avoiding random jumps, unlike SSTF, but still services all requests fairly.

✓ C-SCAN treats the disk as a circular list, moving in one direction and jumping back to start without servicing requests on the return.

Watching C-SCAN's wrap-around clarifies how it provides more uniform wait times compared to SCAN.

Practice

(1/5)
1. Trace the sequence of events when a circular wait condition arises among three processes P1, P2, and P3, each holding one resource and waiting for another. What happens next?
easy
A. Each process waits indefinitely because each is holding a resource the next process needs, forming a cycle.
B. One process releases its resource voluntarily, breaking the cycle immediately.
C. The operating system preempts resources from one process to resolve the wait.
D. Processes detect the cycle and terminate themselves automatically.

Solution

  1. Step 1: Identify circular wait

    Each process holds a resource and waits for another held by the next process, forming a cycle.
  2. Step 2: Understand consequences

    Because each process waits for a resource held by another in the cycle, none can proceed, causing indefinite waiting.
  3. Step 3: Analyze other options

    One process releases its resource voluntarily, breaking the cycle immediately assumes voluntary release, which is not guaranteed. The operating system preempts resources from one process to resolve the wait involves preemption, which is not part of the circular wait condition. Processes detect the cycle and terminate themselves automatically assumes automatic termination, which is not standard behavior.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Circular wait leads to indefinite blocking without external intervention.
Hint: Circular wait means processes wait in a cycle, causing indefinite blocking [OK]
Common Mistakes:
  • Assuming processes will release resources voluntarily
  • Confusing circular wait with preemption or automatic recovery
2. In which scenario is First-Come, First-Served (FCFS) scheduling most appropriate to use?
easy
A. When all processes have similar CPU burst times and arrival times
B. When minimizing average waiting time is the highest priority
C. When process arrival times are unpredictable and preemption is required
D. When simplicity and fairness in process order are more important than responsiveness

Solution

  1. Step 1: Understand FCFS characteristics

    FCFS schedules processes in the order they arrive without preemption, making it simple and fair in terms of arrival order.
  2. Step 2: Analyze each option

    A is incorrect because FCFS does not optimize for similar burst times; it just queues by arrival.
    B is incorrect because FCFS can cause long waiting times if a long process arrives first.
    C is incorrect because FCFS is non-preemptive and does not handle unpredictable arrivals well.
    D is correct because FCFS's main advantage is simplicity and fairness in order, not responsiveness or waiting time optimization.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    FCFS is chosen for simplicity and fairness, not for minimizing waiting time or handling preemption.
Hint: FCFS = simple, fair order, not optimized for waiting time
Common Mistakes:
  • Assuming FCFS minimizes average waiting time
  • Confusing FCFS with preemptive scheduling
  • Believing FCFS handles unpredictable arrivals efficiently
3. Which of the following statements best explains why eliminating the 'No Preemption' condition is often impractical in operating systems?
medium
A. Preemption increases the chance of circular wait conditions.
B. Preemption always leads to starvation of some processes.
C. Preempting resources can cause inconsistent states and data corruption if not handled carefully.
D. Preemption is unnecessary because hold and wait can be eliminated instead.

Solution

  1. Step 1: Understand 'No Preemption'

    This condition means resources cannot be forcibly taken from a process.
  2. Step 2: Analyze why preemption is hard

    Preempting resources like CPU or I/O devices can cause inconsistent states or data corruption if the process is interrupted mid-operation.
  3. Step 3: Evaluate other options

    Preemption always leads to starvation of some processes is incorrect because preemption does not always cause starvation; proper scheduling can prevent it. Preemption increases the chance of circular wait conditions is false; preemption reduces circular wait. Preemption is unnecessary because hold and wait can be eliminated instead is misleading; eliminating hold and wait is difficult and does not negate the challenges of preemption.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Preemption risks inconsistent states, making it impractical in many cases.
Hint: No preemption exists because forcibly taking resources risks corruption [OK]
Common Mistakes:
  • Believing preemption always causes starvation
  • Confusing preemption effects with circular wait
  • Assuming eliminating hold and wait removes need for preemption
4. Which of the following statements about memory compaction is INCORRECT?
medium
A. Compaction can be performed without halting all running processes
B. Compaction does not affect internal fragmentation
C. Compaction requires additional CPU overhead and may cause temporary performance degradation
D. Compaction reduces external fragmentation by relocating allocated memory blocks

Solution

  1. Step 1: Understand compaction process

    Compaction moves allocated blocks to create contiguous free memory, reducing external fragmentation (A correct).
  2. Step 2: Analyze process halting

    Compaction usually requires pausing processes to safely move memory (D incorrect).
  3. Step 3: Consider overhead and fragmentation

    Compaction adds CPU overhead and can degrade performance temporarily (C correct); it does not affect internal fragmentation (B correct).
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Compaction generally requires halting processes [OK]
Hint: Compaction = pause + move blocks -> reduce external fragmentation [OK]
Common Mistakes:
  • Assuming compaction is transparent to running processes
  • Confusing internal and external fragmentation effects
  • Underestimating compaction overhead
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
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