CPU Scheduling: Learn First Come First Serve (FCFS) Algorithm

Overview of the First Come First Serve (FCFS) Algorithm

This section summarizes what FCFS does, its assumptions, and where it fits among scheduling strategies. Throughout the article we assume a non-preemptive scheduler by default (single-core execution for clarity) and focus on arrival-order behavior, complexity, and operational trade-offs so you can map theory to the simulator and real systems.

Understanding FCFS

FCFS is a non-preemptive scheduling algorithm implemented with a FIFO queue. When a process arrives, it is appended to the tail; the dispatcher selects the head of the queue and runs it to completion. Implementation complexity is minimal: enqueue on arrival, dequeue for execution.

Time complexity note: if arrival timestamps are not pre-sorted, the scheduler typically sorts processes once by arrival time at O(N log N) cost; subsequent queue operations (enqueue/dequeue) are O(1). If arrivals are already ordered (streaming intake), scheduling can proceed in O(N) time overall. These practical distinctions matter when simulating or batching very large workloads.

Key trade-offs:

• Simplicity and low scheduling overhead
• Fairness in arrival order (no starvation)
• Convoy effect: short jobs can be delayed behind long ones
• Unsuitable for time-sensitive or highly interactive workloads

How FCFS Works: Step-by-Step Explanation

Below is a concise operational description of the FCFS lifecycle in a scheduler: arrival handling, queue management, dispatch decision, and completion. The step-by-step list maps directly to the simulator implementation later, so you can trace timestamps in the code back to each stage in the workflow.

Step-by-Step Process

Workflow:

1. New processes arrive and are appended to the ready queue.
2. The scheduler picks the head of the queue and runs it until completion.
3. When the running process finishes, the scheduler dequeues the next process.
4. Continue until the queue is empty.

Example input (arrival times in seconds): P1(arrive=0, burst=5), P2(arrive=2, burst=3), P3(arrive=3, burst=2). Execution order follows arrival: P1 → P2 → P3. Waiting times: P1=0s, P2=5s, P3=8s; turnaround times: P1=5s, P2=8s, P3=10s.

Gantt Chart Visualization

The following inline SVG visualizes the timeline for the example above. It clarifies start/completion times and illustrates how waiting accumulates.

Notes:

• The chart scale is linear (1s = 60px). Waiting time can be read as the gap between arrival and bar start.
• Gantt charts are useful in reports and can be programmatically generated with plotting libraries such as matplotlib (matplotlib.org) or interactive tools like Plotly.

Full Runnable Python Simulator

This script runs an FCFS simulation, computes waiting & turnaround times, prints a table, and (optionally) plots a Gantt chart using matplotlib. Tested with Python 3.10 and matplotlib 3.7.1.

#!/usr/bin/env python3
"""
fcfs_sim.py - Simple FCFS scheduler simulator
Requires: Python 3.10+
Optional plotting: pip install matplotlib==3.7.1
Run: python fcfs_sim.py
"""
from dataclasses import dataclass
from typing import List

@dataclass
class Process:
    pid: str
    arrival: int
    burst: int
    start: int = -1
    completion: int = -1


def fcfs_schedule(processes: List[Process]) -> List[Process]:
    # Ensure processes are ordered by arrival time
    procs = sorted(processes, key=lambda p: p.arrival)
    current_time = 0
    for p in procs:
        p.start = max(current_time, p.arrival)
        p.completion = p.start + p.burst
        current_time = p.completion
    return procs


def compute_metrics(processes: List[Process]):
    total_wait = 0
    total_turnaround = 0
    for p in processes:
        waiting = p.start - p.arrival
        turnaround = p.completion - p.arrival
        total_wait += waiting
        total_turnaround += turnaround
        print(f"{p.pid:>3} | arrival={p.arrival:>2} | burst={p.burst:>2} | start={p.start:>2} | completion={p.completion:>2} | wait={waiting:>2} | turnaround={turnaround:>2}")

    n = len(processes)
    print("\nAverages:")
    print(f"Average waiting time: {total_wait / n:.2f} s")
    print(f"Average turnaround time: {total_turnaround / n:.2f} s")
    # Throughput (jobs per second) = n / (makespan)
    makespan = max(p.completion for p in processes) - min(p.arrival for p in processes)
    print(f"Throughput: {n / makespan:.3f} jobs/s (makespan={makespan}s)")


if __name__ == '__main__':
    # Example processes: (pid, arrival, burst)
    input_procs = [Process('P1', 0, 5), Process('P2', 2, 3), Process('P3', 3, 2)]
    scheduled = fcfs_schedule(input_procs)
    compute_metrics(scheduled)

    # Optional plotting (matplotlib)
    try:
        import matplotlib.pyplot as plt
        fig, ax = plt.subplots()
        colors = ['#4CAF50', '#2196F3', '#FF9800', '#9C27B0']
        for i, p in enumerate(scheduled):
            ax.broken_barh([(p.start, p.burst)], (10 * i, 9), facecolors=colors[i % len(colors)])
            ax.text(p.start + p.burst / 2, 10 * i + 4.5, p.pid, va='center', ha='center', color='white')
        ax.set_xlabel('Time (s)')
        ax.set_yticks([])
        ax.set_title('FCFS Gantt Chart')
        plt.show()
    except Exception:
        # matplotlib not installed or running headless; skip plotting
        pass

How to run

1. Save as fcfs_sim.py.
2. Install optional plotting dependency: pip install matplotlib==3.7.1 (optional). See matplotlib.org for docs and backends.
3. Run: python fcfs_sim.py (tested on Python 3.10+). See python.org for Python downloads and runtime notes.

Sample console output for the included example shows the per-process metrics and averages.

Troubleshooting tips:

• If your environment is headless (CI), matplotlib may fail to show plots — configure a non-interactive backend (e.g., Agg) via matplotlib.use('Agg') before importing pyplot, or skip plotting entirely.
• If arrival times are not sorted when queued externally, sort by arrival before scheduling to ensure deterministic behavior; avoid relying on insertion order from distributed sources.
• When measuring production latency, prefer monotonic timers (see python.org) like time.monotonic() to avoid clock adjustments affecting measurements.

Performance Metrics and Evaluation

Measuring scheduler performance gives actionable data to guide changes. Key metrics:

• Waiting time (W): time a process waits in ready queue before starting. For process i: W_i = start_i - arrival_i.
• Turnaround time (T): total time from arrival to completion. T_i = completion_i - arrival_i = W_i + burst_i.
• Average waiting time: (Σ W_i) / n.
• Average turnaround time: (Σ T_i) / n.
• Throughput: jobs processed per unit time = n / makespan (where makespan = finish_last - arrival_first).
• CPU Utilization: fraction of time CPU spends executing (use wall-clock busy time / observation window). For multi-core systems, measure per-core and aggregate.

Tools and measurement

• Use language-native timers (e.g., time.monotonic() in Python) to avoid clock jumps when measuring production latency. See python.org for guidance on time APIs.
• For end-to-end load tests use benchmarking tools such as JMeter to generate load, and Prometheus to collect metrics at scale.
• Log arrival/start/completion timestamps to a structured sink (JSON lines or a time-series DB) for offline analysis using pandas or similar tooling.

Interpreting results

High average waiting time with low throughput indicates scheduling inefficiency (e.g., long-running jobs blocking others). High CPU idle with large queue length suggests worker starvation due to blockers or synchronization issues. Use percentiles (p95/p99) of waiting/response times, not only averages, to capture user-facing tail latency.

Advantages and Disadvantages of FCFS Scheduling

Pros of FCFS Scheduling

Advantages include:

• Minimal scheduler overhead — straightforward FIFO implementation.
• No starvation: every process that arrives will eventually run.
• Predictable ordering useful in scenarios that require strict arrival-order fairness (e.g., simple intake queues).

Concrete example: a university course registration intake used FCFS at the intake layer to record submissions; downstream asynchronous workers handled priority and validation, so FCFS simplified the intake process while preserving order of submissions.

Cons of FCFS Scheduling

Drawbacks include:

• Convoy effect and long average waiting times when long jobs precede short ones.
• Lack of priority handling — urgent tasks cannot preempt long-running tasks.
• Not ideal for interactive systems where tail latency matters.

Example cautionary tale: a batch-printing service that processed large documents first caused short print jobs to wait; switching to a small-first heuristic or introducing per-user quotas reduced user-perceived delays.

Real-World Applications of FCFS in Computing

Typical use cases:

• Initial intake queues where order of arrival must be preserved (e.g., ticketing or registration systems).
• Print spoolers where print jobs are expected to be processed in submission order.
• Batch systems that accept jobs and process them without tight latency constraints.

Limitations: in high-demand or interactive applications (game servers, real-time control), FCFS can create unacceptable tail latency; use priority, round-robin, or preemptive schedulers in those contexts.

Conclusion: When to Use FCFS in Your CPU Scheduling Strategy

FCFS is appropriate when simplicity and strict arrival-order fairness outweigh latency concerns — for example, initial intake queues or low-interactivity batch pipelines. In such systems, FCFS can reduce scheduling complexity and make behavior predictable.

However, when workload mix includes short, latency-sensitive tasks alongside long-running jobs, FCFS typically yields poor average and tail latencies due to the convoy effect. In those situations consider alternatives like Shortest Job First (SJF) for offline scheduling, or Round Robin and priority-based preemption for interactive systems.

When reporting measured improvements, provide context: arrival rates, workload mix, measurement window, and tools used. For example, the logistics intake optimization referenced earlier measured CPU idle using system metrics exported to Prometheus and compared averages across identical load windows before and after smoothing and worker pooling; FCFS was only one part of the solution.

Key Takeaways

• FCFS is simple and fair by arrival order but vulnerable to the convoy effect; monitor average and percentile wait times to detect issues.
• Implement FCFS with a FIFO queue; in concurrent systems use thread-safe queues (e.g., queue.Queue in Python — see python.org) and avoid shared mutable state without synchronization.
• Measure waiting time, turnaround time, throughput, and CPU utilization to evaluate scheduling changes. Use monotonic clocks and structured logging for accurate results.
• For production systems, combine FCFS intake with downstream prioritization or worker pools to balance simplicity and responsiveness.

Frequently Asked Questions

What is the main drawback of FCFS scheduling?

The primary drawback is the convoy effect where short processes are delayed behind long ones, increasing average and tail wait times. Use percentile metrics to detect whether this impacts user experience.

How does FCFS compare to Round Robin scheduling?

FCFS runs a process to completion (non-preemptive), which can increase latency for others. Round Robin gives each process a time slice, improving responsiveness for interactive workloads at the cost of higher context-switch overhead.

Can I implement FCFS in Java, and if so, how?

Yes. Use a thread-safe queue like java.util.concurrent.ConcurrentLinkedQueue or LinkedBlockingQueue to enqueue processes. Define a Process class with arrival and burst attributes, dequeue and execute the head, and capture start/completion timestamps for metrics.