💡 SCAN's initial direction and head position set the movement pattern.
traverse
SCAN: Move Head Up to Next Request (48)
Head moves from 50 upwards, servicing requests in ascending order. The closest request in the upward direction is 48, which is serviced first.
💡 SCAN services requests in one direction, reducing seek time by avoiding back-and-forth movement.
Line:next_requests = [r for r in requests if r >= head]
next_request = min(next_requests)
head = next_request
requests.remove(next_request)
serviced.append(next_request)
💡 SCAN moves linearly in one direction, servicing all requests on the way.
traverse
SCAN: Continue Moving Up to Request 48 (No Higher Requests)
No requests remain above 48, so the head moves to the highest track (assumed 199) before reversing direction.
💡 SCAN moves to the end of the disk before reversing to service remaining requests.
Line:if not next_requests:
head = max_track # e.g., 199
direction = 'down'
💡 SCAN's linear movement includes moving to the disk end even if no requests are there.
traverse
SCAN: Move Head Down to Next Request (40)
Head moves downwards from 199, servicing requests in descending order. The next request is 40.
💡 After reaching the end, SCAN services requests on the return path.
Line:next_requests = [r for r in requests if r <= head]
next_request = max(next_requests)
head = next_request
requests.remove(next_request)
serviced.append(next_request)
💡 SCAN services all requests in one direction before reversing.
setup
Initialize C-SCAN Scheduler
Initialize C-SCAN scheduler with head at 50, requests [10, 22, 20, 2, 40, 6, 38, 48], and direction moving upwards.
💡 C-SCAN moves head in one direction only, jumping back to start after reaching the end.
💡 C-SCAN's unidirectional movement simplifies wait time analysis.
traverse
C-SCAN: Move Head Up to Next Request (48)
Head moves upwards from 50, servicing requests in ascending order. The next request is 48.
💡 C-SCAN services requests only in one direction, ignoring requests behind the head until it wraps around.
Line:next_requests = [r for r in requests if r >= head]
next_request = min(next_requests)
head = next_request
requests.remove(next_request)
serviced.append(next_request)
💡 C-SCAN moves linearly and services requests only ahead of the head.
traverse
C-SCAN: Move Head to Disk End and Wrap to Start
After servicing all requests ahead, head moves to disk end (199), then jumps to start (0) without servicing requests during jump.
💡 C-SCAN treats the disk as a circular list, wrapping around to start after reaching the end.
Line:if not next_requests:
head = max_track # 199
head = 0 # wrap around
💡 This jump avoids servicing requests behind the head until the next upward pass.
traverse
C-SCAN: Service Requests from Start Upwards (2)
After wrapping, head moves upwards from 0, servicing the lowest request 2 first.
💡 C-SCAN services requests only in upward direction after wrap-around.
Line:next_requests = [r for r in requests if r >= head]
next_request = min(next_requests)
head = next_request
requests.remove(next_request)
serviced.append(next_request)
💡 Requests behind the initial head position are serviced after wrap-around.
reconstruct
Final Step: All Requests Serviced, Calculate Total Head Movement
All requests have been serviced by each scheduler. Calculate total head movement and output the order of servicing.
💡 Final results show the efficiency of each scheduling algorithm.
Line:return serviced_order, total_head_movement
💡 Comparing total head movement reveals the performance differences between SSTF, SCAN, and C-SCAN.
def sstf_schedule(requests, head):
serviced = [] # STEP 1
while requests: # STEP 2
distances = {r: abs(head - r) for r in requests} # STEP 2
closest = min(distances, key=distances.get) # STEP 2
head = closest # STEP 3
requests.remove(closest) # STEP 3
serviced.append(closest) # STEP 3
return serviced # STEP 14
def scan_schedule(requests, head, max_track=199):
serviced = [] # STEP 6
direction = 'up' # STEP 6
while requests: # STEP 7
if direction == 'up': # STEP 7
next_requests = [r for r in requests if r >= head] # STEP 7
if next_requests: # STEP 7
next_request = min(next_requests) # STEP 7
head = next_request # STEP 7
requests.remove(next_request) # STEP 7
serviced.append(next_request) # STEP 7
else: # STEP 8
head = max_track # STEP 8
direction = 'down' # STEP 8
else: # STEP 9
next_requests = [r for r in requests if r <= head] # STEP 9
if next_requests: # STEP 9
next_request = max(next_requests) # STEP 9
head = next_request # STEP 9
requests.remove(next_request) # STEP 9
serviced.append(next_request) # STEP 9
else: # STEP 14
break # STEP 14
return serviced # STEP 14
def cscan_schedule(requests, head, max_track=199):
serviced = [] # STEP 10
direction = 'up' # STEP 10
while requests: # STEP 11
next_requests = [r for r in requests if r >= head] # STEP 11
if next_requests: # STEP 11
next_request = min(next_requests) # STEP 11
head = next_request # STEP 11
requests.remove(next_request) # STEP 11
serviced.append(next_request) # STEP 11
else: # STEP 12
head = max_track # STEP 12
head = 0 # STEP 12
return serviced # STEP 14
📊
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
Transitionnew → ready pid:SSTF - Initialization of SSTF scheduler
Transitionrunning → running pid:SSTF - Moved head and serviced request 48
SSTF
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUSSTFt=2
SSTF
Transitionrunning → running pid:SSTF - Calculating next closest request
SSTF
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUSSTFt=3
SSTF
Transitionrunning → running pid:SSTF - Moved head and serviced request 40
SSTF
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUSSTFt=4
SSTF
Transitionnew → ready pid:SCAN - Initialization of SCAN scheduler
SCAN
ready
Ready Queue
empty
Waiting Queue
empty
🖥CPUSCANt=0
Transitionready → running pid:SCAN - Moved head and serviced request 48
SCAN
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUSCANt=1
SCAN
Transitionrunning → running pid:SCAN - Moved head to disk end and reversed direction
SCAN
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUSCANt=2
SCAN
Transitionrunning → running pid:SCAN - Moved head and serviced request 40
SCAN
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUSCANt=3
SCAN
Transitionnew → ready pid:C-SCAN - Initialization of C-SCAN scheduler
C-SCAN
ready
Ready Queue
empty
Waiting Queue
empty
🖥CPUC-SCANt=0
Transitionready → running pid:C-SCAN - Moved head and serviced request 48
C-SCAN
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUC-SCANt=1
C-SCAN
Transitionrunning → 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
Transitionrunning → running pid:C-SCAN - Moved head and serviced request 2
C-SCAN
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUC-SCANt=3
C-SCAN
Transitionrunning → 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
Step 1: Identify circular wait
Each process holds a resource and waits for another held by the next process, forming a cycle.
Step 2: Understand consequences
Because each process waits for a resource held by another in the cycle, none can proceed, causing indefinite waiting.
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.
Final Answer:
Option A -> Option A
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
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.
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.
Final Answer:
Option D -> Option D
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
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
Step 1: Understand 'No Preemption'
This condition means resources cannot be forcibly taken from a process.
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.
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.
Final Answer:
Option C -> Option C
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
Step 1: Understand compaction process
Compaction moves allocated blocks to create contiguous free memory, reducing external fragmentation (A correct).
Step 2: Analyze process halting
Compaction usually requires pausing processes to safely move memory (D incorrect).
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).
Final Answer:
Option A -> Option A
Quick Check:
Compaction generally requires halting processes [OK]
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
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.
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.
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.
Step 4: Analyze The elimination of external fragmentation but increased internal fragmentation
Fragmentation trade-offs are more complex; this option oversimplifies and is incorrect.
Step 5: Analyze The requirement that all segments must be the same size