101
0/227
Loading content...
In the datacenter hosting millions of users, on the laptop running dozens of applications, even in the embedded controller managing a single device—processes spend the majority of their existence not running, but waiting to run. This waiting room is the Ready state.
The Ready state is deceptively simple in concept: a process has everything it needs to execute and is merely waiting for the CPU. But this simplicity conceals a rich tapestry of scheduling algorithms, queue data structures, priority schemes, and optimization strategies that determine whether your application feels responsive or sluggish.
Understanding the Ready state is understanding how operating systems create the illusion of parallelism—how a single CPU can appear to run dozens of programs simultaneously by switching between them faster than humans can perceive.
By the end of this page, you will understand the Ready state comprehensively—what it means to be 'ready,' how processes enter and exit this state, how the scheduler organizes ready processes, and the critical distinction between CPU-bound and I/O-bound process behavior. You'll learn why some processes spend more time ready than running, and how this affects system responsiveness.
The Ready state represents a process that is prepared to execute—it has all resources except the CPU. A ready process:
| Property | Ready State Value | Significance |
|---|---|---|
| CPU Allocation | None (waiting for scheduler) | Process cannot make progress despite being runnable |
| Memory Status | Fully allocated (or swappable) | All required code/data pages are accessible or loadable |
| I/O Status | No pending blocking I/O | Process isn't waiting for disk, network, or device completion |
| PCB Location | In scheduler's ready queue(s) | Scheduler knows this process is eligible to run |
| Runnable | Yes | Given CPU, this process can execute immediately |
The crucial difference between Ready and Waiting (Blocked) states:
Ready: "I can run right now, I just don't have a CPU."
Waiting: "Even with a CPU, I cannot proceed—I'm waiting for something external (disk read, network packet, timer, signal)."
This distinction matters for scheduling. Ready processes can use any available CPU time immediately. Waiting processes cannot—giving them the CPU would be wasteful because they would immediately block again.
In an ideal world with unlimited CPUs, no process would ever wait in Ready state—every process that could run would run. In reality:
The ratio of ready processes to CPUs determines CPU load. High load means processes spend more time ready, degrading responsiveness.
The 'load average' displayed by top/uptime represents the average number of processes in Ready (or Running) state over 1, 5, and 15-minute periods. On a 4-core system, a load average of 4.0 means, on average, all CPUs are busy. Load of 8.0 means 4 processes are running while 4 more are waiting—queuing indicates overload.
Processes arrive at the Ready state through multiple pathways, each representing a different lifecycle event:
In typical systems, the Running → Ready and Waiting → Ready transitions occur far more frequently than New → Ready. This is because:
The scheduler may handle thousands of Ready state entries per second on a busy system.
When a process enters Ready state, its position in the queue depends on its priority:
When a process wakes from waiting for I/O, schedulers often boost its priority temporarily. The rationale: I/O-bound processes (like text editors, web browsers) need quick CPU bursts to maintain responsiveness. By boosting their priority, the scheduler ensures they run quickly after I/O completion, process the result, and likely block again—keeping the system feeling responsive.
The term "ready queue" is somewhat misleading—modern systems rarely use a single FIFO queue. Instead, sophisticated data structures enable efficient scheduling decisions across potentially thousands of ready processes.
The simplest implementation: a linked list of PCBs. New processes added at tail, scheduler picks from head.
Advantages: O(1) enqueue and dequeue Disadvantages: No priority support, unfair to interactive processes
12345678910111213141516171819
Priority Levels (Linux traditional scheduler):────────────────────────────────────────────── Level 0: [PCB] → [PCB] → [PCB] ← Highest priority (real-time)Level 1: [PCB] → [PCB]Level 2: [PCB] → [PCB] → [PCB] → [PCB]...Level 139: [PCB] ← Lowest priority Scheduling:1. Find lowest-numbered non-empty queue2. Take first PCB from that queue3. Complexity: O(1) with bitmap tracking non-empty queues Linux O(1) Scheduler (2.6 era):- Two arrays: "active" and "expired"- Running process goes to expired when time slice ends- When active is empty, swap pointers- Result: O(1) for all operationsLinux's current scheduler uses a red-black tree instead of priority queues:
CFS achieves fairness by giving the CPU to whichever process has used the least time. Priorities are implemented by scaling vruntime: high-priority processes' vruntime increases slower, so they stay toward the left of the tree.
| Data Structure | Example Scheduler | Select Next | Insert | Strengths |
|---|---|---|---|---|
| FIFO Queue | Simple batch systems | O(1) | O(1) | Simplicity, low overhead |
| Priority Queue Array | Linux O(1) | O(1) | O(1) | Fast, deterministic real-time support |
| Red-Black Tree | Linux CFS | O(1) | O(log N) | Fairness, proportional sharing |
| Multilevel Feedback Queue | Windows, FreeBSD | O(1) | O(1) | Adapts to process behavior |
| Heap | Some RTOSes | O(1) | O(log N) | Simple priority support |
On SMP (symmetric multiprocessing) systems, a single global ready queue becomes a bottleneck—all CPUs contend for one lock. Modern systems maintain per-CPU ready queues:
This design trades perfect global fairness for scalability. A process might wait slightly longer because its preferred CPU is busy, even though another CPU is idle. Load balancers correct this over time.
The length of the ready queue directly affects scheduling latency. If 100 processes are ready and each gets a 10ms time slice, a newly ready process might wait up to 1 second before running. This is why systems with thousands of threads can feel sluggish even with modern CPUs—ready queue depth matters.
Understanding process behavior patterns is essential for comprehending Ready state dynamics. Processes are broadly categorized by their resource usage patterns:
CPU-bound processes perform extensive computation with minimal I/O. They consume their entire time slice before voluntarily giving up the CPU.
Examples:
Ready State Behavior: CPU-bound processes spend little time in Ready state between time slices—they're either running or just moved to ready after preemption. However, there can be many of them all contending for CPU.
I/O-bound processes spend most of their time waiting for I/O operations. They run briefly, initiate I/O, and block.
Examples:
Ready State Behavior: I/O-bound processes transition frequently between Ready and Waiting states. They're Ready briefly, run even more briefly, then become Waiting. The Ready state is a transit lounge, not a waiting room.
Optimal scheduling differs for each type:
For CPU-bound: Long time slices reduce context switch overhead. There's no point interrupting them early—they'll just run until preempted anyway.
For I/O-bound: Short time slices ensure responsiveness. These processes block voluntarily anyway, so they don't need long slices. What they do need is quick access to the CPU when I/O completes.
Smart schedulers detect process behavior and adjust accordingly. The "multi-level feedback queue" scheduler demotes CPU-bound processes to lower priority queues (longer slices, less frequently scheduled) while keeping I/O-bound processes in higher priority queues (for responsiveness).
CPU-Bound Process (video encoder):Time ─────────────────────────────────────────────────────► |████████████████|Ready|███████████████|Ready|████████ Full slice Wait Full slice Wait I/O-Bound Process (text editor):Time ─────────────────────────────────────────────────────► |██|----Waiting for keystroke----|██|---Waiting---|██| Run Run Run Legend: █ = Running, ─ = Waiting, Ready typically very brief for I/O-boundI/O-bound processes are often 'interactive' (responding to humans), while CPU-bound are often 'batch' (background computation). Modern schedulers exploit this: Linux CFS has an 'interactivity estimator' based on sleep ratio. Processes that sleep frequently (interactive) get boosted priority when they wake, improving perceived responsiveness.
The time a process spends in Ready state directly impacts user experience and system throughput. This metric, called ready queue wait time or scheduling latency, is a key performance indicator.
| Factor | Impact on Wait Time | Mitigation Strategy |
|---|---|---|
| Number of Ready Processes | More processes = longer wait | Limit concurrent processes; improve process efficiency |
| Time Slice Length | Longer slices = longer maximum wait | Reduce time slice (costs more context switches) |
| Process Priority | Lower priority = longer wait | Raise priority for latency-sensitive processes |
| Number of CPUs | More CPUs = shorter wait | Scale horizontally; virtualization limits help |
| Scheduler Overhead | Complex scheduling = added latency | Use O(1) schedulers for many-process systems |
| CPU Affinity | Restricted affinity = may wait for specific CPU | Relax affinity or use more CPUs |
For a simple round-robin scheduler with N ready processes and time quantum Q:
Average wait time ≈ (N - 1) × Q / 2
Maximum wait time ≈ (N - 1) × Q
Example: 10 ready processes, 10ms time slice
This seems small, but consider: if those 10 processes are competing with 100 others, maximum wait becomes 990ms—nearly a full second of latency.
12345678910111213141516
# Using perf to measure scheduler latency on Linux # Record scheduler events for 10 seconds$ sudo perf sched record -a sleep 10 # Analyze scheduler latency$ sudo perf sched latency # Sample output:# Task | Runtime ms | Switches | Avg delay ms | Max delay ms |# ----------------------|---------------|----------|--------------|--------------|# firefox | 450.234 | 2341 | 0.834 | 12.456 |# code | 123.456 | 892 | 0.612 | 8.234 |# kworker/0:1 | 34.567 | 1234 | 0.123 | 2.345 | # High "Max delay" indicates potential scheduling latency issuesInteractive Applications: Ready wait time directly affects perceived responsiveness. If a keystroke triggers processing that must wait 100ms in ready queue, the user perceives lag.
Real-time Systems: Ready wait time must be bounded and minimal. A real-time process that misses its deadline because it was stuck in ready queue fails its purpose.
Batch Processing: Ready wait time matters less—whether a batch job takes 60 minutes or 60 minutes plus 10 seconds of scheduling delay is negligible.
Server Workloads: High ready wait time increases request latency. At p99 (99th percentile), scheduling delays can dominate response time, causing latency spikes.
Minimizing ready wait time (latency) often conflicts with maximizing throughput. Short time slices reduce wait time but increase context switch overhead, reducing productive CPU utilization. Long time slices maximize throughput but increase latency. The scheduler's parameters must balance these competing goals based on workload characteristics.
Preemption is the forced removal of a running process from the CPU, returning it to the Ready state. This mechanism is fundamental to fair CPU sharing and system responsiveness.
1. Time Slice Exhaustion (Timer Preemption)
Every running process gets a time quantum (typically 1-100ms). A hardware timer interrupt fires when the quantum expires, and the scheduler:
2. Priority Preemption
When a higher-priority process becomes Ready (perhaps waking from I/O), the scheduler may:
This ensures high-priority processes run with minimal delay.
12345678910111213141516171819202122
timer_interrupt_handler() { // Called by hardware every tick (e.g., every 1ms) current_process→time_used++; current_process→time_left--; if (current_process→time_left <= 0) { // Time slice exhausted - preemption required save_context(current_process); // Save registers to PCB current_process→state = READY; // Mark as ready enqueue_ready(current_process); // Add to ready queue next = select_next_ready(); // Pick next process next→state = RUNNING; // Mark as running restore_context(next); // Load registers from PCB // Return from interrupt into new process's context } acknowledge_timer(); // Reset timer for next tick}Non-preemptive (Cooperative): Processes run until they voluntarily yield or block. Simple but dangerous—a buggy process can monopolize the CPU.
Preemptive: OS can take CPU away at any time. Essential for modern multi-user, multi-tasking systems.
All modern general-purpose OSes use preemptive scheduling. Real-time systems may use cooperative elements where processes have guaranteed behavior.
User-preemptive: OS can preempt user-mode execution at any time.
Kernel-preemptive: OS can preempt even kernel-mode execution (except in critical sections). Linux became kernel-preemptive in 2.6.
Kernel preemption improves latency by allowing preemption during long-running system calls, but requires careful locking to prevent data corruption.
| Aspect | Non-Preemptive | User-Preemptive | Kernel-Preemptive |
|---|---|---|---|
| Response Time | Unbounded (max = longest task) | Bounded by syscall length | Bounded by short critical sections |
| Implementation | Simple | Moderate complexity | Complex (kernel locking) |
| Context Switches | Minimal | Moderate | High (but acceptable) |
| Fairness | Poor (one process can hog) | Good for user processes | Excellent for all processes |
| Example Systems | Windows 3.1, early Mac OS | Unix tradition | Linux 2.6+, modern Windows |
Consider a process calling read() on a slow device. Without kernel preemption, even if a higher-priority process needs CPU, it must wait until the read() syscall returns to user mode. With kernel preemption, the high-priority process can run during the kernel portion of read(), dramatically improving worst-case latency.
How the scheduler manages the Ready queue directly determines fairness, throughput, and responsiveness. Three major strategies dominate:
Simplest approach: one queue, first-come-first-served. Processes are added at the tail, dispatched from the head.
Pros: Simple, predictable, fair in a basic sense Cons: No priority support, poor for mixed workloads
Separate queues for different process classes:
Scheduler always takes from highest non-empty queue.
12345678910111213141516
┌─────────────────────────────────────────────────────────┐│ Multi-Level Queue │├─────────────────────────────────────────────────────────┤│ ││ Priority 0 (Real-time): [RT1] → [RT2] → [RT3] │ ◄─ Served first│ ↓ ││ Priority 1 (System): [SYS1] → [SYS2] │ ◄─ Only if P0 empty│ ↓ ││ Priority 2 (Interactive): [INT1] → [INT2] → [INT3] │ ◄─ Only if P0,P1 empty│ ↓ ││ Priority 3 (Batch): [BATCH1] → [BATCH2] │ ◄─ Only if all above empty│ │└─────────────────────────────────────────────────────────┘ Problem: Starvation! If real-time processes keep arriving,batch processes NEVER run.MLFQ solves starvation by allowing processes to move between queues based on behavior:
Rules:
Effect:
| Strategy | Fairness | Responsiveness | Throughput | Starvation Risk |
|---|---|---|---|---|
| Single FIFO | High (within queue) | Poor | Moderate | None |
| Multi-Level (MLQ) | Priority-based | Good for high-priority | High | High (low priority) |
| MLFQ | Priority + adaptive | Excellent for interactive | High | Low (with periodic boost) |
| Fair Share (CFS) | Proportional to weight | Good (with latency hints) | High | None |
Real-world schedulers combine multiple strategies. Linux CFS uses a red-black tree for proportional fairness, but also has separate scheduling classes (real-time FIFO, real-time round-robin, deadline-based, and CFS fair-share). Windows uses MLFQ with 32 priority levels. The 'right' approach depends on workload characteristics—there's no universally optimal scheduler.
The transition from Ready to Running is called dispatch. This is the moment a process finally receives the CPU it's been waiting for.
When the scheduler selects a process from the Ready queue:
Dispatch latency is the time from when the scheduler decides to run a process until that process actually executes its first instruction. It includes:
Typical dispatch latency: 1-10 microseconds on modern hardware. Real-time systems work hard to minimize this.
A process may be selected for dispatch when:
123456789101112131415161718192021222324252627
// Conceptual dispatch routinevoid dispatch(struct process *next) { struct process *prev = current; // Update state in PCBs prev->state = READY; // or WAITING, TERMINATED next->state = RUNNING; // Account for time used update_scheduling_stats(prev); // Critical: switch address spaces if different processes if (next->mm != prev->mm) { switch_mm(prev->mm, next->mm); // Update page table pointer } // Set timer for new time slice set_timer(next->time_slice); // The actual context switch (architecture-specific assembly) // Saves all registers to prev->context // Loads all registers from next->context // Returns to next's saved program counter switch_to(prev, next); // Execution continues here when 'prev' is dispatched again}Some systems distinguish between the 'scheduler' (which decides which process should run) and the 'dispatcher' (which performs the actual context switch). The scheduler is the brain; the dispatcher is the hands. This separation allows scheduling decisions to be made at various points (syscall, interrupt, quantum expiration) while actual context switches happen in one centralized routine.
We've completed a comprehensive exploration of the Ready state—the waiting room where processes compete for CPU time. Let's consolidate the key concepts:
What's next:
From the Ready state, processes transition to the Running state—the momentary achievement of actually executing on a CPU. We'll explore what happens during process execution, how the CPU context supports execution, and the various ways a running process can lose the CPU.
You now understand the Ready state comprehensively—from its definition through entry pathways, queue management, CPU-bound vs I/O-bound behavior, performance implications, preemption mechanisms, and finally dispatch to the Running state. This knowledge is essential for understanding system performance and scheduler design.