First Come First Serve

Introduction

"First come, first serve" (FCFS) is a scheduling algorithm used to manage and prioritize tasks or processes. It is a fundamental method that all students must be aware of in order to learn the core principles of CPU Process Scheduling Algorithms. Stay hooked to the end of this tutorial to know more.

Overview

This tutorial is all about the characteristics of FCFS, its advantages, and disadvantages along with several examples that will help you grasp a deeper understanding of this basic concept in computer science.

What is First Come First Serve(FCFS)?

First Come First Serve (FCFS) is a simple CPU scheduling algorithm used in operating systems. In this approach, processes are executed in the order they arrive in the ready queue. The first process that enters the queue is the first one to be executed by the CPU. FCFS is a non-preemptive scheduling algorithm, meaning that upon execution, processes continue to run until they complete or voluntarily release the CPUs.

How Does the First Come First Serve CPU Scheduling Algorithm Work?

Let's understand how FCFS scheduling works with an example:

Suppose we have three processes A, B, and C with their respective burst times:

• Process A: 8 ms
• Process B: 4 ms
• Process C: 6 ms

Assuming they arrive in the order A -> B -> C, the order of execution under FCFS would be:

1. Process A (8 ms)
2. Process B (4 ms)
3. Process C (6 ms)

In this scenario, Process A, being the first to arrive, gets executed first, followed by B and then C.

Now, here's another example with different process burst times:

In this example, we again have three processes X, Y, and Z with their respective burst times:

• Process X: 5 ms
• Process Y: 2 ms
• Process Z: 7 ms

Assuming they arrive in the order X -> Y -> Z, the order of execution under FCFS would be:

1. Process X (5 ms)
2. Process Y (2 ms)
3. Process Z (7 ms)

In this example, Process X starts execution first as it arrived first. After Process X completes, Process Y follows, and finally, Process Z runs.

Pre Emptive Approach

FCFS is a non-preemptive scheduling algorithm, which means that a process will continue to run until it finishes its burst time upon execution. Preemption is not supported in FCFS, so the currently executing process cannot be interrupted by a higher-priority process.

In a preemptive scheduling approach, the operating system can interrupt a running process and allocate the CPU to another process if a higher-priority process becomes available. This means that a running process may be temporarily paused to allow another process with higher priority to execute.

Suppose we have two processes, A and B, with the following burst times and priorities:

• Process A: Burst Time = 10 ms, Priority = High
• Process B: Burst Time = 8 ms, Priority = Low

In preemptive scheduling, if Process B becomes ready while Process A is running, the operating system might decide to preempt (interrupt) Process A to allow Process B, with a higher priority, to execute. After a while, the operating system could resume executing Process A.

Non-Pre Emptive Approach

In FCFS, once a process starts execution, it continues until it completes or releases the CPU voluntarily. Other processes waiting in the ready queue have to wait for the currently executing process to finish before they can start execution.

In a non-preemptive scheduling approach, once processes start executing, they run until they complete their burst times or voluntarily release the CPUs. No process can be interrupted by the operating system until it finishes or enters a blocking state.

Let's use the same processes, A and B, with the same burst times and priorities:

• Process A: Burst Time = 10 ms, Priority = High
• Process B: Burst Time = 8 ms, Priority = Low

In a non-preemptive scheduling scenario, if Process B becomes ready while Process A is running, the operating system will let Process A continue until it completes its execution. Only after Process A finishes or enters a blocking state will Process B get a chance to execute.

Convoy Effect in FCFS

The convoy effect is a phenomenon that can occur in FCFS scheduling. It refers to a situation where long processes occupy the CPUs, making the shorter processes wait behind them. This can lead to poor CPU utilization and increased response times for other processes.

For example, consider a scenario where a long I/O-bound process occupies the CPU under FCFS. Other shorter processes that are CPU-bound might queue up behind this process, resulting in longer waiting times for those processes.

Characteristics of FCFS CPU Process Scheduling

The characteristics of FCFS CPU Process Scheduling are as follows:

• Implementation is simple and easy to understand.
• Adopts both non-preemptive and preemptive strategies.
• Does not cause any resource contention or deadlocks.
• Processes run until they complete or voluntarily yield the CPU.
• Executes processes in the order they arrive in the ready queue.
• Arrival time is used as a selection criterion for determining the execution order.
• This may lead to poor CPU utilization and longer waiting times for certain processes, especially in the presence of both short and long-running processes.

Advantages of FCFS CPU Process Scheduling

Here are the benefits of FCFS CPU Process Scheduling:

• First In First Out (FIFO) Queue: FCFS allocates processes based on their arrival time, following a FIFO queue. This approach ensures that processes are served in the order they arrive, promoting fairness in resource allocation.
• Simplicity and Ease of Implementation: FCFS is a straightforward scheduling algorithm, making it easy to understand and implement. It requires minimal computational overhead, which is advantageous for systems with limited resources or for educational purposes.
• No Process Starvation: In the case of non-preemptive FCFS scheduling, there is no preemption, meaning processes run to completion without interruption. This eliminates the possibility of process starvation, ensuring each process receives its fair share of CPU time.
• Equitable Algorithm: FCFS does not consider process priority; all processes are treated equally. This characteristic is advantageous in scenarios where processes have similar importance, and no preferential treatment is required.

Drawbacks of FCFS

Here are some of the downsides of FCFS CPU Process Scheduling:

• Long Waiting Time: One significant drawback of FCFS is that it can lead to long waiting times for processes. When a long-running process occupies the CPU, other shorter processes in the queue must wait their turn, resulting in increased waiting times and potentially poor system responsiveness.
• Bias towards CPU-bound Tasks: FCFS tends to favor CPU-bound tasks over those involving input or output operations. Since the CPU is allocated to the first process in the queue, I/O-bound tasks may have to wait for extended periods, leading to underutilization of other resources.
• Convoy Effect: FCFS is susceptible to the convoy effect, where a long-running process causes a series of shorter processes to queue up behind it, similar to a convoy formation. This exacerbates waiting times for all subsequent processes and can hinder overall system efficiency.
• Inefficiency with Mixed Workloads: While FCFS is easy to understand and implement, its simplicity can lead to inefficiencies, especially when dealing with mixed workloads comprising both short and long-running processes. Extended processing times of some tasks can cause other orders to remain idle, affecting the system throughout.

Semaphores in OS (Operating System)

Dijkstra proposed a solution to the problem of wasting wake-up signals by introducing Semaphores in operating systems. Semaphores are variables used to store wake-up calls from producers to consumers, preventing direct signaling and potential wastage. The producer stores wake-up calls in the semaphore variable, which can be read and updated automatically in kernel mode by any consumer when needed.

The implementation of Semaphores in user mode is not feasible due to the possibility of race conditions when multiple processes try to access the variable simultaneously. Thus, Semaphores always require support from the operating system for proper functioning.

There are two categories of Semaphores based on their functionality:

• Counting Semaphore: This type of semaphore maintains a counter that can be incremented or decremented by processes. It is used to control access to a finite number of identical resources. Processes can wait or signal the semaphore based on resource availability, ensuring synchronization.
• Binary Semaphore (Mutex): A Binary Semaphore has only two states, 0 and 1. It is primarily used for mutual exclusion, allowing only one process at a time to access a critical section or shared resource. When a process enters the critical section, it sets the semaphore to 1, preventing other processes from entering until it releases the resource and resets the semaphore to 0.

Important Abbreviations

AT: Arrival Time - The time at which a process arrives in the ready queue or becomes ready for execution.

BT: Burst Time - The amount of time a process requires to complete its execution, also known as the CPU time.

CPU: Central Processing Unit - The main processing component of a computer where calculations and data processing take place.

CT: Completion Time - The time at which a process finishes its execution.

FIFO: First In First Out - A queueing principle where the first item to enter the queue is the first one to be removed.

OS: Operating System - Software that manages computer hardware, software resources, and provides services for computer programs.

TAT: Turn Around Time - The total time taken for a process to complete its execution, from arrival to completion.

WT: Waiting Time - The total time a process spends waiting in the ready queue before it starts execution.

Implementation of FCFS in Java

Here's an example of implementing the First Come First Serve CPU scheduling algorithm in Java:

Code:

import java.util.*;

class Process {
    String name;
    int arrivalTime;
    int burstTime;
    
    public Process(String name, int arrivalTime, int burstTime) {
        this.name = name;
        this.arrivalTime = arrivalTime;
        this.burstTime = burstTime;
    }
}

public class FCFSExample {
    public static void main(String[] args) {
        List<Process> processes = new ArrayList<>();
        processes.add(new Process("Process A", 0, 8));
        processes.add(new Process("Process B", 1, 4));
        processes.add(new Process("Process C", 2, 6));

        int currentTime = 0;
        for (Process process : processes) {
            if (process.arrivalTime > currentTime) {
                currentTime = process.arrivalTime;
            }
            
            System.out.println("Executing " + process.name + " from time " + currentTime + " to " + (currentTime + process.burstTime));
            
            currentTime += process.burstTime;
        }
    }
}

In the above code, we define a Process class with attributes for the process name, arrival time, and burst time. We then create a list of processes and simulate their execution using the FCFS scheduling algorithm. The processes are executed in the order they arrive in the list, and their execution times are printed.

Conclusion

The First Come, First Served (FCFS) scheduling algorithm is beneficial due to its fairness, simplicity, and predictability in managing tasks or processes based on their arrival time. It ensures all tasks are eventually processed, preventing starvation. With low overhead and ease of implementation, FCFS is an efficient choice for scenarios where task priorities and execution times are not critical.

Through this tutorial, we aimed to give you a preliminary understanding of what First Come, First Served is. However, if you want a more nuanced understanding, you should enroll in the specially curated computer science courses by upGrad. With the help of these courses by upGrad you will not only be able to get a better understanding of the concepts but also bag lucrative jobs in leading corporations.

FAQs

1. When should I avoid using FCFS CPU Process Scheduling?

Avoid FCFS in scenarios where some processes are time-sensitive or have higher priority. If your system experiences a mix of long and short-running processes, more advanced scheduling algorithms like Shortest Job First (SJF) or Round Robin might be more suitable.

2. Can FCFS be combined with other scheduling algorithms?

Yes, FCFS can be part of hybrid scheduling approaches. For example, in multi-level feedback queues, FCFS might be used in one of the priority queues while other algorithms handle different queues with varying priorities and time quantum.

3. What is the average waiting time in FCFS?

The average waiting time in FCFS depends on the order of process arrival. If shorter processes arrive first, the average waiting time may be lower. However, if longer processes arrive first, the average waiting time can be significantly higher.