FCFS Scheduling in OS

FCFS stands for First-Come-First-Serve. FCSF is an OS scheduling algorithm that executes requests and processes automatically. The OS stores these processes in the form of a queue in order of their arrival. Processes requesting the CPU first get the CPU allocation first in this easy and simple algorithm with the help of a FIFO queue.

After entering the ready queue, the PCB of a process links itself with the tail of the queue. Thus, when the CPU becomes free, it is assigned to the process that is at the beginning of the queue. The process that has the least arrival time receives the processor first.

A simple real-life example of this algorithm is the cash counter. There is a queue on the counter. The person who arrives first at the counter receives the services first, followed by the second person, then third, and so on. The CPU process also works like this.

Characteristics of FCFS Scheduling

Following are some characteristics of FCFS:

• Supports both non-preemptive and preemptive scheduling.
• Executes jobs on the basis of first-come, first-serve.
• Easy to implement and use.
• Poor in performance, and has high wait time.
• May cause starvation if the first job has the longest burst time.

Working of FCFS in OS

Calculating Average Waiting Time:

Following is a list of five processes with the same arrival time and different burst times.

Process	Burst Time	Arrival Time
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Following are the steps to apply FCFS scheduling on the above data:

STEP 1. The process starts with the job that has the least arrival time. Thus, P4 with an arrival time of 0.

QUEUE
RUNNING PROCESSES	P4

STEP 2. At time = 1, the next process arrives; P3. Since P4 is still executing, P3 is placed in a queue.

QUEUE	P3
RUNNING PROCESSES	P4

STEP 3. At time = 2, process P1 arrives in the queue.

QUEUE	P3	P1
RUNNING PROCESSES	P4

STEP 4. At time = 3, process P4 completes executing.

QUEUE	P3	P1
RUNNING PROCESSES	P4

STEP 5. At time = 4, P5 arrives in the queue and the process P3 that arrived first in the queue starts executing.

QUEUE	P1	P5
RUNNING PROCESSES	P4	P3

STEP 6. At time = 5, process P2 arrives in the queue.

QUEUE	P1	P5	P2
RUNNING PROCESSES	P4	P3

STEP 7. At time 11, process P3 completes executing.

QUEUE	P1	P5	P2
RUNNING PROCESSES	P4	P3

STEP 8. At time = 11, process P1 starts executing. With a burst time of 6, it completes execution at time = 17.

QUEUE	P5	P2
RUNNING PROCESSES	P4	P3	P1

STEP 9. At time = 17, process P5 starts executing. With a burst time of 4, it completes execution at time = 21.

QUEUE	P2
RUNNING PROCESSES	P4	P3	P1	P5

STEP 10. At time = 21, process P2 starts executing. With a burst time of 2, it completes execution at time = 23.

QUEUE
RUNNING PROCESSES	P4	P3	P1	P5	P2

STEP 11. The average time is:

P4	P3	P1	P5	P2
0	3                                    11	17	21	23

Waiting time = Starting time – Arrival time

P4 = 0 – 0 = 0

P3 = 3 – 1 = 2

P1 = 11 – 2 = 9

P5 = 17 – 4 = 13

P2 = 21 – 5 = 16

Average Waiting Time = (0+2+9+13+16)/5 = 40/5 = 8

Advantages of FCFS

Following are the advantages of FCFS scheduling:

• Simplest CPU scheduling algorithm.
• Easy to program.
• Works on a first-come, first-serve basis.

Disadvantages of FCFS

Following are the disadvantages of FCFS:

• It doesn’t release the CPU until it finishes executing as it is a Non-Preemptive CPU scheduling algorithm.
• May cause starvation if the first job has the longest burst time.
• High Average Waiting Time.
• Short processes at the back of the queue have to wait for the long processes to finish execution.
• Not ideal for time-sharing systems.
• Inefficient.

Summary

FCFS is an OS scheduling algorithm that executes requests and processes automatically. It is both non-preemptive and pre-emptive. It works on the technique of FIFO and is the simplest and easiest form of the scheduling algorithm. The processes that are not processing form a queue and wait for the CPU to get free.