Definition:
Round Robin is a preemptive CPU scheduling algorithm where each process is assigned a fixed time slice or quantum. The CPU executes each process for this fixed amount of time in a cyclic order. If a process does not finish in its time quantum, it is moved to the end of the ready queue.
Key Features:
- Type: Preemptive scheduling
- Basis: Time-sharing system
- Queue type: FIFO (First In First Out)
- Preemption: Occurs after a fixed time quantum expires
- Fairness: Every process gets equal CPU time turn by turn
Working of Round Robin:
- All processes are kept in a ready queue.
- Each process gets the CPU for a fixed time quantum (say 4 ms).
- If a process completes within the time quantum, it leaves the CPU.
- If not, it is preempted and moved to the end of the ready queue.
- The CPU then schedules the next process in the queue.
Example:
| Process | Burst Time (ms) |
|---|---|
| P1 | 10 |
| P2 | 5 |
| P3 | 8 |
Time Quantum = 4 ms
Execution Order:
P1 (4) → P2 (4) → P3 (4) → P1 (4) → P2(1) → P3 (4) → p1 (2)
Gantt Chart:
| P1 | P2 | P3 | P1 | P2 | P3 | p1
0 4 8 12 16 17 21 23
Advantages:
- Fairness: Every process gets equal CPU time.
- Good for time-sharing systems.
- No starvation: All processes get a chance to execute.
Disadvantages:
- Performance depends on the time quantum:
- If too large, RR → FCFS (First Come First Serve).
- If too small, too many context switches (inefficient).
- Higher overhead due to frequent context switching.
Applications:
- Widely used in time-sharing and interactive systems (e.g., modern operating systems).
his is a CPU Scheduling – Round Robin (RR) problem.
Given
- Time Quantum (TQ) = 3
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 2 | 3 |
| P3 | 3 | 2 |
| P4 | 1 | 3 |
Step 1: Order by Arrival Time
Arrival sequence:
- Time 0 → P1
- Time 1 → P4
- Time 2 → P2
- Time 3 → P3
Step 2: Draw the Gantt Chart (Round Robin, TQ = 3)
Execution Flow
- Time 0–3 → P1 executes (remaining burst = 2)
- Time 3–6 → P4 executes (burst finished)
- Time 6–9 → P2 executes (burst finished)
- Time 9–11 → P1 executes (burst finished)
- Time 11–13 → P3 executes (burst finished)
Gantt Chart
0 3 6 9 11 13
| P1 | P4 | P2 | P1 | P3 |
Step 3: Completion Time (CT)
| Process | Completion Time |
|---|---|
| P1 | 11 |
| P2 | 9 |
| P3 | 13 |
| P4 | 6 |
Step 4: Turnaround Time (TAT)
TAT = Completion Time − Arrival Time
| Process | TAT |
|---|---|
| P1 | 11 − 0 = 11 |
| P2 | 9 − 2 = 7 |
| P3 | 13 − 3 = 10 |
| P4 | 6 − 1 = 5 |
Step 5: Waiting Time (WT)
WT = Turnaround Time − Burst Time
| Process | WT |
|---|---|
| P1 | 11 − 5 = 6 |
| P2 | 7 − 3 = 4 |
| P3 | 10 − 2 = 8 |
| P4 | 5 − 3 = 2 |
Final Answer Summary
✅ Gantt Chart
0 | P1 | 3 | P4 | 6 | P2 | 9 | P1 | 11 | P3 | 13
✅ Average Times
- Average Waiting Time
= (6 + 4 + 8 + 2) / 4 = 5 - Average Turnaround Time
= (11 + 7 + 10 + 5) / 4 = 8.25
If you want, I can also:
- Explain this step-by-step in exam writing format
- Solve it using FCFS / SJF / Priority for comparison