How can an idle CPU be overloaded?

01Four cores, two locks, one misleading dashboard

Consider an RPC server with four cores. Every request enters looking identical, evaluates a condition, then takes one of two data paths. Path A is chosen 20% of the time; Path B is chosen 80% of the time. Each path has its own global mutex, and the critical section behind either mutex takes one millisecond on average.

A mutex permits only one thread inside its critical section at a time. If each critical section occupies the lock for one millisecond, each path can complete at most about 1,000 requests per second—1 kRPS—regardless of how many threads wait for it. More worker threads do not make one critical section parallel.

This is where the AOS lock story changes levels. A scalable queue lock such as MCS reduces coherence traffic and gives each waiter a local place to spin. That makes waiting for the lock scale better. It does not repeal the mutual-exclusion rule: the protected code still runs one holder at a time. If the application uses a blocking mutex, waiting threads may sleep, leaving cores idle while the lock’s queue grows.

The example is deliberately small, but it comes from the motivating construction in the Protego paper. The authors use it to expose a problem that becomes harder with thousands of locks: before executing a request, the server may not know which serialized path that request will need.

02Follow the same workload through three rates

Let λ be the rate admitted through the one global gate. On average, Path A receives 0.2λ and Path B receives 0.8λ. For now, assume each path completes arrivals up to its 1 kRPS capacity and that excess requests either accumulate or are rejected locally.

There is no single clean operating point. Stop at 1.25 kRPS and every path can have low delay, but 37.5% of the two locks’ aggregate capacity is unused. Push to 5 kRPS and both paths are productive, but most requests sent toward Path B cannot complete there immediately.

If the admission gate cannot see the future branch, which path should its “server capacity” describe?

03See the capacity curve, not just the bottleneck

The explorer keeps each lock at 1 kRPS and lets you vary the admitted load and route mix. Start with the three preset loads. The graph shows why the total throughput curve changes slope rather than encountering one universal capacity wall.

At the default 20/80 split, the slope of useful throughput has three pieces:

Before either lock saturates, every additional admitted request becomes additional throughput. After Path B saturates, only the 20% routed to Path A can add completions, so one extra kRPS of input buys only 0.2 kRPS of output. After both locks saturate, more input buys nothing.

This ratio—marginal output gained per marginal input—is the signal Protego uses. Move the efficiency threshold in the explorer. A high threshold treats the first saturated path as the stopping point. A threshold below 20% is willing to accept local rejections in order to uncover Path A’s remaining throughput. The real controller estimates the change across time windows; the graph gives us the steady-state shape it is trying to navigate.

04Why the familiar signals give contradictory advice

The problem is not that delay ceased to matter. It is that delay is local while admission is global. Compress thousands of path states into one tail statistic and the hottest path wins the vote. Ignore it and requests on that path wait far beyond their objective.

Could the server simply use try_lock() after admission? It would reject on the first failed attempt, even when a short wait fits comfortably inside the request’s latency budget. A fixed timed mutex has the opposite problem: under severe contention it may force a doomed request to wait the entire timeout. The decision needs both local queue state and the particular request’s remaining time.

05Protego splits one impossible decision into two possible ones

The global admission gate lacks path knowledge. The lock queue has path knowledge, but sees the request only after some work has already been spent. Protego accepts that information boundary and gives each location the decision it can actually make.

The global decision pursues useful work. The local decision protects latency. Neither pretends to know what only the other location can observe.

06A delay budget that follows the request

Suppose a server should either complete or reject an attempt within 200 μs. The 99th-percentile network cost is 40 μs and the 99th-percentile service cost is 60 μs. The remaining 100 μs is the request’s initial queueing budget.

The request first waits 25 μs in the runnable-thread queue. After it is dequeued, that time is deducted, leaving 75 μs. Later it approaches Mutex B. The oldest waiter in that mutex queue has already waited 90 μs, which Protego uses as the instantaneous queue-delay estimate. Ninety exceeds the request’s remaining 75 μs, so the latency-aware lock call returns failure without joining the queue.

If the observed lock delay had been 50 μs, the request could wait, acquire the lock, and deduct its actual wait afterward. The abstraction is neither “never wait” nor “wait for a fixed timeout.” It spends a single end-to-end queueing allowance across the sequence of queues the request actually encounters.

Protego exposes latency-aware mutex and condition-variable operations that return a Boolean. Existing blocking operations remain available for work that cannot safely abort. That API distinction matters because cancellation is not free: a partially executed request may hold other locks, allocate memory, or mutate state. The application must clean those effects up. Scoped locks and RAII can make the obligation manageable, but the paper does not make it disappear.

07What Breakwater could know—and what changed

Breakwater regulates a server using queueing delay at packet and runnable-thread stages. When the server’s relevant bottleneck produces delay in those measured queues, the server can adjust a global credit pool before most excess work arrives.

Protego changes one assumption: requests can block deeper in the application on different locks, and the chosen lock may be unknowable at admission. The server no longer has one pre-execution delay that faithfully represents every request. Protego keeps receiver-issued credits, but changes how their total is chosen: observed marginal throughput replaces one presumed overload signal. It then moves latency enforcement to the synchronization queue where the hidden path has finally become visible.

08Return to the idle CPU

The opening contradiction came from naming the wrong resource. The server was not globally CPU-saturated; one lock-protected path was. Threads waiting on a blocking mutex can yield their cores, so low CPU use and catastrophic request delay can coexist. Adding workers merely lengthens the set of contenders.

Our 20/80 example then exposed the control dilemma. A global limit of 1.25 kRPS protects the hot path but strands 0.75 kRPS on the cold path. A global limit of 5 kRPS extracts both paths’ full 2 kRPS, but sends 3 kRPS of excess work toward the hot lock. Protego chooses an operating point from the slope of useful throughput, then lets latency-aware lock queues shed the requests that cannot afford their local path.

Change the assumption: suppose the request header reveals its exact path before admission and there are only two stable paths. Two independent credit pools—one per path—could admit 1 kRPS to each lock without the 3 kRPS of waste. Protego’s global-plus-local design earns its complexity when paths are numerous, dynamic, or discoverable only during execution.