FCFS Scheduling Program in C

Introduction

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

Terms In First Come First Serve Scheduling

In First Come First Serve (FCFS) scheduling, tasks are executed based on their arrival order. The first task to arrive is the first to be processed. This scheduling algorithm is non-preemptive, meaning once a task starts, it continues until completion. FCFS is simple to implement and ensures fairness, as tasks are served in the order they arrive. However, it may lead to longer waiting times, especially for long-running tasks that arrive early. FCFS is commonly used in batch processing systems, where the order of execution is less critical, and in scenarios where fairness in task allocation is prioritized over optimization of resource utilization.

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. 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.

Algorithm of FCFS Scheduling Program

The algorithm for the FCFS Scheduling program in C is as follows:

Read the number of processes and their burst times.
Initialize waiting time for the first process as 0.
Calculate waiting time for each subsequent process by adding the burst time of the previous process.
Calculate turnaround time for each process by adding burst time and waiting time.
Calculate average waiting time and average turnaround time.
Display the results.

Example

Suppose, we have three processes: P1, P2, and P3.

The burst times for these processes are 5, 3, and 8 units, respectively.
For the first process (P1), the waiting time is initialized as 0 because it is the first process.
The waiting time for the second process (P2) is calculated by adding the burst time of P1 (5 units) to its waiting time, resulting in 5 units.
Similarly, the waiting time for the third process (P3) is calculated by adding the burst time of P2 (3 units) to its waiting time, resulting in 8 units.
Turnaround time for each process is calculated by adding its burst time and waiting time.
Finally, we calculate the average waiting time and average turnaround time by summing up the respective values and dividing by the total number of processes (3 in this case).
The calculated average waiting time is approximately 4.33 units, and the average turnaround time is approximately 9.67 units.

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:

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.
CPU time is now assigned to the CPU-intensive operation. It takes a long time to finish due to its long burst time.
The I/O bound processes finish their I/O operations and are returned to the ready queue while the CPU-heavy process is running.
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.
When the CPU-intensive process is completed, it is queued for access to an I/O device in the I/O queue.
Meanwhile, the I/O bound processes receive the CPU time they require and return to the I/O queue.
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

C++

#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

Where is FCFS scheduling used?

FCFS (First Come First Serve) scheduling is commonly used in batch processing systems, where tasks are executed based on their arrival order without considering their priority or resource requirements. It is also employed in scenarios prioritizing fairness over optimization, such as printer queues and disk scheduling.

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 Code360.

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.