Является ли работа кражей всегда наиболее подходящим алгоритмом планирования потока пользовательского уровня?

Я изучал различные алгоритмы планирования для пула потоков, который я реализую. Из-за характера проблемы, которую я решаю, я могу предположить, что выполняемые параллельно задачи независимы и не порождают новых задач. Задачи могут быть разных размеров.

Я сразу же пошел на самый популярный алгоритм планирования "кражу работы", используя блокировки без ограничений для локальных очередей заданий, и я довольно доволен этим подходом. Однако мне интересно, существуют ли какие-либо распространенные случаи, когда кража работы - это не лучший подход.

Для этой конкретной задачи я имею хорошую оценку размера каждой отдельной задачи. Работа-кража не использует эту информацию, и мне интересно, есть ли какой-либо планировщик, который даст лучшую балансировку нагрузки, чем кражу работы с этой информацией (очевидно, с той же эффективностью).

NB. Этот вопрос связан с предыдущим question.

Ответ 1

Я бы распределял задачи заранее. С информацией об их предполагаемом времени работы вы можете распределить их в отдельные очереди для каждого потока.

Распространение задач в основном на проблема ранца, каждая очередь должна занимать одинаковое количество времени.

Вы должны добавить некоторую логику для изменения очередей во время их запуска. Например, повторное распределение должно происходить после того, как расчетное время работы отличается на определенную величину от реального времени работы.

Ответ 2

Верно, что планировщик вождения работы не использует эту информацию, но это связано с тем, что он не зависит от нее, чтобы предоставить теоретические ограничения (например, используемую память, ожидаемую общую связь между работниками и также ожидаемое время для выполнения полностью строгих вычислений, как вы можете прочитать здесь: http://supertech.csail.mit.edu/papers/steal.pdf)

Один интересный документ (на который я надеюсь, что вы можете получить доступ: http://dl.acm.org/citation.cfm?id=2442538) на самом деле использует ограниченное время выполнения для предоставления формальных доказательств (которые пытаются как можно ближе к исходным границам работы).

И да, бывают случаи, когда кража работы не выполняется оптимально (например, несбалансированный поиск дерева и другие частные случаи). Но для этих случаев были сделаны оптимизации (например, разрешив украсть половину жертвы deque, вместо того, чтобы выполнять только одну задачу: http://dl.acm.org/citation.cfm?id=571876).