Ready State: Waiting for CPU Allocation

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.

The Ready state represents a process that is prepared to execute—it has all resources except the CPU. A ready process:

1. Has been admitted to the system (passed through New state)
2. Is not waiting for any external event (not blocked on I/O, not waiting for a signal)
3. Is not currently running (another process has the CPU)
4. Competes for CPU allocation via the scheduler's ready queue

Formal Characteristics

The Distinction: Ready vs Waiting

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.

Why Processes Are Ready, Not Running

In an ideal world with unlimited CPUs, no process would ever wait in Ready state—every process that could run would run. In reality:

• Single-core systems: Only one process runs at a time; all others wait
• Multi-core systems: N cores → N processes run; the rest wait
• Over-subscription: Modern systems routinely run more processes than cores

The ratio of ready processes to CPUs determines CPU load. High load means processes spend more time ready, degrading responsiveness.

Processes arrive at the Ready state through multiple pathways, each representing a different lifecycle event:

Transition Frequency Analysis

In typical systems, the Running → Ready and Waiting → Ready transitions occur far more frequently than New → Ready. This is because:

1. Process creation is relatively rare compared to execution
2. Time slices expire regularly (every few milliseconds)
3. I/O operations complete constantly (disk, network, user input)

The scheduler may handle thousands of Ready state entries per second on a busy system.

Priority Upon Entry

When a process enters Ready state, its position in the queue depends on its priority:

• New → Ready: Process enters at priority determined by inheritance or initial assignment
• Preempted → Ready: Process may retain its priority or have it adjusted (anti-starvation aging)
• Waiting → Ready: Many schedulers give I/O-completing processes a temporary priority boost to favor interactivity

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.

Historical: Simple FIFO Queue

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

Multi-Level Priority Queues

Completely Fair Scheduler (CFS) - Linux Modern

Linux's current scheduler uses a red-black tree instead of priority queues:

• Key: "virtual runtime" (vruntime) - how much CPU time the process has consumed
• Leftmost node: process with lowest vruntime (most "deserving" of CPU)
• Operations: O(log N) for insert, O(1) for select leftmost

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.

Per-CPU Ready Queues

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:

• Each CPU has its own ready queue (or portion of the tree)
• Processes have CPU affinity preferences
• Load balancing periodically migrates processes between CPUs
• Reduces lock contention dramatically

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.

Understanding process behavior patterns is essential for comprehending Ready state dynamics. Processes are broadly categorized by their resource usage patterns:

CPU-Bound Processes

CPU-bound processes perform extensive computation with minimal I/O. They consume their entire time slice before voluntarily giving up the CPU.

Examples:

• Scientific simulations
• Video encoding/decoding
• Cryptographic computations
• Compilation of large codebases
• Machine learning training

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

I/O-bound processes spend most of their time waiting for I/O operations. They run briefly, initiate I/O, and block.

Examples:

• Text editors (waiting for keystrokes)
• Web browsers (waiting for network responses)
• Database servers (waiting for disk reads)
• Shell programs (waiting for user input)
• File copy utilities

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.

The Scheduler's Dilemma

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).

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.

Factors Affecting Ready State Duration

Calculating Expected Wait Time

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

• Average wait: 45ms
• Maximum wait: 90ms

This seems small, but consider: if those 10 processes are competing with 100 others, maximum wait becomes 990ms—nearly a full second of latency.

Ready Wait Time in Practice

Impact on Different Workloads

Interactive 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.

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.

Types of Preemption

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:

1. Saves the running process's context
2. Moves it to Ready queue
3. Selects next process from Ready queue
4. Context switches to the new process

2. Priority Preemption

When a higher-priority process becomes Ready (perhaps waking from I/O), the scheduler may:

1. Immediately preempt the current (lower-priority) process
2. Move it to Ready queue
3. Dispatch the higher-priority process

This ensures high-priority processes run with minimal delay.

Preemptive vs Non-Preemptive Scheduling

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.

Preemption Granularity

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.

How the scheduler manages the Ready queue directly determines fairness, throughput, and responsiveness. Three major strategies dominate:

Strategy 1: Single Queue (FIFO-based)

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

Strategy 2: Multi-Level Queue (MLQ)

Separate queues for different process classes:

• Queue 0: Real-time processes (highest priority)
• Queue 1: System processes
• Queue 2: Interactive user processes
• Queue 3: Background/batch processes (lowest priority)

Scheduler always takes from highest non-empty queue.

Strategy 3: Multi-Level Feedback Queue (MLFQ)

MLFQ solves starvation by allowing processes to move between queues based on behavior:

Rules:

1. New processes start in highest-priority queue
2. Processes that use full time slice are demoted (moved to lower queue)
3. Processes that block (I/O) before time slice expires stay or are promoted
4. Periodically, all processes are boosted to highest queue (prevent starvation)

Effect:

• CPU-bound processes sink to lower queues (long slices, infrequent)
• I/O-bound processes stay at top (quick response, blocks anyway)
• System automatically adapts to process characteristics