SwadhyAI Notes

All Operating Systems notes

Start here

Runqueues hold tasks that could run now; wait queues hold tasks blocked on conditions. I/O completion and timers move work between them, scheduling is not magic, it is bookkeeping on these structures.

Runqueue vs wait queue

Per-CPU runqueues reduce lock contention: each core mostly schedules its own runnable set. When a thread blocks in a syscall, it leaves the runqueue and joins a wait queue tied to an object (pipe buffer, futex, disk request). Wakeups return it to runnable.

By the end of this page you should be able to

  1. Contrast runqueue membership with wait-queue membership.
  2. Explain why “one global queue” is usually not how Linux works.
  3. Name one reason a runnable task might still not get CPU time immediately.

Operating systems · Processes

Process scheduling queues

Runqueues, waitqueues, and why “scheduling” is plural

TL;DR

The OS keeps **runnable** tasks on per-CPU runqueues (policy-dependent) while **blocked** tasks sit on wait queues keyed by events (I/O completion, futex, pipe data). Scheduling moves tasks between these structures, confusing them loses interview points.

Summary

Scheduling queues encode the work the OS must do to be fair and responsive. Debugging “slow app” often means identifying whether delay is runqueue wait, lock wait, or I/O wait.

Deeper narrative

Runqueues hold runnable entities; wait queues hold blocked ones. I/O completion moves tasks between them. CFS uses a red-black tree keyed by vruntime; RT classes use priority lists, know both textbook MLFQ and Linux reality.

Mechanism (step by step)

Treat each step as a sentence in the story you tell on a whiteboard.
1

Admission

Fork/ wakeup enqueues on appropriate CPU runqueue (respecting affinity).

2

Dispatch

Scheduler tick or blocking syscall triggers `schedule()`.

3

Blocking

Task removed from runqueue, placed on wait queue with condition.

4

Wakeup

IRQ or completion moves task back to runnable; wake_affine chooses CPU.

Key insights

Each card is a compression of the lesson, use them as spaced-repetition prompts.

Runnable vs blocked

Only runnable entities compete for CPU; blocked entities are removed from the runqueue until woken.

Wake_one vs wake_all

Mutexes wake one waiter; broadcast condition variables may wake many, thundering herd risk.

Priority inversion ties queues

Low-priority holder of a mutex can delay high-priority runnable tasks, priority inheritance adjusts effective priority.

Runqueue length ≠ load average nuance

Short spikes may not move loadavg1 much; use scheduler latency tools for microstutters.

Did you know?

Trivia with teeth: the kind of fact that changes how you reason about a design.
Linux CFS uses a red-black tree keyed by vruntime for normal tasks, not a single FIFO global queue.
Push/pull migration balances load across CPUs but can cause cache coldness.
Softirq/tasklet bottom halves can starve if not bounded, related to runqueue latency.

Common pitfalls

Where smart people still trip, read slowly.

Thinking one global queue

Per-CPU runqueues reduce lock contention; balancing introduces migration cost.

Ignoring throttling

CFS bandwidth and cgroup cpu.max can make tasks appear “runnable” but not scheduled.

Glossary

Runqueue

Per-CPU structure holding runnable tasks for that processor.

Wait queue

Linked list of tasks sleeping until a condition (I/O, futex) completes.

vruntime

CFS virtual runtime, fairness key approximating proportional CPU share.

Interview follow-ups

  1. Difference between runqueue and wait queue?
  2. Why might a task bounce between CPUs excessively?
  3. How does `SCHED_IDLE` differ from nice 19?

Callouts

Tooling

`perf sched`, `latencytop` (where available), and `trace-cmd` visualize wait-for-CPU vs sleep.

Walkthrough & deep dive

Left: practical “how would I use this?” threads. Right: slower, code-leaning explanations, open one panel at a time so the page does not feel like a wall of sameness.

Walkthrough

Diagram

Draw runqueue(s) on the left, device waitqueue on the right; show I/O completion arrow waking a task onto runqueue.

Deep dive

Per-CPU ksoftirqd

Network-heavy workloads can spend time in softirq context, shows why CPU “idle” is not simple.

Scheduler latency snapshot

Terminal
perf sched record -- sleep 1
perf sched latency 2>/dev/null | head

Self-check

Misses here are cheap; misses in an interview are not. Treat wrong answers as a patch list for tomorrow.

1A thread blocked on a pipe read is typically…

2Runqueues primarily hold…

3Thundering herd relates to…