CPU Burst and I/O Burst - Scheduling Concepts | OneNoughtOne

Operating SystemsCPU Scheduling

Scheduling Concepts

LevelIntermediate

Duration60 mins

TopicCPU Scheduling

1 / 5

CPU Burst and I/O Burst

The Rhythm of Process Execution

Every process running on your computer follows an intricate dance—a rhythmic alternation between two fundamentally different activities: computing and waiting. This pattern is so universal, so deeply embedded in the nature of computing, that understanding it unlocks your comprehension of why CPU scheduling exists at all.

When you open a text editor and type a document, the process handling your keystrokes isn't continuously using the CPU. It spends most of its time waiting—waiting for you to press the next key, waiting for the disk to load a file, waiting for the operating system to acknowledge a screen update. Between these waiting periods, it performs brief, intense bursts of computation.

This fundamental pattern—CPU bursts alternating with I/O bursts—is the heartbeat of process execution and the foundation upon which all CPU scheduling decisions are made.

What You Will Learn

By the end of this page, you will understand: (1) What CPU bursts and I/O bursts are and why they matter, (2) The statistical distribution of burst durations, (3) How burst patterns influence scheduling algorithm design, (4) How to analyze the burst characteristics of real processes, and (5) Why this model is foundational to all scheduling theory.

Defining CPU Bursts

A CPU burst is a contiguous period during which a process is actively executing instructions on the processor without requesting any I/O operations or other blocking system calls. During a CPU burst, the process is in the running state, consuming CPU cycles to perform computations.

The mechanics of a CPU burst:

When a process receives the CPU, it begins executing its instruction stream. Each instruction—whether it's an arithmetic operation, a memory access, a conditional branch, or a function call—consumes one or more CPU cycles. The process continues executing until one of several events occurs:

I/O Request: The process needs data from a file, network, or device
Synchronization Wait: The process must wait for a lock, semaphore, or condition variable
Voluntary Yield: The process explicitly relinquishes the CPU
Preemption: The operating system forcibly removes the process (in preemptive systems)
Termination: The process completes its execution

The period from when the process starts executing until any of these events is the CPU burst.

cpu_burst_example.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Example: A function demonstrating CPU-intensive computation
// This entire loop represents a single, long CPU burst
 
void compute_matrix_multiply(double **A, double **B, double **C, int n) {
    // CPU Burst begins when this function starts executing
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            double sum = 0.0;
            for (int k = 0; k < n; k++) {
                // Pure arithmetic operations - no I/O, no waiting
                sum += A[i][k] * B[k][j];
            }
            C[i][j] = sum;
        }
    }
    
    // CPU Burst ends only when:
    // - Function returns and caller performs I/O
    // - Timer interrupt preempts the process
    // - Process terminates
}

Memory Access and CPU Bursts

Memory accesses are part of CPU bursts, even though they might cause cache misses or page faults. A cache miss stalls the CPU briefly but doesn't terminate the burst. However, a page fault that requires disk I/O does terminate the CPU burst because the process must wait for I/O to complete.

Granularity of CPU bursts:

CPU bursts vary enormously in duration:

Microsecond bursts: Character I/O processing, interrupt handlers
Millisecond bursts: Typical interactive application processing
Second-scale bursts: Scientific computations, video encoding
Minute-scale bursts: Long-running simulations, training ML models

The scheduler must handle this entire range efficiently. A scheduling algorithm optimized for microsecond bursts might perform poorly with second-scale bursts, and vice versa.

Defining I/O Bursts

An I/O burst is the period during which a process waits for an input/output operation to complete. During an I/O burst, the process is in the waiting (blocked) state and cannot use the CPU, regardless of whether the CPU is available.

The anatomy of an I/O burst:

I/O bursts begin when a process makes a request that cannot be satisfied immediately and must wait for external events:

Disk I/O: Reading from or writing to files, databases, or virtual memory
Network I/O: Sending or receiving data over network connections
User Input: Waiting for keyboard, mouse, or touch events
Device Communication: Interacting with peripherals (printers, sensors, GPUs)
Inter-process Communication: Waiting for messages from other processes

io_burst_example.c
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
// Example: A sequence showing alternating CPU and I/O bursts
 
void process_log_file(const char *filename) {
    // ====== CPU BURST 1 ======
    // Preparing the file open request
    int fd = open(filename, O_RDONLY);
    
    // ====== I/O BURST 1 ======
    // Process BLOCKS here waiting for:
    // - File system to locate the inode
    // - Disk to read directory entries
    // - Permission checks to complete
    // When open() returns, I/O burst ends
    
    char buffer[4096];
    ssize_t bytes_read;
    
    while (1) {
        // ====== I/O BURST (repeated) ======
        bytes_read = read(fd, buffer, sizeof(buffer));
        // Process is BLOCKED during disk read
        // CPU is free to run other processes
        
        if (bytes_read <= 0) break;
        
        // ====== CPU BURST (repeated) ======
        // Parse and process the data
        // This is pure computation - no waiting
        for (int i = 0; i < bytes_read; i++) {
            process_character(buffer[i]);
        }
        // CPU burst ends when loop restarts and read() is called
    }
    
    // ====== I/O BURST (final) ======
    close(fd);  // May block to flush buffers to disk
}

I/O Latency Orders of Magnitude

Understanding I/O latency helps appreciate why I/O bursts dominate many workloads:

• L1 Cache: ~1 nanosecond • L3 Cache: ~10 nanoseconds • RAM: ~100 nanoseconds • SSD: ~100 microseconds (100,000 ns) • HDD: ~10 milliseconds (10,000,000 ns) • Network (LAN): ~1-10 milliseconds • Network (Internet): ~10-200 milliseconds

During a 10ms disk access, a 3 GHz CPU could have executed 30 million instructions. This is why I/O waits are so expensive and why the OS schedules other processes during I/O bursts.

I/O burst characteristics:

Unlike CPU bursts, which are under the control of the application's logic, I/O burst durations depend on:

Device speed: SSDs vs. HDDs vs. network vs. tape
Device contention: How many other processes are competing for the same device
Queue depth: How many pending requests are ahead in the device queue
Data location: Sequential vs. random access patterns
Network conditions: Latency, bandwidth, congestion

This unpredictability makes I/O burst durations much harder to predict than CPU bursts, which has significant implications for scheduling algorithms that attempt to estimate burst times.

The CPU-I/O Burst Cycle

Process execution follows a predictable structural pattern: an alternating sequence of CPU and I/O bursts that continues until the process terminates. This pattern, known as the CPU-I/O burst cycle, is fundamental to how operating systems manage processor resources.

The canonical execution model:

Process Start
    │
    ▼
┌─────────────┐     ┌───────────┐     ┌─────────────┐
│  CPU Burst  │ ──▶ │ I/O Burst │ ──▶ │  CPU Burst  │ ──▶ ...
│  (Running)  │     │ (Waiting) │     │  (Running)  │
└─────────────┘     └───────────┘     └─────────────┘
                                              │
                                              ▼
                                         (Eventually)
                                      ┌──────────────┐
                                      │  Termination │
                                      │  (CPU Burst) │
                                      └──────────────┘

Key observations about the cycle:

Every process begins with a CPU burst: Even if the first action is an I/O request, the code to make that request must execute first.
Every process ends with a CPU burst: The final CPU burst executes the termination code (exit system call).
The pattern is strictly alternating: A CPU burst is always followed by either an I/O burst or termination; an I/O burst is always followed by a CPU burst.
No overlap within a single process: A process cannot be in CPU burst and I/O burst simultaneously (though multiple processes can be).

Converting Mermaid diagram...

Why this model matters for scheduling:

The CPU-I/O burst cycle has profound implications:

Multiprogramming opportunity: During I/O bursts, the CPU is idle for that process. Other processes can use it.
Scheduling decision points: Every I/O burst is a scheduling opportunity—the OS must decide which ready process runs next.
Efficiency metric: The fraction of time spent in CPU bursts vs. I/O bursts determines how efficiently a workload uses the processor.
Process classification: Processes can be characterized by their burst patterns (CPU-bound vs. I/O-bound), informing scheduling decisions.

The Multiprogramming Imperative

If we ran processes one at a time to completion, the CPU would be idle during all I/O bursts. For I/O-bound workloads, this could mean 90%+ CPU idle time. Multiprogramming—keeping multiple processes ready to run—ensures that when one process waits for I/O, another can use the CPU. This is the fundamental motivation for sophisticated CPU scheduling.

CPU Burst Duration Distribution

One of the most important empirical observations in operating systems research is the distribution of CPU burst durations. Understanding this distribution is crucial because many scheduling algorithms make decisions based on predicted burst lengths.

The empirical finding:

Decades of measurements across diverse workloads have consistently shown that CPU burst durations follow a characteristic distribution:

Many short bursts: The majority of CPU bursts are very short (microseconds to a few milliseconds)
Few long bursts: A small fraction of bursts are much longer (seconds or more)
Exponential-like decay: The frequency of bursts decreases roughly exponentially as duration increases

This distribution is often modeled as an exponential distribution or hyperexponential distribution, though real workloads show variations.

Typical CPU Burst Duration Distribution (Interactive Workload)
Burst Duration	Approximate Frequency	Cumulative Percentage
< 1 ms	~40%	40%
1-10 ms	~30%	70%
10-100 ms	~20%	90%
100 ms - 1 s	~8%	98%
1 second	~2%	100%

Why this distribution exists:

The prevalence of short bursts isn't random—it reflects fundamental patterns in software:

Event-driven programming: Interactive applications respond to events (keystrokes, clicks, messages) with brief processing bursts followed by waits for the next event.
Layered I/O: Even "compute-intensive" programs frequently access data, hitting disk or network for each data item.
Operating system design: Frequent interrupts (timer, I/O completion) fragment what might otherwise be longer bursts.
Memory hierarchy: Cache misses and page faults convert long computations into series of short bursts separated by waits.

Implications for scheduling algorithm design:

How Burst Distribution Shapes Scheduling

•Favor short jobs (SJF): Since most bursts are short, algorithms that run short bursts first can significantly reduce average waiting time.
•Time slicing works well: Short time quantum values (e.g., 10-100 ms) will complete most bursts without preemption, minimizing context switch overhead.
•Prediction is feasible: The regularity of burst patterns makes exponential averaging and other prediction techniques reasonably effective.
•Long bursts are outliers: The rare long bursts need special handling to prevent starvation while not degrading overall system performance.

The 10ms Rule of Thumb

A common heuristic: most interactive processes have CPU bursts under 10 milliseconds. This insight drove the design of time-sharing systems with quantum values around 10-100ms—long enough to complete typical bursts without preemption, short enough to maintain responsive feel.

Measuring and Predicting Bursts

Several scheduling algorithms (notably Shortest Job First and its variants) require knowledge of future CPU burst durations. Since we cannot know the future, we must predict burst lengths based on past behavior. This prediction challenge is central to scheduling algorithm design.

The prediction problem:

At the moment a process becomes ready to run, the scheduler must decide:

How long will this process's next CPU burst be?
Should we run it now, or is there a shorter job waiting?

We cannot query the process—it doesn't know either. We must infer from history.

Exponential averaging (Exponential Moving Average):

The most widely used prediction technique is exponential averaging, which weights recent history more heavily than distant past:

burst_prediction.c
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
// Exponential Averaging for CPU Burst Prediction
// τ(n+1) = α × t(n) + (1 - α) × τ(n)
//
// Where:
//   τ(n+1) = predicted length of next burst
//   t(n)   = actual length of the most recent burst
//   τ(n)   = previous prediction
//   α      = smoothing factor (0 < α < 1)
 
typedef struct {
    double predicted_burst;    // τ: current prediction
    double alpha;              // α: smoothing factor (typically 0.5)
} BurstPredictor;
 
void initialize_predictor(BurstPredictor *p, double initial_estimate, double alpha) {
    p->predicted_burst = initial_estimate;  // τ(0): initial guess
    p->alpha = alpha;
}
 
double predict_next_burst(BurstPredictor *p) {
    return p->predicted_burst;
}
 
void update_with_actual(BurstPredictor *p, double actual_burst) {
    // τ(n+1) = α × t(n) + (1 - α) × τ(n)
    p->predicted_burst = p->alpha * actual_burst + 
                         (1 - p->alpha) * p->predicted_burst;
}
 
// Example usage in scheduler:
// 
// Process P arrives, we predict its burst:
//   estimated_time = predict_next_burst(&P->predictor);
//
// After P completes its CPU burst:
//   update_with_actual(&P->predictor, measured_burst_duration);

Understanding the α parameter:

The smoothing factor α controls how quickly the prediction responds to changes:

α Value	Behavior	Best For
α = 0.0	Prediction never changes (uses only initial estimate)	N/A (degenerate)
α = 0.1	Very slow adaptation, heavily weights history	Stable workloads
α = 0.5	Balanced weighting of recent vs. historical	General purpose
α = 0.9	Rapid adaptation, recent bursts dominate	Volatile workloads
α = 1.0	Prediction equals last burst exactly	Highly variable processes

Example calculation:

Consider a process with burst history: 10ms, 8ms, 12ms, 5ms (most recent)

With α = 0.5 and initial estimate τ₀ = 10:

After 10ms burst: τ₁ = 0.5×10 + 0.5×10 = 10.0
After 8ms burst: τ₂ = 0.5×8 + 0.5×10 = 9.0
After 12ms burst: τ₃ = 0.5×12 + 0.5×9 = 10.5
After 5ms burst: τ₄ = 0.5×5 + 0.5×10.5 = 7.75

Next burst prediction: 7.75ms

Expanding the Exponential Average Formula

The formula τ(n+1) = α×t(n) + (1-α)×τ(n) can be expanded to show that each historical burst contributes with exponentially decreasing weight:

τ(n+1) = α×t(n) + α(1-α)×t(n-1) + α(1-α)²×t(n-2) + ... + (1-α)ⁿ×τ(0)

With α = 0.5: weights are 0.5, 0.25, 0.125, 0.0625... — recent history dominates but old behavior still influences predictions.

Burst Patterns in Real Systems

Different types of applications exhibit characteristic burst patterns. Understanding these patterns helps in workload characterization, capacity planning, and scheduler tuning.

Typical burst patterns by application type:

Burst Characteristics by Application Type
Application Type	CPU Burst Pattern	I/O Burst Pattern	Ratio
Text Editor	Very short (< 1ms), sporadic	Long waits for input	1:1000+ I/O dominated
Web Browser	Short bursts, event-driven	Network waits, render bursts	1:10 to 1:1 mixed
Compiler	Medium bursts, phases	File reads between phases	10:1 CPU dominated
Database Server	Short query processing	Disk I/O for data	1:5 I/O dominated
Video Encoder	Long, steady bursts	Minimal I/O (buffered)	100:1 CPU dominated
Scientific Simulation	Very long bursts	Checkpoint I/O only	1000:1 CPU dominated

Observing bursts with system tools:

Modern operating systems provide tools to observe burst behavior. On Linux, tools like perf, ftrace, and eBPF can capture scheduling events. Here's a conceptual analysis approach:

analyze_bursts.sh
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
#!/bin/bash
# Conceptual script to analyze CPU burst patterns using perf
 
# Record scheduler events for a running process
# This captures context switches, wakeups, and CPU migrations
perf sched record -p <PID> -- sleep 10
 
# Generate a summary of scheduling latency and runtime
perf sched latency
 
# Example output interpretation:
# -------------------------------------------------
#  Task              |   Runtime ms  | Switches |
# -------------------------------------------------
#  firefox           |     342.52    |   1247   |
#  mysqld            |     156.23    |   4521   |
#  ffmpeg            |    2341.67    |     89   |
# -------------------------------------------------
#
# Analysis:
# - firefox: 342.52ms / 1247 switches = 0.27ms average CPU burst (I/O bound)
# - mysqld:  156.23ms / 4521 switches = 0.03ms average CPU burst (very I/O bound)
# - ffmpeg: 2341.67ms / 89 switches = 26.3ms average CPU burst (CPU bound)
 
# For detailed per-burst timing:
perf sched timehist
 
# Sample output showing individual CPU bursts:
#   time           cpu  task name         wait time  sch delay   run time
#   [s]                                   [msec]     [msec]      [msec]
# 2.019329 [0001]  firefox               0.000      0.012       0.342
# 2.019671 [0001]  Xorg                  0.129      0.003       0.089
# 2.019854 [0001]  firefox               0.089      0.008       0.183

Practical Burst Analysis

When optimizing real systems, measuring actual burst distributions is more valuable than theoretical models. Use tools like perf sched, trace-cmd, or Application Performance Monitoring (APM) tools to understand your workload's actual burst characteristics before tuning scheduler parameters.

Implications for Multitasking

The CPU-I/O burst model has profound implications for how operating systems achieve efficient multitasking. Understanding these implications connects the theoretical burst model to practical system design.

Why multiprogramming works:

Consider a simplified scenario with two processes:

Process A: 40% CPU burst, 60% I/O burst (I/O bound)
Process B: 80% CPU burst, 20% I/O burst (CPU bound)

If we run A alone:

CPU utilization = 40%
A completes some work, waits, completes more...

If we run B alone:

CPU utilization = 80%
B completes more work before waiting

If we run A and B together (multiprogramming):

When A waits for I/O, B uses the CPU
When B waits for I/O, A uses the CPU
CPU utilization approaches 100% (minus overhead)

This is the fundamental insight that drives all modern operating system design.

Key Implications of the Burst Model

•Degree of multiprogramming: More processes generally improves CPU utilization—there's always a process ready when others are waiting.
•Job mix matters: Mixing I/O-bound and CPU-bound processes yields better utilization than homogeneous workloads.
•Context switch overhead is tolerable: The cost of switching (microseconds) is tiny compared to typical I/O waits (milliseconds).
•Interactive responsiveness: Short CPU bursts followed by I/O waits naturally create opportunities for other processes, including user interaction handlers.
•Batch throughput: Long CPU bursts should complete without unnecessary preemption to minimize overhead.

The multiprogramming formula:

A classic approximation for CPU utilization with n processes, each with I/O wait fraction p:

CPU Utilization = 1 - pⁿ

For example, if each process waits for I/O 80% of the time (p = 0.8):

1 process: 1 - 0.8¹ = 20% CPU utilization
2 processes: 1 - 0.8² = 36% CPU utilization
5 processes: 1 - 0.8⁵ = 67% CPU utilization
10 processes: 1 - 0.8¹⁰ = 89% CPU utilization
20 processes: 1 - 0.8²⁰ = 99% CPU utilization

This formula, while simplified (assumes independent I/O), illustrates why systems maintain many active processes.

The scheduler's challenge:

Given this model, the scheduler must answer: When multiple processes are ready (not in I/O burst), which one should run?

This is the central question of CPU scheduling, and different answers lead to different scheduling algorithms with different tradeoffs—which we'll explore throughout this module.

The Overhead Reality

While more processes improve utilization in theory, each adds overhead: memory for process structures, context switch costs, and cache pollution. There's a practical limit beyond which adding processes degrades rather than improves performance. Finding this balance is a key system design challenge.

Summary: CPU and I/O Bursts

We've established the foundational model that underlies all CPU scheduling concepts. Let's consolidate the key insights:

Key Takeaways

•CPU burst = contiguous period of CPU execution without I/O; I/O burst = period waiting for I/O completion.
•Processes alternate between CPU and I/O bursts in a strict cycle, starting and ending with CPU bursts.
•Burst distribution is skewed: many short bursts, few long bursts—following approximately exponential distribution.
•Burst prediction using exponential averaging enables intelligent scheduling decisions based on historical behavior.
•Multiprogramming exploits I/O waits by running other processes, dramatically improving CPU utilization.
•Different applications have characteristic burst patterns: I/O-bound (many short CPU bursts) vs. CPU-bound (few long CPU bursts).

What's next:

Now that we understand burst patterns, the next page explores the critical distinction between CPU-bound and I/O-bound processes. This classification, built directly on burst analysis, fundamentally shapes how schedulers prioritize different workloads and balance competing goals like throughput and responsiveness.

Page Complete

You now understand the CPU-I/O burst model—the fundamental rhythm of process execution that all scheduling algorithms must accommodate. This model explains why scheduling exists (to utilize CPU during I/O waits), why prediction matters (to make intelligent choices), and why multiprogramming works (mathematical inevitability with independent processes).

1 / 5

Loading learning content...

Operating SystemsCPU Scheduling

Scheduling Concepts

LevelIntermediate

Duration60 mins

TopicCPU Scheduling

1 / 5

CPU Burst and I/O Burst

The Rhythm of Process Execution

This fundamental pattern—CPU bursts alternating with I/O bursts—is the heartbeat of process execution and the foundation upon which all CPU scheduling decisions are made.

What You Will Learn

Defining CPU Bursts

The mechanics of a CPU burst:

I/O Request: The process needs data from a file, network, or device
Synchronization Wait: The process must wait for a lock, semaphore, or condition variable
Voluntary Yield: The process explicitly relinquishes the CPU
Preemption: The operating system forcibly removes the process (in preemptive systems)
Termination: The process completes its execution

The period from when the process starts executing until any of these events is the CPU burst.

cpu_burst_example.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Example: A function demonstrating CPU-intensive computation
// This entire loop represents a single, long CPU burst
 
void compute_matrix_multiply(double **A, double **B, double **C, int n) {
    // CPU Burst begins when this function starts executing
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            double sum = 0.0;
            for (int k = 0; k < n; k++) {
                // Pure arithmetic operations - no I/O, no waiting
                sum += A[i][k] * B[k][j];
            }
            C[i][j] = sum;
        }
    }
    
    // CPU Burst ends only when:
    // - Function returns and caller performs I/O
    // - Timer interrupt preempts the process
    // - Process terminates
}

Memory Access and CPU Bursts

Granularity of CPU bursts:

CPU bursts vary enormously in duration:

Microsecond bursts: Character I/O processing, interrupt handlers
Millisecond bursts: Typical interactive application processing
Second-scale bursts: Scientific computations, video encoding
Minute-scale bursts: Long-running simulations, training ML models

The scheduler must handle this entire range efficiently. A scheduling algorithm optimized for microsecond bursts might perform poorly with second-scale bursts, and vice versa.

Defining I/O Bursts

The anatomy of an I/O burst:

I/O bursts begin when a process makes a request that cannot be satisfied immediately and must wait for external events:

Disk I/O: Reading from or writing to files, databases, or virtual memory
Network I/O: Sending or receiving data over network connections
User Input: Waiting for keyboard, mouse, or touch events
Device Communication: Interacting with peripherals (printers, sensors, GPUs)
Inter-process Communication: Waiting for messages from other processes

io_burst_example.c
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
// Example: A sequence showing alternating CPU and I/O bursts
 
void process_log_file(const char *filename) {
    // ====== CPU BURST 1 ======
    // Preparing the file open request
    int fd = open(filename, O_RDONLY);
    
    // ====== I/O BURST 1 ======
    // Process BLOCKS here waiting for:
    // - File system to locate the inode
    // - Disk to read directory entries
    // - Permission checks to complete
    // When open() returns, I/O burst ends
    
    char buffer[4096];
    ssize_t bytes_read;
    
    while (1) {
        // ====== I/O BURST (repeated) ======
        bytes_read = read(fd, buffer, sizeof(buffer));
        // Process is BLOCKED during disk read
        // CPU is free to run other processes
        
        if (bytes_read <= 0) break;
        
        // ====== CPU BURST (repeated) ======
        // Parse and process the data
        // This is pure computation - no waiting
        for (int i = 0; i < bytes_read; i++) {
            process_character(buffer[i]);
        }
        // CPU burst ends when loop restarts and read() is called
    }
    
    // ====== I/O BURST (final) ======
    close(fd);  // May block to flush buffers to disk
}

I/O Latency Orders of Magnitude

Understanding I/O latency helps appreciate why I/O bursts dominate many workloads:

During a 10ms disk access, a 3 GHz CPU could have executed 30 million instructions. This is why I/O waits are so expensive and why the OS schedules other processes during I/O bursts.

I/O burst characteristics:

Unlike CPU bursts, which are under the control of the application's logic, I/O burst durations depend on:

Device speed: SSDs vs. HDDs vs. network vs. tape
Device contention: How many other processes are competing for the same device
Queue depth: How many pending requests are ahead in the device queue
Data location: Sequential vs. random access patterns
Network conditions: Latency, bandwidth, congestion

This unpredictability makes I/O burst durations much harder to predict than CPU bursts, which has significant implications for scheduling algorithms that attempt to estimate burst times.

The CPU-I/O Burst Cycle

The canonical execution model:

Process Start
    │
    ▼
┌─────────────┐     ┌───────────┐     ┌─────────────┐
│  CPU Burst  │ ──▶ │ I/O Burst │ ──▶ │  CPU Burst  │ ──▶ ...
│  (Running)  │     │ (Waiting) │     │  (Running)  │
└─────────────┘     └───────────┘     └─────────────┘
                                              │
                                              ▼
                                         (Eventually)
                                      ┌──────────────┐
                                      │  Termination │
                                      │  (CPU Burst) │
                                      └──────────────┘

Key observations about the cycle:

Every process begins with a CPU burst: Even if the first action is an I/O request, the code to make that request must execute first.
Every process ends with a CPU burst: The final CPU burst executes the termination code (exit system call).
The pattern is strictly alternating: A CPU burst is always followed by either an I/O burst or termination; an I/O burst is always followed by a CPU burst.
No overlap within a single process: A process cannot be in CPU burst and I/O burst simultaneously (though multiple processes can be).

Converting Mermaid diagram...

Why this model matters for scheduling:

The CPU-I/O burst cycle has profound implications:

Multiprogramming opportunity: During I/O bursts, the CPU is idle for that process. Other processes can use it.
Scheduling decision points: Every I/O burst is a scheduling opportunity—the OS must decide which ready process runs next.
Efficiency metric: The fraction of time spent in CPU bursts vs. I/O bursts determines how efficiently a workload uses the processor.
Process classification: Processes can be characterized by their burst patterns (CPU-bound vs. I/O-bound), informing scheduling decisions.

The Multiprogramming Imperative

CPU Burst Duration Distribution

The empirical finding:

Decades of measurements across diverse workloads have consistently shown that CPU burst durations follow a characteristic distribution:

Many short bursts: The majority of CPU bursts are very short (microseconds to a few milliseconds)
Few long bursts: A small fraction of bursts are much longer (seconds or more)
Exponential-like decay: The frequency of bursts decreases roughly exponentially as duration increases

This distribution is often modeled as an exponential distribution or hyperexponential distribution, though real workloads show variations.

Typical CPU Burst Duration Distribution (Interactive Workload)
Burst Duration	Approximate Frequency	Cumulative Percentage
< 1 ms	~40%	40%
1-10 ms	~30%	70%
10-100 ms	~20%	90%
100 ms - 1 s	~8%	98%
1 second	~2%	100%

Why this distribution exists:

The prevalence of short bursts isn't random—it reflects fundamental patterns in software:

Event-driven programming: Interactive applications respond to events (keystrokes, clicks, messages) with brief processing bursts followed by waits for the next event.
Layered I/O: Even "compute-intensive" programs frequently access data, hitting disk or network for each data item.
Operating system design: Frequent interrupts (timer, I/O completion) fragment what might otherwise be longer bursts.
Memory hierarchy: Cache misses and page faults convert long computations into series of short bursts separated by waits.

Implications for scheduling algorithm design:

How Burst Distribution Shapes Scheduling

•Favor short jobs (SJF): Since most bursts are short, algorithms that run short bursts first can significantly reduce average waiting time.
•Time slicing works well: Short time quantum values (e.g., 10-100 ms) will complete most bursts without preemption, minimizing context switch overhead.
•Prediction is feasible: The regularity of burst patterns makes exponential averaging and other prediction techniques reasonably effective.
•Long bursts are outliers: The rare long bursts need special handling to prevent starvation while not degrading overall system performance.

The 10ms Rule of Thumb

Measuring and Predicting Bursts

The prediction problem:

At the moment a process becomes ready to run, the scheduler must decide:

How long will this process's next CPU burst be?
Should we run it now, or is there a shorter job waiting?

We cannot query the process—it doesn't know either. We must infer from history.

Exponential averaging (Exponential Moving Average):

The most widely used prediction technique is exponential averaging, which weights recent history more heavily than distant past:

burst_prediction.c
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
// Exponential Averaging for CPU Burst Prediction
// τ(n+1) = α × t(n) + (1 - α) × τ(n)
//
// Where:
//   τ(n+1) = predicted length of next burst
//   t(n)   = actual length of the most recent burst
//   τ(n)   = previous prediction
//   α      = smoothing factor (0 < α < 1)
 
typedef struct {
    double predicted_burst;    // τ: current prediction
    double alpha;              // α: smoothing factor (typically 0.5)
} BurstPredictor;
 
void initialize_predictor(BurstPredictor *p, double initial_estimate, double alpha) {
    p->predicted_burst = initial_estimate;  // τ(0): initial guess
    p->alpha = alpha;
}
 
double predict_next_burst(BurstPredictor *p) {
    return p->predicted_burst;
}
 
void update_with_actual(BurstPredictor *p, double actual_burst) {
    // τ(n+1) = α × t(n) + (1 - α) × τ(n)
    p->predicted_burst = p->alpha * actual_burst + 
                         (1 - p->alpha) * p->predicted_burst;
}
 
// Example usage in scheduler:
// 
// Process P arrives, we predict its burst:
//   estimated_time = predict_next_burst(&P->predictor);
//
// After P completes its CPU burst:
//   update_with_actual(&P->predictor, measured_burst_duration);

Understanding the α parameter:

The smoothing factor α controls how quickly the prediction responds to changes:

α Value	Behavior	Best For
α = 0.0	Prediction never changes (uses only initial estimate)	N/A (degenerate)
α = 0.1	Very slow adaptation, heavily weights history	Stable workloads
α = 0.5	Balanced weighting of recent vs. historical	General purpose
α = 0.9	Rapid adaptation, recent bursts dominate	Volatile workloads
α = 1.0	Prediction equals last burst exactly	Highly variable processes

Example calculation:

Consider a process with burst history: 10ms, 8ms, 12ms, 5ms (most recent)

With α = 0.5 and initial estimate τ₀ = 10:

After 10ms burst: τ₁ = 0.5×10 + 0.5×10 = 10.0
After 8ms burst: τ₂ = 0.5×8 + 0.5×10 = 9.0
After 12ms burst: τ₃ = 0.5×12 + 0.5×9 = 10.5
After 5ms burst: τ₄ = 0.5×5 + 0.5×10.5 = 7.75

Next burst prediction: 7.75ms

Expanding the Exponential Average Formula

The formula τ(n+1) = α×t(n) + (1-α)×τ(n) can be expanded to show that each historical burst contributes with exponentially decreasing weight:

τ(n+1) = α×t(n) + α(1-α)×t(n-1) + α(1-α)²×t(n-2) + ... + (1-α)ⁿ×τ(0)

With α = 0.5: weights are 0.5, 0.25, 0.125, 0.0625... — recent history dominates but old behavior still influences predictions.

Burst Patterns in Real Systems

Different types of applications exhibit characteristic burst patterns. Understanding these patterns helps in workload characterization, capacity planning, and scheduler tuning.

Typical burst patterns by application type:

Burst Characteristics by Application Type
Application Type	CPU Burst Pattern	I/O Burst Pattern	Ratio
Text Editor	Very short (< 1ms), sporadic	Long waits for input	1:1000+ I/O dominated
Web Browser	Short bursts, event-driven	Network waits, render bursts	1:10 to 1:1 mixed
Compiler	Medium bursts, phases	File reads between phases	10:1 CPU dominated
Database Server	Short query processing	Disk I/O for data	1:5 I/O dominated
Video Encoder	Long, steady bursts	Minimal I/O (buffered)	100:1 CPU dominated
Scientific Simulation	Very long bursts	Checkpoint I/O only	1000:1 CPU dominated

Observing bursts with system tools:

Modern operating systems provide tools to observe burst behavior. On Linux, tools like perf, ftrace, and eBPF can capture scheduling events. Here's a conceptual analysis approach:

analyze_bursts.sh
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
#!/bin/bash
# Conceptual script to analyze CPU burst patterns using perf
 
# Record scheduler events for a running process
# This captures context switches, wakeups, and CPU migrations
perf sched record -p <PID> -- sleep 10
 
# Generate a summary of scheduling latency and runtime
perf sched latency
 
# Example output interpretation:
# -------------------------------------------------
#  Task              |   Runtime ms  | Switches |
# -------------------------------------------------
#  firefox           |     342.52    |   1247   |
#  mysqld            |     156.23    |   4521   |
#  ffmpeg            |    2341.67    |     89   |
# -------------------------------------------------
#
# Analysis:
# - firefox: 342.52ms / 1247 switches = 0.27ms average CPU burst (I/O bound)
# - mysqld:  156.23ms / 4521 switches = 0.03ms average CPU burst (very I/O bound)
# - ffmpeg: 2341.67ms / 89 switches = 26.3ms average CPU burst (CPU bound)
 
# For detailed per-burst timing:
perf sched timehist
 
# Sample output showing individual CPU bursts:
#   time           cpu  task name         wait time  sch delay   run time
#   [s]                                   [msec]     [msec]      [msec]
# 2.019329 [0001]  firefox               0.000      0.012       0.342
# 2.019671 [0001]  Xorg                  0.129      0.003       0.089
# 2.019854 [0001]  firefox               0.089      0.008       0.183

Practical Burst Analysis

Implications for Multitasking

Why multiprogramming works:

Consider a simplified scenario with two processes:

Process A: 40% CPU burst, 60% I/O burst (I/O bound)
Process B: 80% CPU burst, 20% I/O burst (CPU bound)

If we run A alone:

CPU utilization = 40%
A completes some work, waits, completes more...

If we run B alone:

CPU utilization = 80%
B completes more work before waiting

If we run A and B together (multiprogramming):

When A waits for I/O, B uses the CPU
When B waits for I/O, A uses the CPU
CPU utilization approaches 100% (minus overhead)

This is the fundamental insight that drives all modern operating system design.

Key Implications of the Burst Model

•Degree of multiprogramming: More processes generally improves CPU utilization—there's always a process ready when others are waiting.
•Job mix matters: Mixing I/O-bound and CPU-bound processes yields better utilization than homogeneous workloads.
•Context switch overhead is tolerable: The cost of switching (microseconds) is tiny compared to typical I/O waits (milliseconds).
•Interactive responsiveness: Short CPU bursts followed by I/O waits naturally create opportunities for other processes, including user interaction handlers.
•Batch throughput: Long CPU bursts should complete without unnecessary preemption to minimize overhead.

The multiprogramming formula:

A classic approximation for CPU utilization with n processes, each with I/O wait fraction p:

CPU Utilization = 1 - pⁿ

For example, if each process waits for I/O 80% of the time (p = 0.8):

1 process: 1 - 0.8¹ = 20% CPU utilization
2 processes: 1 - 0.8² = 36% CPU utilization
5 processes: 1 - 0.8⁵ = 67% CPU utilization
10 processes: 1 - 0.8¹⁰ = 89% CPU utilization
20 processes: 1 - 0.8²⁰ = 99% CPU utilization

This formula, while simplified (assumes independent I/O), illustrates why systems maintain many active processes.

The scheduler's challenge:

Given this model, the scheduler must answer: When multiple processes are ready (not in I/O burst), which one should run?

This is the central question of CPU scheduling, and different answers lead to different scheduling algorithms with different tradeoffs—which we'll explore throughout this module.

The Overhead Reality

Summary: CPU and I/O Bursts

We've established the foundational model that underlies all CPU scheduling concepts. Let's consolidate the key insights:

Key Takeaways

•CPU burst = contiguous period of CPU execution without I/O; I/O burst = period waiting for I/O completion.
•Processes alternate between CPU and I/O bursts in a strict cycle, starting and ending with CPU bursts.
•Burst distribution is skewed: many short bursts, few long bursts—following approximately exponential distribution.
•Burst prediction using exponential averaging enables intelligent scheduling decisions based on historical behavior.
•Multiprogramming exploits I/O waits by running other processes, dramatically improving CPU utilization.
•Different applications have characteristic burst patterns: I/O-bound (many short CPU bursts) vs. CPU-bound (few long CPU bursts).

What's next:

Page Complete

1 / 5