FCFS Scheduling in OS
We offer you a brighter future with industry-ready online courses - Start Now!!
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.
Did you know we work 24x7 to provide you best tutorials
Please encourage us - write a review on Google