Initialize remaining times, counters, and time to start scheduling from time 0.
💡 Setting up these variables is essential to track progress and remaining burst times for each process.
Line:n = len(processes)
remaining_time = [bt for _, bt in processes]
complete = 0
current_time = 0
💡 We now have the initial state with all processes' burst times ready to be decremented as they run.
compare
Select shortest process at time 0
Check all processes that have arrived by current_time=0 and select the one with the shortest remaining time.
💡 At time 0, only process 0 has arrived, so it must be selected to run.
Line:for i in range(n):
if (processes[i][0] <= current_time and remaining_time[i] < min_remaining and remaining_time[i] > 0):
min_remaining = remaining_time[i]
shortest = i
check = True
💡 The algorithm picks the shortest job among arrived processes, here only P0.
traverse
Run process 0 for 1 time unit
Decrement remaining time of process 0 by 1 and advance current_time to 1.
💡 Running the selected process reduces its remaining burst time and moves time forward.
💡 The CPU executes the process for one unit, simulating time passing.
compare
At time 1, select shortest process again
At current_time=1, processes 0 and 1 have arrived. Select the one with the shortest remaining time.
💡 The algorithm checks all arrived processes to decide if preemption is needed.
Line:for i in range(n):
if (processes[i][0] <= current_time and remaining_time[i] < min_remaining and remaining_time[i] > 0):
min_remaining = remaining_time[i]
shortest = i
check = True
💡 Preemption occurs because a shorter job (P1) has arrived.
traverse
Run process 1 for 1 time unit
Decrement remaining time of process 1 by 1 and advance current_time to 2.
💡 Executing the newly selected shortest job reduces its burst time.
💡 The CPU switches to the shorter job and executes it.
compare
At time 2, select shortest process again
At current_time=2, processes 0,1,2 have arrived. Select the shortest remaining time process.
💡 The algorithm continuously checks for the shortest remaining job to run.
Line:for i in range(n):
if (processes[i][0] <= current_time and remaining_time[i] < min_remaining and remaining_time[i] > 0):
min_remaining = remaining_time[i]
shortest = i
check = True
💡 No preemption needed since current running process is still shortest.
traverse
Run process 1 for 1 time unit
Decrement remaining time of process 1 by 1 and advance current_time to 3.
💡 Process 1 continues execution, reducing its remaining burst time.
💡 The CPU continues executing the shortest job without interruption.
compare
At time 3, select shortest process again
At current_time=3, all processes have arrived. Select the shortest remaining time process.
💡 The algorithm checks all arrived processes to find the shortest remaining job.
Line:for i in range(n):
if (processes[i][0] <= current_time and remaining_time[i] < min_remaining and remaining_time[i] > 0):
min_remaining = remaining_time[i]
shortest = i
check = True
💡 The running process is still the shortest, so no preemption occurs.
traverse
Run process 1 for 1 time unit
Decrement remaining time of process 1 by 1 and advance current_time to 4.
💡 Process 1 continues execution, moving closer to completion.
💡 The algorithm tracks completion and waiting time precisely at process finish.
compare
At time 5, select shortest process again
At current_time=5, select the shortest remaining time process among P0, P2, and P3.
💡 The algorithm picks the next shortest job to run after a process finishes.
Line:for i in range(n):
if (processes[i][0] <= current_time and remaining_time[i] < min_remaining and remaining_time[i] > 0):
min_remaining = remaining_time[i]
shortest = i
check = True
💡 The algorithm continues selecting the shortest job dynamically.
traverse
Run process 3 for 1 time unit
Decrement remaining time of process 3 by 1 and advance current_time to 6.
💡 Executing the selected process reduces its remaining burst time.
💡 The CPU executes the process for one unit, simulating time passing.
compare
At time 6, select shortest process again
At current_time=6, select the shortest remaining time process among P0, P2, and P3.
💡 The algorithm checks all arrived processes to find the shortest remaining job.
Line:for i in range(n):
if (processes[i][0] <= current_time and remaining_time[i] < min_remaining and remaining_time[i] > 0):
min_remaining = remaining_time[i]
shortest = i
check = True
💡 The running process is still the shortest, so no preemption occurs.
traverse
Run process 3 for 1 time unit
Decrement remaining time of process 3 by 1 and advance current_time to 7.
💡 Process 3 continues execution, reducing its remaining burst time.
💡 The CPU continues executing the shortest job without interruption.
compare
At time 7, select shortest process again
At current_time=7, select the shortest remaining time process among P0, P2, and P3.
💡 The algorithm checks all arrived processes to find the shortest remaining job.
Line:for i in range(n):
if (processes[i][0] <= current_time and remaining_time[i] < min_remaining and remaining_time[i] > 0):
min_remaining = remaining_time[i]
shortest = i
check = True
💡 The running process is still the shortest, so no preemption occurs.
traverse
Run process 3 for 1 time unit
Decrement remaining time of process 3 by 1 and advance current_time to 8.
💡 Process 3 continues execution, reducing its remaining burst time.
💡 The algorithm tracks completion and waiting time at process finish.
compare
At time 10, select shortest process again
At current_time=10, select the shortest remaining time process among P0 and P2.
💡 The algorithm picks the next shortest job to run after a process finishes.
Line:for i in range(n):
if (processes[i][0] <= current_time and remaining_time[i] < min_remaining and remaining_time[i] > 0):
min_remaining = remaining_time[i]
shortest = i
check = True
💡 The algorithm continues selecting the shortest job dynamically.
traverse
Run process 0 until completion
Process 0 runs for remaining 7 time units, completes at time 17, waiting time calculated.
💡 Completing a process updates counters and waiting time precisely.
Transitionrunning → terminated0 - process completed
0
terminated
burst: 0
1
terminated
burst: 0
2
ready
burst: 9
3
terminated
burst: 0
Ready Queue
2
Waiting Queue
empty
🖥CPU0t=17
idle
1
3
idle
Transitionrunning → terminated pid:2 - process completed
0
terminated
burst: 0
1
terminated
burst: 0
2
terminated
burst: 0
3
terminated
burst: 0
Ready Queue
empty
Waiting Queue
empty
🖥CPU2t=26
idle
1
3
idle
2
Key Takeaways
✓ SJF preemptive scheduling always picks the process with the shortest remaining burst time at every time unit.
This dynamic selection is difficult to visualize from code alone but is clear when watching each scheduling decision.
✓ Preemption occurs immediately when a shorter job arrives, interrupting the currently running process.
Seeing the CPU switch processes step-by-step reveals how preemption minimizes waiting time.
✓ Waiting time is calculated precisely at process completion using finish time, burst time, and arrival time.
Understanding waiting time calculation is easier when you see the exact moment a process finishes and how the formula applies.
Practice
(1/5)
1. In which scenario is the Dining Philosophers problem a suitable model to analyze system behavior?
easy
A. When processes communicate via message passing without shared resources
B. When multiple processes compete for multiple identical resources without any ordering
C. When a single process requires exclusive access to a single resource
D. When multiple processes compete for multiple shared resources arranged in a circular wait pattern
Solution
Step 1: Identify the resource allocation pattern
The Dining Philosophers problem models processes (philosophers) competing for shared resources (forks) arranged in a circular manner, leading to potential circular wait and deadlock.
Step 2: Analyze each option
When multiple processes compete for multiple shared resources arranged in a circular wait pattern correctly describes competition with a circular wait pattern, which is essential for the Dining Philosophers problem; When multiple processes compete for multiple identical resources without any ordering lacks the circular wait pattern; When a single process requires exclusive access to a single resource is a trivial single resource case; When processes communicate via message passing without shared resources involves no shared resources, so no deadlock from resource contention.
Final Answer:
Option D -> Option D
Quick Check:
Only When multiple processes compete for multiple shared resources arranged in a circular wait pattern captures the circular wait condition essential to the Dining Philosophers problem.
Hint: Dining Philosophers = circular wait over shared resources [OK]
Common Mistakes:
Confusing any resource competition with circular wait
Assuming single resource contention models the problem
Ignoring the circular dependency aspect
2. In which scenario is the SSTF (Shortest Seek Time First) disk scheduling algorithm most appropriate compared to SCAN or C-SCAN?
easy
A. When minimizing average seek time is the highest priority and starvation is acceptable
B. When fairness and avoiding starvation are more important than minimizing seek time
C. When the disk requests are uniformly distributed and the workload is heavy
D. When the disk head movement must always proceed in one direction only
Solution
Step 1: Understand SSTF's goal
SSTF selects the closest request to the current head position to minimize seek time.
Step 2: Consider starvation risk
SSTF can cause starvation for requests far from the current head position because it always picks the nearest request.
Step 3: Compare with SCAN and C-SCAN
SCAN and C-SCAN move the head in a fixed direction to provide fairness and avoid starvation, sacrificing some seek time efficiency.
Final Answer:
Option A -> Option A
Quick Check:
When minimizing average seek time is the highest priority and starvation is acceptable correctly identifies SSTF's strength and its tradeoff with starvation risk.
Hint: SSTF = fastest seek but can starve distant requests
Common Mistakes:
Assuming SSTF always avoids starvation
Believing SCAN/C-SCAN minimize seek time better than SSTF
Confusing uniform distribution with SSTF suitability
3. When a CPU switches from running one thread to another within the same process, what sequence of events occurs internally?
easy
A. The OS terminates the current thread and creates a new thread for the next task
B. The OS saves the entire process state and reloads it for the new thread
C. The OS flushes the process's memory cache and reloads it for the new thread
D. The OS saves the thread's CPU registers and stack pointer, then loads the next thread's registers and stack pointer
Solution
Step 1: Identify what is saved during thread context switch
Only the CPU registers and stack pointer specific to the thread are saved and restored, since threads share the process memory space.
Step 2: Understand process state remains unchanged
The process's memory and resources remain intact; no need to save or reload the entire process state.
Step 3: Evaluate options
The OS saves the entire process state and reloads it for the new thread incorrectly saves the entire process state. The OS flushes the process's memory cache and reloads it for the new thread incorrectly flushes memory cache. The OS terminates the current thread and creates a new thread for the next task incorrectly terminates and recreates threads.
Final Answer:
Option D -> Option D
Quick Check:
Thread context switch saves/restores thread-specific CPU state only [OK]
Hint: Thread switch saves CPU registers, not whole process state [OK]
Common Mistakes:
Confusing process context switch with thread context switch
Assuming memory cache must be flushed on thread switch
Believing threads are terminated and recreated on each switch
4. Which of the following statements about deadlock prevention in the Dining Philosophers problem is INCORRECT?
medium
A. Using asymmetric fork picking (odd philosophers pick left first, even pick right first) guarantees no starvation
B. Allowing a philosopher to pick up both forks only if both are available prevents deadlock
C. Imposing a strict ordering on resource acquisition always prevents deadlock
D. Breaking one of the four Coffman conditions is sufficient to prevent deadlock
Solution
Step 1: Analyze each statement
Imposing a strict ordering on resource acquisition always prevents deadlock is correct: ordering resources prevents circular wait; Allowing a philosopher to pick up both forks only if both are available prevents deadlock is correct: atomic acquisition avoids partial hold; Breaking one of the four Coffman conditions is sufficient to prevent deadlock is correct: breaking any Coffman condition prevents deadlock.
Step 2: Evaluate Using asymmetric fork picking (odd philosophers pick left first, even pick right first) guarantees no starvation
Asymmetric fork picking prevents deadlock but does not guarantee no starvation, as some philosophers may be repeatedly delayed.
Final Answer:
Option A -> Option A
Quick Check:
Only Using asymmetric fork picking (odd philosophers pick left first, even pick right first) guarantees no starvation incorrectly claims starvation is guaranteed prevented.
Believing asymmetric picking solves all synchronization issues
Confusing Coffman conditions with starvation conditions
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
Step 1: Identify internal fragmentation cause
Buddy system rounds allocations to power-of-two sizes, causing internal fragmentation.