First Come First Served - Learning Module

Loading content...

0/240

Gantt Chart Analysis

Visualizing CPU Scheduling

A picture is worth a thousand words—and in CPU scheduling, that picture is a Gantt chart. Named after Henry Gantt, who popularized it for project management in the early 1900s, the Gantt chart has become the universal tool for visualizing process execution timelines.

Gantt charts transform abstract scheduling concepts into concrete visual representations. Instead of reasoning about queue states and transition timestamps in your head, you can see which process runs when, identify idle periods, measure waiting times, and compare scheduling algorithms at a glance.

For FCFS scheduling analysis, Gantt charts are indispensable: they make the convoy effect visible, reveal arrival-order sensitivity, and provide the foundation for calculating performance metrics. Mastering Gantt chart construction and interpretation is an essential skill for operating systems engineers.

What You Will Learn

By the end of this page, you will know how to construct FCFS Gantt charts from process specifications, extract all standard scheduling metrics from charts, use charts to compare scheduling algorithms, and identify common patterns that indicate performance characteristics.

Gantt Chart Fundamentals

A CPU scheduling Gantt chart is a horizontal bar chart showing process execution over time. Each bar represents a period during which a specific process holds the CPU.

Chart Structure:

Time:    0    5    10   15   20   25   30   35   40
         |----|----|----|----|----|----|----|----|----|
         
CPU:     [    P1    ][  P2  ][ P3 ][   P4   ]
         └──────────┴───────┴─────┴─────────┘
              12        7      4       9     (durations)

Components:

Time Axis (horizontal): Represents elapsed time from system start (t=0)
CPU Timeline: Single row showing which process is executing
Process Bars: Colored/labeled regions showing each process's CPU tenure
Boundaries: Vertical lines marking transition points (process starts/ends)
Labels: Process identifiers (P1, P2, etc.) and timing annotations

Reading the Chart:

Bar width represents execution duration (burst time used)
Bar position indicates start and end times
Gaps (unlabeled regions) represent CPU idle time
Transitions occur at marked time points

Information Encoded:

A properly constructed Gantt chart reveals:

Feature	How to Read	What It Means
Total time	Right edge of last bar	Makespan (completion time)
CPU utilization	Sum of bar widths / total time	Efficiency
Per-process time	Width of that process's bar	Actual CPU time used
Idle periods	Gaps between bars	CPU waiting for work
Execution order	Left-to-right bar sequence	Scheduling decisions

Extended Information (derived):

With arrival times added:

Metric	Formula from Chart
Completion Time	Right edge of process bar	CT
Turnaround Time	CT - Arrival Time	TAT
Waiting Time	Left edge - Arrival Time (for FCFS)	WT
Response Time	First bar start - Arrival Time	RT

FCFS Simplification

For non-preemptive FCFS, each process has exactly one contiguous bar—it starts, runs to completion, and never returns. This simplifies Gantt chart construction considerably. Preemptive algorithms like Round Robin produce multiple bars per process, showing the interleaving.

Constructing FCFS Gantt Charts

Constructing a Gantt chart for FCFS scheduling follows a systematic algorithm that mirrors the scheduler's operation.

Step-by-Step Construction Algorithm:

Input: List of processes with (PID, Arrival Time, Burst Time)
Output: Gantt chart with (Process, Start Time, End Time)

1. Sort processes by Arrival Time (FCFS order)
2. Set current_time = 0
3. For each process P in arrival order:
   a. If current_time < P.arrival_time:
      - Mark idle period: [current_time, P.arrival_time]
      - current_time = P.arrival_time
   b. P.start_time = current_time
   c. P.end_time = current_time + P.burst_time
   d. Draw bar for P from P.start_time to P.end_time
   e. current_time = P.end_time
4. Chart is complete

Key Rule: Each process starts at max(current_time, arrival_time)—either immediately after the previous process, or at its own arrival time (whichever is later).

Detailed Example:

Given processes:

Process Specification
Process	Arrival Time	Burst Time
P1	0	8
P2	1	4
P3	2	9
P4	3	5

Construction Trace:

Step 1: Sort by arrival → [P1, P2, P3, P4] (already sorted)
Step 2: current_time = 0

Step 3a: Process P1
  - current_time(0) >= P1.arrival(0) ✓ (no idle)
  - P1.start = 0
  - P1.end = 0 + 8 = 8
  - Draw: [P1: 0-8]
  - current_time = 8

Step 3b: Process P2
  - current_time(8) >= P2.arrival(1) ✓ (no idle)
  - P2.start = 8
  - P2.end = 8 + 4 = 12
  - Draw: [P2: 8-12]
  - current_time = 12

Step 3c: Process P3
  - current_time(12) >= P3.arrival(2) ✓ (no idle)
  - P3.start = 12
  - P3.end = 12 + 9 = 21
  - Draw: [P3: 12-21]
  - current_time = 21

Step 3d: Process P4
  - current_time(21) >= P4.arrival(3) ✓ (no idle)
  - P4.start = 21
  - P4.end = 21 + 5 = 26
  - Draw: [P4: 21-26]
  - current_time = 26

Resulting Gantt Chart:

Time:    0         8         12        21        26
         |         |         |         |         |
         |---------|---------|---------|---------|------|
         [   P1    ][   P2   ][    P3   ][   P4   ]
         └─────────┴─────────┴─────────┴─────────┘
              8         4          9         5

gantt_chart_generator.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
"""FCFS Gantt Chart Generator with Metrics"""
 
from dataclasses import dataclass
from typing import List
 
@dataclass
class Process:
    pid: str
    arrival_time: int
    burst_time: int
    # Computed fields
    start_time: int = 0
    completion_time: int = 0
    turnaround_time: int = 0
    waiting_time: int = 0
    response_time: int = 0
 
@dataclass
class GanttBar:
    pid: str        # Process ID or "IDLE"
    start: int
    end: int
 
def fcfs_schedule(processes: List[Process]) -> List[GanttBar]:
    """
    Generate FCFS Gantt chart from process list.
    Returns list of GanttBar objects representing the timeline.
    """
    # Sort by arrival time (FCFS order)
    sorted_procs = sorted(processes, key=lambda p: p.arrival_time)
    
    gantt = []
    current_time = 0
    
    for proc in sorted_procs:
        # Check for idle period
        if current_time < proc.arrival_time:
            gantt.append(GanttBar("IDLE", current_time, proc.arrival_time))
            current_time = proc.arrival_time
        
        # Schedule process
        proc.start_time = current_time
        proc.completion_time = current_time + proc.burst_time
        
        gantt.append(GanttBar(proc.pid, proc.start_time, proc.completion_time))
        
        # Compute metrics
        proc.turnaround_time = proc.completion_time - proc.arrival_time
        proc.waiting_time = proc.turnaround_time - proc.burst_time
        proc.response_time = proc.start_time - proc.arrival_time
        
        current_time = proc.completion_time
    
    return gantt
 
def print_gantt_chart(gantt: List[GanttBar]) -> None:
    """Print ASCII representation of Gantt chart."""
    # Print time markers
    print("
Gantt Chart:")
    print("=" * 60)
    
    # Print bars
    for bar in gantt:
        width = bar.end - bar.start
        label = f"[{bar.pid}]".center(width * 2)
        print(f"t={bar.start:3} {label} t={bar.end}")
    
    print("=" * 60)
 
def print_metrics(processes: List[Process]) -> None:
    """Print scheduling metrics from analyzed processes."""
    print("
Scheduling Metrics:")
    print("-" * 70)
    print(f"{'PID':^5} {'AT':^5} {'BT':^5} {'ST':^5} {'CT':^5} {'TAT':^5} {'WT':^5} {'RT':^5}")
    print("-" * 70)
    
    for p in sorted(processes, key=lambda x: x.arrival_time):
        print(f"{p.pid:^5} {p.arrival_time:^5} {p.burst_time:^5} "
              f"{p.start_time:^5} {p.completion_time:^5} "
              f"{p.turnaround_time:^5} {p.waiting_time:^5} {p.response_time:^5}")
    
    # Averages
    n = len(processes)
    avg_tat = sum(p.turnaround_time for p in processes) / n
    avg_wt = sum(p.waiting_time for p in processes) / n
    avg_rt = sum(p.response_time for p in processes) / n
    
    print("-" * 70)
    print(f"{'AVG':^5} {'-':^5} {'-':^5} {'-':^5} {'-':^5} "
          f"{avg_tat:^5.1f} {avg_wt:^5.1f} {avg_rt:^5.1f}")
 
# Example usage
if __name__ == "__main__":
    processes = [
        Process("P1", arrival_time=0, burst_time=8),
        Process("P2", arrival_time=1, burst_time=4),
        Process("P3", arrival_time=2, burst_time=9),
        Process("P4", arrival_time=3, burst_time=5),
    ]
    
    gantt = fcfs_schedule(processes)
    print_gantt_chart(gantt)
    print_metrics(processes)

Extracting Metrics from Gantt Charts

A Gantt chart contains all the information needed to calculate standard scheduling performance metrics. Understanding how to extract each metric is essential.

Standard Metrics Definitions:

Completion Time (CT): When a process finishes execution

CT[P] = Right edge of P's bar

Turnaround Time (TAT): Total time from arrival to completion

TAT[P] = CT[P] - Arrival_Time[P]

Waiting Time (WT): Time spent in ready queue (not running)

WT[P] = TAT[P] - Burst_Time[P]
       = Start_Time[P] - Arrival_Time[P]  (for non-preemptive)

Response Time (RT): Time from arrival to first execution

RT[P] = Start_Time[P] - Arrival_Time[P]
       = WT[P]  (for non-preemptive FCFS)

For preemptive algorithms, RT ≠ WT because processes may run, be preempted, and wait again.

CPU Utilization:

Utilization = Total_Burst_Time / Makespan × 100%
            = Σ(Burst_Times) / CT[last_process]

Throughput:

Throughput = Number_of_Processes / Makespan
           = n / CT[last_process]

Worked Example:

From our previous Gantt chart:

Time:    0         8         12        21        26
         [   P1    ][   P2   ][    P3   ][   P4   ]

Metric Calculation
Process	AT	BT	ST	CT	TAT = CT - AT	WT = TAT - BT
P1	0	8	0	8	8 - 0 = 8	8 - 8 = 0
P2	1	4	8	12	12 - 1 = 11	11 - 4 = 7
P3	2	9	12	21	21 - 2 = 19	19 - 9 = 10
P4	3	5	21	26	26 - 3 = 23	23 - 5 = 18

Aggregate Metrics:

Average TAT = (8 + 11 + 19 + 23) / 4 = 61 / 4 = 15.25 ms

Average WT = (0 + 7 + 10 + 18) / 4 = 35 / 4 = 8.75 ms

Total Burst Time = 8 + 4 + 9 + 5 = 26 ms
Makespan = 26 ms
CPU Utilization = 26 / 26 = 100%

Throughput = 4 processes / 26 ms = 0.154 processes/ms
           = 154 processes/second

100% CPU utilization in this example because all processes arrived before the previous one completed—no idle gaps.

Idle Time Handling

When there are gaps (idle periods) in the Gantt chart, CPU utilization drops below 100%. The idle time must be excluded from burst time sum but included in makespan. For example, if makespan is 30ms but processes only ran for 24ms, utilization is 24/30 = 80%.

Advanced Gantt Analysis Techniques

Beyond basic metric extraction, Gantt charts enable deeper analysis of scheduling behavior and performance characteristics.

1. Wait Time Visualization:

Annotate the chart with arrival times and waiting periods:

Arrivals:    P1  P2 P3 P4
             ↓   ↓  ↓  ↓
Time:    0   1   2  3         8         12        21        26
         |   |   |  |         |         |         |         |
         |   |   |  |         |         |         |         |
         [       P1          ][   P2   ][    P3   ][   P4   ]
         
Wait:    P1:····(0)····→     runs
              P2:(1)······(7ms)······→  runs
                 P3:(2)·········(10ms)······→  runs
                    P4:(3)···············(18ms)········→  runs

The dotted lines show wait time before each process runs—making the convoy effect visually obvious as wait times grow.

2. Queue State Timeline:

Draw the ready queue contents alongside the CPU timeline:

Time:      0     1     2     3     8    12    21    26
           |     |     |     |     |     |     |     |
CPU:       [           P1          ][P2 ][  P3 ][P4 ]
           
Queue:     []   [P2] [P2   [P2   [P3   [P4]   []    []
                      P3]   P3    P4]
                            P4]

This reveals queue growth during long bursts—the visualization of convoy formation.

3. Comparative Overlay:

Compare FCFS against optimal (SJF) using parallel timelines:

FCFS:      [           P1          ][P2 ][  P3 ][P4 ]
                                                         ^26

SJF:       [P2 ][P4  ][           P1          ][  P3 ]
 (optimal)                                              ^26

Wait times:
           FCFS    SJF     Difference
P1:        0       13      +13 (worse under SJF)
P2:        7       0       -7  (better under SJF)
P3:        10      15      +5  (worse under SJF)
P4:        18      4       -14 (better under SJF)

Avg WT:    8.75    8.0     -0.75 (SJF slightly better overall)

Note: In this particular example, the workloads have similar burst times, so FCFS performs relatively well. With more heterogeneous bursts, SJF's advantage grows dramatically.

4. Distribution Analysis:

Histogram metrics from the Gantt chart:

Waiting Time Distribution:

  0-5:  █ P1
  6-10: ██ P2, P3
 11-15: 
 16-20: █ P4

→ High variance (0-18), indicates convoy effect
→ Later-arriving processes disproportionately affected

A healthy scheduling algorithm shows tight waiting time distribution; FCFS under convoy conditions shows high variance with later processes penalized.

Pattern Recognition

With practice, you'll learn to recognize patterns instantly: a long bar early → convoy likely; bars roughly equal → uniform workload; many short bars → I/O-bound processes; gaps between bars → arrival-limited system.

Complex Scheduling Scenarios

Let's work through complex scenarios that demonstrate FCFS's behavior under challenging conditions, using Gantt charts to visualize and analyze.

Scenario 1: Idle Periods

Processes with gaps in arrival times:

Sparse Arrival Workload
Process	Arrival Time	Burst Time
P1	0	5
P2	10	3
P3	12	7

Construction:

t=0:  P1 arrives, starts immediately
t=5:  P1 completes. P2 not arrived yet → CPU IDLE
t=10: P2 arrives, starts immediately
t=12: P3 arrives, joins queue behind P2
t=13: P2 completes, P3 starts
t=20: P3 completes

Gantt Chart:

Time:    0    5         10   13        20
         |    |          |    |         |
         [P1 ][  IDLE    ][P2][   P3   ]

Metrics:

P1: CT=5,  TAT=5,  WT=0
P2: CT=13, TAT=3,  WT=0
P3: CT=20, TAT=8,  WT=1

CPU Utilization = (5+3+7) / 20 = 15/20 = 75%

The 5-second idle period reduces utilization—not FCFS's fault,
but a characteristic of the arrival pattern.

Scenario 2: Severe Convoy Effect

One CPU-bound process among I/O-bound processes:

Convoy-Prone Workload
Process	Arrival Time	Burst Time	Type
P1	0	100	CPU-bound
P2	5	2	I/O-bound
P3	8	3	I/O-bound
P4	10	2	I/O-bound
P5	15	1	I/O-bound

Gantt Chart:

Time:    0                                   100   102  105  107 108
         |                                    |     |    |    |   |
         [              P1 (100ms)           ][P2][P3 ][P4][P5]
                                              
Arrivals: P2↓   P3↓  P4↓    P5↓
          5     8    10     15

Metrics:

Convoy Effect Metrics
Process	AT	BT	CT	TAT	WT	WT/BT Ratio
P1	0	100	100	100	0	0.0
P2	5	2	102	97	95	47.5
P3	8	3	105	97	94	31.3
P4	10	2	107	97	95	47.5
P5	15	1	108	93	92	92.0

Extreme Wait Ratios

P5 waited 92ms for a 1ms job—a 92:1 wait-to-work ratio! The Gantt chart makes this brutally visible: four tiny bars squeezed after one massive bar. If these were web requests, users P2-P5 would experience unacceptable latency while P1's batch job runs.

What SJF Would Show:

Time:    0  1  3  5  7 8                                   108
         |  |  |  |  | |                                    |
         [P5][P2][P4][P3][             P1 (100ms)          ]

P5: WT=0  (arrived t=15? No—SJF can't run before arrival)

Correction: SJF with arrivals:

Time:    0     5  7  10 12 15 16                           116
         |     |  |   |  |  |  |                            |
         [P1 runs until P2 arrives, OR...
         
Actually: Non-preemptive SJF still runs P1 first since it arrives first!
          P1: 0-100, then SJF picks shortest among {P2,P3,P4,P5}
          P5: 100-101, P2: 101-103, P4: 103-105, P3: 105-108
          
SRTF (preemptive SJF):
          P1: 0-5 (interrupted), P2: 5-7, P1: 7-8 (interrupted)...
          More complex interleaving.

The Gantt chart comparison reveals that non-preemptive SJF doesn't help if the long job arrives first—only preemption breaks the convoy.

Common Patterns and Interpretations

Experienced systems engineers recognize Gantt chart patterns that immediately reveal scheduling characteristics. Let's catalog the common patterns.

Gantt Chart Pattern Recognition
Pattern	Visual Signature	Interpretation
Uniform workload	Bars of similar width	Homogeneous processes; FCFS performs well
Convoy formation	One long bar followed by many short bars	CPU-bound process blocking I/O-bound processes
Sparse arrivals	Gaps between bars	Arrival-limited system; CPU underutilized
Burst arrivals	Many bars starting from same queue buildup	Workload spike; may indicate bottleneck
Descending widths	Bars getting progressively shorter	Favorable FCFS order (coincidentally SJF)
Ascending widths	Bars getting progressively longer	Worst-case FCFS order

Pattern 1: Healthy FCFS (Uniform Workload)

[  P1  ][  P2  ][  P3  ][  P4  ][  P5  ]
   10      10      10      10      10

All bars similar width → uniform burst times
Average WT grows linearly but proportionally
No disproportionate penalties
FCFS is acceptable choice

Pattern 2: Classic Convoy

[           P1              ][P2][P3][P4][P5]
            50                 2   2   2   2

One dominant bar followed by short bars
Short-process waiting times approach long-process burst
Convoy effect in action
FCFS is poor choice; consider preemptive algorithm

Pattern 3: Arrival-Limited

[P1][  IDLE  ][P2][  IDLE  ][P3]

Significant gaps between bars
CPU utilization low not due to scheduling but arrival pattern
FCFS is fine; problem is workload generation, not scheduling

Pattern 4: Queue Buildup and Drain

t=0: [P1]
t=5: Many processes arrive while P1 runs
     [P1........][P2][P3][P4][P5][P6][P7][P8]

Short steady-state followed by rapid sequence
Indicates the convoy forming during long burst
Many processes queued, then serviced in burst

Quick Diagnosis

When analyzing a Gantt chart, first look at bar width variance. High variance = heterogeneous workload = potential FCFS problems. Then identify the longest bar—if it's early, expect convoy effect. Finally, check for idle gaps—they indicate arrival patterns rather than scheduling issues.

Gantt Charts in Practice

Understanding how Gantt charts are used in real engineering contexts—from academic exercises to production system analysis.

Practical Applications of Gantt Analysis

•Algorithm Comparison: Construct charts for same workload under different algorithms to compare performance visually and numerically
•Simulation Validation: Verify that scheduling simulator produces expected behavior by inspecting output Gantt charts
•Performance Debugging: Generate charts from system traces to identify convoy effects, starvation, or resource underutilization
•Capacity Planning: Model proposed workloads to predict system behavior before deployment
•Teaching and Communication: Explain scheduling concepts to non-experts using visual timelines
•Exam/Interview Problems: Standard format for scheduling questions—must know construction and metric extraction

Tools for Gantt Chart Generation:

1. Manual Construction:

Best for learning and small examples
Paper/whiteboard with timeline and bars
Spreadsheet with conditional formatting

2. Simulation Tools:

Process scheduling simulators (educational)
Generate charts from defined workloads
Examples: MOSS Scheduler, OS Sim

3. Production System Analysis:

perf (Linux performance analysis)
trace-cmd / kernelshark (kernel tracing)
Custom logging + visualization scripts

4. Programming:

gantt_visualizer.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
"""Generate visual Gantt chart using matplotlib"""
 
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
from dataclasses import dataclass
from typing import List
 
@dataclass
class GanttBar:
    pid: str
    start: int
    end: int
 
def visualize_gantt(bars: List[GanttBar], title: str = "FCFS Scheduling Gantt Chart"):
    """
    Generate a visual Gantt chart using matplotlib.
    """
    # Color map for processes
    colors = plt.cm.Set3.colors
    process_colors = {}
    color_idx = 0
    
    fig, ax = plt.subplots(figsize=(12, 3))
    
    for bar in bars:
        # Assign color to process
        if bar.pid not in process_colors:
            if bar.pid == "IDLE":
                process_colors[bar.pid] = "#cccccc"
            else:
                process_colors[bar.pid] = colors[color_idx % len(colors)]
                color_idx += 1
        
        # Draw bar
        duration = bar.end - bar.start
        rect = mpatches.Rectangle(
            (bar.start, 0.3),
            duration,
            0.4,
            linewidth=1,
            edgecolor='black',
            facecolor=process_colors[bar.pid]
        )
        ax.add_patch(rect)
        
        # Label
        ax.text(
            bar.start + duration / 2,
            0.5,
            bar.pid,
            ha='center',
            va='center',
            fontsize=10,
            fontweight='bold'
        )
        
        # Time markers
        ax.axvline(x=bar.start, color='gray', linestyle=':', linewidth=0.5)
        ax.text(bar.start, 0.1, str(bar.start), ha='center', fontsize=8)
    
    # Final time marker
    if bars:
        final_time = max(bar.end for bar in bars)
        ax.axvline(x=final_time, color='gray', linestyle=':', linewidth=0.5)
        ax.text(final_time, 0.1, str(final_time), ha='center', fontsize=8)
    
    # Formatting
    ax.set_xlim(-1, final_time + 2)
    ax.set_ylim(0, 1)
    ax.set_xlabel('Time (ms)', fontsize=12)
    ax.set_ylabel('CPU', fontsize=12)
    ax.set_title(title, fontsize=14, fontweight='bold')
    ax.set_yticks([])
    ax.spines['top'].set_visible(False)
    ax.spines['right'].set_visible(False)
    ax.spines['left'].set_visible(False)
    
    plt.tight_layout()
    plt.savefig('gantt_chart.png', dpi=150, bbox_inches='tight')
    plt.show()
 
# Example
if __name__ == "__main__":
    gantt_data = [
        GanttBar("P1", 0, 8),
        GanttBar("P2", 8, 12),
        GanttBar("P3", 12, 21),
        GanttBar("P4", 21, 26),
    ]
    visualize_gantt(gantt_data)

Summary: Gantt Chart Mastery

Gantt charts are the essential visualization tool for CPU scheduling analysis. Let's consolidate the key skills and concepts:

Key Takeaways

•Structure: Gantt charts show process execution over time with bars representing CPU tenure, positions indicating timing, and gaps showing idle periods.
•Construction: For FCFS, sort by arrival time and schedule sequentially—each process starts at max(current_time, arrival_time).
•Metric Extraction: All standard metrics (CT, TAT, WT, RT, utilization, throughput) can be calculated directly from the chart.
•Advanced Analysis: Annotate with arrivals, show queue states, overlay alternatives, and analyze distributions for deeper insights.
•Pattern Recognition: Key patterns (convoy, sparse arrivals, uniform workload) are instantly visible in chart structure.
•Practical Use: Gantt charts are used for algorithm comparison, simulation validation, performance debugging, and communication.

Module Complete!

You've now completed the comprehensive study of First-Come, First-Served scheduling. You understand:

The core FCFS algorithm and its implementation
The FIFO queue data structure underlying FCFS
The convoy effect—FCFS's critical weakness
Complete advantages and limitations assessment
Gantt chart construction and analysis

This foundation prepares you for studying more sophisticated scheduling algorithms. As you learn SJF, Round Robin, Priority Scheduling, and MLFQ, you'll constantly compare back to FCFS—understanding how each algorithm addresses FCFS's limitations while potentially sacrificing some of its advantages.

Module Complete

Congratulations! You've mastered First-Come, First-Served scheduling and Gantt chart analysis. You can now construct FCFS schedules, calculate all standard metrics, identify convoy effects, and evaluate when FCFS is appropriate. These skills form the foundation for all scheduling algorithm study and system performance analysis.

Gantt Chart Analysis

Visualizing CPU Scheduling

What You Will Learn

Gantt Chart Fundamentals

A CPU scheduling Gantt chart is a horizontal bar chart showing process execution over time. Each bar represents a period during which a specific process holds the CPU.

Chart Structure:

Time:    0    5    10   15   20   25   30   35   40
         |----|----|----|----|----|----|----|----|----|
         
CPU:     [    P1    ][  P2  ][ P3 ][   P4   ]
         └──────────┴───────┴─────┴─────────┘
              12        7      4       9     (durations)

Components:

Time Axis (horizontal): Represents elapsed time from system start (t=0)
CPU Timeline: Single row showing which process is executing
Process Bars: Colored/labeled regions showing each process's CPU tenure
Boundaries: Vertical lines marking transition points (process starts/ends)
Labels: Process identifiers (P1, P2, etc.) and timing annotations

Reading the Chart:

Bar width represents execution duration (burst time used)
Bar position indicates start and end times
Gaps (unlabeled regions) represent CPU idle time
Transitions occur at marked time points

Information Encoded:

A properly constructed Gantt chart reveals:

Feature	How to Read	What It Means
Total time	Right edge of last bar	Makespan (completion time)
CPU utilization	Sum of bar widths / total time	Efficiency
Per-process time	Width of that process's bar	Actual CPU time used
Idle periods	Gaps between bars	CPU waiting for work
Execution order	Left-to-right bar sequence	Scheduling decisions

Extended Information (derived):

With arrival times added:

Metric	Formula from Chart
Completion Time	Right edge of process bar	CT
Turnaround Time	CT - Arrival Time	TAT
Waiting Time	Left edge - Arrival Time (for FCFS)	WT
Response Time	First bar start - Arrival Time	RT

FCFS Simplification

Constructing FCFS Gantt Charts

Constructing a Gantt chart for FCFS scheduling follows a systematic algorithm that mirrors the scheduler's operation.

Step-by-Step Construction Algorithm:

Input: List of processes with (PID, Arrival Time, Burst Time)
Output: Gantt chart with (Process, Start Time, End Time)

1. Sort processes by Arrival Time (FCFS order)
2. Set current_time = 0
3. For each process P in arrival order:
   a. If current_time < P.arrival_time:
      - Mark idle period: [current_time, P.arrival_time]
      - current_time = P.arrival_time
   b. P.start_time = current_time
   c. P.end_time = current_time + P.burst_time
   d. Draw bar for P from P.start_time to P.end_time
   e. current_time = P.end_time
4. Chart is complete

Key Rule: Each process starts at max(current_time, arrival_time)—either immediately after the previous process, or at its own arrival time (whichever is later).

Detailed Example:

Given processes:

Process Specification
Process	Arrival Time	Burst Time
P1	0	8
P2	1	4
P3	2	9
P4	3	5

Construction Trace:

Step 1: Sort by arrival → [P1, P2, P3, P4] (already sorted)
Step 2: current_time = 0

Step 3a: Process P1
  - current_time(0) >= P1.arrival(0) ✓ (no idle)
  - P1.start = 0
  - P1.end = 0 + 8 = 8
  - Draw: [P1: 0-8]
  - current_time = 8

Step 3b: Process P2
  - current_time(8) >= P2.arrival(1) ✓ (no idle)
  - P2.start = 8
  - P2.end = 8 + 4 = 12
  - Draw: [P2: 8-12]
  - current_time = 12

Step 3c: Process P3
  - current_time(12) >= P3.arrival(2) ✓ (no idle)
  - P3.start = 12
  - P3.end = 12 + 9 = 21
  - Draw: [P3: 12-21]
  - current_time = 21

Step 3d: Process P4
  - current_time(21) >= P4.arrival(3) ✓ (no idle)
  - P4.start = 21
  - P4.end = 21 + 5 = 26
  - Draw: [P4: 21-26]
  - current_time = 26

Resulting Gantt Chart:

Time:    0         8         12        21        26
         |         |         |         |         |
         |---------|---------|---------|---------|------|
         [   P1    ][   P2   ][    P3   ][   P4   ]
         └─────────┴─────────┴─────────┴─────────┘
              8         4          9         5

gantt_chart_generator.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
"""FCFS Gantt Chart Generator with Metrics"""
 
from dataclasses import dataclass
from typing import List
 
@dataclass
class Process:
    pid: str
    arrival_time: int
    burst_time: int
    # Computed fields
    start_time: int = 0
    completion_time: int = 0
    turnaround_time: int = 0
    waiting_time: int = 0
    response_time: int = 0
 
@dataclass
class GanttBar:
    pid: str        # Process ID or "IDLE"
    start: int
    end: int
 
def fcfs_schedule(processes: List[Process]) -> List[GanttBar]:
    """
    Generate FCFS Gantt chart from process list.
    Returns list of GanttBar objects representing the timeline.
    """
    # Sort by arrival time (FCFS order)
    sorted_procs = sorted(processes, key=lambda p: p.arrival_time)
    
    gantt = []
    current_time = 0
    
    for proc in sorted_procs:
        # Check for idle period
        if current_time < proc.arrival_time:
            gantt.append(GanttBar("IDLE", current_time, proc.arrival_time))
            current_time = proc.arrival_time
        
        # Schedule process
        proc.start_time = current_time
        proc.completion_time = current_time + proc.burst_time
        
        gantt.append(GanttBar(proc.pid, proc.start_time, proc.completion_time))
        
        # Compute metrics
        proc.turnaround_time = proc.completion_time - proc.arrival_time
        proc.waiting_time = proc.turnaround_time - proc.burst_time
        proc.response_time = proc.start_time - proc.arrival_time
        
        current_time = proc.completion_time
    
    return gantt
 
def print_gantt_chart(gantt: List[GanttBar]) -> None:
    """Print ASCII representation of Gantt chart."""
    # Print time markers
    print("
Gantt Chart:")
    print("=" * 60)
    
    # Print bars
    for bar in gantt:
        width = bar.end - bar.start
        label = f"[{bar.pid}]".center(width * 2)
        print(f"t={bar.start:3} {label} t={bar.end}")
    
    print("=" * 60)
 
def print_metrics(processes: List[Process]) -> None:
    """Print scheduling metrics from analyzed processes."""
    print("
Scheduling Metrics:")
    print("-" * 70)
    print(f"{'PID':^5} {'AT':^5} {'BT':^5} {'ST':^5} {'CT':^5} {'TAT':^5} {'WT':^5} {'RT':^5}")
    print("-" * 70)
    
    for p in sorted(processes, key=lambda x: x.arrival_time):
        print(f"{p.pid:^5} {p.arrival_time:^5} {p.burst_time:^5} "
              f"{p.start_time:^5} {p.completion_time:^5} "
              f"{p.turnaround_time:^5} {p.waiting_time:^5} {p.response_time:^5}")
    
    # Averages
    n = len(processes)
    avg_tat = sum(p.turnaround_time for p in processes) / n
    avg_wt = sum(p.waiting_time for p in processes) / n
    avg_rt = sum(p.response_time for p in processes) / n
    
    print("-" * 70)
    print(f"{'AVG':^5} {'-':^5} {'-':^5} {'-':^5} {'-':^5} "
          f"{avg_tat:^5.1f} {avg_wt:^5.1f} {avg_rt:^5.1f}")
 
# Example usage
if __name__ == "__main__":
    processes = [
        Process("P1", arrival_time=0, burst_time=8),
        Process("P2", arrival_time=1, burst_time=4),
        Process("P3", arrival_time=2, burst_time=9),
        Process("P4", arrival_time=3, burst_time=5),
    ]
    
    gantt = fcfs_schedule(processes)
    print_gantt_chart(gantt)
    print_metrics(processes)

Extracting Metrics from Gantt Charts

A Gantt chart contains all the information needed to calculate standard scheduling performance metrics. Understanding how to extract each metric is essential.

Standard Metrics Definitions:

Completion Time (CT): When a process finishes execution

CT[P] = Right edge of P's bar

Turnaround Time (TAT): Total time from arrival to completion

TAT[P] = CT[P] - Arrival_Time[P]

Waiting Time (WT): Time spent in ready queue (not running)

WT[P] = TAT[P] - Burst_Time[P]
       = Start_Time[P] - Arrival_Time[P]  (for non-preemptive)

Response Time (RT): Time from arrival to first execution

RT[P] = Start_Time[P] - Arrival_Time[P]
       = WT[P]  (for non-preemptive FCFS)

For preemptive algorithms, RT ≠ WT because processes may run, be preempted, and wait again.

CPU Utilization:

Utilization = Total_Burst_Time / Makespan × 100%
            = Σ(Burst_Times) / CT[last_process]

Throughput:

Throughput = Number_of_Processes / Makespan
           = n / CT[last_process]

Worked Example:

From our previous Gantt chart:

Time:    0         8         12        21        26
         [   P1    ][   P2   ][    P3   ][   P4   ]

Metric Calculation
Process	AT	BT	ST	CT	TAT = CT - AT	WT = TAT - BT
P1	0	8	0	8	8 - 0 = 8	8 - 8 = 0
P2	1	4	8	12	12 - 1 = 11	11 - 4 = 7
P3	2	9	12	21	21 - 2 = 19	19 - 9 = 10
P4	3	5	21	26	26 - 3 = 23	23 - 5 = 18

Aggregate Metrics:

Average TAT = (8 + 11 + 19 + 23) / 4 = 61 / 4 = 15.25 ms

Average WT = (0 + 7 + 10 + 18) / 4 = 35 / 4 = 8.75 ms

Total Burst Time = 8 + 4 + 9 + 5 = 26 ms
Makespan = 26 ms
CPU Utilization = 26 / 26 = 100%

Throughput = 4 processes / 26 ms = 0.154 processes/ms
           = 154 processes/second

100% CPU utilization in this example because all processes arrived before the previous one completed—no idle gaps.

Idle Time Handling

Advanced Gantt Analysis Techniques

Beyond basic metric extraction, Gantt charts enable deeper analysis of scheduling behavior and performance characteristics.

1. Wait Time Visualization:

Annotate the chart with arrival times and waiting periods:

Arrivals:    P1  P2 P3 P4
             ↓   ↓  ↓  ↓
Time:    0   1   2  3         8         12        21        26
         |   |   |  |         |         |         |         |
         |   |   |  |         |         |         |         |
         [       P1          ][   P2   ][    P3   ][   P4   ]
         
Wait:    P1:····(0)····→     runs
              P2:(1)······(7ms)······→  runs
                 P3:(2)·········(10ms)······→  runs
                    P4:(3)···············(18ms)········→  runs

The dotted lines show wait time before each process runs—making the convoy effect visually obvious as wait times grow.

2. Queue State Timeline:

Draw the ready queue contents alongside the CPU timeline:

Time:      0     1     2     3     8    12    21    26
           |     |     |     |     |     |     |     |
CPU:       [           P1          ][P2 ][  P3 ][P4 ]
           
Queue:     []   [P2] [P2   [P2   [P3   [P4]   []    []
                      P3]   P3    P4]
                            P4]

This reveals queue growth during long bursts—the visualization of convoy formation.

3. Comparative Overlay:

Compare FCFS against optimal (SJF) using parallel timelines:

FCFS:      [           P1          ][P2 ][  P3 ][P4 ]
                                                         ^26

SJF:       [P2 ][P4  ][           P1          ][  P3 ]
 (optimal)                                              ^26

Wait times:
           FCFS    SJF     Difference
P1:        0       13      +13 (worse under SJF)
P2:        7       0       -7  (better under SJF)
P3:        10      15      +5  (worse under SJF)
P4:        18      4       -14 (better under SJF)

Avg WT:    8.75    8.0     -0.75 (SJF slightly better overall)

Note: In this particular example, the workloads have similar burst times, so FCFS performs relatively well. With more heterogeneous bursts, SJF's advantage grows dramatically.

4. Distribution Analysis:

Histogram metrics from the Gantt chart:

Waiting Time Distribution:

  0-5:  █ P1
  6-10: ██ P2, P3
 11-15: 
 16-20: █ P4

→ High variance (0-18), indicates convoy effect
→ Later-arriving processes disproportionately affected

A healthy scheduling algorithm shows tight waiting time distribution; FCFS under convoy conditions shows high variance with later processes penalized.

Pattern Recognition

Complex Scheduling Scenarios

Let's work through complex scenarios that demonstrate FCFS's behavior under challenging conditions, using Gantt charts to visualize and analyze.

Scenario 1: Idle Periods

Processes with gaps in arrival times:

Sparse Arrival Workload
Process	Arrival Time	Burst Time
P1	0	5
P2	10	3
P3	12	7

Construction:

t=0:  P1 arrives, starts immediately
t=5:  P1 completes. P2 not arrived yet → CPU IDLE
t=10: P2 arrives, starts immediately
t=12: P3 arrives, joins queue behind P2
t=13: P2 completes, P3 starts
t=20: P3 completes

Gantt Chart:

Time:    0    5         10   13        20
         |    |          |    |         |
         [P1 ][  IDLE    ][P2][   P3   ]

Metrics:

P1: CT=5,  TAT=5,  WT=0
P2: CT=13, TAT=3,  WT=0
P3: CT=20, TAT=8,  WT=1

CPU Utilization = (5+3+7) / 20 = 15/20 = 75%

The 5-second idle period reduces utilization—not FCFS's fault,
but a characteristic of the arrival pattern.

Scenario 2: Severe Convoy Effect

One CPU-bound process among I/O-bound processes:

Convoy-Prone Workload
Process	Arrival Time	Burst Time	Type
P1	0	100	CPU-bound
P2	5	2	I/O-bound
P3	8	3	I/O-bound
P4	10	2	I/O-bound
P5	15	1	I/O-bound

Gantt Chart:

Time:    0                                   100   102  105  107 108
         |                                    |     |    |    |   |
         [              P1 (100ms)           ][P2][P3 ][P4][P5]
                                              
Arrivals: P2↓   P3↓  P4↓    P5↓
          5     8    10     15

Metrics:

Convoy Effect Metrics
Process	AT	BT	CT	TAT	WT	WT/BT Ratio
P1	0	100	100	100	0	0.0
P2	5	2	102	97	95	47.5
P3	8	3	105	97	94	31.3
P4	10	2	107	97	95	47.5
P5	15	1	108	93	92	92.0

Extreme Wait Ratios

What SJF Would Show:

Time:    0  1  3  5  7 8                                   108
         |  |  |  |  | |                                    |
         [P5][P2][P4][P3][             P1 (100ms)          ]

P5: WT=0  (arrived t=15? No—SJF can't run before arrival)

Correction: SJF with arrivals:

Time:    0     5  7  10 12 15 16                           116
         |     |  |   |  |  |  |                            |
         [P1 runs until P2 arrives, OR...
         
Actually: Non-preemptive SJF still runs P1 first since it arrives first!
          P1: 0-100, then SJF picks shortest among {P2,P3,P4,P5}
          P5: 100-101, P2: 101-103, P4: 103-105, P3: 105-108
          
SRTF (preemptive SJF):
          P1: 0-5 (interrupted), P2: 5-7, P1: 7-8 (interrupted)...
          More complex interleaving.

The Gantt chart comparison reveals that non-preemptive SJF doesn't help if the long job arrives first—only preemption breaks the convoy.

Common Patterns and Interpretations

Experienced systems engineers recognize Gantt chart patterns that immediately reveal scheduling characteristics. Let's catalog the common patterns.

Gantt Chart Pattern Recognition
Pattern	Visual Signature	Interpretation
Uniform workload	Bars of similar width	Homogeneous processes; FCFS performs well
Convoy formation	One long bar followed by many short bars	CPU-bound process blocking I/O-bound processes
Sparse arrivals	Gaps between bars	Arrival-limited system; CPU underutilized
Burst arrivals	Many bars starting from same queue buildup	Workload spike; may indicate bottleneck
Descending widths	Bars getting progressively shorter	Favorable FCFS order (coincidentally SJF)
Ascending widths	Bars getting progressively longer	Worst-case FCFS order

Pattern 1: Healthy FCFS (Uniform Workload)

[  P1  ][  P2  ][  P3  ][  P4  ][  P5  ]
   10      10      10      10      10

All bars similar width → uniform burst times
Average WT grows linearly but proportionally
No disproportionate penalties
FCFS is acceptable choice

Pattern 2: Classic Convoy

[           P1              ][P2][P3][P4][P5]
            50                 2   2   2   2

One dominant bar followed by short bars
Short-process waiting times approach long-process burst
Convoy effect in action
FCFS is poor choice; consider preemptive algorithm

Pattern 3: Arrival-Limited

[P1][  IDLE  ][P2][  IDLE  ][P3]

Significant gaps between bars
CPU utilization low not due to scheduling but arrival pattern
FCFS is fine; problem is workload generation, not scheduling

Pattern 4: Queue Buildup and Drain

t=0: [P1]
t=5: Many processes arrive while P1 runs
     [P1........][P2][P3][P4][P5][P6][P7][P8]

Short steady-state followed by rapid sequence
Indicates the convoy forming during long burst
Many processes queued, then serviced in burst

Quick Diagnosis

Gantt Charts in Practice

Understanding how Gantt charts are used in real engineering contexts—from academic exercises to production system analysis.

Practical Applications of Gantt Analysis

•Algorithm Comparison: Construct charts for same workload under different algorithms to compare performance visually and numerically
•Simulation Validation: Verify that scheduling simulator produces expected behavior by inspecting output Gantt charts
•Performance Debugging: Generate charts from system traces to identify convoy effects, starvation, or resource underutilization
•Capacity Planning: Model proposed workloads to predict system behavior before deployment
•Teaching and Communication: Explain scheduling concepts to non-experts using visual timelines
•Exam/Interview Problems: Standard format for scheduling questions—must know construction and metric extraction

Tools for Gantt Chart Generation:

1. Manual Construction:

Best for learning and small examples
Paper/whiteboard with timeline and bars
Spreadsheet with conditional formatting

2. Simulation Tools:

Process scheduling simulators (educational)
Generate charts from defined workloads
Examples: MOSS Scheduler, OS Sim

3. Production System Analysis:

perf (Linux performance analysis)
trace-cmd / kernelshark (kernel tracing)
Custom logging + visualization scripts

4. Programming:

gantt_visualizer.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
"""Generate visual Gantt chart using matplotlib"""
 
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
from dataclasses import dataclass
from typing import List
 
@dataclass
class GanttBar:
    pid: str
    start: int
    end: int
 
def visualize_gantt(bars: List[GanttBar], title: str = "FCFS Scheduling Gantt Chart"):
    """
    Generate a visual Gantt chart using matplotlib.
    """
    # Color map for processes
    colors = plt.cm.Set3.colors
    process_colors = {}
    color_idx = 0
    
    fig, ax = plt.subplots(figsize=(12, 3))
    
    for bar in bars:
        # Assign color to process
        if bar.pid not in process_colors:
            if bar.pid == "IDLE":
                process_colors[bar.pid] = "#cccccc"
            else:
                process_colors[bar.pid] = colors[color_idx % len(colors)]
                color_idx += 1
        
        # Draw bar
        duration = bar.end - bar.start
        rect = mpatches.Rectangle(
            (bar.start, 0.3),
            duration,
            0.4,
            linewidth=1,
            edgecolor='black',
            facecolor=process_colors[bar.pid]
        )
        ax.add_patch(rect)
        
        # Label
        ax.text(
            bar.start + duration / 2,
            0.5,
            bar.pid,
            ha='center',
            va='center',
            fontsize=10,
            fontweight='bold'
        )
        
        # Time markers
        ax.axvline(x=bar.start, color='gray', linestyle=':', linewidth=0.5)
        ax.text(bar.start, 0.1, str(bar.start), ha='center', fontsize=8)
    
    # Final time marker
    if bars:
        final_time = max(bar.end for bar in bars)
        ax.axvline(x=final_time, color='gray', linestyle=':', linewidth=0.5)
        ax.text(final_time, 0.1, str(final_time), ha='center', fontsize=8)
    
    # Formatting
    ax.set_xlim(-1, final_time + 2)
    ax.set_ylim(0, 1)
    ax.set_xlabel('Time (ms)', fontsize=12)
    ax.set_ylabel('CPU', fontsize=12)
    ax.set_title(title, fontsize=14, fontweight='bold')
    ax.set_yticks([])
    ax.spines['top'].set_visible(False)
    ax.spines['right'].set_visible(False)
    ax.spines['left'].set_visible(False)
    
    plt.tight_layout()
    plt.savefig('gantt_chart.png', dpi=150, bbox_inches='tight')
    plt.show()
 
# Example
if __name__ == "__main__":
    gantt_data = [
        GanttBar("P1", 0, 8),
        GanttBar("P2", 8, 12),
        GanttBar("P3", 12, 21),
        GanttBar("P4", 21, 26),
    ]
    visualize_gantt(gantt_data)

Summary: Gantt Chart Mastery

Gantt charts are the essential visualization tool for CPU scheduling analysis. Let's consolidate the key skills and concepts:

Key Takeaways

•Structure: Gantt charts show process execution over time with bars representing CPU tenure, positions indicating timing, and gaps showing idle periods.
•Construction: For FCFS, sort by arrival time and schedule sequentially—each process starts at max(current_time, arrival_time).
•Metric Extraction: All standard metrics (CT, TAT, WT, RT, utilization, throughput) can be calculated directly from the chart.
•Advanced Analysis: Annotate with arrivals, show queue states, overlay alternatives, and analyze distributions for deeper insights.
•Pattern Recognition: Key patterns (convoy, sparse arrivals, uniform workload) are instantly visible in chart structure.
•Practical Use: Gantt charts are used for algorithm comparison, simulation validation, performance debugging, and communication.

Module Complete!

You've now completed the comprehensive study of First-Come, First-Served scheduling. You understand:

The core FCFS algorithm and its implementation
The FIFO queue data structure underlying FCFS
The convoy effect—FCFS's critical weakness
Complete advantages and limitations assessment
Gantt chart construction and analysis

Module Complete