Модифікація алгоритму пулу потоків з багатьма чергами

Abstract

Наведено модифікацію алгоритму пулу потоків, який запропонував Шон Парент на конференції NDC London 2017. Запропонований алгоритм не поступається оригінальному алгоритму за швидкодією та простотою реалізації, і водночас усуває потенційний недолік оригінального алгоритму, який полягає у тому, що за певних обставин кілька задач можуть виконуватися на тому самому потоці, тоді як інші потоки – перебувати в стані очікування задачі. Основна ідея, яка запропонована в роботі, полягає у відстеженні сумарної кількості задач, які містяться в чергах пулу потоків. Коли головний потік поміщає нову задачу в якусь із черг, лічильник кількості задач збільшується на одиницю. Коли задача вилучається з черги, лічильник кількості задач зменшується на одиницю. У випадку, коли потік пулу хоче отримати задачу, він переглядає черги доти, доки йому не вдасться отримати задачу з якоїсь із черг або доки лічильник кількості задач не дорівнюватиме нулю. Якщо лічильник кількості задач дорівнює нулеві, потік переходить у стан сну до моменту, коли лічильник кількості потоків не стане знову ненульовим. Тоді один із потоків пулу прокидається і починає перевіряти черги на наявність задач. Дуже важливо зберегти рівномірний розподіл задач по чергах, оскільки це істотно впливає на швидкодію програми.

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.