Operating System Tutorial

What is Operating System Evolution of Operating System Types of Operating System Functions of Operating System What is Kernel and Types of Kernel Operating System Properties Operating System Services Components of Operating System Needs of the Operating System Linux Operating System Unix Operating System Ubuntu Operating System What is DOS Operating System Difference Between Multi-programming and Multitasking What is Thread and Types of Thread Process Management Process State What is Process Scheduler and Process Queue What is Context Switching What is CPU Scheduling Scheduling Algorithm FCFS (First-come-First-Serve) Scheduling SJF (Shortest Job First) Scheduling Round-Robin CPU Scheduling Priority Based Scheduling HRRN (Highest Response Ratio Next) Scheduling Process Synchronization Lock Variable Mechanism TSL Mechanism Turn Variable Mechanism Interested Variable Mechanism What is Producer-Consumer Problem What is Semaphore in Operating System Monitors in Operating System What is Deadlock Deadlock Avoidance Strategies for Handling Deadlock Deadlock Prevention Deadlock Detection and Recovery Resource Allocation Graph Banker’s Algorithm in Operating System Fixed Partitioning and Dynamic Partitioning Partitioning Algorithms What is Paging and Segmentation What is Demand Paging What is Virtual Memory Disk Scheduling Algorithms FCFS and SSTF Disk Scheduling Algorithm SCAN and C-SCAN Disk Scheduling Algorithm Look and C-Look Disk Scheduling Algorithm File in Operating System File Access Methods in Operating System File Allocation Method Directory Structure in Operating System Difference between C-LOOK and C-SCAN Difference between Rotational Latency and Disk Assess Time Trap vs Interrupt How to implement Monitors using Semaphores N-Step-SCAN Disk Scheduling Why is it critical for the Scheduler to distinguish between I/O-bound and CPU-bound programs Difference between C-SCAN and SSTF Difference between SCAN and FCFS Difference between Seek Time and Disk Access Time Difference between SSTF and LOOK

FCFS Scheduling in OS

FCFS: First Come First Serve Scheduling in OS

FCFS is a non-preemptive and preemptive scheduling algorithm that is easy to understand and use. In this, the process which reaches first is executed first, or in other words, the process which requests first for a CPU gets the CPU first.

Example of FCFS: buying tickets at the ticket counter.

FCFS is similar to the FIFO queue data structure. In FCFS, the element which is added in the queue first will leave first.

FCFS is used in Batch Operating Systems.

Characteristics of FCFS Scheduling

The characteristics of FCFS Scheduling are:

  1. FCFS is simple to use and implement.
  2. In FCFS, jobs are executed in a First-come First-serve (FCFS) manner.
  3. FCFS supports both preemptive as well as non-preemptive scheduling algorithm.
  4. FCFS is poor in performance due to high waiting times.

Advantages of FCFS

The advantages of FCFS are:

  1. Easy to program
  2. First come, first serve
  3. Simple scheduling algorithm.

Disadvantages of FCFS

  1. Because of non-preemptive nature, the problem of starvation arises.
  2. More Average waiting time.
  3. Due to its simplicity, FCFS is not effective.
  4. FCFS is not the ideal scheduling for the time-sharing system.
  5. FCFS is a Non-Preemptive Scheduling algorithm, so allocating the CPU to a process will never release the CPU until it completes its execution.
  6. In FCFS, it is not possible to use the resources in a parallel manner, which causes the convoy effect, so the resource utilization is poor in FCFS.

What is Convoy Effect

In FCFS, Convoy Effect is a condition that arises in the FCFS Scheduling algorithm when one process holds the CPU for a long time, and another process can get the CPU only when the process holding the CPU finishes its execution. Due to this, resource utilization is poor and also affects the performance of the operating system.

Example of FCFS Scheduling

In the following example, we have 4 processes with process ID P0, P1, P2, and P3. The arrival time of P0 is 0, P1 is 1, P2 is 2, and P3 is 3. The arrival time and burst time of the processes are given in the following table.

The waiting time and Turnaround time are calculated with the help of the following formula.

         Waiting Time = Turnaround time – Burst Time

          Turnaround Time = Completion time – Arrival time 

Process ID Arrival Time Burst Time Completion Time Turnaround Time Waiting Time
P0 0 6 6 6 0
P1 1 8 14 13 5
P2 2  10 24 22 12
P3 3 12 36 33 21
FCFS Scheduling in OS

Average Waiting Time = 0+5+12+21/4

                                         = 38/4

                                          = 9.5 ms

Average Turnaround Time = 6+13+22+33/4


                                               = 18.5 ms