FCFS Scheduling Algorithm: What is, Example Program
What is First Come First Serve Method?
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 of FCFS method
- 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 of FCFS scheduling
A real-life example of the FCFS method is buying a movie ticket on the ticket counter. In this scheduling algorithm, a person is served according to the queue manner. The person who arrives first in the queue first buys the ticket and then the next one. This will continue until the last person in the queue purchases the ticket. Using this algorithm, the CPU process works in a similar manner.
How FCFS Works? Calculating Average Waiting Time
Here is an example of five processes arriving at different times. Each process has a different burst time.
Process | Burst time | Arrival time |
---|---|---|
P1 | 6 | 2 |
P2 | 2 | 5 |
P3 | 8 | 1 |
P4 | 3 | 0 |
P5 | 4 | 4 |
Using the FCFS scheduling algorithm, these processes are handled as follows.
Step 1) The process begins with P4 which has arrival time 0
Step 2) At time=1, P3 arrives. P4 is still executing. Hence, P3 is kept in a queue.
Process | Burst time | Arrival time |
---|---|---|
P1 | 6 | 2 |
P2 | 2 | 5 |
P3 | 8 | 1 |
P4 | 3 | 0 |
P5 | 4 | 4 |
Step 3) At time= 2, P1 arrives which is kept in the queue.
Process | Burst time | Arrival time |
---|---|---|
P1 | 6 | 2 |
P2 | 2 | 5 |
P3 | 8 | 1 |
P4 | 3 | 0 |
P5 | 4 | 4 |
Step 4) At time=3, P4 process completes its execution.
Step 5) At time=4, P3, which is first in the queue, starts execution.
Process | Burst time | Arrival time |
---|---|---|
P1 | 6 | 2 |
P2 | 2 | 5 |
P3 | 8 | 1 |
P4 | 3 | 0 |
P5 | 4 | 4 |
Step 6) At time =5, P2 arrives, and it is kept in a queue.
Process | Burst time | Arrival time |
---|---|---|
P1 | 6 | 2 |
P2 | 2 | 5 |
P3 | 8 | 1 |
P4 | 3 | 0 |
P5 | 4 | 4 |
Step 7) At time 11, P3 completes its execution.
Step 8) At time=11, P1 starts execution. It has a burst time of 6. It completes execution at time interval 17
Step 9) At time=17, P5 starts execution. It has a burst time of 4. It completes execution at time=21
Step 10) At time=21, P2 starts execution. It has a burst time of 2. It completes execution at time interval 23
Step 11) Let’s calculate the average waiting time for above example.
Waiting time = Start time - Arrival time
P4 = 0-0 = 0
P3 = 3-1 = 2
PI = 11-2 = 9
P5= 17-4 = 13
P2= 21-5= 16
Average Waiting Time
Advantages of FCFS
Here, are pros/benefits of using FCFS scheduling algorithm:
- The simplest form of a CPU scheduling algorithm
- Easy to program
- First come first served
Disadvantages of FCFS
Here, are cons/ drawbacks of using FCFS scheduling algorithm:
- 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.
Summary
- Definition: FCFS is an operating system scheduling algorithm that automatically executes queued requests and processes by order of their arrival
- It supports non-preemptive and pre-emptive scheduling
- algorithm.
- FCFS stands for First Come First Serve
- A real-life example of the FCFS method is buying a movie ticket on the ticket counter.
- It is the simplest form of a CPU scheduling algorithm
- 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.