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

First In First Out (FIFO) Algorithm in OS

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

Introduction

Hello Ninjas! Looking for yet another mind-stimulating article? We are here to fulfill your wish. Dive with us into the First-in-First-Out (FIFO) Algorithm in OS. It is an algorithm that executes processes in the order in which they arrive in a queue.

first in first out (fifo) algorithm in os

This article will briefly overview First-In-First-Out (FIFO), a scheduling algorithm used in Operating Systems. It will go through its implementation, advantages, limitations, and real-world applications.

Also see: Multiprogramming vs Multitasking, Open Source Operating System.

What is the FIFO Algorithm?

FIFO, or First-In-First-Out, is an algorithm used in operating systems to manage resources such as CPU time, memory, and input/output operations. The idea behind FIFO is simple: the first process that enters the queue is the first to be served or executed, while the later processes wait in a queue. 

To make it simple consider an example of a College Canteen. The first student in the queue will be the person to get the meal first and the last person in the queue will wait for the remaining to leave.

What is the FIFO Algorithm?

Similarly, when the OS is executing various processes using the FIFO algorithm, the first process will be executed first. The first process that arrives in the queue (the line of processes waiting to use a resource) is the first one to get to use that resource.

FIFO in OS is a simple and fair algorithm that ensures all processes are given equal opportunity to use system resources. So, we can say that it uses the FIRST COME, FIRST SERVE algorithm.

It is commonly used when process arrival times are known in advance, such as in batch processing systems, where many similar jobs are submitted to the system for processing.

However, FIFO may not be the most efficient algorithm in all cases, as it does not consider process priorities or the time required to execute a process. It forms the basis for more complex scheduling algorithms in modern operating systems.

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

Implementation of FIFO in OS

  • The OS manages these resources through scheduling algorithms, which determine which process gets to use which resource and when.
     
  • One scheduling algorithm the OS can use is First-In-First-Out or FIFO for short. This algorithm is like a line at a store or a restaurant. 
     
  • The OS uses a queue data structure to implement the FIFO algorithm. A queue is a line where processes wait in a specific order until it's their turn to use the needed resource. Processes are added to the back and removed from the front in a queue. This step is known as enqueueing and dequeuing, respectively.
     
  • The OS uses algorithms to manage the queue, ensuring the processes are added and removed correctly. When a new process arrives, it is added to the end of the queue using the enqueue operation. 
     
  • The OS then checks to see which process is at the start of the queue and executes that process. Once that process is finished, it is removed from the front of the queue using the dequeue operation. The next process in the queue gets to use the resource.
     

In summary, the FIFO algorithm works like a line or queue, where the first process in is the first one out. The OS uses a queue data structure to keep track of the order of the processes waiting to use a resource and uses enqueue and dequeue operations to add and remove processes from the queue.

Example

Consider an example of the FIFO page fault replacement algorithm:

Let’s suppose we have 5 page frames and we have page references: 2, 3, 5, 2, 8,  9, 4, 5. We have to find the total number of page faults.

Note: The first occurrence of any page will always be a page miss.

Example

Here, we can see that the total number of page faults is six.

Advantages of the FIFO Algorithm

FIFO is a scheduling algorithm computers use to decide which programs or tasks use the computer's resources (like the CPU, memory, and input/output operations). 

  1. Simplicity: FIFO is a simple algorithm that's easy to understand and use. It's like a line at a store - the first person in line is the first to be served, and so on. The computer keeps track of which program arrived first and lets it use the resource it needs.
     
  2. Fairness: The FIFO algorithm is a fair way of deciding which program gets to use the resource it needs. It's like taking turns - everyone gets to use the resource in the order they arrive. No one gets to cut in line or jump ahead.
     
  3. Predictability: Because the FIFO algorithm is so simple and fair, it's also predictable. This sentence means that the computer can tell you exactly when a program will get to use the resource it needs. You can plan your work accordingly, knowing that your program will get to use the resource at a certain time.
     
  4. Efficiency: In some cases, FIFO can be more efficient than other scheduling algorithms. It is ideal for situations where process arrival times are known in advance, and there are no priorities or deadlines to meet. In these cases, FIFO can reduce the overhead of scheduling and context switching, resulting in faster overall system performance.
     

Overall, using the FIFO algorithm makes it easy for the computer to decide which program gets to use the resource it needs. It's a fair way of doing things that's easy to understand and predict.
 

Must Read Process Management in OS

Examples of where FIFO is used

FIFO is a way for the computer to track which job came first and do that next. Let's look at some examples of how FIFO is used in different parts of the operating system:

  • In process scheduling, the computer uses FIFO to decide which job to do next. The first job that came in gets done first. For example, if you ask the computer to print a document and then copy a file, the computer will start printing it first because you asked for it first.
     
  • In memory management, the computer uses FIFO first to decide which program to load. It's like stacking your documents in a box - the document you put in first will be the first you see when you open the box. Similarly, the computer remembers which program came first and loads that one first.
     
  • In input/output operations, the computer manages everything you do with it, like typing on the keyboard or saving files to the hard drive. FIFO decides which task to do first based on the order of request. It's like sending an email - the first email will be the first one to be read.
     

Overall, FIFO is a simple and fair way for the computer to keep track of which task to do next in different parts of the operating system.

Real-world Applications

FIFO is widely used in many real-world applications to manage resources effectively. Here are some examples of how FIFO is used in different applications:

  1. Network packet scheduling: Data is transmitted in packets in computer networks. FIFO is often used to manage the queue of packets waiting to be transmitted. The first packet arrives to be transmitted, ensuring that all packets are treated fairly.
     
  2. Disk scheduling: A queue is formed to manage the requests, when multiple processes need to access a disk. FIFO is one of the simplest algorithms used to manage this queue. The first request is the first to be serviced, ensuring that all processes are treated equally.
     
  3. Printer scheduling: When multiple print jobs are sent to a printer, a queue is formed to manage the requests. FIFO is often used to manage this queue. The first print job arrives to be printed, ensuring that all print jobs are treated fairly.
     
  4. Audio and video streaming: Data is transmitted continuously in audio and video streaming applications. FIFO is used to manage the buffer that stores the data waiting to be played. The first data that arrives is the first to be played, ensuring no interruptions or delays in the stream.
     

Overall, FIFO is a valuable tool in many real-world applications, ensuring that resources are allocated fairly and efficiently.

Must Read Evolution of Operating System

Frequently Asked Questions

What is a page fault in FIFO?

A page fault, in FIFO, occurs when a process requests a page that is not currently in memory, and the operating system must swap out a page from memory to make room for the requested page.

Is FIFO the same as FCFS?

No, FIFO and FCFS (First-Come-First-Serve) are not the same. FIFO manages processes, memory, and input/output operations. At the same time, FCFS is a scheduling algorithm for managing process execution.

What is the main difference between FIFO and LIFO?

The main difference between FIFO and LIFO is that FIFO uses a queue data structure to manage resources. In contrast, LIFO uses a stack data structure. In FIFO, the first item that enters the queue is the first to exit, while in LIFO, the last item that enters the stack is the first to exit.

Conclusion

In conclusion, FIFO is a simple and efficient algorithm for managing operating system resources. Although it has some limitations, it ensures fairness and predictability in resource allocation. Its understanding is crucial for system designers and developers, as it is widely used in real-world applications. FIFO is an essential concept in operating systems and a valuable tool for building efficient and reliable systems. 

To learn more about such concepts, head to;

Demand Paging in OS

First In First Out approach in Programming

Kadane's Algorithm

Design and Analysis of Algorithms

Difference between Array, Queue & Stack

Sorting a Stack Using a Temporary Stack

What is bios

Advantages of Operating System

Pcb in operating system

You may refer to our Guided Path on Code Studios to enhance your skill set on DSA and many more. Check out essential interview questions, practice our available mock tests, and more!

Guided path
Free
gridgp-icon
Operating system track
14 chapters
83+ Problems
gp-badge
Earn badges and level up
Live masterclass