First-Come, First-Served (FCFS)

Every engineering decision involves tradeoffs. FCFS scheduling is no exception—its simplicity buys certain guarantees while accepting certain costs. A mature understanding of FCFS requires seeing both sides clearly, without bias toward dismissing it as "outdated" or championing it as "fundamentally fair."

In production systems, the right scheduling algorithm depends on workload characteristics, performance requirements, and implementation constraints. FCFS remains the correct choice in specific contexts, just as it's clearly wrong in others. This page builds the complete evaluation framework to make that determination.

By examining FCFS's advantages and limitations systematically, we develop the analytical toolkit applicable to evaluating any scheduling algorithm—a skill far more valuable than memorizing when to use FCFS.

FCFS's advantages are genuine and significant in appropriate contexts. Let's examine each in depth.

1. Implementation Simplicity

FCFS is the simplest possible scheduling algorithm to implement correctly:

• Data Structure: A single FIFO queue
• Selection Logic: return queue.dequeue() — no comparisons, no sorting, no state examination
• Code Size: Often under 50 lines for a complete implementation
• Verification: Trivial to prove correct—FIFO queue invariants directly enforce scheduling behavior

Why This Matters:

In safety-critical systems (aviation, medical devices, nuclear reactors), simpler code is more trustworthy code. Formal verification of a scheduler is vastly easier when the algorithm has minimal branches and no complex logic. FCFS can be verified exhaustively; more complex schedulers require sophisticated proof techniques.

In resource-constrained embedded systems, scheduler code competes for the same limited memory as application code. A 50-line FCFS scheduler leaves more room for functionality than a 5000-line CFS implementation.

2. Minimal Computational Overhead

FCFS has the lowest possible scheduler overhead:

• Scheduling Decision: O(1) — constant time regardless of queue length
• No Sorting: Unlike SJF, no need to maintain sorted order
• No Comparisons: Unlike priority scheduling, no need to examine process attributes
• No History Tracking: Unlike MLFQ, no need to track past behavior

Quantitative Impact:

Consider a system with 10,000 scheduling decisions per second:

At extreme decision frequencies, FCFS's overhead advantage compounds. In real-time systems where scheduler overhead must be bounded and minimal, this matters.

3. Starvation-Free Guarantee

FCFS provides an absolute guarantee against starvation:

• Every process that enters the queue will eventually reach the front
• No process can be indefinitely delayed by later arrivals
• Progress is guaranteed for all processes

Formal Property:

For any process P entering the queue at time t with n processes ahead of it:

Start_time(P) ≤ t + Σ(burst_times of n preceding processes)

This upper bound exists and is finite (assuming bounded burst times). Compare with priority scheduling, where a low-priority process may never run if higher-priority processes keep arriving.

When This Matters:

• Long-running scientific computations that must eventually complete
• Fairness-sensitive environments where "queue cutting" is unacceptable
• Systems where silent failures (never-scheduled processes) are catastrophic

4. Determinism and Reproducibility

Given identical input sequences, FCFS always produces identical schedules:

• No randomness: Unlike some load balancers or work-stealing queues
• No state dependency: Unlike MLFQ (which depends on process history)
• No timing sensitivity: Unlike preemptive schedulers affected by quantum boundaries

Applications:

• Debugging: Reproduce exact execution sequences for bug investigation
• Testing: Deterministic schedules enable reproducible test cases
• Simulation: Model system behavior precisely
• Certification: Demonstrate predictable behavior to regulatory bodies

5. No Prerequisite Information Required

FCFS requires no advance knowledge about processes:

• No burst time estimates: Unlike SJF, which needs burst duration
• No priority assignments: Unlike priority scheduling
• No behavior classification: Unlike MLFQ (interactive vs. batch)
• No deadline information: Unlike EDF

This makes FCFS applicable when:

• Process behavior is unpredictable or unknown
• Users cannot or will not provide scheduling hints
• System lacks instrumentation for behavior tracking

FCFS's limitations are equally significant and often dominate in modern systems. Understanding these precisely is essential for making informed algorithm choices.

1. Poor Average Waiting Time

FCFS's average waiting time is suboptimal for heterogeneous workloads:

• SJF is provably optimal for minimizing average waiting time
• FCFS can be arbitrarily worse than optimal depending on arrival order
• The gap between FCFS and optimal grows with workload heterogeneity

Mathematical Demonstration:

For the workload [100ms, 10ms, 10ms, 10ms]:

FCFS can achieve optimal performance by luck (favorable arrival order), but has no mechanism to ensure it.

2. Convoy Effect (Previously Analyzed)

As discussed in detail previously, FCFS suffers from the convoy effect:

• Long processes block short processes
• I/O devices experience bursty, inefficient utilization
• Short-process wait times become disproportionate to their CPU needs

This isn't just a theoretical concern—it's the primary reason FCFS is unsuitable for interactive systems, web servers, and most general-purpose computing.

3. No Responsiveness to Priority or Urgency

FCFS treats all processes identically, ignoring:

• User-assigned priorities: System administrators cannot prioritize critical services
• Urgency: Time-sensitive processes (real-time, interactive) wait behind non-urgent work
• Quality of Service: Cannot implement tiered service levels
• Resource importance: Cannot protect essential system processes

Real-World Impact:

In a web server using FCFS:

• An admin's critical configuration update waits behind queued requests
• A real-time video stream buffers while batch analytics run
• Health check requests (preventing system detection failure) queue behind normal traffic

4. Non-Preemptive: No Interactive Responsiveness

FCFS is inherently non-preemptive:

• A running process cannot be interrupted except by its own action
• Interactive users experience freezes whenever long processes run
• System administrators cannot quickly interrupt runaway processes (scheduler-wise)

Interactive System Failure Mode:

User types on keyboard → keystroke handler enters ready queue → CPU-bound process running → user waits for keystroke processing until CPU burst completes (potentially seconds or minutes)

This is fundamentally incompatible with interactive computing expectations.

5. Throughput Degradation Under Heterogeneous Load

By causing I/O underutilization (convoy effect) and preventing optimal CPU use, FCFS reduces overall system throughput:

• I/O devices idle during long CPU bursts
• CPU idles during synchronized I/O bursts
• Neither resource achieves sustained high utilization

Throughput Comparison (Simulated):

FCFS's throughput advantage disappears with any workload heterogeneity.

6. Sensitivity to Arrival Order

FCFS performance is extremely sensitive to something completely outside scheduler control—arrival order:

• Best case and worst case can differ by orders of magnitude
• Performance is non-deterministic in systems with random arrival patterns
• Cannot adapt to or correct for unfavorable orderings

This randomness makes FCFS unsuitable when consistent, predictable performance is required.

To fully evaluate FCFS, we must compare it systematically against alternative scheduling algorithms across multiple dimensions.

Detailed Algorithm Comparisons:

FCFS vs. Shortest Job First (SJF):

• SJF is provably optimal for minimizing average waiting time
• FCFS requires no burst time knowledge; SJF requires accurate estimates
• SJF can starve long processes; FCFS cannot
• SJF has higher overhead (maintaining sorted structure)

Verdict: Prefer SJF when burst times are predictable and starvation is manageable; prefer FCFS when burst times unknown or starvation intolerable.

FCFS vs. Round Robin (RR):

• RR provides good response time for interactive workloads
• FCFS has lower overhead (no timer interrupts)
• RR requires quantum tuning; FCFS requires no parameters
• RR prevents convoy effect through preemption

Verdict: Prefer RR for interactive systems; prefer FCFS for batch or when minimal overhead critical.

FCFS vs. Priority Scheduling:

• Priority allows distinguishing important from unimportant work
• FCFS provides implicit "arrival priority" (earlier = higher)
• Priority can starve low-priority processes; FCFS cannot
• Priority requires priority assignment mechanism

Verdict: Prefer priority when workload has genuine importance hierarchy; prefer FCFS when all processes equally important.

Based on our comprehensive analysis, we can now define when FCFS is and is not appropriate.

Decision Framework:

When selecting a scheduling algorithm, consider these questions:

1. What's the workload distribution?

   • Uniform → FCFS acceptable
   • Heterogeneous → Avoid FCFS

2. What matters more: latency or throughput?

   • Throughput (batch) → FCFS acceptable
   • Latency (interactive) → Avoid FCFS

3. Do you have burst time estimates?

   • No → FCFS or RR
   • Yes → Consider SJF/SRTF

4. Can you tolerate starvation?

   • No → FCFS or RR
   • Yes → Consider priority or SJF

5. What's your overhead budget?

   • Minimal → FCFS
   • Moderate → RR or priority
   • Flexible → MLFQ or CFS

6. Need priority support?

   • Yes → Priority or MLFQ
   • No → FCFS or RR

Let's examine how the FCFS evaluation framework applies to real systems, understanding why particular choices were made.

Example 1: Print Queue

System: Office printer queue Workload: Print jobs varying from 1 page to 500 pages

Analysis:

• Users expect documents in submission order (social contract)
• No job has genuine priority over others (fairness required)
• Throughput matters less than perceived fairness
• Simple implementation preferred (embedded printer firmware)

Choice: FCFS Justification: Fairness and simplicity trump efficiency. Users accept waiting because "first come, first served" is intuitively fair.

Example 2: Web Server Request Queue

System: High-traffic web server Workload: Mix of quick page loads (10ms) and expensive API calls (500ms)

Analysis:

• Response time critical for user experience
• Heterogeneous workload (convoy effect severe)
• No inherent priority difference between requests
• High throughput required

Choice: NOT FCFS → Processing queues typically use worker pools with bounded request processing Justification: Convoy effect would destroy response times. Instead, use connection limiting and timeout-based preemption.

Example 3: Message Queue (e.g., RabbitMQ, SQS)

System: Asynchronous task queue Workload: Varies by use case

Analysis:

• Message ordering often semantically important
• Processing time varies by message type
• Starvation unacceptable (all messages must be processed)
• Simple, reliable delivery is priority

Choice: FCFS (with priority extensions available) Justification: Message ordering preservation is primary requirement. Extensions like priority queues address heterogeneity when needed.

Example 4: Linux CPU Scheduler

System: General-purpose desktop/server OS Workload: Mix of interactive (GUI, editors) and batch (compilation, analytics)

Analysis:

• Must serve interactive and batch workloads
• User expects responsive system
• Workload highly heterogeneous and unpredictable
• Fair resource sharing required

Choice: NOT FCFS → Completely Fair Scheduler (CFS) Justification: Interactive responsiveness and fair sharing under mixed workloads. CFS uses virtual runtime tracking for proportional fairness—far more sophisticated than FCFS.

FCFS rarely appears in pure form in modern systems. Instead, it's commonly combined with other mechanisms to capture its benefits while mitigating its weaknesses.

1. FCFS Within Priority Levels

Many priority schedulers use FCFS within each priority band:

Priority 0 (highest): [P1] → [P5] → [P9]  ← FCFS within priority 0
Priority 1:           [P2] → [P3] → [P7]  ← FCFS within priority 1
Priority 2 (lowest):  [P4] → [P6] → [P8]  ← FCFS within priority 2

Scheduler selects highest non-empty priority level, then FCFS within that level.

Benefits: Priority responsiveness + fairness within priority classes Used in: Windows thread scheduling, many RTOSes

2. FCFS with Request Deadlines

Some systems use FCFS ordering but abort or deprioritize requests exceeding time limits:

Queue: [Request1, Request2, Request3]
Processing: FCFS
Timeout: If any request waits > 5 seconds, mark as failed and skip

Benefits: FCFS fairness + protection against convoy infinite delays Used in: Web servers, API gateways, database connection pools

3. Multi-Queue FCFS

Route requests to separate FCFS queues based on characteristics:

Fast Queue (short requests): Request1 → Request3 → Request7
Slow Queue (long requests):  Request2 → Request4

Scheduler alternates between queues or uses weighted scheduling

Benefits: Convoy effect isolated to slow queue; fast queue remains responsive Used in: Disk I/O schedulers (but with seek optimization), network packet scheduling

Beyond qualitative guidance, we can establish quantitative criteria for when FCFS is appropriate based on workload statistics.

Coefficient of Variation (CV) Rule:

The coefficient of variation of burst times indicates workload heterogeneity:

CV = σ / μ  (standard deviation / mean)

Guidelines:

Example:

• Workload [10, 11, 9, 10, 12]: μ=10.4, σ=1.14, CV=0.11 → FCFS excellent
• Workload [5, 100, 10, 5, 200]: μ=64, σ=83.5, CV=1.30 → Avoid FCFS

Response Time Requirement Test:

If the system has a target response time R:

If max(burst_time) > R, FCFS cannot guarantee response time

Since FCFS is non-preemptive, any process arriving behind a long burst will violate R if that burst exceeds R.

Example: Target R = 100ms

• If longest possible burst = 50ms → FCFS may meet target
• If longest possible burst = 500ms → FCFS will violate target when convoy forms

Convoy Severity Estimation:

Estimate convoy penalty using:

Expected Penalty = P(long first) × (n × (B_max - B_avg))

Where:
  P(long first) = probability a long burst leads the queue
  n = average queue length when convoy forms
  B_max = maximum burst time
  B_avg = average burst time

If Expected Penalty exceeds acceptable overhead, switch from FCFS.

We've completed a comprehensive evaluation of FCFS scheduling's advantages and limitations. Let's consolidate the key insights:

What's Next:

In the final page of this module, we'll examine Gantt Chart Analysis—the standard visualization and analytical tool for understanding scheduling behavior. We'll learn to construct, interpret, and analyze Gantt charts for FCFS and lay the groundwork for comparing scheduling algorithms visually.