Part 5 · 5 chapters · ~40 min

Scheduling Algorithms

The event loop is a priority scheduler over per-source queues, React's priorities are bits in a Smi, and responsiveness during heavy work comes from cooperative slicing against a deadline. This part is the browser's task selection with its anti-starvation rules, the lane model operation by operation, slicing and where a continuation lands, idle and deadline scheduling, and a comparison of every scheduler a frontend runs on.

The event loop as a scheduler

the question

"The spec says tasks run in order. Then why does a setTimeout fire after a fetch callback that was queued later?"

Because "in order" is per task source, and the browser chooses which source to pull from with a priority policy. The HTML spec defines task queues per source and lets the host pick any queue at each turn; Chrome's renderer scheduler has about twenty queues with dynamic priorities and anti-starvation rules. The loop is a priority scheduler with FIFO inside each queue, a rendering opportunity interleaved at the display rate, and microtasks drained outside the whole mechanism.

the selection algorithm, as Chrome does it

Queues per source with a priority each: input handling (highest during a gesture), compositor sync, the frame task, user-visible defaults (postMessage, timers, networking), loading tasks (deprioritised during interaction), and idle.
Pick: the highest-priority queue with a runnable task; within it, the oldest. Ties by age across queues of equal priority.
Policies shift with state: during touch or scroll, input and compositor queues are boosted and loading queues throttled; after load completes, defaults return; in a hidden tab, timers are throttled to once per second (and later, once per minute).
Anti-starvation: a queue whose oldest task has waited past a threshold gets a boost so that nothing is starved forever by a busy high-priority queue.
The frame: when a vsync is due and the page has pending visual changes, the frame task (rAF callbacks, style, layout, paint, commit) is scheduled at high priority. It cannot pre-empt a running task; a task longer than the time to vsync delays the frame.
Microtasks: drained to completion after every task, inside the task's turn (the JS course, part 10). Not scheduled; not interruptible.

what follows

Timer order is not guaranteed relative to other sources, only relative to other timers. setTimeout(fn, 0) after a fetch completes is "after the fetch callback, probably" during load and "before it, probably" during a scroll.
Yielding is the only way to let the scheduler decide. A long task holds the thread; the scheduler's priorities apply only at task boundaries. Slicing (chapter 3) creates boundaries.
Node is different: libuv runs phases (timers, pending callbacks, poll for I/O, check for setImmediate, close) in a fixed cycle, with process.nextTick and microtasks drained between callbacks. No priorities; order is by phase. The Node course has it.

the pointer

The browser course part 6 draws the loop as the browser runs it, with the input pipeline and INP. This chapter is the selection policy only; the next is what React builds on top of it.

THE EVENT LOOP'S TASK SELECTION

per-source queues, priorities, and the rendering opportunity

swipe the figure sideways, or tap expand for full screen

1/6

per-source queues

Queues, each FIFO internally: input (highest when a frame is pending), rendering (the frame task itself), timers, networking (fetch completions), postMessage and MessageChannel, idle (requestIdleCallback), and more. A task source is the spec's name for a queue.

React's lane model: priorities as bits

React needs to batch updates, render some before others, interrupt a low-priority render when a high-priority update arrives, and never let anything starve. Its data structure for all of that is a 31-bit integer: each bit a lane, each lane a priority class. Every scheduling decision is a bitwise operation on a Smi.

the operations

Assign: an update's lane comes from its event: discrete events (click, keydown) → SyncLane; continuous events (mousemove, scroll) → InputContinuousLane; everything else → DefaultLane; startTransition → the next free TransitionLane (a rotating pool of 16); useDeferredValue → a transition lane; retries after Suspense → RetryLanes; offscreen content → OffscreenLane.
Record: fiber.lanes |= lane; walk up setting childLanes |= lane so a parent knows some descendant has work; root.pendingLanes |= lane.
Select: getNextLanes(root): the highest-priority pending lane (lowest set bit, via lanes & -lanes), expanded to include all lanes of the same priority group, plus any lanes entangled with it, plus expired lanes. The result is renderLanes.
Render: walk the fiber tree; a fiber with (fiber.lanes | fiber.childLanes) & renderLanes === 0 is skipped entirely (bailout). Updates whose lane is not in renderLanes are left in the queue for a later render. This is how a transition render ignores a pending sync update and vice versa.
Interrupt: between units of work, if root.pendingLanes contains a lane of higher priority than renderLanes, abandon the current work-in-progress tree and start over with the higher lanes. The abandoned render's fibers keep their alternate state, so the restart reuses what it can.
Commit: on finishing, root.pendingLanes &= ~renderLanes; the remaining bits schedule the next render.
Expire: each pending lane gets an expiration time when first seen; a lane past its time is rendered synchronously and uninterruptibly on the next pass. Starvation protection.
Entangle: transitions that update the same state are ORed into an entanglement mask so they render together and never show an intermediate state.

why it is this and not a priority queue

Cost: every operation is one or two integer instructions on a Smi; a queue would allocate and compare per update.
Batching falls out: updates in the same lane are rendered together by construction; no explicit batching logic for events.
Partial rendering falls out: "render only these lanes" is a mask test per fiber.
The limit: 31 lanes. Transitions share 16 and wrap around; two unrelated transitions can share a lane and then render together. In practice invisible.

underneath

The scheduler package (part 1's heap) holds the callback that performs a render at a given priority; lanes decide what that render includes. Two data structures: a heap for "when", a bitmask for "what".

REACT'S LANE MODEL

priorities as a bitmask, batching as a bitwise OR

swipe the figure sideways, or tap expand for full screen

1/6

the lanes

The lanes, from highest priority (bit 0) to lowest: SyncLane (1), InputContinuousLane (4), DefaultLane (16), then a block of TransitionLanes (bits 7 to 22), RetryLanes, SelectiveHydrationLane, IdleLane, OffscreenLane. 31 bits in a number: a Smi, so the operations are integer ops (the JS course part 6).

Cooperative scheduling: slices, deadlines, and where to yield

JavaScript cannot be pre-empted; a long task holds the main thread until it returns. The only way to keep a page responsive during heavy work is to make the work cooperative: split it into units, check a deadline between units, and yield to the event loop when the slice is spent or input is waiting. React's concurrent rendering, every virtualised renderer's chunked mount, and the platform's own scheduler.yield() are this algorithm.

code

// a long job, made cooperative (works today in Chrome; falls back elsewhere)
const yieldToMain = () => 'scheduler' in globalThis && 'yield' in scheduler ? scheduler.yield() : new Promise(r => setTimeout(r, 0))
const inputPending = () => navigator.scheduling?.isInputPending?.() ?? false

async function processAll(items, work, { slice = 5 } = {}) {
  let start = performance.now()
  for (const item of items) {
    work(item)
    if (performance.now() - start > slice || inputPending()) { await yieldToMain(); start = performance.now() }
  }
}
// what this costs: an await per yield (a microtask hop + a task); the loop variables carry the state. generators do the same with less syntax.
// what it does not do: make the work smaller. 200 ms of work is still 200 ms of CPU; it is spread so input and frames fit between.

// priorities (Prioritized Task Scheduling API)
scheduler.postTask(() => prefetchNextPage(), { priority: 'background' })     // runs when nothing user-facing is pending
scheduler.postTask(() => applyFilter(), { priority: 'user-visible' })        // default
scheduler.postTask(() => respondToClick(), { priority: 'user-blocking' })    // ahead of everything but input itself
// with a signal: TaskController to abort or change priority; postTask returns a promise of the callback's result

the parameters

Unit size: the granularity at which the deadline is checked. One fiber in React; one row, one token, one chunk of a file in your own code. Too small and the check itself costs; too large and a single unit can exceed the slice.
Slice length: how long to run before yielding. 5 ms (React) keeps input delay under a frame; 50 ms is the long-task threshold. isInputPending() lets the slice run long when the queue is empty and yield at once when it is not.
Where the continuation lands: scheduler.yield(): the front of the same priority, so the job continues right after whatever pre-empted it. MessageChannel: the back of the normal queue, no clamp. setTimeout(0): the back, plus a 4 ms clamp when nested: never for this. requestAnimationFrame: the next frame, which pins the job to the frame rate (fine for visual work, wrong for CPU work).
Priority of the job itself: scheduler.postTask with background for work the user is not waiting on; user-visible for work that updates what they see; user-blocking only for the response to their action.

the trade, in numbers

A 200 ms job in 5 ms slices: ~40 yields at ~20 µs each: ~1 ms of overhead; the job finishes at ~215 ms because input and frames ran in between; maximum input delay 5 ms; every frame hit.
The same in 50 ms slices: 4 yields; finishes at ~205 ms; maximum input delay 50 ms; three frames missed per slice.
Unsliced: finishes at 200 ms; input delay up to 200 ms; 12 frames missed.
The job does not get smaller. If the CPU time is the problem (a phone takes 800 ms for the same job), slicing keeps it responsive but not fast; a worker (the browser course part 7) moves the time off the main thread; a smaller algorithm (part 0 of this course) removes it.

COOPERATIVE SCHEDULING WITH A DEADLINE

slicing a 200 ms job so input never waits more than 5 ms

swipe the figure sideways, or tap expand for full screen

1/6

one task

The job: 200 ms of work as one task. The user clicks at 30 ms. The click handler cannot run until the task ends at 200 ms: 170 ms of input delay. The frame at 16 ms is also missed; the page is frozen for 200 ms. INP: 200+ ms (the browser course part 12).

Idle time, deadlines, and the platform API

code

// requestIdleCallback: run only in a frame's slack, with a deadline object
requestIdleCallback(deadline => {
  while (deadline.timeRemaining() > 0 && queue.length) work(queue.shift())   // timeRemaining: ms left before the next frame is due (≤ 50)
  if (queue.length) requestIdleCallback(cb)                                   // re-schedule the rest
}, { timeout: 2000 })                                                         // run anyway after 2 s even if never idle (anti-starvation)
// the scheduler's view: an idle task is lowest priority; it runs only when the frame has slack (no pending input, no frame work, no normal tasks)
// uses: analytics, prefetching, pre-rendering offscreen content, warming caches. not for anything the user is waiting on.
// Safari did not ship it for years (now has it); scheduler.postTask with 'background' is the standard replacement

idle scheduling

requestIdleCallback: the callback runs when the frame has slack: after rendering, before the next frame is due, with no higher-priority tasks pending. The deadline.timeRemaining() (up to 50 ms) is how long the callback may run before it would delay a frame. A timeout option forces it to run eventually.
What "idle" means to the scheduler: the idle queue is selected only when every other queue is empty and the next frame is not due. On a busy page it may not run for seconds; the timeout is the floor.
Uses: work with no user waiting: analytics batching, prefetching the next route's data, pre-computing a search index, warming a cache, rendering offscreen content ahead of time. Anything with a deadline of its own should use postTask with a priority and a timeout instead.

deadline scheduling, generally

Earliest deadline first (EDF): always run the task whose deadline is soonest; optimal for meeting deadlines on one processor when it is possible at all. React's expiration times approximate it: a pending lane's expiration is its deadline, and expired lanes jump the queue.
Aging: raise priority with waiting time, so that low-priority work is not starved. The browser's anti-starvation boosts and React's expirations are both aging.
Admission: refuse or shed work when the system cannot meet deadlines: a renderer that drops intermediate frames of a fast-changing input (only the latest value matters) is shedding; useDeferredValue is admission control for renders.
The analogue in Node: no priorities; the pattern is to keep each callback short and use setImmediate to yield between chunks (it runs in the check phase, after I/O, before timers of the next loop), or to move CPU work to worker_threads.

the Prioritized Task Scheduling API, in one place

scheduler.postTask(cb, { priority, delay, signal }): three priorities, optional delay, abortable via a TaskController whose priority can also be changed after posting (controller.setPriority). Returns a promise of the callback's result.
scheduler.yield(): a promise that resolves as a continuation at the front of the current task's priority. The correct way to break up a long task.
navigator.scheduling.isInputPending({ includeContinuous }): whether an input event is waiting; lets a slice decide to yield early.
Support: Chromium shipped; others partial. Feature-detect and fall back to MessageChannel for yielding and setTimeout for delays.

the pointer

Part 6 is V8's own algorithms as algorithms: the transition tree as a trie, inline cache lookup as a tiny polymorphic dispatch, generational collection as copying, mark-sweep with the tri-colour invariant, incremental marking with a write barrier. The JS course drew them as mechanism; this part names the algorithm under each.

Scheduling: measuring and the comparison

Scheduler	Structure	Selection	Pre-emption	Starvation guard	Where
Browser event loop (Chrome)	~20 FIFO queues with dynamic priorities	Highest-priority non-empty queue; frame task at vsync	None (task boundaries only)	Age-based boost per queue	Every page
Node (libuv)	Phase queues: timers, pending, poll, check, close	Fixed phase cycle; nextTick and microtasks between callbacks	None	Phase rotation; poll timeout bounded by the next timer	Every Node process
React scheduler package	Two binary heaps (by expiration, by start time)	Pop-min; 5 ms slices; shouldYield	Cooperative (returns a continuation)	Expiration times by priority	React 18+ concurrent features
React lanes	31-bit mask per root and per fiber	Lowest set bit, expanded by group, entanglement, expiration	Restart on higher lane (between units)	Expired lanes render sync	Inside the reconciler
Prioritized Task Scheduling	Three priority queues per page	Priority, then FIFO; yield() continuations at front	Cooperative	Host anti-starvation	Your code, in Chromium
requestIdleCallback	The idle queue	Only when everything else is empty and no frame is due	Deadline object	timeout option	Deferrable work
Signals (Solid, Preact, Angular)	Dependency graph with dirty marks	Pull on read; recompute in topological order (part 1)	Synchronous by default; batched updates	Not applicable	Fine-grained reactivity

Question	Tool	What to read
Is a long task blocking input?	Performance → Interactions track; long-task red markers; the Main lane	Input delay (the first segment of an interaction) against the task that was running
Did yielding help?	Performance before and after slicing	Many short tasks with input and frames between them, versus one long block
What priority did a task get?	Performance → task tooltips (Chrome shows scheduler priority in recent versions); `scheduler.postTask` promise timing	Whether background work ran during an interaction
Which lane did React render?	React DevTools Profiler → lane labels on each commit (Sync, Transition, Default)	A transition that rendered as Sync (an expiration, or a non-transition update entangled)
Is a transition being interrupted repeatedly?	React Profiler: many discarded renders before a commit	Input arriving faster than the transition can finish; the job is too big for the slice budget
Does the idle work ever run?	Performance; a counter inside the idle callback	Starvation on a busy page; use the timeout or postTask