Round Robin Scheduling - Quantum & Turnaround Time

▶

Steps

setup

Initialize Processes and Ready Queue

All processes are created with their arrival and burst times. The ready queue is empty initially. The CPU is idle at time 0.

💡 Initialization sets up the process list and prepares the scheduler to start at time 0 with no processes ready yet.

Line:

processes = [P1, P2, P3, P4]
ready_queue = []
time = 0
cpu_running = None

💡 Processes exist but none have arrived yet; CPU is idle waiting for arrivals.

setup

Process P1 Arrives and Enters Ready Queue

At time 0, process P1 arrives and is moved from new to ready state and added to the ready queue.

💡 Arrival events add processes to the ready queue so they can be scheduled.

Line:

if time == 0:
  ready_queue.append(P1)
  P1.state = 'ready'

💡 The ready queue now contains P1, so CPU can start scheduling.

expand

Start Running P1 for Quantum 2

CPU picks P1 from the ready queue to run for up to the quantum of 2 units. P1 state changes to running.

💡 Round Robin picks the first ready process to run for a fixed time slice.

Line:

current = ready_queue.pop(0)
current.state = 'running'
cpu_running = current

💡 CPU is now busy running P1, ready queue is empty temporarily.

expand

Run P1 for 1 Unit; P2 Arrives

P1 runs for 1 unit of time. At time 1, P2 arrives and is added to the ready queue.

💡 Time advances one unit; arrivals can happen during execution and update the ready queue.

Line:

time += 1
P1.burst_remaining -= 1
if time == 1:
  ready_queue.append(P2)
  P2.state = 'ready'

💡 Ready queue now contains P2 while P1 is running.

expand

Run P1 for 1 More Unit; P3 Arrives

P1 runs for the second unit of its quantum. At time 2, P3 arrives and is added to the ready queue.

💡 Completing the quantum slice triggers preemption after this step.

Line:

time += 1
P1.burst_remaining -= 1
if time == 2:
  ready_queue.append(P3)
  P3.state = 'ready'

💡 Ready queue now contains P2 and P3 in order.

shrink

Preempt P1 and Enqueue Back; Start Running P2

P1's quantum expires with remaining burst 3, so it is preempted and added to the ready queue's end. P2 is dequeued and starts running.

💡 Round Robin preempts after quantum and cycles processes fairly.

Line:

if P1.burst_remaining > 0:
  P1.state = 'ready'
  ready_queue.append(P1)
current = ready_queue.pop(0)
current.state = 'running'
cpu_running = current

💡 CPU switches to P2; ready queue updates to [P3, P1].

expand

Run P2 for 1 Unit; P4 Arrives

P2 runs for 1 unit. At time 3, P4 arrives and is added to the ready queue.

💡 Arrivals continue during execution and update the ready queue.

Line:

time += 1
P2.burst_remaining -= 1
if time == 3:
  ready_queue.append(P4)
  P4.state = 'ready'

💡 Ready queue now contains P3, P1, and P4 in order.

shrink

Run P2 for 1 More Unit; Quantum Expires

P2 runs for the second unit of its quantum. Its burst remaining is now 1. Quantum expires, so P2 is preempted and added to the ready queue.

💡 Processes are preempted after quantum if not finished, ensuring fairness.

Line:

time += 1
P2.burst_remaining -= 1
if P2.burst_remaining > 0:
  P2.state = 'ready'
  ready_queue.append(P2)

💡 Ready queue updates to [P3, P1, P4, P2].

expand

Start Running P3

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.

P1

new

burst: 5

P2

new

burst: 3

P3

new

burst: 8

P4

new

burst: 6

Ready Queue

empty

Waiting Queue

empty

🖥CPUidlet=0

Transition new → ready pid:P1 - arrival at time 0

P1

ready

burst: 5

P2

new

burst: 3

P3

new

burst: 8

P4

new

burst: 6

Ready Queue

P1

Waiting Queue

empty

🖥CPUidlet=0

Transition ready → running pid:P1 - start running

P1

running

burst: 5

P2

new

burst: 3

P3

new

burst: 8

P4

new

burst: 6

Ready Queue

empty

Waiting Queue

empty

🖥CPUP1t=0

Transition new → ready pid:P2 - arrival at time 1

P1

running

burst: 4

P2

ready

burst: 3

P3

new

burst: 8

P4

new

burst: 6

Ready Queue

P2

Waiting Queue

empty

🖥CPUP1t=1

Transition new → ready pid:P3 - arrival at time 2

P1

running

burst: 3

P2

ready

burst: 3

P3

ready

burst: 8

P4

new

burst: 6

Ready Queue

P2P3

Waiting Queue

empty

🖥CPUP1t=2

Transition running → ready pid:P1 - quantum expired, preempted

P1

ready

burst: 3

P2

running

burst: 3

P3

ready

burst: 8

P4

new

burst: 6

Ready Queue

P3P1

Waiting Queue

empty

🖥CPUP2t=2

P1

Transition new → ready pid:P4 - arrival at time 3

P1

ready

burst: 3

P2

running

burst: 2

P3

ready

burst: 8

P4

ready

burst: 6

Ready Queue

P3P1P4

Waiting Queue

empty

🖥CPUP2t=3

P1

Transition running → ready pid:P2 - quantum expired, preempted

P1

ready

burst: 3

P2

ready

burst: 1

P3

ready

burst: 8

P4

ready

burst: 6

Ready Queue

P3P1P4P2

Waiting Queue

empty

🖥CPUidlet=4

P1

P2

Transition ready → running pid:P3 - start running

P1

ready

burst: 3

P2

ready

burst: 1

P3

running

burst: 8

P4

ready

burst: 6

Ready Queue

P1P4P2

Waiting Queue

empty

🖥CPUP3t=4

P1

P2

Transition running → ready pid:P3 - quantum expired, preempted

P1

ready

burst: 3

P2

ready

burst: 1

P3

ready

burst: 6

P4

ready

burst: 6

Ready Queue

P1P4P2P3

Waiting Queue

empty

🖥CPUidlet=6

P1

P2

P3

Key Takeaways

✓ 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. In a multi-threaded system, which scenario best describes when starvation occurs?

easy

A. Two or more processes wait indefinitely for each other to release resources.

B. A low-priority process never gets CPU time because higher-priority processes keep running.

C. Processes continuously change states without making progress due to resource contention.

D. A process is blocked waiting for I/O to complete.

Solution

1. Step 1: Identify starvation characteristics

   Starvation happens when a process is perpetually denied access to resources due to scheduling policies favoring others, typically higher-priority processes.

2. Step 2: Analyze each option

   A low-priority process never gets CPU time because higher-priority processes keep running correctly describes starvation as a low-priority process being indefinitely postponed. Two or more processes wait indefinitely for each other to release resources describes deadlock, where processes wait on each other. Processes continuously change states without making progress due to resource contention describes livelock, where processes are active but not progressing. A process is blocked waiting for I/O to complete is normal blocking, not starvation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Starvation involves indefinite postponement due to priority, matching a low-priority process never getting CPU time because higher-priority processes keep running.

Hint: Starvation = low priority starved of CPU time

Common Mistakes:

• Confusing starvation with deadlock
• Thinking livelock is the same as starvation

2. In which scenario is the working set model most effective for preventing thrashing in a multiprogramming environment?

easy

A. When processes have highly variable and unpredictable memory access patterns

B. When the system can allocate pages based on the current active set of pages each process uses

C. When the system uses a fixed number of frames per process regardless of workload

D. When the system relies solely on page-fault frequency without considering locality

Solution

1. Step 1: Understand the working set model purpose

   The working set model tracks the set of pages a process actively uses to allocate enough frames to avoid thrashing.

2. Step 2: Analyze each option

   A is incorrect because unpredictable access patterns reduce the effectiveness of working set tracking.
   B is correct because allocating frames based on the active working set directly prevents thrashing.
   C is incorrect because fixed allocation ignores dynamic working set size, risking thrashing.
   D is incorrect because page-fault frequency alone does not capture locality as precisely as working set.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Working set model adapts allocation to active pages, preventing thrashing effectively.

Hint: Working set = active pages -> allocate accordingly

Common Mistakes:

• Assuming fixed frame allocation prevents thrashing
• Believing page-fault frequency alone suffices
• Ignoring locality in memory allocation

3. Why might using multiple threads within a single process not always improve performance compared to multiple processes?

medium

A. Because thread context switching is slower than process context switching

B. Because threads have higher memory overhead than processes

C. Because threads share the same memory space, leading to potential synchronization bottlenecks

D. Because threads cannot run on multiple CPU cores simultaneously

Solution

1. Step 1: Analyze memory overhead

   Threads share memory, so they have lower memory overhead than processes, making Because threads have higher memory overhead than processes incorrect.

2. Step 2: Consider synchronization issues

   Shared memory requires synchronization mechanisms (locks, mutexes), which can cause contention and reduce performance.

3. Step 3: Evaluate context switching speed

   Thread context switching is generally faster than process switching, so Because thread context switching is slower than process context switching is false.

4. Step 4: Understand CPU core utilization

   Threads can run on multiple cores simultaneously, so Because threads cannot run on multiple CPU cores simultaneously is false.

5. Final Answer:

   Option C -> Option C

6. Quick Check:

   Synchronization overhead can limit thread performance gains [OK]

Hint: Threads share memory but need locks; locks can slow things down [OK]

Common Mistakes:

• Assuming threads always outperform processes
• Confusing context switch overhead between threads and processes
• Believing threads cannot utilize multiple cores

4. If the Dining Philosophers problem is extended to allow philosophers to pick up forks in any order but with a timeout mechanism to release held forks after waiting too long, what is a potential downside of this approach?

hard

A. It completely eliminates deadlock and starvation without any performance penalty

B. It may cause livelock where philosophers repeatedly pick up and release forks without eating

C. It guarantees fairness by enforcing strict turn-taking among philosophers

D. It simplifies synchronization by removing the need for semaphores or locks

Solution

1. Step 1: Understand timeout-based fork release

   Philosophers release forks if waiting too long, preventing indefinite blocking.

2. Step 2: Analyze consequences

   This can cause livelock, where philosophers continuously pick up and release forks without making progress.

3. Step 3: Evaluate other options

   It completely eliminates deadlock and starvation without any performance penalty is false because performance penalties and livelock can occur; It simplifies synchronization by removing the need for semaphores or locks is false as synchronization primitives are still needed; It guarantees fairness by enforcing strict turn-taking among philosophers is false as fairness is not guaranteed.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Timeouts prevent deadlock but risk livelock due to repeated retries.

Hint: Timeouts prevent deadlock but can cause livelock [OK]

Common Mistakes:

• Assuming timeouts solve all synchronization issues
• Confusing livelock with deadlock
• Believing fairness is guaranteed by timeouts

5. In a system using priority scheduling with aging to prevent starvation, what unexpected behavior might occur if a process holding a critical resource is preempted by an aged higher-priority process, and how can this be mitigated?

hard

A. Livelock will occur due to continuous priority changes; mitigation involves fixed priorities.

B. Deadlock will occur immediately; mitigation requires disabling aging.

C. Priority inversion may occur, delaying the critical resource release; mitigation involves priority inheritance protocols.

D. Starvation will worsen for low-priority processes; mitigation involves removing aging.

Solution

1. Step 1: Identify the problem

   When a low-priority process holding a critical resource is preempted by a higher-priority process (due to aging), priority inversion can occur because the resource holder cannot proceed to release the resource.

2. Step 2: Understand mitigation

   Priority inheritance protocols temporarily raise the priority of the resource-holding process to prevent inversion and reduce blocking time.

3. Step 3: Analyze options

   Priority inversion may occur, delaying the critical resource release; mitigation involves priority inheritance protocols correctly identifies priority inversion and its mitigation. Deadlock will occur immediately; mitigation requires disabling aging incorrectly claims deadlock occurs immediately and suggests disabling aging, which is not a solution. Livelock will occur due to continuous priority changes; mitigation involves fixed priorities confuses livelock with priority changes. Starvation will worsen for low-priority processes; mitigation involves removing aging incorrectly states starvation worsens and suggests removing aging, which would increase starvation risk.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Priority inversion + priority inheritance = correct diagnosis and fix.

Hint: Priority inversion = resource holder preempted; fix with inheritance

Common Mistakes:

• Confusing priority inversion with deadlock
• Thinking aging always prevents all scheduling issues