FCFS Algorithm
First Come First Serve (FCFS) is an operating system scheduling algorithm that automatically executes queued requests and processes in order of their arrival. It is the easiest and simplest CPU scheduling algorithm. In this type of algorithm, processes which requests the CPU first get the CPU allocation first. This is managed with a FIFO queue. The full form of FCFS is First Come First Serve.
As the process enters the ready queue, its PCB (Process Control Block) is linked with the tail of the queue and, when the CPU becomes free, it should be assigned to the process at the beginning of the queue.
Characteristics
- It supports non-preemptive and pre-emptive scheduling algorithm.
- Jobs are always executed on a first-come, first-serve basis.
- It is easy to implement and use.
- This method is poor in performance, and the general wait time is quite high.
Example
| process |
Arrival Time |
Burst Time |
| P1 |
2 |
6 |
| P2 |
5 |
3 |
| P3 |
1 |
8 |
| P4 |
0 |
3 |
| P5 |
4 |
4 |
Working
- Step 0) The process begins with P4 which has arrival time 0
- Step 1) At time=1, P3 arrives. P4 is still executing. Hence, P3 is kept in a queue.
- Step 2) At time= 2, P1 arrives which is kept in the queue.
- Step 3) At time=3, P4 process completes its execution.
- Step 4) At time=4, P3, which is first in the queue, starts execution.
- Step 5) At time =5, P2 arrives, and it is kept in a queue.
- Step 6) At time 11, P3 completes its execution.
- Step 7) At time=11, P1 starts execution. It has a burst time of 6. It completes execution at time interval 17
- Step 8) At time=17, P5 starts execution. It has a burst time of 4. It completes execution at time=21
- Step 9) At time=21, P2 starts execution. It has a burst time of 2. It completes execution at time interval 23
- Step 9) After calculating Completion Time using above steps calculate Turn Around Time, Waiting Time and Response Time
Gantt Chart
| P4 |
P3 |
P1 |
P5 |
P2 |
| 0-3 |
3-11 |
11-17 |
17-21 |
21-23 |
Final Table
| process |
Arrival Time |
Burst Time |
Complition Time |
Turn Around Time |
Waiting Tme |
Response Time |
| P1 |
2 |
6 |
17 |
15 |
9 |
9 |
| P2 |
5 |
3 |
23 |
18 |
15 |
15 |
| P3 |
1 |
8 |
11 |
10 |
2 |
2 |
| P4 |
0 |
3 |
3 |
3 |
0 |
0 |
| P5 |
4 |
4 |
21 |
17 |
13 |
13 |
Advantages
- The simplest form of a CPU scheduling algorithm
- Easy to program
- First come first served
Disadvantages
- It is a Non-Preemptive CPU scheduling algorithm, so after the process has been allocated to the CPU, it will never release the CPU until it finishes executing.
- The Average Waiting Time is high.
- Short processes that are at the back of the queue have to wait for the long process at the front to finish.
- Not an ideal technique for time-sharing systems.
- Because of its simplicity, FCFS is not very efficient.