In this tutorial, we will learn about FCFS First Come First Serve Scheduling.
An operating system (OS) acts as a bridge between computer hardware and the user. It facilitates the execution of application programs, and managing software and hardware resources. This also controls various peripherals such as printers and disk drives. It plays a crucial role in tasks like file management, memory management, and input/output operations.
Every computer system needs an operating system to run different applications effectively. Whether it’s browsing the internet, using MS Office, playing games, or running a simple text editor like Notepad. All these applications rely on the underlying operating system to provide the necessary environment for their execution and functionality.
What is FCFS?
First-Come-First-Serve (FCFS) scheduling is a basic CPU scheduling algorithm. In this approach, the process that arrives first is executed first, and the next process starts only after the previous one finishes.
When using FCFS scheduling, processes are arranged in the order they arrive. The CPU serves the processes in the same sequence. If a process arrives while another process is running, it waits in a queue until it’s its turn.
This scheduling algorithm is easy to understand and implement since it follows a simple rule of serving processes in the order they arrive. However, it may lead to a problem known as “the convoy effect,” where a long-running process can hold up subsequent processes.
Overall, FCFS scheduling provides a fair execution order based on arrival time, but it may not be the most efficient algorithm in terms of minimizing waiting times or optimizing system performance.
How to Implementation FCFS in JAVA?
Here’s an implementation of the First Come First Serve (FCFS) scheduling algorithm in Java :
import java.util.*;
class Process {
int processId;
int arrivalTime;
int burstTime;
public Process(int processId, int arrivalTime, int burstTime) {
this.processId = processId;
this.arrivalTime = arrivalTime;
this.burstTime = burstTime;
}
}
public class FCFS_Scheduling {
public static void main(String[] args) {
List<Process> processes = new ArrayList<>();
// Add processes
processes.add(new Process(1, 0, 8));
processes.add(new Process(2, 1, 4));
processes.add(new Process(3, 2, 9));
processes.add(new Process(4, 3, 5));
int numberOfProcesses = processes.size();
// Sort processes based on arrival time
Collections.sort(processes, Comparator.comparingInt(p -> p.arrivalTime));
int[] completionTime = new int[numberOfProcesses];
int[] turnAroundTime = new int[numberOfProcesses];
// Calculate completion time and turn around time
int currentTime = 0;
for (int i = 0; i < numberOfProcesses; i++) {
Process currentProcess = processes.get(i);
currentTime = Math.max(currentTime, currentProcess.arrivalTime);
completionTime[currentProcess.processId - 1] = currentTime + currentProcess.burstTime;
turnAroundTime[currentProcess.processId - 1] = completionTime[currentProcess.processId - 1] - currentProcess.arrivalTime;
currentTime += currentProcess.burstTime;
}
// Calculate average completion time
double totalCompletionTime = 0;
for (int i = 0; i < numberOfProcesses; i++) {
totalCompletionTime += completionTime[i];
}
double averageCompletionTime = totalCompletionTime / numberOfProcesses;
// Calculate average turn around time
double totalTurnAroundTime = 0;
for (int i = 0; i < numberOfProcesses; i++) {
totalTurnAroundTime += turnAroundTime[i];
}
double averageTurnAroundTime = totalTurnAroundTime / numberOfProcesses;
// Print the results
System.out.println("Process\tCompletion Time\tTurnaround Time");
for (int i = 0; i < numberOfProcesses; i++) {
System.out.println(processes.get(i).processId + "\t\t" + completionTime[i] + "\t\t\t" + turnAroundTime[i]);
}
System.out.println("Average Completion Time: " + averageCompletionTime);
System.out.println("Average Turnaround Time: " + averageTurnAroundTime);
}
}
Output:
Process Completion Time Turnaround Time
1 8 8
2 13 12
3 22 20
4 27 24
Average Completion Time: 17.5
Average Turnaround Time: 16.0
In this code, we have a Process
class representing each process with its ID, arrival time, and burst time. The FCFS algorithm is implemented by sorting the processes based on arrival time and then calculating the completion time and turnaround time for each process.
The code above includes a sample set of processes with their arrival time and burst time values. You can modify these values or add more processes as per your requirement. The code calculates the average completion time and an average turnaround time and prints the results at the end.
What are the Advantages of FCFS?
- Simplicity: FCFS is easy to implement, following a simple approach where processes are executed in the order they arrive.
- Non-preemptive: FCFS does not interrupt processes once they start running. They continue until completion or until they willingly give up the CPU.
- Fairness: FCFS treats all processes equally, executing them in the order they arrive. The first process to arrive is the first to be served, ensuring fairness in CPU allocation.
- Minimal overhead: FCFS has low overhead in terms of context switching or additional data structures. It only requires a basic queue to manage incoming processes.
- Deterministic behavior: FCFS produces consistent results. Given the same set of processes and arrival times, the order in which they are scheduled remains the same. This predictability can be advantageous for certain applications.
- Low starvation: FCFS guarantees that no process will starve indefinitely. Each process eventually gets a chance to run since they are executed based on their arrival order.
What are the Disadvantages of FCFS?
- Convoy Effect: FCFS can suffer from the convoy effect, where a long process occupying the CPU blocks other shorter processes from executing, even if they arrive later. This can result in poor overall system throughput and increased waiting times for subsequent processes.
- Poor Average Waiting Time: FCFS does not prioritize processes based on their burst time or any other metric. As a result, shorter processes that arrive later may experience longer waiting times due to longer processes already in the queue.
- Lack of Preemption: FCFS does not support preemption. Once a process starts executing, it continues until completion or until it voluntarily yields the CPU. This lack of preemption can be problematic if a higher priority process arrives later, as it will have to wait until all earlier processes are complete.
- Inefficient Utilization of Resources: FCFS does not consider the remaining burst time of processes. It may result in inefficient utilization of resources, as a process with a long burst time could hold the CPU for an extended period, leading to underutilization of the system.
- No Response Time Guarantee: FCFS does not provide any guarantee for the response time of processes. Processes with longer burst times may experience significant delays in receiving CPU time, leading to reduced responsiveness.
- Not Suitable for Time-Critical Systems: FCFS is not suitable for time-critical systems or real-time applications where strict deadlines must be met. Since there is no consideration for deadlines or priorities, processes may not receive timely execution, leading to missed deadlines and system failures.
- Poor Performance with Varying Burst Times: FCFS performs poorly when dealing with a mix of long and short burst time processes. If long burst time processes arrive first, shorter processes may be delayed significantly, resulting in increased average waiting time and decreased system performance.