Search Knowledge

© 2026 LIBREUNI PROJECT

Operating Systems Engineering/Protection, isolation, and synthesis
Page 26 of 29

Multicore Scalability and Observability

Amdahl bounds, lock contention, cache-line migration, sharding, RCU, kernel tracing, performance counters, and reproducible bottleneck diagnosis.

Lesson briefProtection, isolation, and synthesis · 6 h · 4 outcomes

Required knowledge

  • Threads, locks, atomic operations, memory ordering, and condition variables
  • Cache coherence, false sharing, interrupts, and scheduling
  • Statistical summaries, experimental controls, and asymptotic reasoning

Learning outcomes

  • Derive speedup and efficiency bounds from serialized work and identify where the model omits coherence and queueing costs.
  • Trace lock contention, false sharing, sharded invariants, and RCU reclamation on multiple cores.
  • Choose counters, samples, traces, and pressure signals that can discriminate competing kernel bottleneck hypotheses.
  • Design a reproducible scaling experiment and report model outputs, measurements, uncertainty, and threats separately.

Assessment target

Given an unfamiliar throughput collapse, derive competing causal models, inspect a supplied counter/trace bundle, propose a correctness-preserving redesign, and specify the experiment needed to support or reject the claim.

Scope boundary

  • Full weak-memory proofs, lock-free data-structure verification, NUMA placement policy, real-time multicore analysis, and architecture-specific PMU event catalogs are deferred.
  • The interactive curves are analytical models with stated assumptions; they are not benchmark results.

A kernel service completes 1.0 million operations per second on one core, 3.4 million on four, 4.2 million on eight, and 4.1 million on sixteen. All sixteen cores are busy. The team concludes that the operation is “CPU-bound” and adds cores.

Busy cores do not imply useful parallel work. They may spin on one lock, migrate a cache line, retry an atomic operation, handle interrupts, or run instrumentation. Scalability analysis needs a causal chain from workload to shared state to hardware event to observable delay.

Define the quantities before drawing a curve

For fixed work WW

  • throughput X(N)X(N) is completed operations per unit time on NN cores;
  • latency is elapsed time per operation, whose distribution includes tails;
  • speedup is S(N)=T(1)/T(N)S(N)=T(1)/T(N) for the same work and defined environment;
  • efficiency is E(N)=S(N)/NE(N)=S(N)/N
  • scalability is how a metric changes as a named resource or workload dimension changes;
  • contention is delay or retry caused by competition for a shared resource; and
  • serialization is work that the model permits only one participant to perform at once.

Strong scaling fixes total work. Weak scaling grows work with resources. A server saturation study may fix offered load, increase it to capacity, or keep per-core load fixed; those are different experiments.

Derive Amdahl’s bound

Normalize one-core time to 1. If fraction ss remains serial and fraction 1−s1-s parallelizes perfectly over NN cores, then

T(N)=s+1−sN,T(N)=s+\frac{1-s}{N},

so

S(N)=1s+(1−s)/N,lim⁡N→∞S(N)=1s.S(N)=\frac{1}{s+(1-s)/N}, \qquad \lim_{N\to\infty}S(N)=\frac{1}{s}.

This is an upper bound under the model. Real multicore costs can grow with NN lock handoff, coherence messages, remote memory, scheduler migration, interrupts, and queueing. Treating ss as a universal constant can hide the mechanism being diagnosed.

Worked calculation: eight percent serialized

With s=0.08s=0.08 and N=16N=16

S(16)=10.08+0.92/16=10.1375≈7.27,S(16)=\frac{1}{0.08+0.92/16} =\frac{1}{0.1375}\approx7.27, E(16)=7.27/16≈45.5%.E(16)=7.27/16\approx45.5\%.

The asymptotic bound is 12.5×12.5\times If measured speedup is 5×, Amdahl’s model does not prove that the serial fraction is exactly 16.7%; growing overhead can produce the same curve.

Retrieval checkpoint: invert the model carefully

A fixed-work experiment measures S(8)=4S(8)=4 Under the ideal Amdahl model, solve for ss Then state why this inferred value is not yet a measured lock critical-section fraction.

Reveal the inversion and caveatExpand

Solve

1s+(1−s)/8=4.\frac{1}{s+(1-s)/8}=4.

Thus s+(1−s)/8=1/4s+(1-s)/8=1/4 so 8s+1−s=28s+1-s=2 7s=17s=1 and s=1/7≈14.3%s=1/7\approx14.3\% This is an effective serial fraction in the model. It can absorb load imbalance, memory stalls, scheduling, coherence, and other overhead. Only instrumentation tying time to a lock path can identify a lock critical-section fraction.

Amdahl scalability bounds and multicore contention

0 / 4 answered

Evaluate each statement regarding Amdahl scalability bounds, lock contention, and multicore kernel behavior:

Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.

1
Adding physical CPU cores always produces linear throughput scaling if all cores report 100 percent utilization.
2
Amdahl model establishes that the maximum speedup is strictly bounded by the inverse of the serialized fraction.
3
Independent CPU cores writing to distinct variables located on the same cache line incur cache invalidation stalls.
4
Read-copy update synchronization completely eliminates the need for locks or synchronization among writers.

Predict the analytical curves

At 16 cores and 10% serialized critical work, predict the global-lock relative throughput and its infinite-core limit before changing any control. All designs will be divided by the one-core global-lock throughput, not by their own one-core result. Given a fixed RCU management/grace cost, predict whether the RCU curve may begin above, at, or below 1× on one core. Then predict its direction as the read share falls from 90% to 10%.

Interactive exploration

Watch one lock flatten a multicore speedup curve

Change core count, critical-section fraction, read share, and synchronization design. Every curve reports throughput relative to the same one-core global-lock baseline; the graph is an analytical hypothesis, not benchmark data.

one global lock · 6.4× baseline throughput at 16 cores
0×10×20×30×40×1 core64 cores
one global lock: 6.4×
eight-way sharding: 14.5×
read-optimized RCU model: 12.6×

Model assumptions: balanced shards, no cache-coherence traffic, no NUMA penalty, and an illustrative fixed RCU management/grace cost equal to 8% of read-side critical work. The RCU model moves that read work into the parallel term; it does not erase it. All values use one-core global-lock throughput as 1×. The model predicts a bottleneck; it does not replace profiling, contention traces, or correctness analysis.

Watch one lock flatten a multicore speedup curve
0×10×20×30×40×1 core64 cores

Static state: with 10% serialized work, one global lock yields 6.4× modeled speedup at 16 cores; adding cores cannot remove the serial bottleneck.

Normalize the one-core global-lock time to 1. With critical-work fraction ff read share rr within that work, core count NN and K=min⁡(8,N)K=\min(8,N) active shards, the displayed relative-throughput hypotheses are

RG(N)=1f+(1−f)/N,R_G(N)=\frac{1}{f+(1-f)/N}, RS(N)=1f/K+(1−f)/N,R_S(N)=\frac{1}{f/K+(1-f)/N},

and

RR(N)=1f(1−r)+0.08fr+((1−f)+fr)/N.R_R(N)=\frac{1}{f(1-r)+0.08fr+\big((1-f)+fr\big)/N}.

For the global lock, RG(16)=1/(0.10+0.90/16)=6.4R_G(16)=1/(0.10+0.90/16)=6.4 and the limit is 10×. The RCU expression does not delete read-side critical work: frfr moves into the parallel term. Updates f(1−r)f(1-r) remain serialized, and the illustrative 0.08fr0.08fr management/grace term is fixed with respect to core count. Therefore RR(1)=1/(1+0.08fr)R_R(1)=1/(1+0.08fr) can be slightly below the common 1× baseline. Lowering read share erodes the modeled RCU opportunity because more critical work becomes serialized update work. The sharded curve assumes balanced requests across at most eight shards.

The graph labels all three designs; color is supplementary. Every value is relative throughput against the same one-core global-lock baseline, so it is not a within-design speedup when the selected design is sharding or RCU. The 8% RCU term is an illustrative model assumption, not a measured grace-period cost; the sharded curve omits skew. None of the curves includes cache-coherence traffic, NUMA, allocator contention, interrupt placement, or correctness cost.

Transfer after breaking balance

Keep eight shards but send 90% of operations to one shard. Explain why the displayed sharded curve becomes optimistic and derive a lower-level bottleneck hypothesis.

Reveal the skew diagnosisExpand

The model divides critical work evenly by the number of active shards. Under 90% hot-shard traffic, one lock serializes most operations while seven locks are lightly used. Aggregate shard count is not effective parallelism. Hypotheses include hot-key distribution, a shared allocator beneath all shards, or one cache line containing multiple shard locks. Measure per-shard acquisition/wait distributions and address placement before attributing the curve to the high-level design alone.

Lock contention is a queueing mechanism

A contended lock has at least four times:

request -> wait/spin -> acquire -> critical work -> release/handoff

Reducing critical-section instruction count can help, but a lock’s cost also includes cache-line ownership transfer and wakeup/scheduling. A spinlock is appropriate only when sleeping is forbidden or expected waits are shorter than sleep/wakeup cost under the stated preemption model. A mutex avoids burning CPU during long waits but can add scheduler transitions and convoy behavior.

Worked trace: one global inode-cache lock

Four cores repeatedly look up distinct inodes. The cache uses one lock for lookup, reference increment, and a slow eviction scan.

timecore 0core 1core 2core 3lock line
t0t_0acquires; scansrequestsrequestsrequestsowned by core 0
t1t_1releasesacquiresspins/waitsspins/waitsmigrates to core 1
t2t_2requests againscanswaitswaitsremains core 1
t3t_3waits behind earlier callersreleasesacquireswaitsmigrates to core 2

Distinct inode identities do not help because lookup and eviction share one lock. Core count increases both queue length and ownership migration. Candidate redesigns include partitioning lookup buckets, separating eviction policy from fast lookup, per-CPU references with safe aggregation, or an RCU-protected read path. Each changes invariants and must be proven before performance testing.

Application checkpoint: shorten or split?

Profiling shows 70% of lock hold time is a linear scan for an eviction victim; 20% is hash lookup; 10% is reference update. Give one local optimization and one structural optimization. State a correctness risk for each.

Reveal two defensible directionsExpand

A local optimization maintains an eviction data structure so victim selection does not scan the whole cache under the lock. Its risk is stale or inconsistent replacement metadata under concurrent hits. A structural optimization shards the identity map and separates global eviction coordination; its risk is duplicate cache identities, cross-shard lock cycles, or an eviction selecting an entry whose shard/reference state changed. “Use a faster lock” does not remove the long serialized scan.

False sharing without a logical lock

Cache coherence commonly tracks fixed-size lines. If core 0 increments counter A and core 1 increments adjacent counter B in the same line, each write requires ownership of the line even though the variables are logically independent.

64-byte cache line
+----------------------+----------------------+-------------------+
| counter[0] (core 0)  | counter[1] (core 1)  | unused / others   |
+----------------------+----------------------+-------------------+

The ownership trace alternates:

core 0 obtains write ownership -> invalidates core 1 copy -> writes A
core 1 obtains write ownership -> invalidates core 0 copy -> writes B
repeat

No source-level data race exists if each counter has one writer. Performance still collapses through coherence. Padding or per-CPU allocation can place counters on separate lines, followed by occasional aggregation. The trade-off is footprint, cache pressure, aggregation cost, and topology dependence.

Boundary checkpoint: padding did not help

After aligning counters to separate lines, throughput remains flat and lock-wait time remains high. What conclusion is justified?

Reveal the bounded conclusionExpand

The tested padding did not remove the dominant measured bottleneck under that workload. It does not prove false sharing was absent, because the event attribution or layout may be wrong; nor does it prove the global lock is causal solely because wait time correlates with flattening. Inspect addresses/layout, coherence or cache events where supported, lock traces, and a controlled lock-structure change.

Sharding changes the proof

Partition a table by h(key) mod Kh(key)\bmod K A single-key operation locks one shard. A two-key operation may need two. Canonical shard order prevents deadlock, but atomic multi-key semantics may still require a version, global sequence, or retry protocol.

The critical invariants are:

  • each key has exactly one authoritative shard under the current mapping;
  • resize or rehash does not make a key absent or duplicated to readers beyond the API’s allowed state;
  • operations touching multiple shards acquire them in one global order; and
  • per-shard accounting sums to the global quantity without lost updates or double counting.

Worked cross-shard transfer

Moving one resource from key A in shard 7 to key B in shard 2 must atomically preserve total ownership.

  1. Compute both shard identities before locking.
  2. Lock shard 2, then shard 7 because 2<72<7 independent of transfer direction.
  3. Revalidate source ownership and destination eligibility.
  4. Remove A and add B while both locks are held.
  5. Release shard 7, then shard 2.

If the reverse transfer locks source first, concurrent opposite transfers can deadlock. If each operation releases one shard between remove and add, readers can observe missing or duplicated ownership.

RCU separates removal from reclamation

Read-copy update targets read-mostly structures. Readers enter an RCU read-side critical section, obtain a protected pointer, and traverse an immutable or carefully updated version. An updater publishes a new pointer or removes the old object, then waits for a grace period before reclaiming memory that pre-existing readers could still hold.

Code
participant "reader R1" as R1
participant "shared root" as ROOT
participant "updater U" as U
participant "grace-period mechanism" as GP
R1 -> R1 : rcu_read_lock()
R1 -> ROOT : rcu_dereference(root)
ROOT --> R1 : old pointer O
U -> ROOT : publish new pointer N
U -> GP : wait / defer callback
R1 -> R1 : read immutable O fields
R1 -> R1 : rcu_read_unlock()
GP --> U : all pre-publication readers quiesced
U -> U : reclaim O
reader R1shared rootupdater Ugrace-period mechanismreader R1reader R1shared rootshared rootupdater Uupdater Ugrace-period mechanismgrace-period mechanismrcu_read_lock()rcu_dereference(root)old pointer Opublish new pointer Nwait / defer callbackread immutable O fieldsrcu_read_unlock()all pre-publicationreaders quiescedreclaim O

RCU does not mean “reads need no rules.” The pointer must be published and dereferenced with the required primitives; referenced data must remain valid through the read-side critical section; updates requiring atomic multi-field visibility need an appropriate publication design; and reclamation cannot precede the grace period. Writers commonly still serialize with locks.

Worked failure: reclaim before grace

R1 reads pointer O and is preempted. U removes O from the shared list and immediately frees it. The allocator reuses O’s memory for object X. R1 resumes and interprets X bytes as O. No stale-list link is needed; lifetime alone is violated. A grace period delays reuse until every reader that could have obtained O has completed.

Transfer checkpoint: RCU under write-heavy load

Why can an RCU conversion worsen a write-heavy workload even if read-side lock acquisition disappears?

Reveal the cost shiftExpand

Writers still need synchronization, allocate or copy versions, publish pointers with ordering, track callbacks, and delay reclamation. Frequent updates can build callback backlog, increase memory footprint, and spend more work copying than the removed reader lock cost. RCU is a correctness protocol with a read-mostly performance opportunity, not a universally faster lock replacement.

Observe mechanisms at the right resolution

Different evidence answers different questions:

evidencestrengthcommon ambiguity
aggregate counterlow overhead count/rateloses temporal and call-path context
sampled eventattributes recurring events to codesampling bias, skid, lost samples, multiplexing
tracepoint/event traceordered state transitions with timestampsinstrumentation overhead and finite buffers
lock statisticsacquisition, contention, wait/hold distributionsconfiguration overhead; correlation is not redesign proof
pressure signaltime workloads stall for CPU/memory/I/Oidentifies resource pressure, not the exact code path
controlled interventiontests a causal predictionchange may alter several mechanisms at once

Linux perf_event_open supports counting and sampled hardware, software, cache, tracepoint, and implementation-specific events. Availability and meaning vary by platform. time_enabled and time_running reveal multiplexing. Ftrace supplies function, function-graph, latency, and event tracing. Lockstat requires a configured kernel and reports lock behavior. PSI reports time in which some or all non-idle work is stalled on CPU, memory, or I/O pressure.

Illustrative commands—not portable promises—might include:

perf stat -r 15 -e cycles,instructions,context-switches,cpu-migrations ./workload
perf lock record ./workload
perf lock report

Record whether events exist, whether kernel access is permitted, whether counters were multiplexed, and what scope was measured. Raw cache-event names are processor-specific; a command succeeding does not make two machines’ event semantics identical.

Worked evidence bundle

The following values are illustrative data, not results measured for LibreUni:

coresthroughput (Mop/s)p99 (µs)global-lock wait sharemigrations/op
11.0120.5%0.00
21.9143%0.01
43.42312%0.03
84.27135%0.08
164.119058%0.15

The bundle supports a hypothesis: a global lock and associated migration become dominant as concurrency rises. It does not isolate whether hold time, handoff, scheduler placement, or a shared cache line beneath the lock causes the wait. Next evidence should include hold/wait distributions by call path, owner/waiter CPU, critical-section samples, and a controlled implementation that removes or partitions the suspected shared state while preserving workload and correctness tests.

Application checkpoint: choose a discriminating measurement

Two hypotheses fit the flat curve: H1, long critical sections queue on one lock; H2, per-CPU counters falsely share a line outside that lock. Choose one observation and one intervention that distinguish them.

Reveal a discriminating pairExpand

Observe lock hold/wait distributions tied to call paths and inspect counter addresses/cache-line layout with coherence/cache events where the platform supports meaningful ones. Intervene separately: first remove the counters from shared lines without changing lock code; then, in another build, shorten or shard the lock path without changing counter layout. H1 predicts lock wait and throughput respond primarily to the lock intervention; H2 predicts the layout intervention reduces coherence traffic and improves scaling even if lock statistics are unchanged. Run correctness tests for both builds.

Reproducible scaling experiment

A defensible experiment records:

  1. source revision, configuration, compiler, kernel, firmware, and microcode where relevant;
  2. processor topology, SMT state, CPU affinity, NUMA placement, frequency/turbo policy, and interrupt placement;
  3. workload generator, offered-load model, dataset, operation mix, seeds, warm-up, and stopping rule;
  4. baseline and changed implementation built from the same environment;
  5. repetitions at each core count in randomized or counterbalanced order;
  6. throughput plus latency distributions, not throughput alone;
  7. raw counter/trace output with lost-sample and multiplex information;
  8. uncertainty intervals or complete replicate distributions; and
  9. threats to construct, internal, external, and conclusion validity.

Instrumentation can perturb the schedule. First quantify no-trace versus trace overhead. High-rate tracing that drops events cannot support complete event counts unless loss is modeled.

Section Exercises

Deep Practice

Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.

Exercise 7.4.1: Inverting Amdahl Model from Measured Multicore Speedup

Verificationapplication

A kernel benchmark executes on an 8-core symmetric multiprocessing system and achieves a measured speedup of S(8)=5.0S(8) = 5.0 compared to single-core execution on identical fixed work. Assuming the ideal Amdahl scalability equation S(N)=1s+(1−s)/NS(N) = \frac{1}{s + (1 - s)/N} derive the implied serial fraction ss Determine the theoretical maximum speedup attainable on an infinite number of cores N→∞N \to \infty under this model.

HintExpand

Equate S(8) to 5.0 and solve for s algebraically before evaluating the limit 1/s.

Worked solutionExpand

Equate the observed speedup to the Amdahl equation:

1s+1−s8=5.0  ⟹  s+1−s8=15=0.20\frac{1}{s + \frac{1 - s}{8}} = 5.0 \implies s + \frac{1 - s}{8} = \frac{1}{5} = 0.20

Multiply through by 8 to clear the denominator:

8s+1−s=1.6  ⟹  7s=0.6  ⟹  s=0.67=335≈0.0857 (8.57%)8s + 1 - s = 1.6 \implies 7s = 0.6 \implies s = \frac{0.6}{7} = \frac{3}{35} \approx 0.0857 \text{ (8.57\%)}

Under the ideal Amdahl model with s=335s = \frac{3}{35} the infinite-core asymptotic speedup limit is:

S(∞)=lim⁡N→∞1s+1−sN=1s=353≈11.67×S(\infty) = \lim_{N \to \infty} \frac{1}{s + \frac{1 - s}{N}} = \frac{1}{s} = \frac{35}{3} \approx 11.67\times

Even with an infinite number of cores, execution time cannot fall below 8.57% of the original single-core execution time because the serialized component cannot be parallelized.

Exercise 7.4.2: Eliminating False Sharing via Cache-Line Alignment and Padding

Constructionapplication

Consider an array of per-core statistics counters defined as struct core_stats { uint64_t rx_packets; uint64_t tx_packets; } stats[64]; running on a 64-core system with standard 64-byte hardware cache lines. Explain why concurrent updates by different cores cause severe cache-line bouncing (false sharing). Rewrite the structure definition using cache-line alignment attributes or explicit padding to ensure each core writes to an isolated cache line.

HintExpand

Calculate sizeof(struct core_stats) and compare to 64 bytes; apply __attribute__((aligned(64))).

Worked solutionExpand

In the initial definition, sizeof(struct core_stats) = 16 bytes (two 8-byte integers). Consequently, 64/16=464 / 16 = 4 distinct core structures pack into a single 64-byte cache line. When Core 0 increments stats[0].rx_packets and Core 1 concurrently increments stats[1].rx_packets, both cores execute read-for-ownership (RFO) requests, invalidating each other’s L1/L2 cache lines repeatedly despite accessing distinct variables.

To eliminate false sharing, pad or align each entry to 64 bytes:

struct alignas(64) core_stats {
    uint64_t rx_packets;
    uint64_t tx_packets;
    uint8_t  _pad[48]; /* 16 bytes payload + 48 bytes padding = 64 bytes */
};

struct core_stats stats[64];

Or using GCC/Clang attribute syntax:

struct core_stats {
    uint64_t rx_packets;
    uint64_t tx_packets;
} __attribute__((aligned(64)));

struct core_stats stats[64];

Each element occupies exactly one cache line (64 bytes), ensuring concurrent updates by distinct cores modify disjoint cache lines without generating coherence invalidations.

Exercise 7.4.3: Tracing RCU Removal, Grace Period Detection, and Memory Reclamation

Constructiontransfer

Explain how Read-Copy Update (RCU) decouples readers from writers in a linked list lookup table. Trace the exact sequence of steps when a writer deletes a node N:

  1. Pointer removal (list_del_rcu),
  2. Waiting for a grace period (synchronize_rcu or call_rcu), and
  3. Node deallocation (kfree). State what condition must be met on every active CPU core before the grace period ends and kfree(N) is safe.
HintExpand

Recall that readers execute within rcu_read_lock/rcu_read_unlock without blocking writers; grace periods expire once all cores pass a quiescent state.

Worked solutionExpand

The sequence proceeds as follows:

  1. Removal step: The writer executes list_del_rcu(N) (or updates the preceding node’s next pointer using an atomic store with release semantics). Node N is unlinked from the active list. Concurrent readers that entered their critical section before or during the update either see the old pointer or the new pointer; readers seeing N continue traversing it safely because N remains allocated in memory.
  2. Grace period detection: The writer initiates a grace period via synchronize_rcu() (blocking) or call_rcu() (asynchronous callback). The kernel tracks quiescent states across all CPU cores. In non-preemptible kernels, a quiescent state occurs whenever a core undergoes a context switch, enters the idle loop, or executes in user mode. Once every core has passed through at least one quiescent state, all readers that were inside rcu_read_lock() at the time of unlinking are guaranteed to have exited their read-side critical sections.
  3. Reclamation step: When the grace period completes, no reader retains a reference to node N. The callback or returning thread invokes kfree(N) safely without locks or memory corruption.

Exercise 7.4.4: Diagnosing Lock Contention Bottlenecks with lockstat and perf

Descriptionapplication

A 32-core database server experiences degraded transaction throughput accompanied by 85% system CPU utilization. Profiling with Linux kernel observability tools reveals that the time is spent in native_queued_spin_lock_slowpath. Describe how you would utilize /proc/lock_stat and perf record -g -e lock:lock_acquire to identify:

  1. The exact lock symbol exhibiting the highest contention,
  2. The ratio of contention events (con-bounces) to total acquisitions, and
  3. The specific kernel call chains responsible for holding the lock for the longest hold durations.
HintExpand

Explain how lockstat tracks acquisition count, hold time, and wait time, and how perf record samples call stacks on lock events.

Worked solutionExpand
  1. Enabling and inspecting lockstat: Enable lock statistics via echo 1 > /proc/sys/kernel/lock_stat. Run the workload, then inspect /proc/lock_stat. The output sorts locks by contention counts and wait times. Look for the top entry in the contentious: table to identify the lock data structure and symbolic name (for example, &sb->s_umount or inode_hash_lock).
  2. Evaluating contention metrics: Examine the acquisition columns: acquisitions (successful acquires), contentions (acquisitions that failed immediately and had to spin/block), and waittime (total and maximum nanoseconds spent waiting). If contentions / acquisitions approaches a substantial fraction (for example, > 20%), the lock is a primary scalability bottleneck.
  3. Attributing hold time call stacks with perf: To discover who holds the lock while others wait, record lock events with stack traces:
    perf record -g -e lock:lock_acquire -e lock:lock_acquired -- sleep 10
    perf report
    Inspect call graphs under the lock hold events to pinpoint the kernel function executing inside the critical section. If hold time is dominated by heavy memory allocations or iterative scans under the lock, refactoring the algorithm outside the lock or sharding the protected state resolves the contention.

Exercise 7.4.5: Proving Consistency Invariants in Sharded Multicore Counters

Proofsynthesis

To prevent global atomic contention, an operating system implements a sharded statistics counter with KK per-core slots: int64_t slots[K]. Updates execute locally on core ii slots[i] += delta. A global reader reads the total count by summing all slots: T=∑i=0K−1slots[i]T = \sum_{i=0}^{K-1} \text{slots}[i]

  1. Prove that without global locking, TT does not guarantee a linearizable snapshot across concurrent increments.
  2. Construct a concrete race trace where two increments of +1+1 on Core 0 and Core 1 occur concurrently with a reader summation, such that the reader returns a value that reflects neither the initial state nor the final state, yet satisfies monotonicity if increments are strictly non-negative.
  3. Formulate the correctness invariant guaranteed by this sharded counter design under relaxed reader execution.
HintExpand

Consider the order in which the reader loop scans slot indices relative to concurrent writes; prove conservation of increments.

Worked solutionExpand
  1. Non-linearizability proof: Linearizability requires each read operation to appear to take effect instantaneously at some point between its invocation and its return. Suppose Core 0 has completed incrementing slots[0] = 1, and the reader reads slots[0] = 1. Before the reader reads slots[1], Core 1 transfers a count from slots[1] to slots[0] by subtracting 1 from slots[1] and adding 1 to slots[0]. The reader then reads slots[1] = 0. The reader computes total T=1+0=1T = 1 + 0 = 1 However, the true total after the transfer was 2, and before the transfer was 2. The read observes an impossible intermediate state where one component was read post-transfer and the other pre-transfer, violating linearizable atomic snapshot semantics.
  2. Concrete race trace: Let initial state be slots[0] = 0, slots[1] = 0.
    • Reader begins summation loop: reads slots[0] = 0.
    • Core 0 executes slots[0] += 1 (now slots[0] = 1).
    • Core 1 executes slots[1] += 1 (now slots[1] = 1).
    • Reader advances loop to index 1: reads slots[1] = 1.
    • Reader computes T=0+1=1T = 0 + 1 = 1 The true final state has total 2. The initial state had total 0. The reader observes total 1. If all updates are non-negative increments, the reader never reads a value exceeding the true final count or less than the state prior to invocation, preserving monotonic progress.
  3. Guaranteed invariant (eventual conservation): If all updates cease at time t0t_0 any reader whose execution begins strictly after t0t_0 evaluates:
T=∑i=0K−1slots[i]=∑ΔijT = \sum_{i=0}^{K-1} \text{slots}[i] = \sum \Delta_{ij}

which equals the exact sum of all committed deltas. Under concurrent execution with monotonically increasing deltas, the observed sum satisfies Tinvoc≤Tobserved≤TcompletionT_{\text{invoc}} \le T_{\text{observed}} \le T_{\text{completion}} providing an admissible bounded approximation without serializing writers.

References & Further Reading