Rethinking Thread Scheduling under Oversubscription: A User-Space Framework for Coordinating Multi-runtime and Multi-process Workloads

This paper introduces the User-space Scheduling Framework (USF) and its default cooperative policy, SCHED_COOP, which leverage user-space thread scheduling via the nOS-V runtime to eliminate OS-level preemption interference under oversubscription, achieving up to 2.4x performance gains in complex multi-runtime and multi-process HPC and AI workloads without requiring invasive application changes.

The Gist

Imagine a busy kitchen in a high-end restaurant. This kitchen represents a powerful computer processor with many chefs (cores) ready to cook.

The Problem: Too Many Orders, Too Many Chefs

In the world of High-Performance Computing (HPC) and Artificial Intelligence (AI), applications are becoming like massive, complex recipes that require many chefs working at once. Sometimes, the restaurant gets so busy that there are more cooks ready to work than there are stoves (cores) available. This is called oversubscription.

Traditionally, the "Head Chef" (the Operating System's scheduler) manages this chaos by forcing every cook to take turns. Every few seconds, the Head Chef yells, "Stop what you're doing! Switch to the next cook!" This is called preemption.

While this ensures everyone gets a turn, it causes two major problems in a high-stakes kitchen:

1. The "Lock-Holder" Problem: Imagine a cook is holding a heavy pot (a lock) and waiting for another cook to finish chopping onions. If the Head Chef yells "Stop!" and takes the pot away from the first cook to give it to someone else, the second cook is now stuck waiting for a pot that isn't being held by anyone. The whole line grinds to a halt.
2. The "Switching" Cost: Constantly stopping and starting cooks wastes time. It's like a chef dropping a knife, walking to the other side of the kitchen, picking up a new knife, and starting over. This wastes energy and slows down the meal service.

The Solution: A New Way to Manage the Kitchen

The authors of this paper, Aleix Roca and Vicenç Beltran, built a new system called USF (User-Space Scheduling Framework). Think of this as a new, specialized manager who works inside the kitchen team rather than being the distant Head Chef in the office.

Instead of the OS forcing random switches, USF lets the cooks manage themselves using a rule called SCHED_COOP.

How SCHED_COOP Works:

• No Interrupts: Once a cook starts a task, they are allowed to keep working until they naturally hit a pause point (like waiting for an ingredient or finishing a step). The manager never yells "Stop!" in the middle of a task.
• Smart Swapping: The manager only swaps cooks when one of them voluntarily stops to wait (blocks). If Cook A is waiting for onions, the manager immediately hands the stove to Cook B, who is ready to cook.
• The "Cooperative" Aspect: The cooks agree to this system. They know that if they get stuck waiting, they will step aside so someone else can work. This prevents the "stuck pot" problem and eliminates the wasted time of constant switching.

The Magic Ingredient: The "Glibc" Extension

The clever part of this research is how they built it. Usually, changing how a computer schedules tasks requires rewriting the computer's core operating system (the "kernel"), which is like rebuilding the entire restaurant's plumbing and electrical system. That's hard, dangerous, and requires special permissions.

Instead, the authors modified the GNU C Library (glibc).

• The Analogy: Think of glibc as the universal "uniform" and "instruction manual" that almost every computer program wears and reads. By slightly altering this uniform, the authors made the cooks (threads) automatically follow the new SCHED_COOP rules without the restaurant owner (the user) having to rewrite the recipes (the applications).
• Seamless: Because they changed the uniform, existing applications (like OpenMP, PyTorch, or molecular dynamics simulations) just put on the new uniform and start working better immediately. No invasive surgery on the code was needed.

The Results: Faster Service

The authors tested this in several scenarios, acting like a restaurant manager running different simulations:

1. Nested Runtimes: Imagine a recipe that calls for a sub-recipe, which calls for another sub-recipe. This creates a chaotic mix of many cooks. The new system handled this mix much better than the old "stop-and-start" method, speeding up performance by up to 2.4 times in some cases.
2. AI Inference (LLaMA-3): They ran multiple AI models at once. The new system allowed them to run smoothly together without the "noise" of constant switching, keeping the service fast even when the kitchen was packed.
3. Molecular Dynamics: Simulating how molecules move is like a complex dance. The new system allowed multiple dances to happen on the same floor without the dancers tripping over each other, utilizing the kitchen's resources more efficiently.

The Catch

The system works perfectly as long as the cooks follow the rules. However, some older recipes use a technique called "busy-waiting," where a cook stands at the stove staring at a pot, refusing to step aside even if they are just waiting. The new system can't force these specific cooks to move unless the recipe is slightly tweaked to tell them, "If you're waiting, take a quick breath and let someone else work." The authors found this tweak easy to do.

Summary

In short, this paper presents a way to let computer programs manage their own busy schedules without needing the operating system to constantly interrupt them. By changing the "uniform" (glibc) rather than the "building" (kernel), they created a system that is easier to use, requires no special permissions, and makes complex, overloaded computer tasks run significantly faster and smoother.

Technical Summary

Technical Summary: Rethinking Thread Scheduling under Oversubscription

1. Problem Statement

The convergence of High-Performance Computing (HPC), data analytics, and Artificial Intelligence (AI) has led to increasingly complex parallel applications. Modern workflows often integrate multiple parallel runtimes (e.g., OpenMP, TBB, PyTorch) within a single process or across co-located jobs. This complexity creates severe scheduling challenges, particularly under oversubscription (where the number of ready threads exceeds available cores).

Traditional OS schedulers (e.g., Linux's EEVDF) rely on periodic preemption based on fixed time quanta to enforce fairness. In oversubscribed HPC and AI environments, this approach introduces significant "scheduling noise," including:

• Interference: Preemptions disrupt critical-path computations and pollute CPU caches.
• Lock-Holder Preemption (LHP) and Lock-Waiter Preemption (LWP): Preempting a thread holding a lock or waiting for one degrades performance and can cause scalability collapse.
• Runtime Composition Issues: Multiple runtimes creating independent worker pools lead to thread redundancy and resource contention.
• Inflexibility: Existing solutions often require resource partitioning (static core assignment) or a single unified runtime, which are difficult to adopt given the heterogeneity of HPC software stacks.

Developers historically avoid combining runtimes or co-executing processes to "fill gaps" in resource usage due to these performance penalties.

2. Methodology

The authors propose a two-part solution: the User-space Scheduling Framework (USF) and a default cooperative policy named SCHED_COOP.

The User-space Scheduling Framework (USF)

USF is a seamless framework implemented entirely in user-space by extending the GNU C Library (glibc). It does not require kernel modifications, special permissions, or invasive application changes.

• Architecture: USF extends glibc (creating glibcv) and integrates with the nOS-V threading and tasking library.
• Mechanism: It intercepts standard pthread APIs (creation, destruction, blocking, affinity). When a pthread is created, it is converted into a nOS-V worker thread associated with a task.
• Multi-process Support: USF utilizes a shared memory segment to maintain a centralized scheduler across multiple processes. Idle workers can pick up tasks from any process, but execution is strictly managed to ensure one worker per core at all times.
• Thread-Local Storage (TLS): Because tasks remain bound to the same worker thread, USF maintains full compatibility with TLS, a critical requirement for many runtimes.

SCHED_COOP Policy

SCHED_COOP is a cooperative scheduling policy designed specifically for oversubscribed HPC and AI workloads.

• Cooperative Switching: Unlike preemptive OS schedulers, SCHED_COOP threads run uninterruptedly on a single core until they block (e.g., on a mutex, condition variable, or I/O) or voluntarily yield.
• No Periodic Preemption: Threads are never preempted by the scheduler. Context switches occur only at explicit scheduling points (task suspension, completion, or yield).
• Affinity Management: Threads retain a preferred affinity to their last running core. Upon unblocking, the scheduler attempts to place the thread back on its preferred core, falling back to the same NUMA domain or any available node if necessary.
• Blocking Interception: The framework intercepts blocking calls (e.g., pthread_mutex_lock). If a thread blocks, it notifies the scheduler, which immediately assigns another ready task to that core, ensuring the core remains busy without the overhead of OS context switches.

3. Key Contributions

1. USF Framework: A novel, seamless user-space scheduling framework that allows users to implement custom scheduling policies without kernel modifications, special permissions, or application source code changes. It supports multi-process coordination and TLS.
2. SCHED_COOP Policy: A specific cooperative policy that mitigates oversubscription issues by eliminating periodic preemptions, thereby reducing LHP, LWP, and cache pollution.
3. Seamless Integration: The implementation extends glibc and nOS-V to support standard pthread APIs, covering a vast majority of runtime systems (OpenMP, PyTorch, Rust, etc.) without requiring invasive changes.
4. Comprehensive Evaluation: A detailed evaluation across multi-runtime and multi-process scenarios, including nested BLAS workloads, multi-process PyTorch inference (LLaMA-3), and Molecular Dynamics (MD) simulations.

4. Experimental Results

The evaluation was conducted on a 56-core Intel Sapphire Rapids node (Marenostrum 5) using a production environment where kernel modifications were prohibited.

• Matrix Multiplication (Nested Runtimes): In a benchmark combining OmpSs-2 and BLIS (OpenMP), SCHED_COOP demonstrated speedups between 2% and 28% compared to a tuned baseline (which included manual sched_yield adaptations). The "Manual" integration of nOS-V achieved up to 36% speedup, establishing an upper bound, while the seamless SCHED_COOP approach achieved comparable gains transparently.
• Cholesky Factorization: SCHED_COOP outperformed the baseline in all tested runtime compositions (GNU OpenMP, LLVM OpenMP, TBB, pthreads). Notably, in configurations using the pthread BLAS backend, SCHED_COOP achieved speedups up to 14.7x by transparently caching threads and preventing OS noise, whereas the baseline suffered from frequent thread creation/destruction.
• AI Microservices (LLaMA-3, GPT-2, RoBERTa): In a multi-process inference scenario with varying request rates, SCHED_COOP achieved up to 2.4x higher throughput compared to the best static resource partitioning baseline. It maintained low latency and sustained throughput even under heavy oversubscription, whereas the standard Linux scheduler collapsed due to synchronization noise.
• Molecular Dynamics (LAMMPS + DeePMD-kit): In a scenario involving two concurrent simulation ensembles, SCHED_COOP achieved the highest memory bandwidth usage and performance (up to 4% speedup over co-execution scenarios). It effectively managed load imbalance and eliminated the performance penalties of busy-wait barriers that plagued other configurations.

5. Significance and Claims

The paper claims that USF and SCHED_COOP provide a transparent, practical approach to managing oversubscription in complex HPC and AI environments.

• Enabling Runtime Composition: The framework allows developers to combine multiple runtimes and co-execute processes without the severe performance penalties traditionally associated with oversubscription.
• Eliminating Scheduling Noise: By removing periodic preemptions, the system avoids the interference that disrupts critical computations and degrades cache efficiency.
• Accessibility: Unlike previous user-space schedulers that require kernel patches (e.g., sched_ext with eBPF limitations) or extensive application modifications, USF works on vanilla Linux kernels and requires no elevated privileges.
• Limitations: The authors acknowledge that the framework relies on intercepting standard blocking APIs. Applications using custom busy-wait barriers (common in low-latency runtimes) require manual adaptation (e.g., inserting sched_yield) to function correctly under SCHED_COOP, though this is described as a simple fix.

In conclusion, the paper argues that cooperative user-space scheduling is a viable and effective strategy for modern, heterogeneous workloads, unlocking performance potential in scenarios previously avoided due to scheduling overhead.