Source-linked AI summary
SchedBlame: Who Ran While You Waited? Culprit-Attributed CPU Contention for Containers on Stock Kernels
Hao Li, Tonghao Zhang, Honglei Wang
TL;DR
SchedBlame addresses the lack of deployed signals that identify which co-tenant causes a container’s CPU wait by continuously attributing contention on stock kernels. Its bitmap-based attribution runs in production with about 1% Redis-throughput overhead and 6% of one core on a 96-core host tracking 84 containers.
Problem
Existing CPU signals report that a container waited but do not identify which co-tenant took its CPU.
Method
SchedBlame uses a per-CPU bitmap stamped onto completed run slices to charge competitor CPU time to waiting victims without enumerating cross-product pairs on the scheduler hot path.
Results
About 1% of Redis throughput and 6% of one core on a 96-core host tracking 84 containers, running on unmodified 4.18 and 5.10 kernels.
Takeaways & Limitations
Self-describing records and separated state maintenance let SchedBlame remain continuously deployed while sampling trades cost for variance without a correctness cliff.
Takeaways & Limitations
SchedBlame measures CFS runqueue contention, so it under-attributes hosts with significant real-time or deadline work and excludes shared-cache, memory-bandwidth, and SMT contention.
Abstract
from arXiv · showhide
Containers that share a machine compete for CPU. When one slows down, the operator needs to know which co-tenant is responsible, and no deployed signal can say. Pressure stall information, per-cgroup wait counters, and run-queue latency histograms are all victim-side: they report that a container waited, never who it waited for. Recovering the culprit means a kernel patch, full scheduler tracing, or statistical inference: unportable, too costly to leave on, or unreliable when victims coexist. SchedBlame is an eBPF tracer that attributes CPU contention to the cgroups that caused it, on stock kernels, continuously. It inverts the accounting: instead of measuring how long a victim waited, it measures the CPU time every other cgroup consumed while that victim was runnable but not running on the same CPU. The mechanism is a per-CPU bitmap of which measured cgroups are waiting, maintained from the kernel's own runnable counts at four scheduler hooks. Every run slice carries that bitmap, so one 16-byte record charges CPU time to a full row of a competitor x victim blame matrix; the kernel stores no per-pair state. Three properties follow. Slices are self-describing, so userspace holds no waiting state and a lost record costs measurements, not correctness. The measured set is reconfigured by publishing an epoch, invalidating every cache and per-CPU bitmap in constant time while the hooks keep running. Sampling never touches waiting state, so rescaling by the inverse keep probability keeps the estimator unbiased. SchedBlame splits each container's per-second CPU demand into runtime, internal contention, external contention, and throttling, flags anomalies against a rolling 99th-percentile baseline, and names the competitors responsible. In production on unmodified 4.18 and 5.10 kernels, tracking 84 containers on a 96-core host, it costs about 1% of Redis throughput and 6% of one core.
1 Introduction
SchedBlame addresses the missing culprit identity in victim-side CPU contention signals by observing which cgroups run while measured victims are runnable but not running. Its bitmap-based, self-describing tracer supports continuous attribution with bounded overhead, reconfiguration, and unbiased sampling.
- Problem: Existing CPU contention signals report how long a container waited but not which co-tenant was running during that wait.PSI, scheduler statistics, quota reports, and run-queue tools are all victim-side.
- Inversion: SchedBlame treats contention as CPU-level responsibility, measuring other cgroups’ runtime while a victim remains runnable and not running.This changes attribution from statistical correlation to an observation at the scheduling event.
- Mechanism: A per-CPU bitmap lets each completed run slice charge one competitor’s CPU time to every waiting victim in a single 16-byte record.The measured victim set is dense and bounded, while potentially blamed cgroups use sparse kernel identities.
- Deployability: Self-describing slices make userspace stateless and limit a lost record’s cost to the CPU time in that slice.The next slice carries a fresh waiting snapshot, so userspace need not reconstruct transitions.
- Deployability: Epoch publication invalidates caches and per-CPU waiting bitmaps in constant time without scanning, draining, or pausing concurrent hooks.This supports measured-set changes as containers come and go.
- Deployability: Sampling affects only observed completed slices, so inverse-probability rescaling preserves unbiasedness while trading CPU cost for variance.Waiting-state maintenance remains unconditional.
- Output: SchedBlame separates runtime, internal contention, external contention, and throttling, then flags anomalies against a rolling 99th-percentile baseline and ranks responsible competitors.External contention is the third demand term divided by total demand.
2 Background and Problem
Stock-kernel CPU signals quantify victim-side waiting, while existing alternatives trade away portability, continuous operation, or reliable culprit identity. SchedBlame’s requirements therefore combine culprit-attributed time, bounded stock-kernel instrumentation, continuous deployment, and degradation without persistent corruption.
- Kernel background: Linux’s runnable-state counters and runqueue locks provide consistent per-CPU waiting snapshots for SchedBlame’s measurements.h_nr_running includes the selected entity, and scheduler mutations occur under the runqueue lock.
- Kernel background: Throttling is distinct from contention because the group’s own quota forbids execution rather than another cgroup taking the CPU.SchedBlame accounts quota throttling separately.
- Existing signals: Deployed signals such as PSI, wait counters, quota reports, and run-queue histograms all describe the victim rather than naming a cause.Their differences in granularity and cost do not change their victim-side perspective.
- Alternatives: Kernel patches provide precise decomposition but are difficult to maintain across heterogeneous fleets and make the signal depend on the kernel build.The alternative is therefore not portable as a monitoring-tool capability.
- Alternatives: Full scheduler tracing recovers culprits but produces too much continuous per-event delivery and storage overhead for bursty contention.Such tools are generally diagnostic instruments attached after a problem is known.
- Alternatives: Statistical attribution deploys easily but becomes inconsistent when several victims coexist and share contention.Correlation cannot reliably distinguish co-ramping containers in that setting.
- Alternatives: Existing scheduler-event approaches either establish only that contention came from outside or tag a single preemption rather than accumulated culprit time.Preemption tagging can miss starvation when a victim is never selected while several groups run in turn.
- Requirements: The target requirements are culprit attribution, stock-kernel operation, continuous low overhead, bounded state, non-corrupting degradation, and demand-normalized output.These requirements make responsible cgroups and comparable contention ratios operationally visible.
3 Blame the Runner
SchedBlame defines contention as competitor runtime coinciding with a target’s runnable-but-not-running state, then records that coincidence efficiently as blame-matrix rows. Its demand decomposition separates external competition from self-inflicted queueing, throttling, and runtime.
- Formulation: SchedBlame measures how much CPU time each competitor consumed while a target was runnable but not running.The blame quantity is expressed in CPU-nanoseconds and directly ranks culprits.
- Demand decomposition: External contention sums competitor-target coincidence, while same-target coincidence measures internal contention caused by the target’s own parallelism.High internal contention with low external contention indicates self-oversubscription rather than interference.
- Demand decomposition: Each target’s demand is divided into runtime, internal contention, external contention, and throttling.Every demand unit belongs to exactly one category.
- Demand decomposition: The external contention ratio is the fraction of wanted CPU taken by external competition, making it comparable across containers with different sizes and activity levels.The ratio is based on external contention divided by total demand.
- Measurement choice: The indicator counts one waiting opportunity per target and CPU, not one unit per queued task.This enables a single bitmap bit per target, but diverges from task-weighted wait when runnable parallelism changes sharply within an interval.
- Cheap measurement: A completed run slice carries the waiting bitmap at its ending boundary, so one fixed-size record charges one competitor against every waiting target without enumerating pairs.The kernel stores no per-pair state and performs no work proportional to the number of targets.
4 In-Kernel Design
The in-kernel design reconstructs waiting state from kernel runnable counts at scheduler hooks and represents measured targets as a per-CPU bitmap. Epoch-tagged publication makes reconfiguration constant-time, while self-describing slices and sampling preserve correctness under drops and unbiased subsampling.
- Waiting state: The tracer keeps one per-CPU state item: the set of measured targets waiting on that CPU.Its state is O(CPUs), independent of the number of tasks or containers, and can be discarded and rebuilt.
- Packed representation: A 20-bit base field plus one extension word supports 84 targets in a 16-byte slice; the byte-sized dense identifier permits up to 212 targets.The base field shares a 64-bit word with competitor identity and slice duration.
- Waiting state: SchedBlame recomputes waiting bits from h_nr_running at scheduler hooks instead of maintaining transition counters.A missed update is repaired by the next observation rather than corrupting accumulated state.
- Scheduler hooks: Hook ordering lets the tracer stamp completed slices before updating switch state and safely reconstruct wakeup, migration, and throttling effects.The design uses runqueue-lock invariants across 4.18 and 5.10; migration repairs the source bit while the destination is reconstructed later.
- Reconfiguration: Epoch publication invalidates every identity cache and per-CPU waiting bitmap without scanning, draining, or pausing concurrent hooks.A new epoch also permits immediate dense-slot reuse while stale in-flight results are discarded.
- Loss tolerance: Self-describing slices leave userspace stateless and make a lost record cost only the CPU time in that slice.Because sampling does not alter waiting state, retained durations can be divided by keep probability for an unbiased estimator.
5 Userspace Attribution
Userspace decodes self-contained slices into runtime, internal and external contention, throttling, and competitor charges, then evaluates target-relative anomalies each second. Reports provide the decomposition, baseline comparison, and ranked competitors without blocking the measurement runner.
- Attribution pipeline: The runner serially owns attribution state, interval evaluation, target synchronization, and report assembly to produce consistent snapshots.Concurrent lifecycle callbacks only signal work, while uploads receive immutable documents.
- Slice attribution: Userspace unpacks each slice, rescales duration by 1/p, and adds it to runtime, internal contention, or competitor-target charges according to the snapshot bits.Unknown competitor identities are discarded, and throttle records contribute directly to throttled time.
- Charge matrix: The charge matrix is a flat 4096 × M array, allocated once; at M=84 it occupies 2.6 MiB.Set-bit iteration costs are proportional to targets actually waiting, and each cell update is a contiguous indexed add.
- Interval evaluation: Every second, userspace computes total wait W=I+E+T, total demand D=R+W, and external contention ratio r=E/D for each active target.Intervals with zero demand are skipped.
- Anomaly detection: Anomalies are baseline-relative: each target’s current ratio is compared against its rolling history rather than a fixed absolute threshold.The history retains 600 valid ratios and requires at least 60 samples before reporting; K defaults to 1.0.
- Reports: Each report includes R, I, E, T, the ratio, baseline, threshold, ranked competitors, and the CPU-nanoseconds attributed to each.Reports are queued asynchronously, and a full queue drops new reports instead of blocking the runner.
- Target management: Target selection preserves dense slots for surviving eligible containers and refreshes assignments when lifecycle notifications arrive or every 60 seconds.Stable slots preserve each target’s 600-sample ratio history.
6 Estimator and Cost Model
SchedBlame uses inverse-probability sampling to reduce observation and transport cost while preserving unbiased estimates under configured sampling. Its overhead is controlled by sampling probability, but short events and uncompensated transport loss limit accuracy.
- Estimator: Sampling retains completed slices with probability p and rescales their durations by 1/p, yielding an unbiased estimator under the sampling design.The estimator’s variance increases as sampling becomes more aggressive.
- Estimator: At p = 0.1 with n = 1000 contributing slices, the relative standard error is about 9.5%.Precision depends on the number of contributing slices, not sampling rate alone.
- Estimator: Short contention events may contribute too few slices, so aggressive sampling degrades their estimates first.A one-second interval can contain no sampled contributing slices for brief waits.
- Limitations: Configured sampling does not compensate for full perf rings or failed batch submissions, so sustained transport loss biases estimates downward.Exported counters expose this error rather than hiding it.
- Cost model: Kernel work is constant per context switch, with no loop over targets, no per-task lookup, and sampling-dependent snapshot copying.Perf submission occurs once per 128 retained slices.
- Cost model: Userspace attribution costs O(|{t: w_t = 1}|), proportional to waiting targets in each snapshot rather than total target capacity.Kernel memory is fixed by compile-time bounds, while the charge matrix dominates userspace memory.
- Cost model: At C = 64, f = 2000, p = 1, and extra = 1, transport produces 128 K slices per second and about 2 MB/s in 1000 perf records.Sampling controls this transport volume.
7 What SchedBlame Gets Wrong
SchedBlame documents approximation, scope, and transport limits that affect how its contention ratios and blame assignments should be interpreted. The most consequential boundary is that ancestor-imposed throttling can appear as external contention.
- Accounting limits: SchedBlame’s accounting taxonomy explicitly records each approximation, its error direction, and the conditions under which it matters.This error model defines where reported ratios should be trusted.
- Accounting limits: Demand is measured per affected CPU rather than per queued task, so rapidly changing parallelism can make opportunity loss diverge from aggregate lost task time.The two measures differ by a factor that cancels when per-CPU runnable counts remain stable.
- Accounting limits: Ending-boundary snapshots charge a slice according to its state at completion, creating an error bounded by one slice duration per transition.The error is unbiased over many transitions but grows with slice length.
- Accounting limits: If K·P99 reaches 1, anomaly reporting is suppressed until the baseline or K falls.This can silence alerts for persistently severe contention.
- State and scope: Migration, task moves, and epoch resets can leave bitmap state stale or under-reported until a later scheduling event rebuilds it.Task-group moves may leave stale bits indefinitely if no later event references the group.
- State and scope: The tracer measures at most M containers and excludes CSS IDs above 4095 from both measurement and blame attribution.Dense-slot reuse and lifecycle lag can also misattribute in-flight data or delay classification updates.
- Transport limits: Lost transport records bias estimates downward because configured sampling correction does not compensate for loss correlated with load.Delayed partial batches can also shift work into the interval when they arrive.
- Throttling limits: Ancestor-imposed quota loss may be attributed as external contention because only throttling applied directly to the target’s own cfs_rq is observed.This is the most consequential misattribution when deployments impose quota at a parent cgroup.
8 Implementation
The implementation runs on unmodified 4.18 and 5.10 kernels by using verifier-compatible, compile-time-bounded BPF structures and perf-event transport. Runtime configuration remains flexible, while diagnostic counters expose transport and accounting errors.
- Implementation: SchedBlame comprises about 1,000 lines of BPF C and 3,100 lines of Go, and runs on unmodified 4.18 and 5.10 kernels.The shared container-discovery interface is excluded from these counts.
- Kernel compatibility: Because the BPF ring buffer is unavailable before 5.8, the implementation uses a per-CPU perf event array.Compile-time verifier constraints require power-of-two partial-batch capacities.
- Kernel compatibility: Successful unthrottling is handled with an entry/return kprobe pair because no suitable tracepoint exposes the affected runqueue.This choice supports the older kernel targets.
- Configuration: Bitmap width and target capacity M = 20 + 64 extra are fixed at compile time, while keep probability, batch size, ring sizing, and polling remain runtime settings.Userspace validates map and batch-header widths before operation to prevent misattribution.
- Diagnostics: About a dozen counters expose submission failures, ring loss, invalid runnable counts, saturation, CSS-ID overflow, upload drops, and queue occupancy.Transport loss is visible because the estimator does not compensate for it.
9 Preliminary Evaluation
The preliminary production evaluation measures deployment cost rather than accuracy or detection quality. On a 96-core host tracking 84 containers at full sampling, the tracer adds about 1% Redis throughput cost and 6% of one core, while detection quality remains unevaluated.
- Setup: The preliminary measurements come from a 96-core Intel Xeon production host tracking 84 containers with sampling disabled at p = 1.The configuration exercises the default build’s widest snapshot and largest charge matrix.
- Cost: About 1% of Redis throughput is lost when SchedBlame’s scheduler hooks are attached.No significant p99 latency change was observed.
- Cost: Approximately 6% of one core is consumed by the userspace tracer, equivalent to about 0.06% of the 96-core machine.This is an upper bound because sampling and contention reduce userspace work.
- Transport: Peak perf-ring occupancy was about 1%, while the shared userspace queue reached about 15% of capacity.The userspace queue is the tighter backpressure indicator as target counts or machine sizes grow.
- Interpretation: Together, the measurements indicate roughly 1% application-throughput cost and a fifteenth of a core per machine at full sampling.These figures characterize cost, not accuracy or detection quality.
- Evaluation boundary: Operational experience finds anomaly reports most valuable for bursty contention, but detection quality has not been evaluated against a labelled set.The planned evaluation includes accuracy, sampling behavior, hook cost, detection quality, scaling, and comparison experiments.
10 Limitations and Future Work
SchedBlame’s current scope is bounded by scheduler class, hierarchy, kernel version, cgroup structure, and approximation choices. Future work targets broader attribution, validation, and action.
- Scope: SchedBlame measures CFS runqueue contention, under-attributing hosts where real-time work consumes CPU and excluding cache, memory-bandwidth, and SMT interference.Hardware-counter techniques are complementary for microarchitectural interference.
- Scope: Only cgroup v1 has been tested; validating cgroup v2 and its unified hierarchy layout is the immediate next step.
- Scope: Deployment targets kernels 4.18 and 5.10, while each newer kernel requires re-verifying the ordering invariants that support correctness.The design trades kernel-patch portability for an ongoing verification obligation.
- Scope: A target is exactly one CPU cgroup, so containers with descendant cgroups require explicit descendant selection rather than one aggregated dense slot.Subtree aggregation is possible but would break the one-to-one task-group-to-dense-ID mapping.
- Approximation gaps: Ancestor bandwidth throttling is currently charged as external contention and requires hierarchical throttle-state observation to correct.
- Approximation gaps: The one-bit indicator sacrifices task-weighted demand; recovering fidelity would require carrying small saturating counters instead.
- Future work: SchedBlame produces culprit signals but does not act on them; feeding its blame matrix into placement or throttling is the proposed next system.
11 Related Work
Prior work detects victim disruption, tags individual preemptions, or infers antagonists statistically, but does not provide SchedBlame’s direct full-interval culprit attribution. SchedBlame also separates state maintenance from sampled measurement to preserve unbiased estimation.
- Victim-side signals: Victim-side signals quantify CPU suffering but do not name its cause, motivating SchedBlame’s culprit-oriented attribution.
- Scheduler-event instrumentation: Volpert et al. separate external from self-inflicted disruption using scheduler metrics, but observe only the victim cgroup and cannot identify the disturbing cgroup.Their evaluation reports eight Kubernetes contention scenarios and no overhead figures.
- Scheduler-event instrumentation: Netflix’s tracer tags the cgroup of the outgoing task at each preemption, whereas SchedBlame charges every cgroup running throughout the victim’s waiting interval.SchedBlame also covers non-preemptive starvation episodes.
- Statistical attribution: Correlation-based methods such as CPI2, PANDA, and Granger-causality approaches infer antagonists from resource time series, with shared victims making correlation-based attribution inconsistent.
- Interference-aware placement: Interference-aware placement and isolation systems consume signals derived from profiling or correlated metrics, while SchedBlame directly observes runqueue contention.
- Resource attribution: SchedBlame answers whose resource use denied CPU to whom, complementing profilers that identify who used the resource.
- Sampling: Separating state maintenance from measurement enables uniform sampling with inverse-probability rescaling, avoiding biased, load-dependent event dropping.
12 Conclusion
SchedBlame turns CPU contention from victim-side scalar measurement into direct competitor attribution by observing other cgroups’ runtime while a victim waits. Its deployable design supports continuous operation with low reported overhead on stock kernels.
- Contribution: SchedBlame measures every other container’s CPU time while a container is runnable but not running, making blame an observation rather than an aggregate-metric inference.
- Design: Sparse blamed identities, dense measured identities, self-describing slices, and separated sampling make the cross-product accounting deployable and loss-tolerant.These choices also allow continuous operation for bursty contention.
- Deployment: SchedBlame runs on unmodified 4.18 and 5.10 kernels in production, costing about 1% of Redis throughput and 6% of one core while tracking 84 containers on a 96-core host.The implementation is planned for open-source release.