CPS: A Cooperative Para-virtualized Scheduling Framework for Manycore Machines

Cloud virtual machines now have dozens or hundreds of virtual processors, but the guest operating system inside cannot see what the hypervisor underneath is doing — which physical cores are actually busy, and which fast-communicating cache cluster each virtual processor currently sits in — so it schedules threads badly and wastes the machine; this work from Shanghai Jiao Tong builds CPS, a cooperative scheme where the hypervisor continuously shares that live internal state with each guest through a shared table, and the guest schedules against the truth, lifting parallel-benchmark performance by up to 81 percent.

The argument in one glance

Problem

Two schedulers stacked on top of each other fight blindly

A cloud virtual machine has a guest operating system that schedules threads onto its virtual processors. Underneath, the hypervisor schedules those virtual processors onto real cores. The two schedulers cannot see each other. On a big machine with many cores this "double scheduling" wastes performance, because each side makes decisions without knowing what the other is doing.
What people did

Bridge the gap for locks and synchronization

Most prior work attacked one symptom: the hypervisor pausing a virtual processor while it holds a lock, stalling everyone waiting. Fixes either let the hypervisor guess when a guest is in a critical section, or let the guest tell the hypervisor about its locks through a special interface.
Why it fell short

The guest is still blind to the hypervisor's live state

Those fixes handle locks, but a deeper gap remains: the guest cannot see the hypervisor's runtime internal state that is not specific to any one virtual machine — how busy each real core is, and which fast cache cluster each virtual processor currently sits in. And even if the guest learned this once, the hypervisor keeps moving virtual processors, so the information is stale almost immediately. Scheduling against a wrong picture, the guest crowds work onto a few cores and idles the rest.
This paper's idea

Share the live state both ways through one table

CPS is a cooperative scheme. The hypervisor continuously writes its live internal state — each core's load and each virtual processor's cache cluster — into a table mapped into every guest. The guest reads it and schedules against the truth: it places waking work on idle-but-preempted virtual processors, and keeps communicating threads in the same fast cache cluster. The guest also sends hints back. On an ARM manycore server it lifts parallel benchmarks by up to 81 percent.

Why this problem is worth solving

The waste comes from two independent schedulers that never talk.

In a virtual machine, scheduling happens twice. The guest operating system decides which of its threads runs on which virtual processor — a virtual processor being the guest’s illusion of a CPU. Underneath, the hypervisor decides which real, physical core each virtual processor actually runs on, and it time-shares physical cores among many virtual machines. This is double scheduling, and the two layers do not share what they know, a mismatch called the semantic gap. The classic symptom is lock-holder preemption: the guest gives a thread a lock, but the hypervisor, unaware, pauses that thread’s virtual processor to run something else, so every other thread waiting for the lock stalls. Years of research have chipped at this for locks and other synchronization, either by having the hypervisor infer when a guest is inside a critical section, or by adding an interface so the guest can tell the hypervisor about its locks. This paper identifies a different, broader gap. The guest is blind not just to lock timing but to the hypervisor’s general runtime internal state that is not tied to any single guest — for example, how heavily loaded each physical core is right now, and where each virtual processor is currently placed. The authors call this the absence of runtime hypervisor-internal state, and they show it has two nasty features: the guest cannot access it, and even if it could, the state changes so fast that a snapshot is instantly out of date.

On modern manycore chips a second, hardware version of the same blindness appears.

Large server chips no longer treat all cores as equidistant. They have a deep cache hierarchy in which a slice of the last-level cache is shared by a small cluster of cores — the paper calls such a cluster a cache group. On an AMD server a cache group is three cores; on the ARM server the authors use, it is four. Threads running on cores within the same cache group communicate through that shared cache slice far faster than threads spread across the chip. The paper measures a simple shared-counter update: about 7.08 million operations per second when the two cores share a cache group, versus 4.76 within the same memory node, 4.45 within the same socket, and only 2.97 across sockets — so keeping communicating threads in one cache group is more than twice as fast as letting them drift apart. A guest that knew its layout could place chatty threads together. But it cannot: it does not know the live mapping from its virtual processors to physical cores and cache groups, and the hypervisor keeps migrating virtual processors to balance load, so any mapping the guest guesses is quickly wrong. The performance left on the table is large, and it grows as chips add more cache clusters.

What people did before, and where it broke

Bridge the semantic gap for locks (many prior systems). Detect or announce guest critical sections so the hypervisor avoids pausing a lock holder. Where it broke. It fixes lock-related stalls but says nothing about the broader hypervisor state — physical-core load and cache-group placement — that the guest also needs to schedule well.
Tell the guest only whether a virtual processor is preempted. A para-virtualized interface lets the guest learn that a virtual processor is currently paused, so it can move a waking task to a running one. Where it broke. Knowing only “preempted or not” ignores how busy each physical core is, so the guest crowds waking tasks onto the few running virtual processors and overlooks paused ones sitting on idle cores that would resume almost instantly.
Signal a physical core as simply idle or not. Expose a boolean saying a physical core is free. Where it broke. With many virtual machines, the first one to spot an idle core grabs it and marks it busy, starving the others — a fairness race — and a single bit cannot express degrees of load.
The gap. No mechanism gave the guest a live, fair, low-cost view of the hypervisor’s general runtime state — physical-core load and cache-group mapping — that stays fresh as the hypervisor moves things around, nor a way for the guest to hint back. Providing that two-way, always-current channel is what CPS does.

How CPS works

From two blind schedulers to a shared, live view

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Turn a hidden boundary into a shared, always-current view. The root trouble is that a wall — the boundary between guest and hypervisor — hides state each side needs from the other, and that state is not static but changing every moment. CPS answers with a single shared structure, the Refer-Table, that the hypervisor keeps writing and the guest keeps reading, so the guest schedules against the hypervisor’s live truth rather than a guess. Making a shared structure the coherent meeting point that keeps two separated components’ views consistent as things change is the same design the serverless file-system-metadata work covered elsewhere on this site relies on, using a coherent cache so that separated servers all act on the same, up-to-date picture of the metadata instead of drifting apart.

Place communicating threads where the hardware makes them fast. On a manycore chip, cores that share a cache slice talk to each other far faster than distant cores, so where a thread runs matters as much as whether it runs. CPS tracks, in real time, which cache group each virtual processor maps to, and steers the guest to gather threads that talk to each other into one cache group, keeping their shared data in the near cache. Scheduling work with an eye to the memory hierarchy, so that pieces that communicate stay close and cheap, is the same instinct the dynamic-task-parallelism-on-manycore work covered elsewhere on this site follows, balancing and placing work across a mesh of cores so that data movement stays short rather than crossing the whole chip.

Share a coarse degree, not a precise number. CPS deliberately does not hand the guest exact loads or precise hypervisor internals. It shares a coarse load degree — low or high — because an exact idle-or-not signal triggers a race in which one virtual machine seizes a core and starves the rest, and precise state would leak hypervisor details and go stale even faster. A rough, cautious signal is enough to spread work well and is safe to expose. Choosing a coarse, conservative signal over precise-but-costly tracking is the same trade the copy-on-write correctness work covered elsewhere on this site makes, replacing exact accounting of a page’s sharing with a single cautious flag that is cheaper, safer, and good enough to act on.

Following a parallel program past a barrier

Why a barrier used to collapse, and how CPS fixes it

Tracing a common parallel pattern shows the load-degree idea at work.

Step 1 of 5

Threads sleep at a barrier

A parallel program reaches a barrier where most threads must wait for the last one. The waiting threads go to sleep, so their virtual processors have nothing to do, and the hypervisor pauses those virtual processors to run other work.

This pattern is common in the PARSEC benchmark suite the paper uses.

Why it works

Two schedulers cannot see each other. Because the hypervisor places virtual processors and the guest places threads with no shared view → the guest picks virtual processors blind to which physical cores are truly busy → so it stalls tasks behind paused processors while real cores sit idle.
A shared table closes the gap cheaply. Because the hypervisor writes its live load and mapping state into a table mapped into every guest → the guest reads the current truth instead of guessing → so its scheduling decisions finally match what the hardware is doing.
A coarse load degree beats a single idle bit. Because a plain idle flag lets one virtual machine seize a core and starve the others, while a low-or-high degree describes how busy each core is → the guest spreads work by degree rather than racing for one flag → so utilization rises without a fairness collapse.
Keeping communicating threads in one cache group speeds them up. Because cores in the same cache group exchange data more than twice as fast as cores across sockets → co-locating threads that talk to each other in one group → so their shared data stays in the near cache and throughput climbs.
Shared pages keep the view fresh at scale. Because each physical core’s load lives in one page mapped read-only into every virtual machine that uses it → the hypervisor updates a single page rather than walking every guest’s table → so the shared state stays current even with many virtual machines running.

What it costs (trade-offs and scope)

It requires changing both the guest and the hypervisor. CPS adds a backend to the hypervisor and a frontend to each guest kernel, and applications must opt in to name their communicating threads. It is a cooperative, para-virtualized design, so it does not help unmodified, fully-virtualized guests.
The shared view is deliberately coarse. To stay safe and fair, CPS exposes only a low-or-high load degree and gives each virtual machine its own disguised cache-group identifiers. This limits how finely the guest can optimize, which is an intentional trade for security and fairness.
Keeping the mapping fresh is real work. Because the hypervisor constantly migrates virtual processors, the guest must re-check the table often, including inside its interrupt handling, and the backend must remap load pages as processors move. This machinery adds complexity and some overhead.
The guest adds scheduling latency over a bare machine. Consulting the table makes the guest’s choice of virtual processor slower than a hardware virtual machine that does no such work, though it is much faster than the previous para-virtual baseline. The extra time buys better placement.
Gains depend on the workload and the hardware. The benefits are largest for parallel programs with heavy synchronization or clear communicating groups, on chips with pronounced cache clusters. Programs without barriers or communicating groups, or flatter machines, see little.
Evaluated on one manycore server and set of benchmarks. The results come from an ARM Kunpeng server under a specific hypervisor and benchmark suite; the design is argued to generalize to x86 cache clusters, but that is reasoned, not measured here.

The evaluation

Three ways a guest scheduler sees the machine underneath it

Property	Bare virtual machine	Para-virtual (preempted bit)
Sees physical-core load
Sees cache-group mapping	No	No
Stays fresh as processors move	Not applicable
Virtual-processor selection time
Benchmark performance	Baseline

Three ways the guest scheduler in a virtual machine sees the machine beneath it, measured on a Huawei TaiShan server with 128 ARM Kunpeng cores across two sockets and thirty-two cache groups. A bare virtual machine is blind to the hypervisor and does no extra work, so its virtual-processor selection is fastest but its placement is poor. The older para-virtual approach knows only whether a virtual processor is paused, which is coarse, goes stale, and can even hurt by crowding work onto a few cores. CPS shares the hypervisor's live load degrees and cache-group mappings through a table mapped into each guest, keeps it fresh as virtual processors migrate, and lets the guest hint back. It cuts virtual-processor selection time from 1835 to 707 nanoseconds versus the para-virtual baseline while adding the information, and improves the PARSEC parallel suite by 81.1 percent and the FxMark file-system suite by 1.01 times on average across the two problems it targets. The results are from one ARM server and benchmark set.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

CPS is a focused systems contribution: it names a specific blind spot in virtualization — the guest cannot see the hypervisor’s live, non-guest-specific runtime state, and that state changes constantly — and closes it with a shared table that flows information both ways. The two case studies are concrete and well matched to real pain: spreading waking threads onto paused-but-idle-core virtual processors using a coarse load degree, and gathering communicating threads into the same fast cache group using a live mapping. The reported gains are substantial, up to 81 percent on a parallel suite, and the design is careful about security and fairness, exposing only coarse degrees and giving each virtual machine a disguised view of the topology. Read the results with their scope. This is a cooperative, para-virtualized design: it modifies both the guest and the hypervisor and asks applications to identify their communicating threads, so it does not help unmodified guests. The benefits concentrate on synchronization-heavy or communication-heavy workloads on chips with strong cache clusters; flatter workloads or flatter machines gain little. Keeping the shared view fresh as the hypervisor migrates processors is genuine engineering that adds some overhead, and the numbers come from one ARM manycore server and a particular benchmark set, with the generalization to other chips argued rather than measured. The durable lesson is that when a layered abstraction hides state the layer above needs, the fix can be a small, deliberate, two-way window rather than tearing the layers apart.

Background

Why a scheduler's hidden state cuts both ways

It is worth placing CPS beside a sharper reminder that a scheduler’s internal state is powerful. The controlled-preemption work covered elsewhere on this site shows the danger side of the same coin: an attacker who understands exactly how a scheduler’s internal rules behave can exploit them to spy on a victim with fine precision. CPS shows the cooperative side: when the hypervisor deliberately and carefully shares the right slice of its scheduling state with a guest, both sides make far better decisions. The common thread is that the internal state buried inside a scheduler — who is loaded, who is paused, who sits where — is high-value information. Hidden, it causes the guest to schedule blindly and waste the machine; leaked carelessly, it becomes an attack channel; shared on purpose, coarsely and fairly, it becomes a performance win. The broad point is that the boundaries we draw between layers of a system are not neutral. What each layer chooses to reveal, and how coarsely, shapes both how well the whole system runs and how safe it is, and getting that sharing right is a design problem worth taking as seriously as the schedulers themselves.

If you remember only three things

1. A cloud virtual machine is scheduled twice: the guest operating system places threads on virtual processors, and the hypervisor places virtual processors on physical cores, with no shared view. Prior work fixed lock-related stalls from this double scheduling, but a broader gap remained: the guest cannot see the hypervisor's live internal state that is not tied to any one guest — how busy each physical core is, and which fast cache group each virtual processor sits in — and that state changes constantly as the hypervisor migrates virtual processors, so any snapshot is instantly stale. Scheduling blind, the guest crowds work onto a few cores and idles the rest.
2. CPS is a cooperative para-virtualized scheme. The hypervisor writes its live state into a shared two-level table (the Refer-Table) mapped into each guest, updating it as load changes and processors move, with per-core load kept in shared read-only pages so one write reaches every virtual machine at once. The guest reads the table to schedule against the truth, and can hint back. Two case studies: it shares a coarse low-or-high load degree so the guest places waking threads on paused-but-idle-core virtual processors without a fairness race, and it tracks live cache-group mappings so the guest gathers communicating threads into one fast cache group.
3. On a 128-core ARM Kunpeng server, CPS improves the PARSEC parallel suite by 81.1 percent and the FxMark file-system suite by 1.01 times on average for the two targeted problems, cutting the guest's virtual-processor selection time from 1835 to 707 nanoseconds versus the para-virtual baseline while adding the shared information; same-cache-group communication is over twice as fast as cross-socket. Its limits: it modifies both guest and hypervisor and needs applications to name communicating threads, the shared view is deliberately coarse for safety and fairness, keeping it fresh adds overhead, and the gains are concentrated on synchronization- and communication-heavy workloads on cache-clustered chips.

Check yourself

Check your understanding

1. What is the "double scheduling" problem, and what new part of it does this paper target?
2. Why does CPS share a coarse "low or high" load degree instead of an exact idle-or-busy signal?
3. How does CPS make communicating threads run faster on a manycore chip?
4. A workload is single-threaded, or its threads rarely synchronize or communicate. What does CPS predict?

Sources

The paper is “CPS: A Cooperative Para-virtualized Scheduling Framework for Manycore Machines” by Yuxuan Liu, Tianqiang Xu, Zeyu Mi, Zhichao Hua, Binyu Zang, and Haibo Chen, published at ASPLOS 2023, DOI 10.1145/3623278.3624762. The authors are at the Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University. CPS is implemented in Linux KVM.

This explainer is written from the full text of the paper, obtained from the authors’ Institute of Parallel and Distributed Systems publications page, which matches the ASPLOS 2023 proceedings. Everything above comes from the paper’s own sections: the introduction and background on double scheduling and its lock-related symptoms (lock-holder preemption and related problems) and on the deep memory hierarchy and cache groups (three cores on an AMD server, four on the ARM server used, and the shared-counter microbenchmark of 7.08, 4.76, 4.45, and 2.97 million operations per second for same cache group, same node, same socket, and different socket); the definition of the runtime hypervisor-internal state problem and its two case studies (invisible physical-core load and dynamic cache-group mapping); the CPS design (the two-level Refer-Table with virtual-processor-level and information-level blocks, the direct and indirect storage methods with shared read-only load pages, the backend module with its update and hint-checking functions, the frontend module with its device interface and virtual-processor selection, and the security measures of coarse load degrees and disguised virtual cache-group identifiers); the two solutions, load-degree scheduling and cache-group-aware scheduling with its per-group data structures; and the evaluation on a Huawei TaiShan 200 server with 128 ARM Kunpeng cores, two sockets, four memory nodes, and thirty-two cache groups, running openEuler with the Linux 5.10 kernel, including the virtual-processor selection times (103, 1835, 707, and 1090 nanoseconds for the bare, para-virtual, load-degree, and cache-group configurations), the reported per-problem gains (an average 59 percent and 1.03 times for load scheduling, 1.40 times and 62.4 percent for cache-group scheduling), and the overall improvements of 81.1 percent on PARSEC and 1.01 times on FxMark.