Introduction
Imagine waiting in line at a ticket counter, first in line gets served first. This is exactly how First Come First Serve (FCFS) scheduling works in computer systems.
Understanding First Come First Serve Scheduling is key to grasping core concepts of process management.
In this tutorial, you will learn its characteristics, advantages, disadvantages, and practical examples to master this basic concept. Let’s start by understanding the algorithm deeply.
Want to elevate your software development skills? Enroll in upGrad’s Online Software Engineering Courses today. Build a strong foundation and accelerate your career by mastering JavaScript, Node.js, APIs, React, and beyond.
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:
Advance your career by mastering in-demand skills in Cloud, DevOps, AI, and Full Stack Development. Gain hands-on experience with real-world projects and learn directly from industry experts to excel in the job market.
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:
- Process A (8 ms)
- Process B (4 ms)
- 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:
- Process X (5 ms)
- Process Y (2 ms)
- 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.
Also Read: Types of Memory in Computers and Their Uses with Examples
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.
Also Read: Structure of Operating System
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.
Also Read: Thrashing in Operating Systems: A Deep Dive
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.
Also Read: System Calls in OS: Different Types Explained
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.
Also Read: Difference Between Process and Program
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 Serve (FCFS) scheduling algorithm is simple, fair, and processes tasks in the order they arrive, preventing starvation. This tutorial covered the basics of First Come First Serve and First Come First Serve Scheduling. For a deeper understanding and practical mastery, explore upGrad’s computer science courses to strengthen your skills and career prospects.
FAQs
1. What is the First Come First Serve Scheduling algorithm?
The First Come First Serve Scheduling algorithm, often abbreviated as FCFS, is the simplest CPU scheduling algorithm. In this non-preemptive algorithm, the process that requests the CPU first gets the CPU first. It operates on a first-in, first-out (FIFO) basis, where processes are executed in the exact order they arrive in the ready queue. This straightforward approach makes First Come First Serve easy to implement and understand.
2. When should I avoid using FCFS CPU Process Scheduling?
You should avoid First Come First Serve Scheduling in scenarios where some processes are time-sensitive or have higher priority. This algorithm is particularly inefficient in systems with a mix of long and short-running processes, a phenomenon known as the convoy effect. If a long process arrives first, all subsequent short processes will have to wait for a significant amount of time, leading to a high average waiting time. In such cases, more advanced scheduling algorithms like Shortest Job First (SJF) or Round Robin are more suitable.
3. What is the average waiting time in FCFS?
The average waiting time in First Come First Serve depends heavily on the arrival order of processes. If a few very long processes arrive before a large number of short processes, the average waiting time can be very high due to the convoy effect. Conversely, if shorter processes arrive first, the average waiting time may be lower. The predictability of waiting time is low, as it is entirely dependent on the specific sequence of arrivals.
4. Can First Come First Serve be combined with other scheduling algorithms?
Yes, the First Come First Serve Scheduling algorithm can be part of hybrid scheduling approaches. For example, in a multi-level feedback queue, FCFS might be used in one of the lower-priority queues to process background or batch jobs, while higher-priority queues use a different algorithm like Round Robin for interactive processes. This allows a system to benefit from the simplicity of First Come First Serve for certain workloads while providing better responsiveness for others.
5. What is the main disadvantage of the First Come First Serve Scheduling algorithm?
The main disadvantage of the First Come First Serve Scheduling algorithm is its high average waiting time and a lack of consideration for process priority or execution time. This can lead to the convoy effect, where a single long-running process can hold up all subsequent processes, regardless of their length. This inefficiency makes First Come First Serve a poor choice for modern operating systems that require responsiveness and fairness, as shorter, high-priority tasks may be unnecessarily delayed.
6. Is First Come First Serve a preemptive or non-preemptive algorithm?
The First Come First Serve Scheduling algorithm is a non-preemptive algorithm. This means that once a process is assigned to the CPU, it continues to execute until it completes its CPU burst or voluntarily gives up the CPU (e.g., for I/O). The CPU cannot be taken away from the currently running process, even if a higher-priority or shorter process arrives in the ready queue. This rigid nature is a key characteristic of First Come First Serve.
7. How does the First Come First Serve algorithm work with a process queue?
The First Come First Serve Scheduling algorithm uses a standard First-In, First-Out (FIFO) queue. When processes enter the ready state, they are placed at the back of the queue. The CPU dispatcher then selects the process at the front of the queue to execute. This simple queuing mechanism is at the very core of how First Come First Serve functions, ensuring that processes are always served in their order of arrival.
8. What is the 'convoy effect' in the context of First Come First Serve Scheduling?
The 'convoy effect' is a major issue with First Come First Serve Scheduling. It occurs when a CPU-bound (long-running) process holds the CPU for a long time, forcing all other processes, especially I/O-bound (short) processes, to wait. This creates a "convoy" of waiting processes behind the long-running one, severely underutilizing other system resources and leading to very high average waiting times.
9. What is the throughput of First Come First Serve?
The throughput of the First Come First Serve Scheduling algorithm is generally lower compared to other algorithms like SJF, especially in environments with a mix of long and short processes. Throughput is the number of processes completed per unit of time. Because FCFS does not prioritize short jobs, it can take a long time to complete a given set of processes if a long one arrives early, thus reducing the overall throughput of the system.
10. How does a time quantum apply to First Come First Serve?
A time quantum does not apply to the First Come First Serve Scheduling algorithm. A time quantum is a feature of preemptive algorithms, most notably Round Robin, where a process is allowed to run for a specific, limited time slice before being moved to the back of the ready queue. Since FCFS is a non-preemptive algorithm, a process runs to completion without any time limit, making the concept of a time quantum irrelevant.
11. Is First Come First Serve used in modern operating systems?
While First Come First Serve Scheduling is generally not used as the primary scheduling algorithm in modern general-purpose operating systems, it is still used in specific scenarios. It is often a component of more complex, hybrid scheduling systems. For example, it might be used for batch processing or for managing processes within a specific priority queue, particularly for non-time-critical tasks. Its simplicity makes it useful for contexts where it's the most straightforward and effective approach.
12. Does the First Come First Serve algorithm have a starvation problem?
The First Come First Serve Scheduling algorithm does not have a starvation problem. Starvation occurs when a process is repeatedly delayed and never gets to execute. Because FCFS services every process in the order of its arrival, every process is guaranteed to be eventually executed. No process can be indefinitely blocked, which is a key advantage of the algorithm's simple and fair queuing mechanism.
13. How is the turnaround time calculated in First Come First Serve?
The turnaround time for a process in First Come First Serve is calculated as the time from its arrival until its completion. It is the sum of the process's waiting time and its CPU burst time. The average turnaround time for a set of processes is the average of all their individual turnaround times. Like average waiting time, it is heavily influenced by the order of arrival and can be high due to the convoy effect.
14. What are some real-world examples of First Come First Serve Scheduling?
A simple real-world example of First Come First Serve Scheduling is a ticket queue. The person who gets in line first is the first person to be served. Other examples include a printer queue, where print jobs are processed in the order they were submitted, or a customer service call center, where calls are answered in the order they are received. These simple queues are a direct analogy to how First Come First Serve works in a computing context.
15. How does FCFS compare to Shortest Job First (SJF) in terms of performance?
First Come First Serve generally performs worse than Shortest Job First (SJF) in terms of average waiting time and turnaround time. SJF prioritizes processes with the smallest CPU burst time, which significantly reduces the average waiting time for the entire set of processes. While FCFS is simpler to implement because it doesn't require knowing the future burst time of a process, SJF is almost always more efficient in terms of performance metrics.
16. What is the overhead of the First Come First Serve Scheduling algorithm?
The First Come First Serve Scheduling algorithm has very low overhead. Because it is so simple, it requires minimal CPU cycles for context switching and for making scheduling decisions. It simply takes the process from the front of the queue and lets it run. There is no complex calculation, priority check, or time slicing involved, making First Come First Serve an efficient choice from a resource management perspective, even if it is inefficient from a process waiting time perspective.
17. How is the response time calculated in a First Come First Serve system?
In a non-preemptive algorithm like First Come First Serve, the response time for a process is the same as its waiting time. Response time is the time from when a process arrives until the first time it gets the CPU. Because the First Come First Serve Scheduling algorithm does not preempt processes, a process does not start and stop its execution. It simply waits for its turn and then runs to completion, so the first time it gets the CPU is also the time it stops waiting.
18. What kind of applications are suitable for First Come First Serve Scheduling?
Applications that are suitable for First Come First Serve Scheduling are typically batch processing jobs where no user interaction is required. Examples include tasks like generating reports, running nightly backups, or performing large data transfers. In these scenarios, the primary goal is to complete all tasks, and a user isn't waiting for a quick response, so the simplicity and fairness of First Come First Serve are acceptable, and the potential for long waiting times is not a major issue.
19. How does the First Come First Serve Scheduling algorithm handle process priorities?
The First Come First Serve Scheduling algorithm does not handle process priorities. It treats every process equally, regardless of its importance or priority level. This is a significant limitation of the algorithm. If a high-priority, mission-critical process arrives but a low-priority, long-running process is already executing, the important process will have to wait, which can be detrimental to system performance and responsiveness.
20. How can I learn more about the First Come First Serve Scheduling algorithm?
You can learn more about the First Come First Serve Scheduling algorithm and other CPU scheduling techniques through online learning platforms. upGrad offers comprehensive programs in computer science and software engineering that cover operating systems and key concepts like First Come First Serve. These courses provide hands-on experience and a deeper understanding of how these algorithms work in real-world operating systems.
