Group Assignment for 3rd Year IT department students
*. 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. Round Robin with time quantum = 2
Process Arrival Time Burst Time
P1 0 7
P2 1 4
P3 2 1
P4 3 4
P5 4 5
P6 5 2
The process arrival time indicates the time at which the process arrives in the system, and the burst time is the total time required by each process to complete.
Using Round Robin scheduling with a time quantum of 2, we can calculate the average waiting time as follows:
1. P1 arrives at time 0 and gets executed for 2 units of time. Remaining burst time for P1 = 7 - 2 = 5.
2. P2 arrives at time 1 and gets executed for 2 units of time. Remaining burst time for P2 = 4 - 2 = 2.
3. P3 arrives at time 2 and gets executed for 1 unit of time. Remaining burst time for P3 = 1 - 1 = 0.
4. P4 arrives at time 3 and gets executed for 2 units of time. Remaining burst time for P4 = 4 - 2 = 2.
5. P5 arrives at time 4 and gets executed for 2 units of time. Remaining burst time for P5 = 5 - 2 = 3.
6. P6 arrives at time 5 and gets executed for 2 units of time. Remaining burst time for P6 = 2 - 2 = 0.
Now, we need to go back to the first process P1 and continue executing until all processes have completed their burst time.
7. P1 gets executed for the remaining burst time, which is 5 units.
8. P2 gets executed for the remaining burst time, which is 2 units.
9. P4 gets executed for the remaining burst time, which is 2 units.
10. P5 gets executed for the remaining burst time, which is 3 units.
The final Gantt chart for Round Robin scheduling is as follows:
P1 P2 P3 P4 P5 P6 P1 P4 P5 P1 P5 P1
To calculate the average waiting time, we measure the waiting time for each process. Waiting time is the difference between the completion time and the arrival time.
P1: Waiting time = (2 + 13 - 0) / 2 = 7.5
P2: Waiting time = (4 + 12 - 1) / 2 = 7.5
P3: Waiting time = (3 - 2) / 2 = 0.5
P4: Waiting time = (9 + 16 - 3) / 2 = 11
P5: Waiting time = (11 + 14 - 4) /2 = 10.5
P6: Waiting time = (13 - 5) / 2 = 4
Average waiting time = (7.5 + 7.5 + 0.5 + 11 + 10.5 + 4) / 6 = 41/6 = 6.83
2. FCFS (First-Come-First-Serve)
For FCFS scheduling, we execute the processes in the order of their arrival. The process Gantt chart would be as follows:
P1 P2 P3 P4 P5 P6
To calculate the average waiting time, we use the same formula as before:
P1: Waiting time = (7 + 23 - 0) / 6 = 5.83
P2: Waiting time = (11 + 15 - 1) / 6 = 4.17
P3: Waiting time = (12 - 2) / 6 = 1
P4: Waiting time = (15 + 19 - 3) / 6 = 3.5
P5: Waiting time = (19 + 24 - 4) / 6 = 3.17
P6: Waiting time = (23 - 5) / 6 = 3
Average waiting time = (5.83 + 4.17 + 1 + 3.5 + 3.17 + 3) / 6 = 21.67 / 6 = 3.61
3. SJF (Shortest Job First)
For SJF scheduling, we execute the process with the shortest burst time first. The process Gantt chart would be as follows:
P3 P6 P2 P4 P5 P1
To calculate the average waiting time, we use the same formula:
P3: Waiting time = (1 - 2) / 6 = -0.17 (Negative waiting time indicates the process arrived after completion, so we set it to 0)
P6: Waiting time = (2 - 5) / 6 = -0.5 (Similarly, set it to 0)
P2: Waiting time = (5 + 8 - 1) / 6 = 2
P4: Waiting time = (9 + 14 - 3) / 6 = 3.33
P5: Waiting time = (14 + 19 - 4) / 6 = 4.17
P1: Waiting time = (19 - 0) / 6 = 3.17
Average waiting time = (0 + 0 + 2 + 3.33 + 4.17 + 3.17) / 6 = 12.67 / 6 = 2.11
4. Comparison and analysis:
Based on the average waiting time:
- Round Robin (6.83) has the highest average waiting time, followed by FCFS (3.61) and SJF (2.11).
- SJF (Shortest Job First) algorithm performs the best in terms of average waiting time, as it prioritizes the processes with the shortest burst time.
- FCFS (First-Come-First-Serve) performs better than Round Robin as it doesn't involve preemption and allows the process with the earliest arrival time to execute first.
Process synchronization is not directly relevant to CPU scheduling algorithms. It is primarily concerned with coordinating the execution of multiple processes or threads to avoid conflicts and ensure proper order of execution.
To calculate the average waiting time for each scheduling policy, we need to follow the given arrival time and burst time for the set of 6 processes. Let's work through each policy step-by-step:
Process | Arrival Time | Burst Time
--------------------------------------
Process 1 | 0 | 5
Process 2 | 1 | 3
Process 3 | 2 | 8
Process 4 | 3 | 6
Process 5 | 4 | 2
Process 6 | 5 | 4
1. Round Robin (time quantum = 2)
- The time quantum is 2, which means each process will get 2 units of CPU execution time.
- The scheduling will be done in a round-robin manner, where each process gets a turn based on their arrival time.
- Let's calculate the waiting time for each process:
Process | Burst Time | Remaining Time | Waiting Time
-----------------------------------------------------
Process 1 | 5 | 3 | 8
Process 2 | 3 | 1 | 2
Process 3 | 8 | 4 | 2
Process 4 | 6 | 2 | 5
Process 5 | 2 | 0 | 2
Process 6 | 4 | 0 | 3
Total waiting time = 22
Average waiting time = Total waiting time / Number of processes
= 22 / 6
≈ 3.67
2. FCFS (First-Come, First-Served)
- FCFS scheduling follows the arrival time of processes, executing them in the order of their arrival.
- Let's draw the process Gantt chart and calculate the waiting time:
Process Gantt Chart: |P1|P2|P3|P4|P5|P6|
Waiting Time for each process:
Process | Burst Time | Waiting Time
--------------------------------------
Process 1 | 5 | 0
Process 2 | 3 | 5
Process 3 | 8 | 8
Process 4 | 6 | 16
Process 5 | 2 | 22
Process 6 | 4 | 24
Total waiting time = 24
Average waiting time = Total waiting time / Number of processes
= 24 / 6
= 4
3. SJF (Shortest Job First)
- SJF scheduling selects the process with the shortest burst time first.
- Let's calculate the waiting time for each process:
Process | Burst Time | Waiting Time
--------------------------------------
Process 1 | 5 | 0
Process 2 | 3 | 5
Process 3 | 8 | 8
Process 4 | 6 | 16
Process 5 | 2 | 22
Process 6 | 4 | 8
Total waiting time = 59
Average waiting time = Total waiting time / Number of processes
= 59 / 6
≈ 9.83
4. Comparison and Analysis
- Based on the average waiting time calculated for each scheduling policy:
- Round Robin has an average waiting time of 3.67.
- FCFS has an average waiting time of 4.
- SJF has an average waiting time of 9.83.
- From these results, we can analyze the performance and efficiency of each algorithm:
- Round Robin outperforms FCFS and SJF in terms of average waiting time as it provides fair CPU execution to each process.
- FCFS has a better average waiting time than SJF but is outperformed by Round Robin.
- SJF has the highest average waiting time, indicating that it may not be suitable for this set of processes as it prioritizes shorter processes over longer ones, causing longer processes to wait longer.
- Process synchronization may play a role in determining the efficiency of scheduling policies, particularly in scenarios where processes are dependent on one another. However, the given information does not provide specific details on process synchronization.
To calculate the average waiting time for each scheduling policy and compare the results, follow these steps:
1. Step One: Understanding the input
- We are given the arrival time and burst time for 6 processes.
- Make note of the arrival time and burst time for each process.
2. Step Two: Implementing the scheduling policies
a) Implement the Round Robin (RR) algorithm with a time quantum of 2.
b) Implement the First-Come, First-Served (FCFS) algorithm.
c) Implement the Shortest Job First (SJF) algorithm.
3. Step Three: Calculate the average waiting time for RR:
- Use time quantum 2 and execute the processes according to the RR algorithm.
- Calculate the waiting time for each process (waiting time = turnaround time - burst time).
- Find the average waiting time by summing up all the waiting times and dividing by the total number of processes.
4. Step Four: Draw the Gantt chart for FCFS:
- Arrange the processes based on their arrival time.
- Draw a horizontal timeline to represent the CPU execution.
- Fill in each process in the order of their arrival time and calculate the waiting time for each process.
- Mark the start and end times for each process on the Gantt chart.
5. Step Five: Calculate the average waiting time for FCFS:
- Calculate the waiting time for each process (waiting time = turnaround time - burst time).
- Find the average waiting time by summing up all the waiting times and dividing by the total number of processes.
6. Step Six: Calculate the average waiting time for SJF:
- Use the SJF algorithm to schedule the processes based on their burst times.
- Calculate the waiting time for each process (waiting time = turnaround time - burst time).
- Find the average waiting time by summing up all the waiting times and dividing by the total number of processes.
7. Step Seven: Compare the average waiting times for all three algorithms:
- Analyze and compare the results obtained from RR, FCFS, and SJF algorithms.
- Identify the algorithm with the lowest average waiting time.
- Provide an explanation and analysis of the outcomes based on process synchronization.
Note: The specific calculations and implementation details for each algorithm will depend on the programming language or simulator being used.