First Come First Serve CPU Scheduling Algorithm With Implementation in Java
The First-Come-First-Serve (FCFS) CPU scheduling algorithm is one of the simplest and most intuitive approaches employed in operating systems to manage the execution of processes. As the name suggests, this algorithm schedules processes based on their arrival time, with the first process arriving being the first to be served by the CPU. FCFS operates on the principle of a non-preemptive scheduling policy, where once a process starts its execution, it continues until completion without interruption.
FCFS leverages the First-In-First-Out (FIFO) queue mechanism within a structured data system to manage incoming processes. Those with earlier arrival times are granted priority and are executed first, while subsequent processes are placed in the queue, patiently waiting for the CPU to be released by the ongoing process.
Step by step process of FCFS algorithm
Consider the given table below where AT is the arrival time and BT is burst time also known as the execution time. We will find the completion time (CT), turn-around time (TAT), waiting time (WT) of each process.
Step 1: Draw a gantt chart, we will start at time 0 indicated at the left most part of the gantt chart. Then identify if there any process whose arrival time is 0. Since P2 has arrival time of 0, we will burst P2 by 1.
Step 2: Now P2 is done executing, there are 4 remaining process. Select the process whose arrival time is 1. Since at time 1 we have no process in ready queue so we put N/A from time 1 to time 2 but in time 2 we have two process P1, and P3 to be executed so we will burst P1 and P3.
Even if P1 and P3 have the same arrival time, we burst P1 first because it is the first process to be listed in the table. P1 completed at time 4 because it has a burst time of 2 and current time is 2 (burst time + current time = completion time) while P3 completed at time 7. To calculate the completion time of the process, we need to add the current time and the process’s burst time.
Step 3: Now we have 2 remaining process to be executed P4 and P5. P4 has been in ready queue since time 3 and it has an arrival time less than P5 so we burst P4 by 5 and calculate its completion time which gives us 12.
Step 4: Now we have 1 remaining process left to be executed which is P5. P5 has been in ready queue since time 4. We will burst P5 by 4 and calculate its completion time which gives us 16.
Step 5: Calculate their turn around time (TAT) and waiting time (WT). The completion time is listed below each process from the gantt chart. The TAT is calculated by finding the difference of the process's completion time and its arrival time (CT - AT = TAT). The WT is calculated by finding the difference of the process's turn around time and its burst time (TAT - BT = WT).
FCFS algorithm implementation in Java
For more information about the source code you can refer to this repository.
We first create a class for our Job object to store the job’s name, arrival time, burst time, completion time, turn around time and waiting time.
public class Job {
String jobName;
int arrivalTime;
int burstTime;
int completionTime;
int turnAroundTime;
int waitingTime;
public Job(String jobName, int arrivalTime, int burstTime) {
this.jobName = jobName;
this.arrivalTime = arrivalTime;
this.burstTime = burstTime;
}
}Then we initialize the array list jobs to store the jobs inputted by the user, array list queue to store jobs that will be queued when a job is currently using the CPU. The ongoingJob variable is where we put the currently running job and the ongoingJobEstimatedCompletionTime variable is an integer value to store the estimated completion time of a currently running job. The estimated completion time is calculated by adding the current time and the burst time of the ongoing job.
ArrayList<Job> jobs = new ArrayList<>();
// The jobs array list stores the process inputted by the user.
ArrayList<Job> queue = new ArrayList<>();
// If there is a process currently using the CPU then incoming process will be place in the queue.
Job ongoingJob = null;
int ongoingJobEstimatedCompletionTime = 0;
int currentTime = 0;This is the first while loop in our code where it asks user to enter the job name, arrival time and burst time. Example format could be “A 3 2” where A is the job’s name, 3 is the arrival time and 2 is the burst time. Then we create an instance of a Job and append it in the jobs array list. If the user inputs “confirm” then the program proceeds on scheduling the inputted jobs.
while (true) {
// Ask user to input the job name, arrival time and burst time. For example: A 2 3 where A is the process's
// name, 2 is the process's arrival time and 3 is the process's burst time.
System.out.print("Enter (job name, arrival time, burst time) or type 'confirm ' to finish: ");
Scanner scanner = new Scanner(System.in);
String[] input = scanner.nextLine().split(" ");
if ("confirm".equals(input[0])) {
break;
}
jobs.add(new Job(input[0], Integer.parseInt(input[1]), Integer.parseInt(input[2])));
}We then process the jobs by looping through the jobs array list and moving each job from jobs array list to queue array list only if their arrival time is equal to the current time. Then the first if statement “if(ongoingJobEstimatedCompletionTime == currentTime)” checks if the estimated completion time of the job is equal to the current time so that it can remove this job as ongoing to calculate its turn around time and waiting time then output the result. While the statement “if (ongoingJob == null)” checks if CPU is vacant so that it can increment the ongoingJobEstimatedCompletionTime. The last if statement is when the jobs and queue array list are both empty so therefore no jobs can be process.
while (true) {
for (int i = 0; i < jobs.size(); i++) {
Job currJob = jobs.get(i);
if (currJob.arrivalTime == currentTime) {
queue.add(jobs.remove(i));
// Decrement i so that it does not skip other process. It happens when two process has the same
// arrival time.
i--;
}
}
if (ongoingJobEstimatedCompletionTime == currentTime) {
if (ongoingJob != null) {
// A job has finish executing, calculate and output the result.
calcTurnAroundTimeAndWaitingTime(ongoingJob, ongoingJobEstimatedCompletionTime);
ongoingJob = null;
}
if (!queue.isEmpty()) {
// Get a process from the queue and calculate its estimated completion time.
ongoingJob = queue.remove(0);
// The new process from the queue is now using the CPU.
ongoingJobEstimatedCompletionTime = ongoingJob.burstTime + currentTime;
}
}
if (ongoingJob == null) {
// Increment if CPU is vacant
ongoingJobEstimatedCompletionTime++;
}
currentTime++;
if (queue.isEmpty() && jobs.isEmpty()) {
// Queue and jobs array list are both empty, no jobs can be process.
if (ongoingJob != null) {
// A job has finish executing, calculate and output the result.
calcTurnAroundTimeAndWaitingTime(ongoingJob, ongoingJobEstimatedCompletionTime);
}
break;
}
}
}This function calculates and outputs the job’s completion time, turn around time, and waiting time. This function is called when a job is remove from ongoing job or is finish using the CPU.
private static void calcTurnAroundTimeAndWaitingTime(Job job, int ongoingJobEstimatedCompletionTime) {
job.completionTime = ongoingJobEstimatedCompletionTime;
job.turnAroundTime = ongoingJobEstimatedCompletionTime - job.arrivalTime;
job.waitingTime = job.turnAroundTime - job.burstTime;
System.out.println("Job: " + job.jobName + ", Completion time: " + job.completionTime + ", Turn around time: " +
job.turnAroundTime + ", Waiting time: " + job.waitingTime);
}