First Come First Serve (FCFS) CPU scheduling is a simplest and earliest CPU scheduling algorithm used in operating systems. The name of the algorithm itself gives an insight into the functioning of the algorithm - processes are executed in the order in which they arrive. The operating system executes the process that arrives first and completes its execution before moving to the next process.
In FCFS scheduling, the operating system does not prioritize any process based on its execution time, priority, or any other criterion. All processes are treated equally and are executed in the order in which they arrive. This algorithm is simple to implement, but it does not guarantee that the processes with short execution times will be executed quickly, leading to long wait times for processes with short execution times.
An example of FCFS scheduling can be seen in a queue system at a hospital. Consider a scenario where three patients, P1, P2, and P3, arrive at the hospital in the order P1, P2, and P3 respectively. The doctor sees patients in the order in which they arrive and so the doctor will see P1 first, P2 second, and P3 last. Similarly, in FCFS CPU scheduling, the operating system executes the processes in the order in which they arrive.
Consider another example where three processes, P1, P2, and P3, arrive with execution times of 8 units, 4 units, and 9 units respectively. In this scenario, the CPU scheduling would be as follows:
- P1 is executed first since it arrived first
- P2 is executed next since it arrived next
- P3 is executed last since it arrived last
The above example shows that the process with the shortest execution time, P2, had to wait for P1 to complete its execution, leading to an increase in the waiting time for P2. This is one of the drawbacks of the FCFS scheduling algorithm.
In a real-time operating system, where the processes have deadlines, the FCFS scheduling algorithm can lead to missing deadlines and hence is not suitable for such systems. The FCFS scheduling algorithm is mainly used in batch processing systems where the processes are executed one after the other and the waiting time is not an issue.
In conclusion, the First Come First Serve (FCFS) CPU scheduling algorithm is a simple and straightforward algorithm that executes processes in the order in which they arrive. However, it does not prioritize processes based on their execution time or priority, leading to an increase in the waiting time for processes with short execution times. The FCFS scheduling algorithm is mainly used in batch processing systems where the waiting time is not an issue.
Here is a numerical example of First Come First Serve (FCFS) CPU scheduling:
Consider a scenario where four processes, P1, P2, P3, and P4, arrive in the order P1, P2, P3, and P4 and each process requires the following execution times:
- Process P1 requires 10 units of time
- Process P2 requires 5 units of time
- Process P3 requires 8 units of time
- Process P4 requires 7 units of time
The CPU scheduling algorithm used here is FCFS and so the processes will be executed in the order in which they arrive. The Gantt chart for the process execution is as follows:
| Process | Start Time | Finish Time |
|---|---|---|
| P1 | 0 | 10 |
| P2 | 10 | 15 |
| P3 | 15 | 23 |
| P4 | 23 | 30 |
The waiting time for each process can be calculated as follows:
- Waiting time for P1 = 0 (since it is the first process)
- Waiting time for P2 = 10 (start time of P2) - (finish time of P1) = 10 - 10 = 0
- Waiting time for P3 = 15 (start time of P3) - (finish time of P2) = 15 - 15 = 0
- Waiting time for P4 = 23 (start time of P4) - (finish time of P3) = 23 - 23 = 0
The average waiting time for the processes can be calculated as follows:
Average Waiting Time = (0 + 0 + 0 + 0) / 4 = 0
In conclusion, the above example shows the functioning of the First Come First Serve (FCFS) CPU scheduling algorithm, where the processes are executed in the order in which they arrive and the waiting time for each process is calculated. The example also shows that the FCFS scheduling algorithm does not prioritize processes based on their execution time or priority and hence processes with short execution times may have to wait for longer periods of time.
Here is a sample C++ program that implements the First Come First Serve (FCFS) CPU scheduling algorithm:
cpp#include <iostream>
#include <vector>
struct Process
{
int pid; // Process ID
int arrival; // Arrival time
int burst; // Burst time
// Constructor to initialize the process
Process(int pid, int arrival, int burst)
{
this->pid = pid;
this->arrival = arrival;
this->burst = burst;
}
};
// Function to calculate waiting time for all processes
void calculateWaitingTime(std::vector<Process> &processes)
{
int n = processes.size();
processes[0].burst = processes[0].burst + processes[0].arrival;
for (int i = 1; i < n; i++)
{
processes[i].burst = processes[i - 1].burst + processes[i].burst; processes[i].arrival = processes[i - 1].burst;
}
for (int i = 0; i < n; i++)
{
processes[i].arrival = processes[i].burst - processes[i].arrival;
}
}
// Function to calculate turn around time for all processes
void calculateTurnAroundTime(std::vector<Process> &processes)
{
int n = processes.size();
for (int i = 0; i < n; i++)
{
processes[i].burst = processes[i].arrival + processes[i].burst;
}
}
// Function to display the results
void displayResults(std::vector<Process> &processes)
{
int n = processes.size();
std::cout << "Process ID\tArrival Time\tBurst Time\tWaiting Time\tTurn Around Time" << std::endl;
for (int i = 0; i < n; i++)
{
std::cout << processes[i].pid << "\t\t" << processes[i].arrival << "\t\t" << processes[i].burst << "\t\t"
<< processes[i].arrival << "\t\t" << processes[i].burst << std::endl;
}
}
int main()
{
std::vector<Process> processes = {Process(1, 0, 10), Process(2, 2, 5), Process(3, 4, 8), Process(4, 6, 7)};
calculateWaitingTime(processes);
calculateTurnAroundTime(processes);
displayResults(processes);
return 0;
}In the above code, a structure Process is defined to store the details of a process, such as the process ID, arrival time, and burst time. The calculateWaitingTime function calculates the waiting time for each process, while the calculateTurnAroundTime function calculates the turn around time for each process. The displayResults function displays the results in a tabular format.
In the main function, a vector of processes is created and the calculateWaitingTime, calculateTurnAroundTime, and displayResults functions are called in sequence to display the results.
