Compare the performance of FCFS, SJF, Priority (Preemptive) and RR algorithms
Consider the following four processes, with the length of the CPU burst given in milliseconds.
|
Process |
Arrival Time |
Burst Time |
Priority |
|
P1 |
0 |
11 |
2 |
|
P2 |
5 |
28 |
0 |
|
P3 |
8 |
2 |
3 |
|
P4 |
2 |
10 |
2 |
Some Definitions:
1. Average Waiting Time = Waiting Time of all Processes / Total Number of Process
2.
Turnaround
Time = Waiting time in the ready queue + executing time + waiting time in
waiting-queue for I/O
FCFS Solution:
|
Process |
Arrival Time |
Burst Time |
Waiting Time |
Turnaround Time |
|
P1 |
0 |
11 |
0 |
11 |
|
P2 |
5 |
28 |
16 |
44 |
|
P3 |
8 |
2 |
41 |
43 |
|
P4 |
2 |
10 |
9 |
19 |
Gangchart:
|
P1 |
P4 |
P2 |
P3 |
Average Waiting Time= (0+16+41+9)/4=66/4=16.5 ms
Average Turnaround Time= (11+44+43+19)/4=117/4= 29.25 ms
Average Throughput = (11+28+2+10)/4=12.75 ms
SJF Solution:
|
Process |
Arrival Time |
Burst Time |
Waiting Time |
Turnaround Time |
|
P1 |
0 |
11 |
0 |
11 |
|
P2 |
5 |
28 |
18 |
46 |
|
P3 |
8 |
2 |
3 |
50 |
|
P4 |
2 |
10 |
11 |
21 |
Gangchart:
|
P1 |
P3 |
P4 |
P2 |
Average Waiting Time= (0+18+3+11)/4=32/4=8 ms
Average Turnaround Time= (11+46+50+21)/4=83/4= 20.75 ms
Average Throughput = (11+28+2+10)/4=12.75 ms
Priority
Solution:
|
Process |
Arrival Time |
Priority |
Burst Time |
Waiting Time |
Turnaround Time |
|
P1 |
0 |
2 |
11 |
28 |
39 |
|
P2 |
5 |
0 |
28 |
0 |
28 |
|
P3 |
8 |
3 |
2 |
41 |
43 |
|
P4 |
2 |
2 |
10 |
37 |
47 |
Gangchart:
|
P1 |
P2 |
P1 |
P4 |
P3 |
W(P1)=33-5=28;
W(P2)=5-5=0; W(P3)=49-8=41; W(P4)=39-2=37
Average Waiting Time= (28+0+41+37)/4=106/4=26.5 ms
Average Turnaround Time= (39+28+43+47)/4=157/4= 39.25 ms
Average Throughput = (11+28+2+10)/4=12.75 ms
Round Robin(RR)
Solution:
|
Process |
Arrival Time |
Burst Time |
Waiting Time |
Turnaround Time |
|
P1 |
0 |
11 |
22 |
33 |
|
P2 |
5 |
28 |
18 |
46 |
|
P3 |
8 |
2 |
2 |
4 |
|
P4 |
2 |
10 |
20 |
30 |
Gangchart:
|
P1 |
P4 |
P2 |
P3 |
W(P1)=12+10=22;
W(P2)=12+6=18; W(P3)=2; W(P4)=10+10=20
Average Waiting Time= (22+18+2+20)/4=62/4=15.5 ms
Average Turnaround Time= (33+46+4+30)/4=113/4= 28.25 ms
Average Throughput = (11+28+2+10)/4=12.75 ms
Performance
Analysis:
|
Parameter |
FCFS |
SJF |
Priority |
RR |
|
Average Waiting
Time(ms) |
16.5 |
8 |
26.5 |
15.5 |
|
Average Turnaround
Time (ms) |
29.25 |
20.75 |
39.25 |
28.25 |
|
Average Throughput
(ms) |
12.75 |
12.75 |
12.75 |
12.75 |
So, SJF algorithm is better for this problem.
No comments