It is simplest CPU scheduling algorithm. The FCFS scheduling algorithm is non preemptive i.e. once the CPU has been allocated to a process, that process keeps the CPU until it releases the CPU, either by terminating or by requesting I/O.
In this technique, the process that requests the CPU first is allocated the CPU first i.e. when a process enters the ready queue, its PCB is linked onto the tail of the queue. When the CPU is free, it is allocated to the process at the head of the queue. The running process is then removed from the queue.
The average waiting time under this technique is often quite long.
Example
Q1. Consider the following set of processes that arrives at time 0, with the length of the CPU burst given in milliseconds:
Process |
Burst Time |
P1 |
24 |
P2 |
3 |
P3 |
3 |
- Suppose that the processes arrive in the order: P1, P2, and P3
The Gantt chart for the schedule is:
- Waiting time for P1 = 0; P2 = 24; P3 = 27
- Average waiting time: (0 + 24 + 27)/3 = 17 ms
- Turnaround time for P1 = 24; P2 = 27; P3 = 30
- Average Turnaround time: (24 + 27 + 30)/3 = 27 ms
b. Suppose that the processes arrive in the order: P2, P3, and P1
The Gantt chart for the schedule is:
- Waiting time for P1 = 6; P2 = 0; P3 = 3
- Average waiting time: (6 + 0 + 3)/3 = 3 milliseconds
- Turnaround time for P1 = 30; P2 = 3; P3 = 6
- Average Turnaround time: (30 + 3 + 6)/3 = 13 ms
Q2. Consider the following set of processes that arrives at time 0, with the length of the CPU burst given in milliseconds:
Process | Arrival Time | Burst Time |
P1 | 0 | 10 |
P2 | 1 | 6 |
P3 | 3 | 2 |
P4 | 5 | 4 |
Find:
- Average Turnaround Time (ATAT) (ans 14.25)
- Average Waiting Time (AWT) (ans 8.75)
- Waited TAT (WTAT) (ans 1.295)
- Average WTAT (AWTAT) (ans 14.25)
Soln
Process | Arrival Time(T0) | Burst Time (ΔT) | Finish Time (T1) |
TAT=(T1 – T0) |
WT=(TAT-ΔT) |
Response Time (RT) =( T1-ΔT) |
P1 | 0 | 10 | 10 | 10 | 0 | 0 |
P2 | 1 | 6 | 16 | 15 | 9 | 10 |
P3 | 3 | 2 | 18 | 15 | 13 | 16 |
P4 | 5 | 4 | 22 | 17 | 13 | 18 |
- Average Turnaround Time (ATAT) = (10+15+15+17)/4 = 25
- Average Waiting Time (AWT) = (0+9+13+13) /4 = 75
- Waited TAT (WTAT) WTATi= TATi / RTi where i = 1 to n
= (10+15+15+17)/ (0+10+16+18)
= 1.295
- Average WTAT (AWTAT) = WTAT/n = (10+15+15+17)/4 = 14.25