Tick Accounting and How a Slice Is Measured

Every scheduling policy in this cluster assumes the kernel knows how much CPU time each thread has consumed. Fair-share schedulers divide by accumulated time, deadline schedulers subtract remaining budget from it, and a preemptive policy needs a way to notice that a slice has run out. None of that time is measured directly. There is no counter in the CPU that says “this thread has executed 3.7 milliseconds”; the kernel constructs the number from a periodic event and a subtraction.

That construction is where most of the interesting errors live. Time is attributed at a granularity set by the timer, it is charged to whoever happened to be running when the sample was taken, and it is divided into categories that do not always correspond to what the thread actually did. A scheduler built on top of a sloppy clock will make defensible decisions from bad inputs.

The interrupt as the clock source

The classic arrangement is a timer that fires at a fixed frequency: historically 100 Hz, later 250 Hz or 1000 Hz on desktop-oriented configurations. Each firing runs a kernel routine on the interrupted CPU which increments a counter of elapsed intervals and, under a scheduler that measures slices in ticks, decrements the current thread’s remaining slice. When the remaining slice reaches zero the routine sets a flag that causes the scheduler to run on the way out of the interrupt.

The tick rate sets the resolution of anything derived from it, but not the slice length itself, which a policy chooses in its own units. A scheduler that arms the timer for a 6 millisecond slice on a 1000 Hz tick fires it after six ticks and preempts on the last; a scheduler that charges a tick to the running thread at 100 Hz attributes time in 10 millisecond units. The two quantities are easy to confuse because they are both called “a tick”, and the second is the one that accounts for CPU time.

That attribution is coarse. A thread that runs for 4 milliseconds and blocks has, from the sampler’s point of view, consumed either zero ticks or one, depending on where the boundaries fell. Charge it one tick of a 100 Hz clock and it is over-charged by 6 milliseconds; charge it zero and it is free. Averaged over many runs the error cancels, but the variance does not, and a policy that reacts to short bursts, such as an interactive responsiveness heuristic, sees mostly noise.

The tick’s cost is also not negligible at high rates. At 1000 Hz each CPU takes a thousand interrupts a second, each of which saves state, runs a handler, and returns; the aggregate is a measurable fraction of a percent of the machine, and on an otherwise idle CPU a periodic tick prevents the deepest idle states, because the next interrupt is always imminent.

Sampling versus switch-time accounting

There are two ways to turn the tick into per-thread numbers, and the choice determines the error profile.

Sampled accounting charges one tick to whatever thread is running at the instant of the interrupt. It is cheap, a pointer dereference and an increment, and it is what a profiler wants, because the sample is an unbiased draw from the execution. It is also what makes short-lived threads nearly invisible: a thread that lives for less than a tick may be charged nothing at all, and if it wakes, runs, and blocks repeatedly, its total charge can be zero while it consumes real CPU.

Switch-time accounting reads a free-running timestamp counter at every context switch and charges the difference to the thread that was running. Its granularity is the counter’s, which on x86-64 is sub-nanosecond, so no time is lost to rounding. It costs a read of the timestamp register plus a subtract on every switch, which at high switch rates is itself measurable.

Most general-purpose kernels combine the two: sampled ticks for preemption decisions and coarse statistics, switch-time deltas for accurate per-thread totals. The combination has a subtlety. If the tick handler also updates the per-thread total, and the switch path updates it again, the same interval can be counted twice unless the tick path first refreshes the switch baseline. Kernels that get this wrong produce user-visible totals slightly larger than wall-clock elapsed time.

/* Switch-time accounting. now() reads the CPU timestamp counter.
   The tick handler must also advance prev_stamp when it charges the
   running thread, or the interval is counted twice. */
static void account_switch(struct thread *prev, struct thread *next)
{
    uint64_t now = read_tsc();
    uint64_t delta = now - prev->stamp;     /* ticks since prev last charged */
    prev->cpu_ns += tsc_to_ns(delta);
    prev->stamp  = now;
    next->stamp  = now;                     /* next starts accruing here */
}

The arithmetic has to be careful about the counter’s width. A 64-bit timestamp counter at a few gigahertz wraps after decades, which is fine for accounting but not for comparing absolute values across a wrap, so the conversion to nanoseconds cannot be derived by multiplying the raw counter straight away; the multiplication must be split so that the low bits and the high bits are scaled separately and recombined. A 32-bit counter at the same rate wraps every couple of seconds, and the delta computed by plain unsigned subtraction is still correct across the wrap provided the true delta is smaller than half the counter’s range. That constraint is the real limit: a thread descheduled for longer than about a second on a 32-bit counter cannot be accounted correctly by subtraction alone, and the kernel must instead read a wider clock when it notices a suspicious delta.

Tickless operation and its accounting hole

A kernel that idles for long stretches does not want a thousand pointless interrupts per second, so modern designs stop the periodic tick when a CPU goes idle and program a one-shot timer for the next event that actually matters: the running thread’s slice expiry, the next timeout in a timer wheel, or nothing at all if the CPU is genuinely idle.

This creates an accounting gap. With no ticks, a CPU that is idle accumulates no samples, which is correct for the idle thread’s total but breaks any statistic derived from “the fraction of samples in which thread X was running”. The kernel must therefore track idle time explicitly, reading the timestamp counter on entry to and exit from idle, and it must distinguish idle time from time the CPU spent in a shallow sleep from which it was woken by an interrupt.

The same one-shot machinery has to serve preemption. When a thread is selected, the kernel programs the timer to fire no later than the end of its slice, and re-programs it whenever a shorter deadline appears, so preemption granularity becomes the resolution of the timer hardware rather than the tick rate. This is better for latency and worse for predictability: the interrupt arrives at a time determined by the slice, which depends on priority, which depends on history, so the pattern of interrupts on a busy machine is no longer uniform.

Stolen time and the virtualised case

Under a hypervisor the guest’s view of time diverges from the host’s. A guest CPU that is runnable but descheduled by the hypervisor is not executing and not idle; the guest kernel’s own timestamp counter reads keep advancing, because the counter is virtualised and typically continues across the preemption, so a naive delta charges the guest thread for time it never ran.

The standard fix is a separate counter that the hypervisor maintains for exactly this purpose: the guest reads how much time was stolen from it and subtracts that from its accounting. The guest then reports three categories rather than two (user, system, and steal), and the scheduler’s fairness accounting uses only the first two. Without this, a guest with two virtual CPUs on a contended host will believe its threads are consuming far more CPU than the host is granting, and a fair-share scheduler will see every thread as having been served in full and will stop favouring any of them on the basis of elapsed service.

The timestamp counter is also a weak reference across CPUs, for a different reason than virtualisation. The counter’s rate is set by the core’s own clock, and on some hardware the cores do not tick it in lockstep; a thread migrated between them can observe the raw counter drift or, on older designs, jump. Kernels compensate by keeping a per-CPU offset and a scale factor that map the local counter onto a global time base, updated at calibration and applied at migration, and by treating the raw counter as meaningful only for deltas taken on one CPU. This is one of the reasons migration is not a pure pointer move; the bookkeeping that travels with a thread includes its clock baseline, as described in Load Balancing and Thread Migration on Symmetric Multiprocessors.

What the categories hide

The split between user and system time is a split by privilege level at the sample, not by cause. A thread that issues a system call which blocks, so that the kernel deschedules it and runs something else, is charged for the kernel time before the block and nothing after. A thread that causes the kernel to do work on its behalf asynchronously, such as a writeback or a network receive processed in softirq context, is charged nothing for that work, because the softirq runs on whichever CPU took the interrupt and is accounted to that CPU’s current thread or to a separate per-CPU bucket.

The consequence is that per-thread CPU totals are a poor basis for capacity planning and a good basis only for relative fairness within the scheduler. They also make a class of misbehaviour hard to see: a thread that is runnable but never selected shows up as zero CPU time and a growing wait time, and the wait time is the only signal that it is starved. Any diagnostic that reads only CPU time will report a starved thread as idle, which is why the run-queue wait is tracked separately and why a scheduler relying on time-based fairness must also bound how long a thread may sit unselected. A demotion rule approaches that problem from the priority side: a thread that is ready but not running is not consuming slices, so it is not demoted, while one that runs to the end of every slice sinks, the classification trade described in Multi-Level Feedback Queues and Priority Decay.