FCFS: First Come, First Served
First Come, First Served (FCFS) is a scheduling algorithm used by operating systems to manage the execution of processes. It operates under the simplest logic: the first process to request the CPU is the first to receive it. This algorithm is most effective in systems where tasks are relatively similar in nature and execution time. However, its simplicity can lead to inefficiency in handling a mix of short and long processes.
Characteristics of FCFS
- Non-preemptive: Once a process starts execution, it runs to completion without being interrupted by other processes.
- Fairness: Processes are served in the exact order of their arrival, ensuring a first-come, first-served basis.
- Simplicity: FCFS is easy to understand and implement, making it a fundamental concept in operating system design.
- Varying Wait Times: Processes may experience long wait times, especially if preceded by a CPU-intensive process.
Advantages and Disadvantages of FCFS
Advantages
- Simple to understand and implement.
- Ensures fairness among processes.
Disadvantages
- Can lead to inefficient utilization of CPU, known as the convoy effect.
- Varying and potentially long waiting times for processes.
FCFS drawbacks
While FCFS is straightforward, its efficiency can significantly vary depending on the nature and mix of processes. For instance, the "convoy effect" can occur when a series of short processes are delayed by a preceding long process, leading to increased average waiting and turnaround times. Understanding these nuances is crucial for system designers to optimize process scheduling under specific workload conditions.
Contextual Applications of FCFS
Despite its simplicity, FCFS is less efficient for CPU scheduling in multi-programming environments. However, it is effectively used in scenarios requiring simple queue management, such as print spooling and task scheduling in environments where tasks are non-interactive and execution time is relatively predictable.
FCFS Terminologies and their Mathematical Analysis
- Arrival Time (AT): The time at which a process arrives in the queue.
- Burst Time (BT): The total time a process requires the CPU for execution.
- Completion Time (CT): The time at which a process completes its execution. It is calculated based on the burst time of the preceding process and the arrival time of the current process. If a process arrives and finds the CPU free, it starts execution. If the CPU is busy, the process waits until the CPU is free again.
- Turnaround Time (TAT): $TAT = CT - AT$. This measures the total time taken for a process to be executed, including the waiting time in the queue and the actual execution time i.e. from getting to the queue to its completion.
- Waiting Time (WT): $WT = TAT - BT$. This reflects the total time a process spends waiting in the queue to be executed.
- Average Turnaround Time (TATave): $TAT_{ave} = \frac{\sum{TAT}}{n}$ where \(n\) is the number of processes. It is the average of turnaround times for all processes.
- Average Waiting Time (WTave): $WT_{ave} = \frac{\sum{WT}}{n}$, providing the average of waiting times for all processes thus giving overall waiting time efficiency across all processes.
Implementation of FCFS
Implementing FCFS requires a queue structure to hold processes as they arrive. The scheduler selects the first process from the queue, executes it until completion, and then removes it from the queue to proceed with the next process.
Queue Data Structure
The queue is a fundamental data structure for FCFS, enabling FIFO (First In, First Out) management of processes. It supports operations such as enqueue (to add processes) and dequeue (to remove processes for execution).
Algorithm Steps
- Enqueue: Upon arrival, a process is placed at the end of the queue.
- Dequeue: The process at the front of the queue is selected for execution.
- Execute: The selected process is executed until completion.
- Repeat: Upon completion, the process is removed, and the scheduler selects the next process from the queue.
Gantt Chart for FCFS Scheduling
A Gantt chart is a visual representation of the schedule for processes, showing start and finish times against a linear timescale. It illustrates the flow of processes in the FCFS scheduling algorithm and helps in analyzing the efficiency of process execution. Here's how to create a Gantt chart based on a process table containing process ID, arrival time (AT), and burst time (BT).
- Sort Processes by Arrival Time: Arrange the processes in the order they arrive. If two processes have the same arrival time, they can be ordered by their process ID or any other secondary criterion.
- Determine Start and Finish Times: For each process, calculate its start time (equal to the finish time of the previous process or its arrival time, whichever is later) and its finish time (start time plus its burst time).
- Create the Timescale: Draw a horizontal line and mark the time units along it. This line will serve as the timescale for the Gantt chart.
- Plot Processes: For each process, draw a bar starting at its start time and ending at its finish time. Label each bar with the process ID. The length of the bar represents the burst time of the process.
- Indicate Idle Times: If there is a gap between the finish time of one process and the start time of the next, indicate this as idle time on the chart. Idle times show when the CPU is not processing any task.
Below is a simplified example of how to represent this in a textual format, assuming a process table with processes P1, P2, and P3 with respective arrival times and burst times.
| Job | AT | BT |
|---|---|---|
| A | 1 | 2 |
| B | 1 | 3 |
| C | 0 | 5 |
| D | 2 | 1 |
Gantt Chart Representation
C
A
B
D
0
5
7
10
11
This Gantt chart shows that C starts execution at time 0 and runs for 5 units of time, followed by A, which starts immediately after C finishes and runs for 2 units of time. B starts at time 7, immediately after A finishes. D is finally executed and completes at 11 units of time. There are no idle times in this example, indicating efficient CPU utilization for this sequence of processes under FCFS scheduling.
FCFS Scheduling Example
Consider a process table with 5 processes to demonstrate FCFS scheduling, calculate key metrics, and illustrate a Gantt chart.
| Process | Arrival Time (AT) | Burst Time (BT) |
|---|---|---|
| P1 | 0 | 4 |
| P2 | 1 | 3 |
| P3 | 2 | 1 |
| P4 | 3 | 2 |
| P5 | 4 | 5 |
Gantt Chart Representation
The Gantt chart for these processes, scheduled according to FCFS, is as follows:
A
B
C
D
E
0
4
7
8
10
15
Calculating FCFS Metrics
Next, we'll calculate the Completion Time (CT), Turnaround Time (TAT), and Waiting Time (WT) for each process, followed by the average TAT and WT.
Completion Time (CT)
To find the CT for each process:
- \(CT_{P1} = AT_{P1} + BT_{P1} = 0 + 4 = 4\)
- \(CT_{P2} = CT_{P1} + BT_{P2} = 4 + 3 = 7\)
- \(CT_{P3} = CT_{P2} + BT_{P3} = 7 + 1 = 8\)
- \(CT_{P4} = CT_{P3} + BT_{P4} = 8 + 2 = 10\)
- \(CT_{P5} = CT_{P4} + BT_{P5} = 10 + 5 = 15\)
Turnaround Time (TAT)
To find the TAT for each process (\(TAT = CT - AT\)):
- \(TAT_{P1} = CT_{P1} - AT_{P1} = 4 - 0 = 4\)
- \(TAT_{P2} = CT_{P2} - AT_{P2} = 7 - 1 = 6\)
- \(TAT_{P3} = CT_{P3} - AT_{P3} = 8 - 2 = 6\)
- \(TAT_{P4} = CT_{P4} - AT_{P4} = 10 - 3 = 7\)
- \(TAT_{P5} = CT_{P5} - AT_{P5} = 15 - 4 = 11\)
Waiting Time (WT)
To find the WT for each process (\(WT = TAT - BT\)):
- \(WT_{P1} = TAT_{P1} - BT_{P1} = 4 - 4 = 0\)
- \(WT_{P2} = TAT_{P2} - BT_{P2} = 6 - 3 = 3\)
- \(WT_{P3} = TAT_{P3} - BT_{P3} = 6 - 1 = 5\)
- \(WT_{P4} = TAT_{P4} - BT_{P4} = 7 - 2 = 5\)
- \(WT_{P5} = TAT_{P5} - BT_{P5} = 11 - 5 = 6\)
Average Turnaround Time (TATave)
$$TAT_{ave} = \frac{\sum{TAT_i}}{n}$$ $$= \frac{4 + 6 + 6 + 7 + 11}{5}$$ $$= \frac{34}{5}$$ $$= 6.8$$
Average Waiting Time (WTave)
$$WT_{ave} = \frac{\sum{WT_i}}{n}$$ $$= \frac{0 + 3 + 5 + 5 + 6}{5}$$ $$= \frac{19}{5}$$ $$= 3.8$$
| Job | AT | BT | FT | TT | WT |
|---|---|---|---|---|---|
| A | 0 | 4 | 4 | 4 | 0 |
| B | 1 | 3 | 7 | 6 | 3 |
| C | 2 | 1 | 8 | 6 | 5 |
| D | 3 | 2 | 10 | 7 | 5 |
| E | 4 | 5 | 15 | 11 | 6 |
| Average | 34 / 5 = 6.8 | 19 / 5 = 3.8 | |||
FCFS Implementation in Python
Consider the following process table for an FCFS scheduling scenario:
| Process ID | Arrival Time (AT) | Burst Time (BT) |
|---|---|---|
| P1 | 0 | 4 |
| P2 | 1 | 3 |
| P3 | 2 | 2 |
# Python code to calculate CT, TAT, WT for the given process table
def calculate_fcfs_metrics(processes):
current_time = 0
metrics = []
for process in processes:
pid, at, bt = process
if current_time < at:
current_time = at
ct = current_time + bt
tat = ct - at
wt = tat - bt
metrics.append((pid, ct, tat, wt))
current_time = ct
return metrics
# Define the processes
processes = [("P1", 0, 4), ("P2", 1, 3), ("P3", 2, 2)]
# Calculate metrics
metrics = calculate_fcfs_metrics(processes)
# Output the results
for metric in metrics:
print(f"Process {metric[0]}, CT: {metric[1]}, TAT: {metric[2]}, WT: {metric[3]}")
This code calculates the Completion Time (CT), Turnaround Time (TAT), and Waiting Time (WT) for each process based on the FCFS scheduling algorithm. The results provide the necessary data to create a Gantt chart.