Last Updated on May 11, 2023 by Prepbytes
In this article, we will look at FCFS, which stands for First Come First Serve Scheduling Algorithm. Furthermore, we will understand how the scheduling algorithm works as well as code it from scratch, and terminologies related to the First Come, First Serve Scheduling Algorithm will be discussed. In interviews, FCFS is one of the most frequently asked questions about Operating Systems topics. Students can answer any conceptual question in interviews by focusing on the code and algorithm used in this article on the FCFS Scheduling Program in C.
What is FCFS Scheduling?
The CPU assigns tasks using a non-preemptive scheduling algorithm called First Come, First Serve. As the name implies, it prioritizes tasks based on the request that was made first.
No preemption ensures that no job takes over a job that is already in progress, and the processes are executed in a queue-like fashion.
Queues can be a viable data structure to assume the function of people at the end going out and entering from the back, waiting for their turn. Similarly, when a process requires CPU, it is placed at the end of the queue, and each process is completed one at a time, leaving the queue from the front until no processes remain and the queue is empty.
When idle, the CPU is assigned to the queue’s head, and when the process enters the FIFO queue, the PCB is attached to the queue’s tail.
Terminologies Related to FCFS
-
Burst Time – The total time elapsed to execute a process is known as burst time.
-
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 -
Waiting Time – The difference between the Start Time and Arrival Time can be classified as the waiting time.
-
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 of FCFS Program in C 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 completes at the 11th second and Process C enters the queue at the 8th second, the waiting time can be calculated by subtracting the arrival time, i.e. 8, from the starting time, i.e. 11, which equals 3 seconds.
Process C is completed at the 13th second because its burst time is 2 seconds.
Pseudocode of the FCFS Scheduling Algorithm
- Create a queue to get the requests or processes that must be stored to execute.
- On the arrival of a new process, it is placed at the end of the queue.
- If the CPU is idle, assign the request or process at the front of the queue to the CPU for processing.
- But in case the CPU is busy, wait until the current process is finished processing.
- 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 for execution.
- Repeat steps 3 to 5 until all processes have been serviced.
Code Implementation of FCFS Program in C
The preceding heading, Algorithm to FCFS Scheduling Program in C, explains how to create the FCFS Scheduling program.
#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;
}
The solution’s time complexity is O(N), and its space complexity will be O(N) as well, because auxiliary space is used in this program.
Applications of the FCFS Scheduling Program in C
Now that we’ve covered the theoretical, algorithmic, and code components of the FCFS Scheduling Program in C, let’s look at the application where the algorithm is most commonly used.
- The FCFS Scheduling Algorithm is mostly used in operating systems to ensure that processors perform tasks properly.
- A restaurant or drive-through is a real-world example of first come, first served, with customers who ordered first being served first.
Conclusion
In this article, we learned how FCFS works according to the FIFO principle, as well as important terminologies to know when solving problems. Keep in mind that FCFS is non-preventive, and simplistic, and the average waiting time is not optimal.
The algorithm, code, and application of the FCFS Scheduling Algorithm are described in the following sections of the article. We hope you found this article on FCFS scheduling in C informative. I hope to see you again with another insightful article in the future.
Frequently Asked Questions (FAQs)
Q1. What is an example of FCFS scheduling?
Ans. A real-life example of the FCFS method is buying a movie ticket at the ticket counter.
Q2. What is the first come first serve FCFS scheduling program?
Ans. First Come, First Served (FCFS) is a type of scheduling algorithm used by operating systems and networks to efficiently and automatically execute queued tasks, processes, and requests in the order of their arrival.
Q3. What is the FCFS sequencing rule?
Ans. The five priority sequencing rules are:
- First come, first served (FCFS); or First in, first out (FIFO):
- Jobs are sequenced in the order in which they arrive at the workstation.
- Earliest due date (EDD):
- Jobs are sequenced in the order in which they are due for delivery to the customer.
Q4. What are the advantages of FCFS?
Ans.
- There is no starvation in the case of FCFS.
- It is a fair algorithm as no priority of the processes is involved.
- Easy and simple implementation.
- It follows the FIFO queue to assign processes.
Q5. What is the importance of FCFS?
Ans. Perhaps the most obvious advantage of FCFS is in the name itself. Orders are processed in the exact order that they are placed, which serves as a straightforward and fair way of processing
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