First-Come First-Served Scheduling

First-Come First-Served (FCFS), also called First-In First-Out (FIFO) scheduling, is a non-preemptive CPU scheduling discipline. When a process enters the ready state, it is appended to the tail of a single ready queue. The scheduler always selects the process at the head of the queue to run next. Crucially, once selected, a process retains the CPU for its entire next CPU burst — the scheduler never interrupts a running process to give the CPU to a newly arrived or higher-priority process. A running process only releases the CPU voluntarily: by terminating, or by issuing a blocking operation (e.g., I/O) that moves it out of the ready queue. Two properties define FCFS completely: (1) the queueing discipline is FIFO — ties in arrival order are broken by whichever tie-break the system uses (typically arrival timestamp or process ID), and (2) the dispatch mode is non-preemptive — no timer-based or priority-based interruption occurs. Both properties matter independently: a preemptive scheduler could still choose "oldest-first" as its selection rule, but FCFS specifically pairs FIFO ordering with strict non-preemption, which is what produces its characteristic behavior. The performance metrics relevant to FCFS are the same ones defined generally in Scheduling Performance Metrics: waiting time (time spent in the ready queue, not running), turnaround time (completion time minus arrival time), and response time (time from arrival to first execution — for FCFS, response time equals waiting time, since a process runs to completion once dispatched). FCFS optimizes none of these in general; it only guarantees that no process waits forever, since the queue is monotonically drained in arrival order — this gives FCFS a strong freedom from starvation, even though its average performance is often poor.

The mechanism is deliberately minimal. There is one ready queue. Arrivals are pushed to the tail; the CPU always pulls from the head. ``` structure Process: pid arrival_time burst_time # length of next CPU burst remaining_time # = burst_time, never decremented mid-run (non-preemptive) start_time = None completion_time = None FCFS_SCHEDULE(process_list):

# Step 1: order arrivals into the ready queue queue = SORT(process_list by arrival_time, tie-break by pid) current_time = 0 results = [] for p in queue: # process the queue strictly in order

# Step 2: if CPU is idle waiting for this process to arrive, advance clock if current_time < p.arrival_time: current_time = p.arrival_time # CPU idles until next arrival

# Step 3: dispatch p — it runs to completion, uninterrupted p.start_time = current_time current_time = current_time + p.burst_time p.completion_time = current_time

# Step 4: derive metrics p.turnaround_time = p.completion_time - p.arrival_time p.waiting_time = p.turnaround_time - p.burst_time p.response_time = p.start_time - p.arrival_time results.append(p) return results ``` Two subtleties are easy to miss and are worth stating explicitly:

• Idle-CPU handling (Step 2): if the queue empties and the next arrival hasn't happened yet, the CPU must idle rather than time-travel — `current_time` can only jump forward to the next arrival, never run ahead of real arrivals.
• Non-preemption (Step 3): the entire `burst_time` is consumed in one atomic step. No arrival occurring during `[start_time, completion_time)` can affect `p`, which is exactly what distinguishes FCFS from Round-Robin Scheduling.

The figure below shows the ready queue as a physical FIFO structure and the resulting single-CPU timeline (Gantt chart) it produces.

Time complexity. Given `n` processes, sorting arrivals costs `O(n log n)` (or `O(n)` if arrivals are already presented in order, as is typical since arrival order is definitionally how they enter the queue). The scheduling loop itself is `O(n)`: each process is dequeued once, and updating its four timing fields is `O(1)` work per process. So the whole algorithm is: ``` T(n) = O(n log n) [dominated by the initial sort] ``` or `O(n)` if the input is pre-sorted by arrival, which is the common case since the ready queue naturally receives processes in arrival order via interrupts. Each ready-queue operation (enqueue on arrival, dequeue on dispatch) is `O(1)` with a standard linked-list or circular-buffer FIFO implementation — this is in fact FCFS's chief practical virtue: dispatch overhead is minimal, with no comparisons, no priority recomputation, no aging.

Space complexity. `O(n)` to hold the queue and the per-process bookkeeping fields; no auxiliary data structures beyond the FIFO itself.

Correctness argument. "Correctness" for a scheduler means: every process is eventually dispatched, is dispatched exactly once, and the computed metrics match the algorithm's own definition. This follows from a simple loop invariant on Step-by-step execution: Invariant: immediately before iteration `k` of the `for` loop, `current_time` equals the completion time of the `(k-1)`-th process in arrival order (or the time of the first arrival, if `k = 1`), and every process before position `k` has been dispatched exactly once, in order.

• Base case (`k=1`): before the first iteration, no process has run, and `current_time = 0`. The invariant holds vacuously.
• Inductive step: assume the invariant holds before iteration `k`. Step 2 advances `current_time` to `max(current_time, p_k.arrival_time)`, which is correct because the CPU cannot start `p_k` before it exists, but also should not idle if it's already available. Step 3 then runs `p_k` for exactly `burst_time` uninterrupted (justified by non-preemption — no other event can intervene), setting `completion_time` correctly. This restores the invariant for `k+1`.
• Termination: the loop processes each of the `n` processes exactly once (FIFO, no reordering, no skipping), so after the final iteration all processes are dispatched and the invariant, applied at `k = n+1`, certifies every completion time is correct.

No-starvation guarantee. Because the queue is strictly FIFO and monotonically drained (no process is ever moved backward or re-inserted ahead of others), every process's position in the queue can only decrease over time — hence every process reaches the head after a bounded number of dispatches (at most `n-1` others ahead of it). This is a real guarantee: FCFS cannot starve a process indefinitely, unlike naive priority schedulers.

What FCFS does not guarantee — the convoy effect. FCFS makes no attempt to minimize waiting time, and this is not a minor gap: it can be made arbitrarily bad. Consider one long process `P_long` with burst `B` arriving at time 0, followed immediately by `k` short processes each with burst `ε`. Under FCFS, each short process waits at least `B` (the entire duration of `P_long`), giving total waiting time roughly `k·B`, whereas the optimal (non-preemptive) order — placing all short jobs first — gives total waiting time close to `k·ε + B` (dominated by the small jobs finishing almost immediately, with only the last one waiting on the sum of all short bursts, still `≪ k·B` for `B ≫ ε`). This gap can be made arbitrarily large by increasing `B/ε`, which is a proof by construction that FCFS has unbounded competitive ratio against the optimal non-preemptive order for average waiting time. This is precisely the convoy effect: short jobs (or I/O-bound jobs that briefly need the CPU) queue up behind one CPU-bound job, and every one of them absorbs that job's full burst as wasted waiting time.

Tradeoff summary. FCFS trades average-case efficiency for simplicity, fairness-by-arrival, and starvation-freedom. It is provably non-optimal for average waiting/turnaround time (Shortest-Job-First is optimal among non-preemptive disciplines for average waiting time — this is proved by an exchange argument shown in Shortest-Job-First Scheduling), but it requires no burst-time prediction, no ready-queue reordering, and has zero context-switch overhead beyond one per process.

Consider five processes arriving at a system, with the following arrival times and CPU burst lengths:

Trace the algorithm exactly as pseudocode executes it. The queue, sorted by arrival, is `[P1, P2, P3, P4, P5]`.

Completing the metrics table:

Average waiting time: ``` (0 + 5 + 6 + 13 + 13) / 5 = 37 / 5 = 7.4 ``` Average turnaround time: ``` (6 + 7 + 14 + 14 + 16) / 5 = 57 / 5 = 11.4 ``` Notice the convoy effect concretely: P4, which needs only 1 unit of CPU time, waits 13 units — thirteen times its own burst — purely because it landed behind P1 (burst 6) and P3 (burst 8). If P3 (the long job) had instead arrived last rather than third, P4 and P5 would each wait far less, and the average waiting time would drop substantially, even though the total CPU work is unchanged. This is the crux of FCFS's weakness: average performance depends on arrival order, not on total work, which no scheduler that only reorders by burst-length awareness would tolerate — exactly the gap Shortest-Job-First Scheduling closes.

FCFS was not "invented" by a single researcher in the way an algorithm like Dijkstra's shortest path was — it is the natural, zero-assumption baseline that emerged as soon as the first multiprogrammed batch systems needed any rule for ordering competing jobs. Its formal analysis, however, belongs to the broader development of queueing theory and early operating systems scheduling research in the 1950s–60s, when batch computing made the cost of scheduling decisions economically visible for the first time.

Pure FCFS is rarely a production system's sole CPU scheduler today, because interactive and mixed workloads punish it via the convoy effect. But it survives, unmodified, in several important places:

• Batch processing systems (mainframe job queues, print spoolers, and many HPC job schedulers for non-interactive workloads) still use FCFS, or FCFS-with-backfilling, because job order fairness and predictability matter more than optimizing average wait when jobs run for hours regardless.
• Disk I/O scheduling historically included an FCFS mode as the simplest disk-arm scheduling policy, serving as the baseline against which SCAN, C-SCAN, and SSTF disk schedulers are compared — directly analogous to how FCFS is the CPU-scheduling baseline.
• Network routers and switches use FIFO queuing as the default packet-scheduling discipline at each output port, inheriting exactly the same convoy-effect risk (a large packet delaying many small ones), which motivates fair-queueing and weighted round-robin packet schedulers.
• Message queues and task queues in distributed systems (e.g., simple job queues in web backends) frequently default to FIFO ordering for its predictability and implementation simplicity, accepting the head-of-line blocking risk as a tradeoff.
• Teaching and benchmarking: virtually every operating systems course and every scheduling-algorithm comparison begins with FCFS as the control condition, precisely because its flaws are so cleanly demonstrable — as the worked example above shows.

Understanding FCFS deeply is what makes the improvements in Shortest-Job-First Scheduling (reorder by burst length to minimize average waiting time) and Round-Robin Scheduling (add preemption via time slices to bound worst-case waiting) legible as targeted fixes to specific, provable FCFS failures, rather than arbitrary alternative designs.

Ask the tutor: How would the worked example's average waiting time change if P3 (burst 8) arrived last instead of third?