Рекурсивное добавление потоков в пул потоков Java

Question

Я работаю над учебником для моего курса по параллелизму Java. Цель состоит в том, чтобы использовать пулы потоков для параллельного вычисления простых чисел.

Дизайн основан на Сите Эратосфена. Он имеет массив из n bools, где n - наибольшее целое число, которое вы проверяете, и каждый элемент в массиве представляет одно целое число. Истина - это простое число, ложь - не простое число, и изначально весь массив является истинным.

Пул потоков используется с фиксированным числом потоков (мы должны поэкспериментировать с количеством потоков в пуле и наблюдать за производительностью).

Потоку дается целое число, кратное процессу. Затем поток находит первый истинный элемент в массиве, который не кратен целому числу потока. Затем поток создает новый поток в пуле потоков, которому присваивается найденный номер.

После формирования нового потока существующий поток продолжает устанавливать для всех кратных его целого числа в массиве значение false.

Основной поток программы начинает первый поток с целого числа '2', а затем ожидает завершения всех созданных потоков. Затем он выплевывает простые числа и время, необходимое для вычисления.

Проблема, с которой я столкнулся, заключается в том, что чем больше потоков в пуле потоков, тем медленнее будет процесс, когда 1 поток будет самым быстрым. Должно быть быстрее, а не медленнее!

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

Я хотел бы знать, что происходит, и можно ли рекурсивно использовать пулы потоков Java.

Answer 1

Ваше решение может работать медленнее, поскольку потоки добавляются для решения некоторых из следующих проблем:

• Затраты на создание потока: создание потока стоит дорого.

• Конфликт процессора: если потоков больше, чем процессоров для их выполнения, некоторые потоки будут приостановлены в ожидании свободного процессора. В результате средняя скорость обработки для каждого потока падает. Кроме того, ОС затем необходимо разделить потоки по времени, и это отнимает время, которое в противном случае использовалось бы для «реальной» работы.

• Конфликт виртуальной памяти: каждому потоку требуется память для своего стека. Если на вашей машине недостаточно физической памяти для рабочей нагрузки, каждый новый стек потоков увеличивает конкуренцию за виртуальную память, что приводит к подкачке страниц, что замедляет работу

• Конфликт в кэше: каждый поток (предположительно) будет сканировать другой раздел массива, что приведет к отсутствию кэша памяти. Это замедляет доступ к памяти.

• Конфликт блокировки: если все ваши потоки читают и обновляют общий массив и используют synchronized и один объект блокировки для управления доступом к массиву, вы можете страдать от конфликта блокировок. Если используется один объект блокировки, каждый поток будет проводить большую часть своего времени в ожидании получения блокировки. Конечным результатом является то, что вычисления эффективно сериализуются, и общая скорость обработки падает до скорости одного процессора / потока.

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

• Перекодируйте приложение так, чтобы каждый поток сканировал несколько целых чисел, но в своем собственном разделе массива. Это исключит конфликты блокировок на массивах, хотя тогда вам потребуется способ сообщить каждому потоку, что делать, и это нужно разрабатывать с учетом конкуренции.
• Создайте массив блокировок для различных областей массива и попросите потоки выбрать используемую блокировку на основе области массива, с которой они работают. Вы все равно получите раздор, но в среднем вы должны будете получить меньше раздоров.
• Разработка и внедрение решения без блокировки. Это повлечет за собой глубокое понимание модели памяти Java. И было бы очень трудно доказать / продемонстрировать, что решение без блокировки не содержит тонких недостатков параллелизма.

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

Answer 2

Сколько процессоров доступно в вашей системе? Если #threads> #processors, добавление большего количества потоков замедлит выполнение задачи, связанной с вычислениями, подобной этой.

Запомните, сколько бы потоков вы ни запустили, они все еще используют один и тот же процессор. Чем больше времени процессор тратит на переключение между потоками, тем меньше времени он может выполнять фактическую работу.

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

Answer 3

Реструктурируйте вашу программу, чтобы заранее создать фиксированный ThreadPoolExecutor. Убедитесь, что вы вызываете ThreadPoolExecutor # prestartAllCoreThreads (). Пусть ваш основной метод отправит задачу на целое число 2. Каждая задача отправит еще одну задачу. Поскольку вы используете пул потоков, вы не будете создавать и завершать группу потоков, а вместо этого позволять тем же потокам выполнять новые задачи по мере их появления. Это уменьшит общие накладные расходы на выполнение.

Вы должны обнаружить, что в этом случае оптимальное количество потоков равно количеству процессоров (P) на машине. Часто бывает так, что оптимальное количество потоков составляет P + 1. Это связано с тем, что P + 1 минимизирует накладные расходы при переключении контекста, а также минимизирует потери из-за простоя / времени блокировки.

Answer 4

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

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

поток # 1: установить кратное 2 для false

тема # 2: найти 3, установить кратное 3 в false

тема # 3: найти 5, установить кратное 5 для false

тема # 4: найти 7, установить кратное 7 для false

....

Эти потоки должны быть запущены по порядку, и они чередуются (как расписание их выполнения) имеет значение.

Например, если поток № 3 запускается до того, как поток № 1 установит «4» в значение «ложь», он найдет «4» и продолжит сбрасывать кратные 4. Это в конечном итоге делает много дополнительной работы, хотя окончательный результат будет правильным.