Synchronization primitives as the distributed ready queue
Date
2026
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Moderne Software stützt sich zunehmend auf kooperatives Multitasking. Beim kooperativen Multitasking erfolgen Scheduling und Synchronisation vollständig im Userspace. Dadurch werden aufwendige Systemaufrufe und Kontextwechsel auf Thread-Ebene vermieden, was der Leistung zugutekommt. In modernen Systemen, welche Scheduling ausschließlich im Userspace betreiben, werden Scheduling und Synchronisation getrennt behandelt. Das Scheduling erfolgt über einen Work-Stealing-Thread-Pool, während die Synchronisation mit sogenannten task-aware Synchronisationsprimitiven durchgeführt wird. Dieses Design kann jedoch bei hoher Auslastung zusätzlichen Overhead verursachen.
In dieser Arbeit wollen wir einen neuen Ansatz für Userspace-Scheduling untersuchen, der Scheduling und Synchronisation vereint. Wir verteilen Ready-Queues auf die Mutexe, sodass jeder Mutex über eine Blocked- und eine Ready-Queue verfügt. Bei hoher Auslastung zeigen kritische Abschnitte oft das Muster, dass wenn ein Task den kritischen Abschnitt verlässt, ein anderer Task bereits versucht, ihn zu betreten und folglich blockiert wird. Mit diesem Design können wir diese Beobachtung nutzen und die Kontrolle von dem eintretenden Task an den Task übergeben, der den kritischen Abschnitt verlässt. Wir bezeichnen diesen Ansatz als Relay Scheduling. Wir vergleichen unseren neuen Ansatz mit bestehenden Lösungen anhand mehrerer Microbenchmarks sowie eines Application Benchmarks. Wir zeigen, dass Relay Scheduling besonders bei einer geringen Anzahl von Threads eine gute Leistung erbringt.
Modern software increasingly relies on cooperative multitasking. With cooperative multitasking, scheduling and synchronization is handled entirely in user space. This avoids heavy system calls and thread-level context switches, which benefits performance. In state-of-the-art user space scheduled systems, scheduling and synchronization is tackled separately. Scheduling is handled by a work-stealing thread pool and synchronization is done with task-aware synchronization primitives. This design, however, can introduce additional overhead under high contention. In this thesis, we want to investigate a new approach to user space scheduling that combines scheduling and synchronization into one system. Instead of maintaining a global ready queue at the thread pool, we distribute ready queues among the mutexes, such that each mutex has a blocked and a ready queue. Under high contention, critical sections often show the pattern that when a task leaves the critical section, another task is already attempting to enter it and is consequently blocked. With this design we can leverage this observation and hand control from the entering task that is blocked to the one that left the critical section. We call this approach Relay Scheduling. We compare our new approach to existing solutions using several microbenchmarks as well as an application benchmark. We will show that Relay Scheduling performs particularly well for low thread counts.
Modern software increasingly relies on cooperative multitasking. With cooperative multitasking, scheduling and synchronization is handled entirely in user space. This avoids heavy system calls and thread-level context switches, which benefits performance. In state-of-the-art user space scheduled systems, scheduling and synchronization is tackled separately. Scheduling is handled by a work-stealing thread pool and synchronization is done with task-aware synchronization primitives. This design, however, can introduce additional overhead under high contention. In this thesis, we want to investigate a new approach to user space scheduling that combines scheduling and synchronization into one system. Instead of maintaining a global ready queue at the thread pool, we distribute ready queues among the mutexes, such that each mutex has a blocked and a ready queue. Under high contention, critical sections often show the pattern that when a task leaves the critical section, another task is already attempting to enter it and is consequently blocked. With this design we can leverage this observation and hand control from the entering task that is blocked to the one that left the critical section. We call this approach Relay Scheduling. We compare our new approach to existing solutions using several microbenchmarks as well as an application benchmark. We will show that Relay Scheduling performs particularly well for low thread counts.