Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Medium

FCFS Scheduling

Author Nikunj Goel
0 upvote
gp-icon
Operating system track
Free guided path
14 chapters
83+ problems
gp-badge
Earn badges and level up

Introduction

An operating system (OS) is a software program that serves as a conduit between computer hardware and the user. It is a piece of software that coordinates the execution of application programs, software resources, and computer hardware. It also aids in the control of software and hardware resources such as file management, memory management, input/output, and a variety of peripheral devices such as a disc drive, printers, and so on. To run other applications, every computer system must have at least one operating system. Browsers, MS Office, Notepad Games, and other applications require an environment to execute and fulfill their functions.

fcfs scheduling

Let us take a brief look at some Scheduling Concepts before getting into FCFS Scheduling.

CPU Scheduling

CPU scheduling is the process of deciding which process will use the CPU exclusively while another is halted.

The primary purpose of CPU scheduling is to guarantee that the Operating System selects at least one of the processes in the ready queue to run whenever the CPU is idle. The CPU scheduler manages the selection process. It selects from among the ready-to-run processes in memory.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Scheduling Criteria

Distinct CPU scheduling methods have different qualities, and choosing one over another is based on a variety of criteria.

The following are some of the criteria:

  • CPU utilization – Any CPU scheduling algorithm's principal goal is to keep the CPU as busy as feasible. CPU utilization can theoretically range from 0 to 100 percent, but it can vary from 40 to 90 percent in a real-time system, depending on the system's demand.
  • Turnaround time –The turnaround time is the amount of time it takes from the moment a procedure is submitted to the time it is completed.
  • Response time – It is the time taken from submission of the process of the request until the first response is produced.
  • Waiting time is the time spent by a process waiting in the ready queue.
  • Throughput – The throughput of a CPU is a measure of how much work it can complete in a given amount of time. It refers to the number of processes run and finished in a certain amount of time.

FCFS (FIRST-COME, FIRST-SERVED) Scheduling

The most straightforward algorithm is First Come First Served (FCFS).

It's a non-preemptive algorithm, which means that once it starts running, it can't be stopped.

It is implemented using a first-in, first-out (FIFO) queue.

The processes are placed in the ready queue in the order they will arrive.

The process that arrives first goes to the front of the line, while those who come later are pushed to the back.

When the CPU is free, the process that arrives first is dispatched first for execution using the First Come First Served (FCFS) algorithm.

Advantages of FCFS

  • Straightforward: The FCFS algorithm is the most straightforward to integrate into any system.
  • Simple and easy to implement: FCFS is a simple scheduling algorithm that is easy to understand and implement, making it a good choice for small systems.
  • No starvation: Since processes are executed in the order they arrive, no process is left waiting indefinitely, avoiding the problem of starvation.
  • No overhead: FCFS has no overhead associated with scheduling, as it does not require maintaining a scheduling queue or tracking priorities.
  • Non-preemptive: FCFS is a non-preemptive scheduling algorithm, meaning that once a process has started execution, it will continue until it completes or voluntarily yields the CPU.
  • Predictable behavior: FCFS has predictable behavior, as the order in which processes are executed is determined by the order they arrive. This can make it easier to estimate the time it will take for a given set of processes to complete.
  • Favors CPU-bound processes: FCFS is best suited for CPU-bound processes, as it prioritizes long-running processes. This can result in better CPU utilization compared to other scheduling algorithms that prioritize short jobs.

Disadvantages of FCFS

  • Convoy Effect: FCFS leads to the convoy effect.
  • Poor utilization of resources: FCFS scheduling can lead to poor utilization of resources, as processes are scheduled in the order they arrive. This can result in longer wait times and increased resource starvation for high-priority or resource-intensive processes.
  • No consideration for priority: FCFS does not consider the priority of processes, which can result in lower-priority processes waiting for longer periods of time, even if higher-priority processes are not using the resources.
  • No preemption: FCFS does not allow for preemption, meaning that a running process cannot be interrupted to allow a higher-priority process to run. This can result in longer wait times for higher-priority processes.
  • Not suitable for time-critical applications: FCFS is not suitable for time-critical applications, where response time is critical. The unpredictable wait times and lack of prioritization can result in missed deadlines and reduced performance.
  • No consideration for job size: FCFS does not take into account the size of a process, which can result in longer wait times for larger processes, even if they are lower-priority.
  • Favors short processes: FCFS favors short processes, as they are completed quickly and allow other processes to start sooner. This can result in longer wait times for longer processes, even if they are higher-priority.
  • Non-optimal for interactive systems: FCFS is not optimal for interactive systems, where users expect a quick response time. The unpredictable wait times can lead to a poor user experience.


Assume there is one CPU-intensive (long burst time) activity in the ready queue and numerous additional processes with shorter burst periods, frequent I/O operations).

The steps are as follows:

  1. CPU time is first assigned to I/O bound tasks. They are swiftly executed and go to I/O queues since they are less CPU-heavy.
  2. CPU time is now assigned to the CPU-intensive operation. It takes a long time to finish due to its long burst time.
  3. The I/O bound processes finish their I/O operations and are returned to the ready queue while the CPU-heavy process is running.
  4. The I/O-bound processes, on the other hand, are forced to wait since the CPU-intensive task is still running. I/O devices become idle as a result of this.
  5. When the CPU-intensive process is completed, it is queued for access to an I/O device in the I/O queue.
  6. Meanwhile, the I/O bound processes receive the CPU time they require and return to the I/O queue.
  7. They must, however, wait since the CPU-intensive activity is still attempting to contact an I/O device. As a result, the CPU is now inactive.


As a result of the Convoy Effect, one slow process degrades the performance of the entire collection of processes, wasting CPU time and other resources.

Example of FCFS Scheduling

The aim is to use the FCFS scheduling method to calculate the average waiting time and the average turn-around time, given n processes and their burst timings.

 

  • Processes are queued in the order they arrive in the ready queue using FIFO.
  • The process that comes first will be run first, and the following process will begin only once the preceding has completed its execution.
    We're going to assume that all processes arrive at the same time.

C++ Implementation of FCFS Scheduling

#include <iostream>
using namespace std;

// To find the waiting time for all processes
void findWT(int prcs[], int n,int bt[], int wt[])
{
    // waiting time for first process is 0
    wt[0] = 0;

    // calculating waiting time
    for (int i = 1; i < n; i++){
        wt[i] = bt[i - 1] + wt[i - 1];
    }
}

//  to calculate turn around time
void findTAT(int prcs[], int n,int bt[], int wt[], int tat[])
{
    // calculating turnaround time by adding  (burst time)bt[i] + wt[i](waiting time)
    for (int i = 0; i < n; i++)
        tat[i] = bt[i] + wt[i];
}

//To calculate average time
void findavgTime(int prcs[], int n, int bt[])
{
    int wt[n], tat[n], totalWait = 0, totalTAT = 0;

    // To find waiting time of all processes
    findWT(prcs, n, bt, wt);

    // To find turn around time for all processes
    findTAT(prcs, n, bt, wt, tat);

    cout << "Processes  "<< " Burst Time  "<< " Wait Time  "<< " Turn-Around-Time\n";

    //Calculate the total time spent waiting and the total time spent turning around.
    for (int i = 0; i < n; i++)
    {
        totalWait = totalWait  + wt[i];
        totalTAT = totalTAT + tat[i];
        cout << "   " << i + 1 << "\t\t" << bt[i] << "\t\t "
             << wt[i] << "\t\t  " << tat[i] << endl;
    }

    cout << "Avg waiting time = "
         << (float)totalWait  / (float)n;
    cout << "\nAvg turn around time = "
         << (float)totalTAT / (float)n;
}

int main()
{
    //processes
    int prcs[] = {8 , 9, 10};
    int n = sizeof prcs / sizeof prcs[0];

    //Burst time
    int burstTime[] = {8, 3, 6};

    findavgTime(prcs, n, burstTime);
    return 0;
}

 

Output

Processes   Burst time   Waiting time   Turn around time
  1         8        0          8
  2         3        8          11
  3         6        11         17
Avg waiting time = 6.33333
Avg turn around time = 12

Time Complexity: O(N)

Auxiliary Space: O(N)

Also see, Program for FCFS, Multiprogramming vs Multitasking

You can also read about layered structure of operating system.

Frequently Asked Questions

What is FCFS scheduling?

First-Come, First-Served (FCFS) scheduling is a non-preemptive scheduling algorithm used in computing and operating systems. It prioritizes processes based on their arrival order, executing the first process that arrives first, and so on, without considering process priorities or execution time.

What is first come first serve?

First-Come, First-Serve (FCFS) is a principle or policy that prioritizes entities or tasks based on their arrival time, with the one that arrives first being served or processed before others in the order they arrive. This concept is often used in various contexts, including scheduling, queuing, and customer service.

What is FCFS also known as?

FCFS, or First-Come, First-Serve, is also known as First-In, First-Out (FIFO) in certain contexts. FIFO is a similar principle that prioritizes the order of processing or handling based on the order of arrival, where the first to arrive is the first to be served or processed.

Conclusion

In this blog, we learned about the FCFS Scheduling algorithm. We have covered the basic idea of CPU Scheduling. We have also seen Scheduling criteria like CPU utilization, turnaround time, response time, waiting time, and throughput. We have witnessed FCFS, its advantages, and disadvantages. Further, we saw its implementation and its working.


Recommended Readings: 


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Previous article
Difference between Dispatcher and Scheduler
Next article
Shortest Remaining Time First Scheduling Algorithm
Guided path
Free
gridgp-icon
Operating system track
14 chapters
83+ Problems
gp-badge
Earn badges and level up
Live masterclass