High performance wait-free thread scheduling on shared memory multiprocessors

Abstract

We describe a system for effciently scheduling large numbers of user-level threads on shared memory multiprocessors. The scheduler augments the per-processor run queue model with wait-free data structures and a technique known as thread batching to balance the workload across processors while preserving cache content and minimising contention. Preliminary results indicate significant improvements in performance over the traditional lock-based shared run queue approach, especially when scheduling fine grained threads.