To calculate the average waiting time, we need to first calculate the waiting time for each process. The waiting time is defined as the time period between the arrival of a process and when it starts executing.
The arrival time and burst time for the processes are as follows:
Process Arrival Time Burst Time
P1 0 3
P2 0 5
P3 1 2
P4 2 7
P5 4 4
P6 6 2
1. Round Robin with time quantum = 2:
To calculate the average waiting time for Round Robin, we simulate the scheduling algorithm. Start with the first process and assign it the CPU for time quantum 2. If the process completes within the time quantum, it is removed from the queue. If it does not complete within the time quantum, it is moved to the end of the queue and the next process is assigned the CPU.
Process Gantt Chart for Round Robin:
|P1|P2|P3|P4|P5|P6|P2|P4|P5|P4|
The '|' represents the context switch.
The waiting time for each process is as follows:
P1: 0
P2: 5
P3: 1
P4: 9
P5: 9
P6: 7
Average Waiting Time = (0 + 5 + 1 + 9 + 9 + 7) / 6 = 31 / 6 = 5.1667
2. FCFS (First-Come, First-Served):
The FCFS scheduling algorithm assigns the CPU to a process based on the order of their arrival. The process with the lowest arrival time is assigned the CPU first.
Process Gantt Chart for FCFS:
|P1|P2|P3|P4|P5|P6|
The '|' represents the context switch.
The waiting time for each process is as follows:
P1: 0
P2: 3
P3: 5
P4: 6
P5: 8
P6: 12
Average Waiting Time = (0 + 3 + 5 + 6 + 8 + 12) / 6 = 34 / 6 = 5.6667
3. SJF (Shortest Job First):
The SJF scheduling algorithm assigns the CPU to the process with the shortest burst time first.
Process Gantt Chart for SJF:
|P3|P1|P2|P5|P6|P4|
The '|' represents the context switch.
The waiting time for each process is as follows:
P1: 1
P2: 4
P3: 0
P4: 9
P5: 6
P6: 11
Average Waiting Time = (1 + 4 + 0 + 9 + 6 + 11) / 6 = 31 / 6 = 5.1667
4. Comparison and Analysis:
Based on the average waiting time:
- The Round Robin algorithm has the lowest average waiting time, followed by SJF, and then FCFS.
- Round Robin and SJF have the same average waiting time, indicating that both algorithms are fairly efficient in minimizing the waiting time.
- FCFS has the highest average waiting time, suggesting that it may not be the best choice for minimizing waiting times.
In terms of process synchronization, Round Robin and FCFS are non-preemptive algorithms, meaning that once a process is assigned the CPU, it will keep using it until it finishes or voluntarily relinquishes it. This can lead to poor utilization of the CPU if a long process is assigned the CPU first. In Round Robin, the time quantum helps to mitigate this issue by allowing other processes to have a chance to execute.
SJF is a preemptive algorithm, meaning that a process with a shorter burst time can preempt a process with a longer burst time. This can result in better CPU utilization and overall performance. However, if the burst times are not accurately estimated, it can lead to frequent context switches and overhead.
In conclusion, Round Robin and SJF are more efficient in terms of average waiting time compared to FCFS. Round Robin provides better process synchronization by allowing equal opportunities for all processes to execute, while SJF optimizes CPU utilization by prioritizing shorter burst time processes.
Consider the set of 6 processes whose arrival time and burst time are given belowIf the CPU scheduling policy is:-
1. Round Robin with time quantum = 2, calculate the average waiting time.
2. FCFS, Draw Process Gantt chart and calculate the average waiting time
3. SJF, calculate the average waiting time and calculate the average waiting time
4. Compare RR, FCFS and SJF algorithm based on average waiting time and analyze
outcome based on process synchronization.
1 answer
1 answer