Operating System Design/Scheduling Processes/FCFS

The first come, first served (commonly called FIFO ‒ first in, first out) process scheduling algorithm is the simplest process scheduling algorithm. It is rarely used in modern operating systems, but is sometimes used inside of other scheduling systems.

Analogy

edit

A FIFO acts like any normal queue whether, it is a line in a cinema, a checkout line in a store, or a queue for a ticket booth. The first person or process to arrive (First In) is the first one to be dealt with (First Out). If one person goes through the line and then decides they forgot something then they have to go back through.

This is exactly how OS's with this design let programs conduct their business. One person (aka: process) at a time.

Implementation

edit

To implement this, you can create a queue, an abstract data type (ADT) that can be constructed from a linked list data structure. The system can dequeue the next process from the front of the queue, run the process until completion (or enqueue the process at the end of the line in more complex schemes), then enqueue the process at the end of the line, allowing the next process to use the CPU.

Advantages and Disadvantages

edit

Advantages:

  • simple
  • easy and useful and understand
  • first come, first served


Disadvantages:

  • This scheduling method is nonpreemptive, that is, the process will run until it finishes.
  • Because of this nonpreemptive scheduling, short processes which are at the back of the queue have to wait for the long process at the front to finish
  • Throughput is not efficient.
  • It is used in a small system only where I/O efficiency is not very important.