Operating System Design/Scheduling Processes/FCFS

From Wikibooks, open books for an open world
Jump to: navigation, search

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