Consider the following set of processes and the length of CPU burst time given in milliseconds: Process CPU Burst time (ms) P 1 5 P 2 7 P 3 6 P 4 4 Assume that processes being scheduled with Round-Robin Scheduling Algorithm with Time Quantum 4ms. Then the waiting time for P 4is _________ ms.
12
Understanding Round-Robin Scheduling and Waiting Time
This problem requires us to calculate the waiting time for a specific process (P4) when using the Round-Robin (RR) scheduling algorithm. Round-Robin is a CPU scheduling algorithm where each process is assigned a fixed time slice, called a quantum, and is allowed to execute for that time. If a process does not complete within its quantum, it is preempted and moved to the end of the ready queue, and the CPU is given to the next process in the queue. This provides fairness by giving each process a turn.
The waiting time for a process in CPU scheduling is the total time a process spends in the ready queue waiting for the CPU. It can be calculated as the sum of the times a process waits in the ready queue between being ready and getting the CPU.
Problem Details
We are given the following processes and their CPU burst times:
| Process | CPU Burst Time (ms) |
|---|---|
| P1 | 5 |
| P2 | 7 |
| P3 | 6 |
| P4 | 4 |
The scheduling algorithm is Round-Robin with a Time Quantum of 4 ms.
We need to find the waiting time for process P4.
Simulating Round-Robin Execution (Gantt Chart)
Let's simulate the execution of these processes using the Round-Robin algorithm with a time quantum of 4 ms. We assume all processes arrive at time 0.
Initial Ready Queue: [P1, P2, P3, P4]
- Time 0-4: P1 executes for 4 ms. Remaining burst time for P1 = 5 - 4 = 1 ms. P1 is preempted and added to the end of the queue. Ready Queue: [P2, P3, P4, P1]
- Time 4-8: P2 executes for 4 ms. Remaining burst time for P2 = 7 - 4 = 3 ms. P2 is preempted and added to the end of the queue. Ready Queue: [P3, P4, P1, P2]
- Time 8-12: P3 executes for 4 ms. Remaining burst time for P3 = 6 - 4 = 2 ms. P3 is preempted and added to the end of the queue. Ready Queue: [P4, P1, P2, P3]
- Time 12-16: P4 executes for 4 ms. Remaining burst time for P4 = 4 - 4 = 0 ms. P4 finishes execution at time 16 ms. P4 is removed from the queue. Ready Queue: [P1, P2, P3]
- Time 16-17: P1 executes for its remaining 1 ms. Remaining burst time for P1 = 1 - 1 = 0 ms. P1 finishes execution at time 17 ms. P1 is removed from the queue. Ready Queue: [P2, P3]
- Time 17-20: P2 executes for its remaining 3 ms. Remaining burst time for P2 = 3 - 3 = 0 ms. P2 finishes execution at time 20 ms. P2 is removed from the queue. Ready Queue: [P3]
- Time 20-22: P3 executes for its remaining 2 ms. Remaining burst time for P3 = 2 - 2 = 0 ms. P3 finishes execution at time 22 ms. P3 is removed from the queue. Ready Queue: []
The Gantt Chart for this execution is:
| P1 (4) | P2 (4) | P3 (4) | P4 (4) | P1 (1) | P2 (3) | P3 (2) | |
|---|---|---|---|---|---|---|---|
| 0 | 4 | 8 | 12 | 16 | 17 | 20 | 22 |
Calculating Waiting Time for P4
The waiting time for a process is the total time it spends waiting in the ready queue. For process P4:
P4 arrived at time 0. P4 started its execution at time 12.
The time P4 spent waiting in the ready queue before its first execution slice is from its arrival time (0) until it first got the CPU (12).
Wait time before first burst = Start time of first burst - Arrival time Wait time before first burst = $12 - 0 = 12$ ms.
Since P4 finished execution in its first turn (its burst time was exactly the quantum), it did not have to wait in the queue again after being preempted.
Total Waiting Time for P4 = Wait time before first burst + Wait time after subsequent bursts Total Waiting Time for P4 = $12 + 0 = 12$ ms.
Alternatively, we can calculate waiting time using the formula: Waiting Time = Turnaround Time - Burst Time Turnaround Time = Completion Time - Arrival Time P4 completed execution at time 16. P4 arrived at time 0. Turnaround Time for P4 = $16 - 0 = 16$ ms. Burst Time for P4 = 4 ms. Waiting Time for P4 = $16 - 4 = 12$ ms.
Conclusion
Based on the Round-Robin simulation with a time quantum of 4ms, the waiting time for process P4 is 12 ms.
Revision Table - Round-Robin Scheduling
| Concept | Description |
|---|---|
| Round-Robin (RR) | A preemptive CPU scheduling algorithm designed for time-sharing systems. |
| Time Quantum | A fixed time slice assigned to each process in RR scheduling. |
| Preemption | Stopping a process from execution before its CPU burst is complete, usually after its time quantum expires. |
| Ready Queue | A queue holding processes that are ready to execute, waiting for the CPU. In RR, it's typically a FIFO queue. |
| Waiting Time | The total time a process spends waiting in the ready queue. |
| Turnaround Time | The total time from process arrival to completion (Completion Time - Arrival Time). |
Additional Information - CPU Scheduling Metrics
Besides waiting time, other important metrics in CPU scheduling include:
- 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. Turnaround Time = Completion Time - Arrival Time.
- Response Time: The time from process arrival until the first time it gets the CPU. For P4 in this case, Response Time = 12 - 0 = 12 ms.
- Throughput: The number of processes completed per unit of time.
- CPU Utilization: The percentage of time the CPU is busy executing processes.
Round-Robin scheduling generally provides good response time and fairness, but average waiting time can be higher compared to algorithms like Shortest Job First (SJF), especially with a large quantum.
Important Questions from Process Scheduling - Teaching
Consider the following four processes with the arrival time and length of CPU burst given in milliseconds :
Process Arrival Time Burst Time P 1 0 8 P 2 1 4 P 3 2 9 P 4 3 5 The average waiting time for preemptive SJF scheduling algorithm is
Consider three intensive processes, which requires 10,20 and 30 units of time and arrive at times 0,2 and 6 respectively. how many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end.
Which of the following CPU scheduling algorithms is/are supported by LINUX operating system?
Given CPU time slice of 2 ms and the following list of processes.
Process
Burst time (ms)
Arrival time (ms)
p 1
3
0
p 2
4
2
p 3
5
5
Find average turnaround time and average waiting time using round-robin CPU scheduling?
In which of the following scheduling criteria, context switching will never take place?
