First Come First Serve (FCFS)
Non-preemptive scheduling executing processes in arrival order. Simple queue-based scheduling algorithm that serves as the foundation for understanding CPU scheduling. Despite its simplicity, FCFS can suffer from the convoy effect where short processes are delayed by long-running processes ahead of them in the queue.
Visualization
Interactive visualization for First Come First Serve (FCFS)
FCFS Scheduling:
- • First Come First Serve
- • Non-preemptive
Interactive visualization with step-by-step execution
Implementation
1function fcfsScheduling(processes: {id: number; arrivalTime: number; burstTime: number}[]): {avgWaitTime: number; avgTurnaroundTime: number} {
2 processes.sort((a, b) => a.arrivalTime - b.arrivalTime);
3 let currentTime = 0;
4 let totalWait = 0, totalTurnaround = 0;
5
6 for (const p of processes) {
7 if (currentTime < p.arrivalTime) currentTime = p.arrivalTime;
8 const waitTime = currentTime - p.arrivalTime;
9 const turnaroundTime = waitTime + p.burstTime;
10 totalWait += waitTime;
11 totalTurnaround += turnaroundTime;
12 currentTime += p.burstTime;
13 }
14
15 return {
16 avgWaitTime: totalWait / processes.length,
17 avgTurnaroundTime: totalTurnaround / processes.length
18 };
19}Deep Dive
Theoretical Foundation
First Come First Serve (FCFS) is the simplest CPU scheduling algorithm where processes are executed in the exact order they arrive in the ready queue. It's non-preemptive, meaning once a process starts execution, it runs to completion without interruption. The algorithm maintains a FIFO (First In, First Out) queue of processes. While conceptually simple and fair in terms of arrival order, FCFS can lead to poor average waiting times due to the convoy effect, where short processes must wait for long processes that arrived earlier. The algorithm is deterministic and provides no starvation, but lacks optimization for system throughput or response time.
Complexity
Time
O(n log n)
O(n log n)
O(n log n)
Space
O(1)
Applications
Industry Use
Batch processing systems in mainframes
Print job queues in network printers
Simple embedded system task scheduling
Background job processing
First-generation operating systems
Sequential file processing systems
Use Cases
Related Algorithms
Shortest Job First (SJF)
Schedules process with shortest burst time first. Minimizes average waiting time (optimal).
Round Robin Scheduling
Preemptive scheduling with fixed time quantum. Each process gets equal CPU time slices.
Priority Scheduling
Schedules processes based on priority. Higher priority executes first. Can be preemptive or non-preemptive.
Quicksort
A highly efficient, in-place sorting algorithm that uses divide-and-conquer strategy. Invented by Tony Hoare in 1959, it remains one of the most widely used sorting algorithms due to its excellent average-case performance and cache efficiency.