Understanding Round Robin CPU Scheduling

Round Robin (RR) is a CPU scheduling algorithm where each process is assigned a fixed time slice (also called quantum) in a cyclic way. It is a preemptive algorithm because the CPU can be taken away from a process even before it completes, if its time slice expires. It is designed for time-sharing systems.

When a process gets the CPU, it runs for at most one time slice. If the process completes within the time slice, it exits the system. If the process requires more CPU time, it is preempted and moved to the end of the ready queue. The scheduler then picks the next process from the front of the ready queue.

Key terms in CPU scheduling:

• Arrival Time: The time at which a process enters the ready queue.
• Burst Time: The total time required by a process for its execution on the CPU.
• Completion Time: The time at which a process finishes its execution.
• Turnaround Time: The total time a process spends in the system, from arrival to completion. Calculated as: Completion Time - Arrival Time.
• Waiting Time: The time a process spends waiting in the ready queue. Calculated as: Turnaround Time - Burst Time.
• Time Slice (Quantum): A small unit of time assigned to each process in Round Robin scheduling.

Problem Details

We are given three processes with their respective burst times and arrival times, and a CPU time slice (quantum) of 2 ms for Round Robin scheduling.

We need to find the average turnaround time and average waiting time for these processes using the Round Robin algorithm with a time slice of 2 ms.

Step-by-Step Round Robin Execution

Let's trace the execution of the processes using a Gantt chart representation and track the ready queue. The time slice is 2 ms.

• Time 0: p1 arrives (Arrival Time = 0). Ready Queue (RQ): [p1]. CPU picks p1.
• Time 0 to 2: p1 executes. At time 2, p1's time slice expires. p1 has 3 - 2 = 1 ms burst remaining.
• Time 2: p2 arrives (Arrival Time = 2). p1 is preempted. p2 is added to RQ. p1 is added to the end of RQ. RQ: [p2, p1]. CPU picks p2.
• Time 2 to 4: p2 executes. At time 4, p2's time slice expires. p2 has 4 - 2 = 2 ms burst remaining.
• Time 4: p2 is preempted and added to the end of RQ. RQ: [p1, p2]. CPU picks p1.
• Time 4 to 5: p1 executes. p1 has 1 ms burst remaining and completes at time 5. Completion Time (p1) = 5. RQ: [p2].
• Time 5: p3 arrives (Arrival Time = 5). p3 is added to RQ. RQ: [p2, p3]. CPU picks p2.
• Time 5 to 7: p2 executes. p2 has 2 ms burst remaining and completes at time 7. Completion Time (p2) = 7. RQ: [p3]. CPU picks p3.
• Time 7 to 9: p3 executes. At time 9, p3's time slice expires. p3 has 5 - 2 = 3 ms burst remaining.
• Time 9: p3 is preempted and added to the end of RQ. RQ: [p3]. CPU picks p3.
• Time 9 to 11: p3 executes. At time 11, p3's time slice expires. p3 has 3 - 2 = 1 ms burst remaining.
• Time 11: p3 is preempted and added to the end of RQ. RQ: [p3]. CPU picks p3.
• Time 11 to 12: p3 executes. p3 has 1 ms burst remaining and completes at time 12. Completion Time (p3) = 12. RQ: [].

Gantt Chart:

| p1 (2) | p2 (2) | p1 (1) | p2 (2) | p3 (2) | p3 (2) | p3 (1) |
0      2      4      5      7      9      11      12

Note: Let's re-evaluate the Gantt chart and queue state carefully based on the typical RR implementation where arrival at time t occurs before preemption at time t.

• Time 0: p1 arrives (AT=0). RQ: [p1]. CPU picks p1.
• Time 0 to 2: p1 executes. At time 2, p1's time slice expires (Burst remaining = 1).
• Time 2: p2 arrives (AT=2). p1 is preempted. RQ: [p2, p1]. CPU picks p2.
• Time 2 to 4: p2 executes. At time 4, p2's time slice expires (Burst remaining = 2).
• Time 4: p2 is preempted. RQ: [p1, p2]. CPU picks p1.
• Time 4 to 5: p1 executes (Burst remaining = 1). p1 completes at time 5. Completion Time (p1) = 5. RQ: [p2].
• Time 5: p3 arrives (AT=5). RQ: [p2, p3]. CPU picks p2.
• Time 5 to 7: p2 executes (Burst remaining = 2). p2 completes at time 7. Completion Time (p2) = 7. RQ: [p3]. CPU picks p3.
• Time 7 to 9: p3 executes. At time 9, p3's time slice expires (Burst remaining = 3).
• Time 9: p3 is preempted. RQ: [p3]. CPU picks p3.
• Time 9 to 11: p3 executes. At time 11, p3's time slice expires (Burst remaining = 1).
• Time 11: p3 is preempted. RQ: [p3]. CPU picks p3.
• Time 11 to 12: p3 executes (Burst remaining = 1). p3 completes at time 12. Completion Time (p3) = 12. RQ: [].

Revised Gantt Chart:

| p1 (2) | p2 (2) | p1 (1) | p2 (2) | p3 (2) | p3 (2) | p3 (1) |
0      2      4      5      7      9      11      12

The Gantt chart appears consistent across both interpretations for this specific scenario regarding arrivals vs. preemption at the same time point. Let's proceed with calculating metrics based on these completion times.

Calculating Turnaround and Waiting Times

Now we calculate the turnaround time and waiting time for each process.

Calculating Average Times

Now, we calculate the average turnaround time and average waiting time.

Total Turnaround Time = Turnaround Time(p1) + Turnaround Time(p2) + Turnaround Time(p3)
Total Turnaround Time = 5 ms + 5 ms + 7 ms = 17 ms

Average Turnaround Time = $\frac{\text{Total Turnaround Time}}{\text{Number of Processes}}$
Average Turnaround Time = $\frac{17}{3} \text{ ms} \approx 5.66 \text{ ms}$

Total Waiting Time = Waiting Time(p1) + Waiting Time(p2) + Waiting Time(p3)
Total Waiting Time = 2 ms + 1 ms + 2 ms = 5 ms

Average Waiting Time = $\frac{\text{Total Waiting Time}}{\text{Number of Processes}}$
Average Waiting Time = $\frac{5}{3} \text{ ms} \approx 1.66 \text{ ms}$

Summary of Results

Using Round Robin scheduling with a time slice of 2 ms:

• Average Turnaround Time: $\approx 5.66$ ms
• Average Waiting Time: $\approx 1.66$ ms

Revision Table: Key Scheduling Metrics

Additional Information: Round Robin Characteristics

Round Robin scheduling is known for providing fairness among processes by giving each one a turn with the CPU.

• Pros:
  • Fairness: Ensures no process starves.
  • Good for time-sharing: Provides quick response times for interactive users.
• Cons:
  • Performance depends heavily on the time slice size.
  • Context switching overhead: Frequent switching for small time slices can reduce efficiency.
  • Doesn't prioritize based on process importance or burst time length.

Choosing the right time slice is crucial. A large time slice makes RR behave more like First-Come, First-Served (FCFS). A very small time slice increases context switching overhead.