FCFS Scheduling Program in C

In this article, we are going to study about FCFS, acronym for First Come First Serve Scheduling Algorithm. On top of that, we will understand how the scheduling algorithm works along with coding it from scratch and terminologies related to First Come First Serve Scheduling Algorithm are going to be discussed. FCFS is one of the most asked questions from Operating System topics in interviews.

Focusing on code and algorithm used in this article on FCFS Scheduling Program in C, students can stand up to any conceptual question in the interviews.

What is FCFS Scheduling?

First Come First Serve is a non-preemptive scheduling algorithm used by the CPU to assign tasks. As the name suggests, it gives the utmost priority to the tasks on the basis of the request first made.

No preemption assures that no job overtakes a job that is already in process and the processes are executed in a manner similar to queue.

Queue can be a viable data structure to assume the functioning as people at the end go out and enter from the back waiting for their turn. In a similar fashion, the process is placed at the end when it requires CPU and once by one each process is done at a time and leaves the queue from the front until no processes are left and the queue is empty.

At the head of the queue, CPU is assigned when idle and on the other hand, PCB is attached at the tail of the queue for the process to enter the FIFO queue.

Terminologies Related to FCFS

  1. Burst Time – The total time elapsed to execute a process is known as burst time.

  2. Turnaround Time – The summation of waiting time and burst time results in turnaround time. It is the total time that a process takes right after its arrival in the queue.

    Turnaround Time = Waiting Time + Burst Time
  3. Waiting Time – The difference between the Start Time and Arrival Time can be classified as the waiting time.

  4. Average Waiting Time – The sum of all the waiting times by the total number of processes can be stated as Average Waiting Time.

Dry Run using an example

Suppose there is a process queue, Process A enters at first with a burst time of 5 seconds. Process B enters at 3rd second with a burst time of 6 seconds. Process C enters at 8th second with a burst time of 2 seconds.

Process A will finish at 5th second and Process B will be assigned CPU at 5th second. After 2 seconds of waiting in the queue, it will finish its execution at 11th second.

If Process B ends up at 11th second and Process C enters the queue at 8th second, the waiting time can be obtained by subtracting arrival time i.e. 8 by starting time i.e 11, which turns out to be 3 seconds.

Process C finished at 13th second as its burst time is 2 seconds.

Pseudocode of FCFS Scheduling Algorithm

  1. Create a queue to get the requests or processes that must be stored to execute.

  2. On arrival of a new process, it is placed at the end of the queue

  3. If the CPU is idle, assign the request or process at the front of the queue to the CPU for processing.

  4. But in case the CPU is busy, wait until the current process is finished processing.

  5. As the execution of the current process is done, it is removed from the FIFO queue and the next process at the front of the queue is put forward to execution.

  6. Repeat steps 3 to 5 until all processes have been serviced.

C Program of FCFS Scheduling in C

Algorithm to FCFS Scheduling Program in C, stated in the previous head gives a clarity on how the program on FCFS Scheduling can be crafted.

#include<stdio.h>

// Function to find the waiting time for all processes
void WaitingTime(int process_ids[], int num_processes, 
                     int burst_times[], int waiting_times[])
{
  
    waiting_times[0] = 0;
   

    for (int i = 1; i < num_processes; i++)
        waiting_times[i] =  burst_times[i-1] + waiting_times[i-1];
}

void TurnAroundTime(int process_ids[], int num_processes, 
                        int burst_times[], int waiting_times[], int turn_around_times[])
{

    for (int i = 0; i < num_processes; i++)
        turn_around_times[i] = burst_times[i] + waiting_times[i];
}
   

void avgTime(int process_ids[], int num_processes, int burst_times[])
{
    int waiting_times[num_processes], turn_around_times[num_processes];
    int total_waiting_time = 0, total_turn_around_time = 0;
   

    WaitingTime(process_ids, num_processes, burst_times, waiting_times);
   

    TurnAroundTime(process_ids, num_processes, burst_times, waiting_times, turn_around_times);
   
    printf("Processes   Burst time   Waiting time   Turn around time\n");
  
    for (int i = 0; i < num_processes; i++)
    {
        total_waiting_time += waiting_times[i];
        total_turn_around_time += turn_around_times[i];
        printf("   %d ", (i+1));
        printf("       %d ", burst_times[i]);
        printf("       %d", waiting_times[i]);
        printf("       %d\n", turn_around_times[i]);
    }
    int avg_waiting_time = (float)total_waiting_time / (float)num_processes;
    int avg_turn_around_time = (float)total_turn_around_time / (float)num_processes;
    printf("Average waiting time = %d", avg_waiting_time);
    printf("\n");
    printf("Average turn around time = %d ", avg_turn_around_time);
}
   

int main()
{

    int process_ids[] = {1, 2, 3};
    int num_processes = sizeof process_ids / sizeof process_ids[0];
   

    int burst_time[] = {5,6,2};
    avgTime(process_ids, num_processes,  burst_time);
    return 0;
}

Time Complexity of the solution is O(N) as well as the Space Complexity is also going to be O(N), given the reason that auxiliary space is being used in this program

Applications of FCFS Scheduling Algorithm

As we have been across the theoretical, algorithmic and code parts for the FCFS Scheduling Program in C, let us look at the application in which the algorithm is used the most.

  1. FCFS Scheduling Algorithm is used mostly in Operating Systems to ensure proper functioning of Processors to perform tasks.

  2. Restaurant or Drive-Through is a real-world example of FIrst Come First Serve where the customers that were early to order are served first.

Conclusion
In this article, we got to know how FCFS works according to the principle of FIFO and we got to know important terminologies are relevant while solving problems. Important points to keep in mind is that FCFS is non-preemptive, simplistic and the average waiting time is not optimal.

In the following sections of article, algorithm, code and application of FCFS Scheduling Algorithm were stated. We hope you found this article on FCFS Scheduling in C informative. Looking forward to see you with another insightful article in future.

Other C Programs

C Program for Binary Search
C Program to Add Two Numbers
C Program to Calculate Percentage of 5 Subjects
C Program to Convert Binary Number to Decimal Number
C Program to Convert Celsius to Fahrenheit
C Program to Convert Infix to Postfix
C Program to Find Area of Circle
C Program to Find Roots of Quadratic Equation
C program to Reverse a Linked List
C program to reverse a number
Ascending Order Program in C
Menu Driven Program For All Operations On Doubly Linked List in C
C Program for Armstrong Number
C Program For Merge Sort For Linked Lists
C program for performing Bubble sort on Linked List
Hello World Program in C
Perfect Number Program in C
Leap Year Program in C
Odd Even Program in C
Selection Sort Program in C
Linear Search Program in C
While Loop Program in C
C Program to Swap Two Numbers
Calculator Program in C Language
Simple Interest Program in C
Compound Interest Program in C
Priority Scheduling Program in C
Doubly Linked List Program in C

Leave a Reply

Your email address will not be published. Required fields are marked *