Process Queues - Learning Module

Loading content...

0/227

Ready Queue: The Gateway to CPU Execution

The Central Dispatcher's Waiting Room

Of all the queues in an operating system, none is more critical to system performance than the ready queue. This queue represents the heartbeat of process scheduling—it contains every process that is prepared to execute and is simply waiting for the CPU to become available.

The ready queue is where processes spend their time between CPU bursts. How this queue is organized, how processes are selected from it, and how efficiently these operations are performed directly determines system responsiveness, throughput, and fairness. Understanding the ready queue is essential for understanding CPU scheduling itself.

What You Will Learn

By the end of this page, you will understand the ready queue's role in CPU scheduling, how different scheduling algorithms organize the ready queue, implementation strategies used by modern operating systems, and the tradeoffs between different queue structures.

Ready Queue: Formal Definition and Properties

The ready queue is a data structure maintained by the operating system that contains all processes that are in the ready state—that is, processes that:

Have all resources needed for execution (loaded in memory, file handles open, etc.)
Are not waiting for any event or I/O operation
Need only CPU time to continue their execution

Formal Definition:

The ready queue is the set of all processes that are currently runnable and awaiting CPU allocation. A process in the ready queue has completed any pending I/O or wait operation and is eligible for scheduling.

Key Properties of the Ready Queue

•Dynamic Membership — Processes constantly enter and leave the ready queue as they complete I/O, get scheduled, or block on resources.
•Ordering Significance — Unlike the job queue where order is incidental, the ready queue's ordering directly impacts which process runs next.
•Policy Implementation — The ready queue structure embodies the scheduling policy. A FIFO queue implements FCFS; a priority heap implements priority scheduling.
•Performance Critical — Ready queue operations (insert, remove-next, reorder) must be extremely efficient, as they occur during context switches.
•Multiple Possible Structures — Modern systems often use multiple ready queues organized by priority, CPU, or process type.

Converting Mermaid diagram...

The Bottleneck Metaphor

Think of the ready queue as a waiting area at a busy service counter (the CPU). Everyone in the waiting area has their paperwork ready (resources allocated) and just needs their turn at the counter. The scheduling algorithm determines who gets served next. Some counters serve anyone next in line (FCFS), others call VIPs first (priority), and some give everyone exactly 2 minutes before calling the next person (round-robin).

State Transitions: Entering and Leaving the Ready Queue

Understanding when and why processes enter and leave the ready queue is fundamental to understanding system behavior. Let's examine each transition in detail.

Ready Queue Transitions
Transition	Direction	Trigger	Kernel Action
New → Ready	Enter	Process admitted after creation	Add to ready queue, set state to READY
Waiting → Ready	Enter	I/O completion interrupt	Move from device queue to ready queue
Running → Ready	Enter	Timer interrupt (preemption)	Save context, add to ready queue
Stopped → Ready	Enter	SIGCONT signal received	Remove from stopped list, add to ready queue
Ready → Running	Leave	Scheduler dispatch	Remove from ready queue, restore context
Ready → Stopped	Leave	SIGSTOP/SIGTSTP signal	Remove from ready queue, add to stopped list

Detailed Transition Analysis:

1. Entering from New State (Admission)

When a process is first created, it briefly enters the NEW state while the OS allocates resources. Once the process is fully initialized (memory mapped, file descriptors inherited, PCB complete), it transitions to READY:

Process Admission (Conceptual)
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* Simplified process admission flow */
void admit_process(struct task_struct *p) {
    /* Process was in NEW state, all setup complete */
    
    /* Change state to READY (TASK_RUNNING in Linux terminology) */
    p->state = TASK_RUNNING;  /* Confusingly named - means runnable, not running */
    
    /* Add to the ready queue */
    enqueue_task(p, task_rq(p));  /* task_rq returns the run queue for this task */
    
    /* If higher priority than current, request reschedule */
    if (task_has_higher_priority(p, current)) {
        set_need_resched(current);  /* Signal scheduler to reconsider */
    }
}

2. Entering from Waiting State (I/O Completion)

This is one of the most frequent transitions. When an I/O operation completes, a hardware interrupt triggers the OS to:

Identify which process was waiting for this I/O
Remove the process from the device queue
Add the process to the ready queue
Potentially reschedule if the awakened process has higher priority

I/O Completion Handler (Conceptual)
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
/* Called when disk I/O completes (interrupt context) */
void disk_interrupt_handler(int irq, struct io_request *req) {
    struct task_struct *waiting_task = req->waiting_task;
    
    /* Mark the I/O request as complete */
    complete_io_request(req);
    
    /* Wake up the waiting process */
    wake_up_process(waiting_task);
}
 
void wake_up_process(struct task_struct *p) {
    unsigned long flags;
    
    raw_spin_lock_irqsave(&p->pi_lock, flags);
    
    /* Only wake if currently sleeping */
    if (p->state == TASK_INTERRUPTIBLE || 
        p->state == TASK_UNINTERRUPTIBLE) {
        
        /* Transition to runnable state */
        p->state = TASK_RUNNING;  /* Now ready */
        
        /* Add to ready queue */
        activate_task(rq, p, ENQUEUE_WAKEUP);
        
        /* Check if we need to preempt current task */
        check_preempt_curr(rq, p, 0);
    }
    
    raw_spin_unlock_irqrestore(&p->pi_lock, flags);
}

3. Re-entering from Running State (Preemption)

When a timer interrupt fires and the current process has exhausted its time slice, the scheduler preempts it—saving its state and returning it to the ready queue:

Timer Preemption (Conceptual)
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
38
39
/* Timer interrupt handler */
void scheduler_tick(void) {
    struct task_struct *curr = current;
    struct rq *rq = this_rq();
    
    /* Update time accounting */
    update_rq_clock(rq);
    curr->sched_class->task_tick(rq, curr, 0);
    
    /* For CFS: update virtual runtime */
    /* For Round Robin: decrement time slice */
    curr->time_slice--;
    
    if (curr->time_slice <= 0) {
        /* Time quantum exhausted */
        curr->time_slice = default_time_slice;  /* Reset for next time */
        
        /* Move current task to end of ready queue */
        requeue_task(rq, curr);
        
        /* Signal that rescheduling is needed */
        set_need_resched(curr);
    }
}
 
/* Later, in return-from-interrupt path */
void schedule(void) {
    if (need_resched()) {
        /* Save current context to its PCB */
        context_save(current);
        
        /* Select next task from ready queue */
        struct task_struct *next = pick_next_task(rq);
        
        /* Current goes back to ready queue (already done by requeue_task) */
        /* Switch to next task */
        context_switch(prev, next);
    }
}

Race Conditions

Ready queue operations often occur in interrupt context (I/O completion) or with interrupts disabled (scheduler critical sections). Improper synchronization can lead to lost wakeups (process never scheduled) or queue corruption (system crash). Modern kernels use sophisticated locking strategies like per-CPU queues to minimize contention.

Data Structures for Ready Queue Implementation

The choice of data structure for the ready queue has profound implications for scheduler efficiency. Different scheduling algorithms require different queue structures to achieve optimal performance.

Ready Queue Data Structures by Scheduling Algorithm
Scheduling Algorithm	Optimal Data Structure	Insert	Extract Next	Notes
FCFS	Simple FIFO Queue (linked list)	O(1)	O(1)	Tail insert, head remove
Priority (non-preemptive)	Priority Queue (heap)	O(log n)	O(log n)	Or O(k) array for k priority levels
Priority (preemptive)	Priority Queue + Preemption Check	O(log n)	O(log n)	Insert triggers comparison with running
Round Robin	FIFO Queue with time slice	O(1)	O(1)	Same as FCFS, timer drives preemption
Multilevel Queue	Array of FIFO Queues	O(1)	O(k)	k = number of queue levels
MLFQ	Array of FIFO Queues + promotion/demotion	O(1)	O(k)	Periodic boost adds overhead
CFS (Linux)	Red-Black Tree	O(log n)	O(log n)	Nodes sorted by virtual runtime

1. Simple FIFO Queue (Linked List)

The simplest implementation, suitable for FCFS and Round Robin schedulers:

FIFO Ready Queue Implementation
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
38
39
40
41
42
43
44
45
46
47
/* Simple FIFO ready queue using doubly-linked list */
struct ready_queue {
    struct task_struct *head;   /* Next to run */
    struct task_struct *tail;   /* Most recently added */
    int count;                  /* Number of waiting tasks */
    spinlock_t lock;            /* Protects queue operations */
};
 
/* Insert at tail - O(1) */
void ready_queue_insert(struct ready_queue *rq, struct task_struct *task) {
    spin_lock(&rq->lock);
    
    task->next = NULL;
    task->prev = rq->tail;
    
    if (rq->tail) {
        rq->tail->next = task;
    } else {
        rq->head = task;  /* Queue was empty */
    }
    
    rq->tail = task;
    rq->count++;
    
    spin_unlock(&rq->lock);
}
 
/* Remove from head - O(1) */
struct task_struct *ready_queue_extract(struct ready_queue *rq) {
    struct task_struct *task;
    
    spin_lock(&rq->lock);
    
    task = rq->head;
    if (task) {
        rq->head = task->next;
        if (rq->head) {
            rq->head->prev = NULL;
        } else {
            rq->tail = NULL;  /* Queue is now empty */
        }
        rq->count--;
    }
    
    spin_unlock(&rq->lock);
    return task;
}

2. Priority Queue (Heap Implementation)

For priority-based scheduling, a heap provides efficient priority ordering:

Priority Ready Queue (Heap)
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
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
/* Priority queue using binary min-heap */
#define MAX_PROCESSES 1024
 
struct priority_ready_queue {
    struct task_struct *heap[MAX_PROCESSES];
    int size;
    spinlock_t lock;
};
 
/* Helper: Compare priorities (lower number = higher priority) */
static inline int higher_priority(struct task_struct *a, struct task_struct *b) {
    return a->priority < b->priority;
}
 
/* Insert with heap bubble-up - O(log n) */
void priority_queue_insert(struct priority_ready_queue *pq, 
                           struct task_struct *task) {
    spin_lock(&pq->lock);
    
    int i = pq->size++;
    pq->heap[i] = task;
    
    /* Bubble up to maintain heap property */
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (higher_priority(pq->heap[i], pq->heap[parent])) {
            /* Swap with parent */
            struct task_struct *tmp = pq->heap[parent];
            pq->heap[parent] = pq->heap[i];
            pq->heap[i] = tmp;
            i = parent;
        } else {
            break;
        }
    }
    
    spin_unlock(&pq->lock);
}
 
/* Extract highest priority with heap bubble-down - O(log n) */
struct task_struct *priority_queue_extract(struct priority_ready_queue *pq) {
    struct task_struct *result;
    
    spin_lock(&pq->lock);
    
    if (pq->size == 0) {
        spin_unlock(&pq->lock);
        return NULL;
    }
    
    result = pq->heap[0];
    pq->heap[0] = pq->heap[--pq->size];
    
    /* Bubble down to maintain heap property */
    int i = 0;
    while (2 * i + 1 < pq->size) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = i;
        
        if (higher_priority(pq->heap[left], pq->heap[smallest]))
            smallest = left;
        if (right < pq->size && 
            higher_priority(pq->heap[right], pq->heap[smallest]))
            smallest = right;
        
        if (smallest != i) {
            struct task_struct *tmp = pq->heap[i];
            pq->heap[i] = pq->heap[smallest];
            pq->heap[smallest] = tmp;
            i = smallest;
        } else {
            break;
        }
    }
    
    spin_unlock(&pq->lock);
    return result;
}

3. Multi-Level Queue (Array of Queues)

For systems with distinct process classes (real-time, interactive, batch), an array of separate queues provides efficient classification:

Multilevel Ready Queue
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/* Multilevel Queue: Array of FIFO queues */
#define NUM_PRIORITY_LEVELS 140  /* Linux uses 140: 0-99 RT, 100-139 normal */
 
struct multilevel_queue {
    struct list_head queues[NUM_PRIORITY_LEVELS];
    unsigned long bitmap[BITS_TO_LONGS(NUM_PRIORITY_LEVELS)];  /* Quick empty check */
    int total_count;
    spinlock_t lock;
};
 
/* Insert at appropriate priority level - O(1) */
void multilevel_insert(struct multilevel_queue *mq, 
                       struct task_struct *task) {
    int prio = task->priority;
    
    spin_lock(&mq->lock);
    
    list_add_tail(&task->run_list, &mq->queues[prio]);
    __set_bit(prio, mq->bitmap);  /* Mark this level as non-empty */
    mq->total_count++;
    
    spin_unlock(&mq->lock);
}
 
/* Extract from highest priority non-empty queue - O(k) worst case */
struct task_struct *multilevel_extract(struct multilevel_queue *mq) {
    struct task_struct *task = NULL;
    int prio;
    
    spin_lock(&mq->lock);
    
    /* Find first non-empty queue (priority 0 is highest) */
    prio = find_first_bit(mq->bitmap, NUM_PRIORITY_LEVELS);
    
    if (prio < NUM_PRIORITY_LEVELS) {
        /* Remove from queue head */
        task = list_first_entry(&mq->queues[prio], 
                                struct task_struct, run_list);
        list_del_init(&task->run_list);
        
        /* Clear bitmap if queue is now empty */
        if (list_empty(&mq->queues[prio])) {
            __clear_bit(prio, mq->bitmap);
        }
        
        mq->total_count--;
    }
    
    spin_unlock(&mq->lock);
    return task;
}

Linux O(1) Scheduler

The Linux 2.6 O(1) scheduler (before CFS) used exactly this multilevel bitmap-based approach, achieving O(1) scheduling decisions regardless of the number of runnable processes. The bitmap's find_first_bit operation is highly optimized, often compiling to a single CPU instruction (BSF/TZCNT on x86).

Case Study: Linux Completely Fair Scheduler (CFS)

The Linux Completely Fair Scheduler (CFS), introduced in kernel 2.6.23 (2007), represents a sophisticated approach to ready queue implementation. Instead of traditional priority queues or multi-level feedback, CFS uses a red-black tree keyed by virtual runtime.

CFS Core Concepts

•Virtual Runtime (vruntime) — Each task tracks how much 'virtual' CPU time it has consumed. Virtual time advances more slowly for high-priority (low-nice) tasks and faster for low-priority (high-nice) tasks.
•Red-Black Tree — Tasks are stored in a red-black tree keyed by vruntime. The leftmost node (smallest vruntime) is the task that has received the least CPU time relative to its weight.
•Fairness Principle — CFS always runs the task with the smallest vruntime, ensuring that over time all tasks receive CPU time proportional to their weight.
•Weight Mapping — Nice values (-20 to +19) map to weights through a carefully designed table, where adjacent nice values differ by approximately 10% in weight.

CFS Ready Queue Structure (Simplified)
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
38
39
40
41
42
43
44
45
46
/* CFS Run Queue (per-CPU) */
struct cfs_rq {
    /* Red-black tree root for tasks */
    struct rb_root_cached tasks_timeline;  /* Cached leftmost node */
    
    /* Number of runnable tasks */
    unsigned int nr_running;
    
    /* Total weight of all runnable tasks */
    unsigned long load;
    
    /* Current running task's vruntime checkpoint */
    u64 min_vruntime;
    
    /* Currently running entity */
    struct sched_entity *curr;
    
    /* Cache of leftmost (next-to-run) entity */
    struct rb_node *rb_leftmost;  /* Deprecated: now in rb_root_cached */
};
 
/* Scheduler Entity - embedded in task_struct */
struct sched_entity {
    u64 vruntime;               /* Virtual runtime */
    u64 exec_start;             /* Start of current execution slice */
    u64 sum_exec_runtime;       /* Total CPU time consumed */
    
    struct rb_node run_node;    /* Red-black tree linkage */
    
    unsigned long weight;       /* Task weight (from nice) */
    unsigned long inv_weight;   /* Inverse weight for division */
    
    struct cfs_rq *cfs_rq;      /* Parent run queue */
};
 
/* Nice value to weight conversion table */
const int sched_prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

CFS Operations:

CFS Core Operations
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
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
/* Enqueue task into CFS ready queue - O(log n) */
static void enqueue_entity(struct cfs_rq *cfs_rq, 
                           struct sched_entity *se, 
                           int flags) {
    /* Update vruntime relative to current min */
    if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED)) {
        se->vruntime += cfs_rq->min_vruntime;
    }
    
    /* Update statistics */
    update_curr(cfs_rq);
    
    /* Insert into red-black tree by vruntime */
    __enqueue_entity(cfs_rq, se);
    
    cfs_rq->nr_running++;
}
 
/* Insert into RB tree maintaining vruntime order */
static void __enqueue_entity(struct cfs_rq *cfs_rq, 
                             struct sched_entity *se) {
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
    struct rb_node *parent = NULL;
    struct sched_entity *entry;
    bool leftmost = true;
    
    /* Binary search for insertion point */
    while (*link) {
        parent = *link;
        entry = rb_entry(parent, struct sched_entity, run_node);
        
        if (se->vruntime < entry->vruntime) {
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
            leftmost = false;  /* Not the new minimum */
        }
    }
    
    /* Insert and rebalance */
    rb_link_node(&se->run_node, parent, link);
    rb_insert_color_cached(&se->run_node, 
                           &cfs_rq->tasks_timeline, leftmost);
}
 
/* Pick next task from CFS queue - O(1) with cached leftmost */
static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq) {
    struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);
    
    if (!left)
        return NULL;
    
    return rb_entry(left, struct sched_entity, run_node);
}
 
/* Update current task's vruntime as it runs */
static void update_curr(struct cfs_rq *cfs_rq) {
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec;
    
    if (unlikely(!curr))
        return;
    
    /* Calculate actual execution time since last update */
    delta_exec = now - curr->exec_start;
    curr->exec_start = now;
    curr->sum_exec_runtime += delta_exec;
    
    /* Calculate virtual runtime increase (weighted by priority) */
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    
    /* Update min_vruntime */
    update_min_vruntime(cfs_rq);
}

Elegance of CFS

CFS elegantly combines fairness, efficiency, and simplicity. By always running the task with the smallest vruntime, it automatically provides proportional CPU sharing without complex bookkeeping. A task that has been sleeping will have a low vruntime and thus be quickly scheduled when it wakes—providing good interactive response without special-case code.

Per-CPU Ready Queues and SMP Scheduling

Modern multi-processor systems don't use a single global ready queue. Instead, they maintain per-CPU ready queues to minimize contention and maximize cache efficiency.

Problems with Single Global Queue

•Lock Contention — Every CPU contends for the same lock on every scheduling decision
•Cache Thrashing — Moving tasks between CPUs invalidates cache lines
•Scalability Limit — Performance degrades as CPU count increases
•NUMA Unfriendliness — No consideration for memory locality

Benefits of Per-CPU Queues

•No Contention — Each CPU accesses its own queue independently
•Cache Affinity — Tasks tend to stay on the same CPU, reusing cached data
•Linear Scalability — Adding CPUs doesn't increase scheduling overhead
•NUMA Awareness — Tasks can be kept near their memory allocations

Per-CPU Run Queue Structure (Linux)
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
38
39
/* Per-CPU run queue - one per processor */
struct rq {
    /* Current and idle tasks */
    struct task_struct *curr;   /* Currently running task */
    struct task_struct *idle;   /* Idle task for this CPU */
    
    /* Per-scheduler-class run queues */
    struct cfs_rq cfs;          /* CFS (normal tasks) run queue */
    struct rt_rq rt;            /* Real-time run queue */
    struct dl_rq dl;            /* Deadline run queue */
    
    /* Queue statistics */
    unsigned int nr_running;    /* Total runnable tasks on this CPU */
    
    /* Load tracking for load balancing */
    unsigned long cpu_load[CPU_LOAD_IDX_MAX];
    
    /* Clock */
    u64 clock;
    u64 clock_task;
    
    /* Lock protecting this run queue */
    raw_spinlock_t lock;
    
    /* Load balancing */
    int active_balance;
    struct task_struct *push_cpu_stop; /* For migration */
    unsigned long next_balance;         /* When to next balance */
    
    /* NUMA statistics */
    unsigned int numa_preferred_nid;
};
 
/* Array of per-CPU run queues */
DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
 
/* Access current CPU's run queue */
#define this_rq()  this_cpu_ptr(&runqueues)
#define cpu_rq(cpu) per_cpu_ptr(&runqueues, cpu)

Load Balancing:

The challenge with per-CPU queues is that loads can become imbalanced—some CPUs may have many runnable tasks while others sit idle. Linux addresses this through periodic load balancing:

Load Balancing (Conceptual)
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
38
39
40
41
42
43
44
45
/* Simplified load balancing logic */
void load_balance(int this_cpu, struct rq *this_rq) {
    struct sched_domain *sd;
    struct sched_group *busiest_group;
    struct rq *busiest_rq;
    struct task_struct *p;
    
    /* Traverse scheduling domains (groups of CPUs) */
    for_each_domain(this_cpu, sd) {
        /* Find the busiest group in this domain */
        busiest_group = find_busiest_group(sd, this_cpu);
        if (!busiest_group)
            continue;
        
        /* Find the busiest CPU in that group */
        busiest_rq = find_busiest_queue(busiest_group);
        if (!busiest_rq || busiest_rq == this_rq)
            continue;
        
        /* Calculate how many tasks to move */
        int imbalance = calculate_imbalance(this_rq, busiest_rq);
        
        /* Pull tasks from busiest to this queue */
        while (imbalance > 0) {
            p = detach_one_task(busiest_rq);
            if (!p)
                break;
            
            /* Migrate task to this CPU */
            attach_one_task(this_rq, p);
            imbalance -= task_load(p);
        }
    }
}
 
/* Called periodically and on CPU idle */
void scheduler_tick(void) {
    /* ... update accounting ... */
    
    /* Trigger load balance if needed */
    if (time_after(jiffies, this_rq()->next_balance)) {
        load_balance(smp_processor_id(), this_rq());
        this_rq()->next_balance = jiffies + HZ/10;  /* Every 100ms */
    }
}

Scheduling Domains

Modern CPUs have complex topologies—SMT threads share cores, cores share L2/L3 caches, sockets share NUMA nodes. Linux scheduling domains model this hierarchy, preferring to balance load within tight domains (same cache) before crossing to distant domains (different NUMA nodes) where migration is more expensive.

Case Study: Windows Ready Queue Implementation

Windows takes a different approach to ready queue organization, using a multilevel priority queue with processor sets for CPU affinity.

Windows Scheduling Characteristics

•32 Priority Levels — Priorities 0-31, with 1-15 for variable (normal) threads and 16-31 for real-time threads.
•Priority-Based Preemption — Higher priority threads always preempt lower priority threads.
•Quantum-Based Time Slicing — Within the same priority, threads receive time quanta (typically 2 or 12 clock intervals).
•Dynamic Priority Boost — Interactive and I/O-completing threads receive temporary priority boosts.
•Processor Affinity Masks — Threads can be restricted to specific processors.

Windows Ready Queue Structure (Conceptual)
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
38
39
40
41
42
43
44
/* Windows Per-Processor Ready Queue (KPRCB) */
typedef struct _KPRCB {
    /* Dispatcher ready lists - one per priority level */
    LIST_ENTRY DispatcherReadyListHead[32];
    
    /* Bitmap indicating which queues are non-empty */
    ULONG ReadySummary;  /* Bit n set if priority n queue non-empty */
    
    /* Currently running thread */
    PKTHREAD CurrentThread;
    PKTHREAD NextThread;     /* Already selected, waiting for switch */
    PKTHREAD IdleThread;
    
    /* Quantum tracking */
    ULONG QuantumEnd;
    
    /* DPC (Deferred Procedure Call) queue */
    KDPC_DATA DpcData[2];
    
    /* ... many more fields ... */
} KPRCB, *PKPRCB;
 
/* Thread scheduling state (KTHREAD) */
typedef struct _KTHREAD {
    /* Priority information */
    SCHAR Priority;          /* Current priority (0-31) */
    SCHAR BasePriority;      /* Base priority (0-31) */
    SCHAR PriorityDecrement; /* Quantum exhaustion penalty */
    
    /* Processor affinity */
    KAFFINITY Affinity;      /* Which processors this thread can run on */
    ULONG IdealProcessor;    /* Preferred processor */
    
    /* Scheduling state */
    UCHAR State;             /* Ready, Running, Waiting, etc. */
    
    /* Quantum */
    SCHAR Quantum;           /* Remaining quantum */
    
    /* Queue linkage */
    LIST_ENTRY WaitListEntry;  /* For ready/wait queue linkage */
    
    /* ... many more fields ... */
} KTHREAD, *PKTHREAD;

Windows Scheduling Algorithm:

Windows Thread Selection (Conceptual)
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/* Select next thread to run on this processor */
PKTHREAD KiSelectNextThread(PKPRCB Prcb) {
    ULONG Priority;
    PKTHREAD Thread;
    
    /* If a thread is pre-selected (from interrupt), use it */
    if (Prcb->NextThread) {
        Thread = Prcb->NextThread;
        Prcb->NextThread = NULL;
        return Thread;
    }
    
    /* Find highest priority non-empty queue using ReadySummary bitmap */
    if (Prcb->ReadySummary == 0) {
        /* No ready threads - run idle thread */
        return Prcb->IdleThread;
    }
    
    /* Find highest set bit (highest priority) */
    Priority = 31 - BitScanReverse(Prcb->ReadySummary);
    
    /* Remove first thread from that priority's queue */
    Thread = CONTAINING_RECORD(
        Prcb->DispatcherReadyListHead[Priority].Flink,
        KTHREAD,
        WaitListEntry
    );
    
    RemoveEntryList(&Thread->WaitListEntry);
    
    /* Clear bitmap bit if queue is now empty */
    if (IsListEmpty(&Prcb->DispatcherReadyListHead[Priority])) {
        Prcb->ReadySummary &= ~(1 << Priority);
    }
    
    return Thread;
}
 
/* Insert thread into ready queue */
VOID KiInsertReadyQueue(PKTHREAD Thread, PKPRCB Prcb) {
    ULONG Priority = Thread->Priority;
    
    /* Add to tail of appropriate priority queue */
    InsertTailList(&Prcb->DispatcherReadyListHead[Priority],
                   &Thread->WaitListEntry);
    
    /* Update bitmap */
    Prcb->ReadySummary |= (1 << Priority);
    
    /* Check if this thread should preempt current */
    if (Priority > Prcb->CurrentThread->Priority) {
        /* Request dispatch interrupt */
        KiRequestSoftwareInterrupt(DISPATCH_LEVEL);
    }
}

Priority Boost Mechanism

Windows provides excellent interactive responsiveness through priority boosting. When a GUI thread receives user input, it gets a priority boost of +2. When any thread completes an I/O wait, it receives a boost based on the device type (keyboard: +6, disk: +1). These boosts decay over subsequent quanta, naturally returning threads to their base priority.

Performance Analysis and Optimization

Ready queue operations occur during context switches—one of the most performance-sensitive code paths in the kernel. Let's analyze the computational costs and optimization strategies.

Ready Queue Operation Costs
Operation	FIFO Queue	Binary Heap	Red-Black Tree	Bitmap + Array
Insert	O(1)	O(log n)	O(log n)	O(1)
Extract Next	O(1)	O(log n)	O(1)*	O(1)*
Priority Change	N/A	O(log n)	O(log n)	O(1)
Remove Arbitrary	O(n)	O(log n)	O(log n)	O(1)
Space Overhead	2 pointers/task	1 pointer/task	3 pointers/task	Fixed size bitmap

*With caching of minimum element

Key Optimizations in Modern Implementations:

Performance Optimization Techniques

•Cached Minimum — Both Linux CFS (rb_first_cached) and Windows (ReadySummary) cache the next-to-run entity, making selection O(1) despite the underlying tree structure.
•Per-CPU Queues — Eliminating global lock contention is the single biggest performance optimization for multiprocessor systems.
•Lockless Techniques — Linux uses RCU for some read paths and careful ordering to minimize lock hold times.
•Batched Operations — When multiple I/O operations complete simultaneously, wakeups can be batched to reduce lock acquisitions.
•Lazy Rebalancing — Linux CFS allows min_vruntime to drift slightly rather than rebalancing on every operation.
•Hardware Assistance — Modern CPUs provide fast bit-scan instructions (BSF/TZCNT) that make bitmap searching extremely efficient.

Benchmark: Context Switch Overhead
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
/* Conceptual context switch timing breakdown */
/*
 * Typical context switch on modern x86-64 (2020s era):
 *
 * Total: ~1-5 microseconds, consisting of:
 *
 * 1. Save registers to current PCB:         ~50-100 ns
 * 2. Ready queue update (current):          ~50-200 ns
 * 3. Ready queue select next:               ~50-200 ns
 * 4. TLB/ASID management:                   ~100-500 ns
 * 5. Restore registers from next PCB:       ~50-100 ns
 * 6. Cache warm-up (indirect):              ~500-2000 ns
 *
 * Factors that increase overhead:
 * - Lock contention (global queue systems)
 * - Cache misses on queue traversal
 * - TLB flush (if ASIDs exhausted)
 * - FPU/SIMD state save/restore
 * - Spectre mitigations (IBPB, STIBP)
 */
 
/* Linux provides context switch metrics */
// $ cat /proc/PID/sched
// nr_switches               : 12345
// nr_voluntary_switches     : 10000
// nr_involuntary_switches   : 2345
 
/* Measure context switch rate system-wide */
// $ vmstat 1
// procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu-----
//  r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa st
//  1  0      0 1234567  12345 567890    0    0     0     0  100 2000  5  2 93  0  0
//                                                             ^
//                                                          context switches/sec

The Hidden Cost

The direct cost of ready queue operations is dwarfed by the indirect cost of cache pollution. When a context switch occurs, the new process typically has cold caches—its data and instructions aren't in L1/L2 cache. This 'cache warm-up' period can cost more than the switch itself. Good schedulers try to balance load while minimizing task migration.

Summary: The Ready Queue as Scheduling Cornerstone

The ready queue is the operational center of CPU scheduling—where policy meets implementation. Let's consolidate our understanding:

Key Takeaways

•Central Role — The ready queue holds all processes that are runnable but waiting for CPU time. It is the bridge between process creation/wakeup and actual execution.
•Dynamic Nature — Processes continuously enter (from NEW, WAITING states) and leave (to RUNNING state) the ready queue. Understanding these transitions is key to understanding system behavior.
•Structure Determines Policy — The data structure used for the ready queue directly implements scheduling policy. FIFO queues give FCFS, heaps give priority scheduling, red-black trees enable CFS fairness.
•Per-CPU Optimization — Modern SMP systems use per-CPU ready queues to eliminate lock contention, with periodic load balancing to prevent imbalance.
•Linux CFS — Uses a red-black tree keyed by virtual runtime to achieve proportional fair scheduling with O(log n) operations and O(1) cached selection.
•Windows Approach — Uses a 32-level priority queue with bitmap optimization for O(1) operations, combined with dynamic priority boosting for interactivity.
•Performance Critical — Ready queue operations occur during context switches. Efficient implementation directly impacts system responsiveness and throughput.

What's Next:

We've explored the two primary queues—the job queue (all processes) and the ready queue (runnable processes). Next, we'll examine device queues—the specialized queues where processes wait when they need I/O services.

Page Complete

You now have a comprehensive understanding of the ready queue: its role in scheduling, state transitions, implementation strategies, and real-world implementations in Linux and Windows. This knowledge forms the foundation for understanding CPU scheduling algorithms and system performance optimization.