Modification of a thread Pool algorithm with multiple task queues

: pp. 96 - 102
Lviv Polytechnic National University, Ukraine

In this paper, the author suggests a modification of the thread pool algorithm that was presented by Sean Parent at NDC London 2017. The suggested algorithm is as simple as the original implementation and demonstrates similar performance, while eliminating a potential drawback of the original implementation consisting in the fact that under certain circumstances, multiple tasks can be executed on the same thread, while other threads may be waiting for a task.

The suggested idea consists in tracking the total number of tasks that are in the queues of the thread pool. When the main thread pushes a new task to one of the queues, the tasks counter is incremented. When a task is removed from the queue, the task counter is decremented. When a thread wants to get a task, it keeps checking the queues until it succeeds in getting a task from one of the queues, or until the tasks counter becomes equal to zero. When the tasks counter becomes equal to zero, the thread becomes idle until the counter becomes non-zero again. Then, one of the threads wakes up and starts checking the queues. An important point is to maintain even distribution of tasks in the queues since it has a significant impact on the performance of the algorithm.

  1. Amdahl G., The validity of the single processor approach to achieving large-scale computing capabilities, Proceedings of AFIPS Spring Joint Computer Conference, Atlantic City, N.J., AFIPS Press, pp. 483-485.
  2. ISO International Standard ISO/IEC 14882:2020(E) – Programming Language C++. 
  3. David Chase and Yossi Lev, Dynamic circular work-stealing deque, SPAA, pp. 21–28. ACM, 2005. DOI:10.1145/1073970.1073974
  4. K. Agrawal et al. Executing task graphs using work-stealing, IEEE IPDPS, April 2010, pp. 1–12. DOI:10.1109/IPDPS.2010.5470403
  5. Nhat Minh et al., Correct and efficient work-stealing for weak memory models, PPoPP, pp. 69–80. ACM, 2013. DOI:10.1145/2442516.2442524
  6. T. Huang et al., Cpp-Taskflow: Fast task-based parallel programming using modern C++. In IEEE IPDPS, May 2019, pp. 974–983. DOI: 10.1109/IPDPS.2019.00105
  7. C. -X. Lin, T. -W. Huang and M. D. F. Wong, An Efficient Work-Stealing Scheduler for Task Dependency Graph, 2020 IEEE 26th International Conference on Parallel and Distributed Systems (ICPADS), Hong Kong, 2020, pp. 64-71, doi: 10.1109/ICPADS51040.2020.00018
  8. Intel oneAPI Threading Building Blocks. [Elektronnyi resurs]. -URL:
  9. Sean Parent, Better Code: Concurrency, NDC { London } 2017. [Elektronnyi resurs]. -URL:
  10. Thread Pool Benchmark. [Elektronnyi resurs]. -URL: benchmark/