Loading learning content...
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.
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.
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:
The period from when the process starts executing until any of these events is the CPU burst.
12345678910111213141516171819202122
// 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 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:
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.
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:
12345678910111213141516171819202122232425262728293031323334353637
// 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}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:
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.
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).
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.
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.
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:
This distribution is often modeled as an exponential distribution or hyperexponential distribution, though real workloads show variations.
| 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:
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.
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:
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:
123456789101112131415161718192021222324252627282930313233343536
// 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:
Next burst prediction: 7.75ms
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.
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:
| 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:
123456789101112131415161718192021222324252627282930313233
#!/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 migrationsperf sched record -p <PID> -- sleep 10 # Generate a summary of scheduling latency and runtimeperf 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.183When 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.
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:
If we run A alone:
If we run B alone:
If we run A and B together (multiprogramming):
This is the fundamental insight that drives all modern operating system design.
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):
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.
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.
We've established the foundational model that underlies all CPU scheduling concepts. Let's consolidate the key insights:
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.
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).