CPU dequeues P3 from the ready queue and starts running it for up to quantum 2.
💡 Round Robin picks next ready process to run after preemption.
Line:current = ready_queue.pop(0)
current.state = 'running'
cpu_running = current
💡 CPU now runs P3; ready queue is [P1, P4, P2].
shrink
Run P3 for 2 Units; Quantum Expires
P3 runs for full quantum of 2 units, reducing burst from 8 to 6. Quantum expires, so P3 is preempted and added to ready queue end.
💡 Longer burst processes get multiple quanta, preempted repeatedly until done.
Line:for _ in range(2):
time += 1
P3.burst_remaining -= 1
if P3.burst_remaining > 0:
P3.state = 'ready'
ready_queue.append(P3)
💡 Ready queue updates to [P1, P4, P2, P3].
processes = [
{'pid': 'P1', 'arrival': 0, 'burst': 5, 'remaining': 5, 'state': 'new'},
{'pid': 'P2', 'arrival': 1, 'burst': 3, 'remaining': 3, 'state': 'new'},
{'pid': 'P3', 'arrival': 2, 'burst': 8, 'remaining': 8, 'state': 'new'},
{'pid': 'P4', 'arrival': 3, 'burst': 6, 'remaining': 6, 'state': 'new'}
]
quantum = 2
ready_queue = []
time = 0
cpu_running = None
gantt = []
while any(p['remaining'] > 0 for p in processes):
# STEP: Add newly arrived processes to ready queue
for p in processes:
if p['arrival'] == time and p['state'] == 'new':
p['state'] = 'ready'
ready_queue.append(p)
if cpu_running is None and ready_queue:
# STEP: Pick next process to run
cpu_running = ready_queue.pop(0)
cpu_running['state'] = 'running'
slice_start = time
slice_time = 0
if cpu_running:
# STEP: Run process for one unit
cpu_running['remaining'] -= 1
time += 1
slice_time += 1
# STEP: Check for new arrivals during this time
for p in processes:
if p['arrival'] == time and p['state'] == 'new':
p['state'] = 'ready'
ready_queue.append(p)
# STEP: Check quantum expiration or process completion
if cpu_running['remaining'] == 0 or slice_time == quantum:
gantt.append({'pid': cpu_running['pid'], 'start': slice_start, 'end': time})
if cpu_running['remaining'] > 0:
cpu_running['state'] = 'ready'
ready_queue.append(cpu_running)
else:
cpu_running['state'] = 'terminated'
cpu_running = None
else:
# STEP: CPU idle, advance time
time += 1
# STEP: Calculate waiting and turnaround times
waiting_times = {}
turnaround_times = {}
for p in processes:
turnaround_times[p['pid']] = time - p['arrival']
waiting_times[p['pid']] = turnaround_times[p['pid']] - p['burst']
avg_waiting = sum(waiting_times.values()) / len(processes)
avg_turnaround = sum(turnaround_times.values()) / len(processes)
📊
Round Robin Scheduling - Quantum & Turnaround Time - Watch the Algorithm Execute, Step by Step
Watching each scheduling decision and queue update live reveals how Round Robin fairly shares CPU time and how turnaround and waiting times accumulate.
✓ Round Robin scheduling cycles through processes in fixed time slices, ensuring fairness and preventing starvation.
This fairness is hard to see from code alone but becomes clear when watching the ready queue and CPU allocation update step-by-step.
✓ Processes arriving during execution are immediately added to the ready queue and will be scheduled in turn.
Visualizing arrivals during CPU bursts clarifies how the scheduler dynamically updates the ready queue.
✓ Preemption occurs exactly when a process exhausts its quantum without finishing, cycling it back to the ready queue.
Seeing preemption and re-queuing live helps understand how Round Robin balances responsiveness and throughput.
Practice
(1/5)
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
Step 1: Identify external fragmentation effect
External fragmentation means free memory is split into small noncontiguous blocks.
Immediate rejection (B) ignores compaction; buddy system merges only buddies, not all blocks (C); internal fragmentation (D) is unrelated to external fragmentation.
Final Answer:
Option D -> Option D
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. You are designing a web server that must handle thousands of simultaneous client requests efficiently. Which approach is most suitable to maximize resource sharing and minimize overhead?
easy
A. Use multiple threads within a single process to handle client requests concurrently
B. Use multiple processes with shared memory segments for communication
C. Use a single-threaded process with blocking I/O for all requests
D. Use multiple processes, each handling a single client request independently
Solution
Step 1: Understand resource sharing in threads
Threads within the same process share memory and resources, allowing efficient communication and lower overhead compared to processes.
Step 2: Compare overhead of context switching
Thread context switching is lighter than process context switching, making threads better for high concurrency.
Step 3: Evaluate options
Use multiple processes, each handling a single client request independently uses processes, which have higher overhead and less efficient resource sharing. Use a single-threaded process with blocking I/O for all requests is single-threaded and blocks, limiting concurrency. Use multiple processes with shared memory segments for communication adds complexity with shared memory and still has process overhead.
Final Answer:
Option A -> Option A
Quick Check:
Threads maximize resource sharing and minimize overhead for concurrent tasks [OK]
Assuming processes are always better for concurrency
Ignoring context switching overhead differences
Believing shared memory between processes is as simple as threads
3. Which trade-off is a key limitation of using a global waiter (arbitrator) to prevent deadlock in the Dining Philosophers problem?
medium
A. It simplifies resource allocation but introduces a single point of failure and potential bottleneck
B. It increases concurrency but risks livelock under high contention
C. It eliminates deadlock but can cause starvation due to unfair scheduling
D. It guarantees fairness but requires complex priority inheritance mechanisms
Solution
Step 1: Understand the global waiter approach
A global waiter serializes fork acquisition requests to prevent circular wait.
Step 2: Analyze trade-offs
This centralization simplifies deadlock prevention but creates a single point of failure and can bottleneck performance.
Step 3: Evaluate other options
It increases concurrency but risks livelock under high contention is incorrect as concurrency is reduced; It eliminates deadlock but can cause starvation due to unfair scheduling is incorrect because starvation is not guaranteed; It guarantees fairness but requires complex priority inheritance mechanisms is incorrect as priority inheritance is unrelated here.
Final Answer:
Option A -> Option A
Quick Check:
Centralized control trades deadlock prevention for potential bottleneck and failure risk.
Hint: Global waiter = deadlock-free but centralized bottleneck [OK]
Common Mistakes:
Confusing starvation with deadlock prevention
Assuming increased concurrency with global waiter
Misattributing priority inheritance to this solution
4. Which of the following statements about the C-SCAN disk scheduling algorithm is INCORRECT?
medium
A. C-SCAN services requests in one direction only and jumps back to the beginning without servicing requests on the return trip.
B. C-SCAN eliminates starvation by always servicing the closest request next.
C. C-SCAN can cause longer average seek times than SSTF because it ignores the closest requests on the return path.
D. C-SCAN provides a more uniform wait time compared to SCAN by treating the disk as a circular list.
Solution
Step 1: Review C-SCAN behavior
C-SCAN moves the head in one direction, servicing requests, then jumps back to the start without servicing requests on the return.
Step 2: Understand fairness and wait times
This approach provides uniform wait times and avoids starvation.
Step 3: Analyze each option
C-SCAN eliminates starvation by always servicing the closest request next. is incorrect because C-SCAN does not always service the closest request next; it ignores requests on the return jump.
Final Answer:
Option B -> Option B
Quick Check:
C-SCAN eliminates starvation by always servicing the closest request next. is the only incorrect statement about C-SCAN.
Hint: C-SCAN jumps back without servicing requests, so closest next request isn't guaranteed
Common Mistakes:
Assuming C-SCAN always picks the closest request next
Confusing C-SCAN with SCAN regarding servicing on return
Believing C-SCAN causes starvation
5. If a system uses the working set model but still experiences thrashing under heavy load, which advanced technique should be applied next to mitigate thrashing?
hard
A. Increase the working set window size to capture more pages per process
B. Implement load control to reduce the number of active processes competing for frames
C. Disable page replacement algorithms to avoid unnecessary page faults
D. Assign a fixed number of frames to each process regardless of working set size
Solution
Step 1: Understand why thrashing persists despite working set model
Even with working set allocation, total demand may exceed physical memory.
Step 2: Analyze options
A is incorrect because increasing window size may increase working set size, worsening thrashing. B is correct because load control reduces active processes, lowering total memory demand. C is incorrect because disabling page replacement is not feasible and increases faults. D is incorrect because fixed allocation ignores dynamic working sets, risking thrashing.
Final Answer:
Option B -> Option B
Quick Check:
Load control is the next step after working set model to prevent thrashing under overload.
Hint: Load control = reduce active processes to fit memory