Multi Bucket Queues: Efficient Concurrent Priority Scheduling
Guozheng Zhang, Gilead Posluns, Mark C. Jeffrey · 2024
Many irregular algorithms converge more quickly when they execute tasks in a specific order. When this order is discovered at run time, the algorithm demands a dynamic task scheduler. Scaling a priority scheduler to large systems with many cores is challenging and while many concurrent priority schedulers (CPS) have been proposed, a general classification of their design space is still lacking. We survey prior work and propose three dimensions for the design of CPSs: the degree of synchrony, the drift of priorities, and the underlying data structure. We use this taxonomy to classify existing schedulers and evaluate their strengths and weaknesses.