First-Come First-Served Scheduling Algorithm (FCFS)
- First-Come First-Served Scheduling Algorithm (FCFS) is simplest and the most straight forward of all scheduling algorithms. is simplest and the most straight forward of all scheduling algorithms.
- In this scheduling, the process that requests the CPU first is allocated the CPU first. Thus the name first come first served.
- When CPU is free, it is allocated to the process at the head of ready queue. The running process is then removed from the queue.
- FCFS scheduling algorithm is non-preemptive. Once the CPU is allocated to a process that process keeps the CPU until it releases the CPU, either by terminating or by requesting I/O.
FCFS tends to favor CPU-bound processes. Consider a system with one CPU bound process and a number of I/O bound processes. In such as system, the following scenario may arise:
- The CPU bound process will get the CPU and holds it.
- During this time all the other processes will finish their 1/O and move into the ready queue, waiting for CPU. When these processes are waiting in ready queue, the I/O devices are idle.
- After some time, the CPU-bound process finishes its CPU burst (CPU burst time indicates for how much time, the process needs the CPU) and moves to an I/O device. At this time all the 1/O bound processes, (having very short CPU burst) execute quickly and move back to the I/O queues. At this point of time CPU is idle.
- The CPU-bound process will then move back to ready queue and be allocated the CPU. Again all the I/O processes end up waiting in the ready queue until the CPU- bound process is done. The scenario depicted above is called Convoy effect as all other processes wait for one big process to get off the CPU. The result of convoy effect is the lower CPU and device utilization.
Advantages of First-Come First-Served Scheduling (FCFS)
- It is simple to understand and code.
- FCFS is suitable for batch system where one process executes after the other.
- It is better method of scheduling for long processes.
- There is no problem of starvation.
Disadvantages of First-Come First-Served Scheduling (FCFS)
- It suffers from poor performance.
- In FCFS scheduling, waiting time can be large if short requests wait behind the long ones.
- A proper mix of jobs (I/O bound and CPU bound) is needed to achieve good results from FCFS scheduling.
- FCFS is not suited for time sharing systems where each user needs to get the CPU for an equal amount of time interval.
Example of FCFS Scheduling:
|Process||Burst time (in milliseconds)|
If the processes arrived in the order P4, P3, P2, P1, then the average waiting time for the processes obtained from the following Gantt chart:
How to Calculate Completion Time?
Completion time is the time taken by a process for its execution. Calculated by subtracting initial time from time of its completion.
How to calculate Turn Around Time (T.A.T.)?
Turn Around Time (T.A.T.) = Completion Time – Arrival Time (0 if not given in question).
How to calculate Waiting Time for First-Come First-Served Scheduling (FCFS)?
Waiting time (W.T.) = Turn Around Time (T.A.T.) – Burst Time (B.T.)
|Process||Arrival Time (0 if not given in question)||Burst Time||Completion Time||Turn Around Time (T.A.T.)||Waiting time (W.T.)|
Waiting time for P1 = 0 milliseconds
Waiting_time for P2 =30 milliseconds
Waiting time for P3 = 34 milliseconds
Waiting time for P4 = 37 milliseconds
Average waiting time = Total waiting time/No. of process
= (0+30+34 + 37) /4
If the processes arrived in the order P4, P3, P2, P1 then the average waiting time is :
Waiting time for P4 = 0 milliseconds
Waiting_time for P3 = 2 milliseconds
Waiting time for P2 = 5 milliseconds
Waiting time for P1 = 9 milliseconds
Average waiting time = (0+2+5+9)/4
= 4 milliseconds
Thus, the average waiting time depends on the order in which the processes arrive. Thus waiting time greatly vary depending upon whether the process having less CPU burst arrive first in the ready queue.