Рекурсивно добавляя потоки к пулу потоков Java
Я работаю над учебным руководством для своего курса параллелизма Java. Цель состоит в том, чтобы использовать пулы потоков для вычислений простых чисел параллельно.
Дизайн основан на Решете Эратосфена. Это имеет массив n bools, где n является самым большим целым числом, Вы проверяете, и каждый элемент в массиве представляет одно целое число. Верный является главным, ложным, не является главным, и массив - первоначально все верное.
Пул потоков используется с постоянным числом потоков (мы, как предполагается, экспериментируем с количеством потоков в пуле и наблюдаем производительность).
Потоку дают целое число несколько для обработки. Поток затем находит первый истинный элемент в массиве, который не является несколькими из целого числа потока. Поток затем создает новый поток на пуле потоков, которому дают найденное число.
После того, как новый поток формируется, существующий поток затем продолжает устанавливать все кратные числа, он - целое число в массиве ко лжи.
Основной поток программы запускает первый поток с целого числа '2' и затем ожидает всех порожденных потоков для окончания. Это затем выкладывает простые числа и время, потраченное для вычислений.
Проблема, которую я имею, то, что, чем больше потоков там находится в пуле потоков, тем медленнее он берет с 1 потоком, являющимся самым быстрым. Это должно становиться быстрее не медленнее!
Весь материал в Интернете о пулах потоков Java создает n рабочие потоки, которые основной поток затем ожидает всех потоков для окончания. Метод, который я использую, является рекурсивным, поскольку рабочий может породить больше рабочих потоков.
Я хотел бы знать то, что идет не так, как надо, и если пулы потоков Java могут использоваться рекурсивно.
4 ответа
Решение может работать медленнее, так как потоки добавляются для решения некоторых из следующих проблем:
Накладные расходы на создание потока: создание потока стоит дорого.
Конфликт процессора: если потоков больше, чем процессоров для их выполнения, некоторые из потоков будут приостановлены в ожидании освобождения процессора. В результате падает средняя скорость обработки для каждого потока. Кроме того, ОС затем должна разрезать потоки по времени, а это отнимает время, которое в противном случае использовалось бы для «реальной» работы.
Конфликт за виртуальную память: каждому потоку требуется память для своего стека. Если на вашей машине недостаточно физической памяти для рабочей нагрузки, каждый новый стек потока увеличивает конкуренцию за виртуальную память, что приводит к разбиению на страницы, что замедляет работу
Конфликт кеша: каждый поток (предположительно) будет сканировать разные части массива , что приводит к пропускам кеш-памяти. Это замедляет доступ к памяти.
Конфликт блокировок: если все ваши потоки читают и обновляют общий массив и используют
synchronizedи один объект блокировки для управления доступом к массиву, вы можете столкнуться с конфликтом блокировок. Если используется один объект блокировки, каждый поток будет проводить большую часть времени в ожидании получения блокировки. В конечном итоге вычисление эффективно сериализуется, а общая скорость обработки падает до скорости одного процессора / потока.
Первые четыре проблемы присущи многопоточности, и реальных решений нет ... кроме не создания слишком большого количества потоков и повторного использования тех, которые вы уже создали.Однако есть несколько способов решить проблему конкуренции за блокировку. Например,
- перекодируйте приложение так, чтобы каждый поток просматривал несколько целых чисел, но в своем собственном разделе массива. Это устранит конкуренцию за блокировку массивов, хотя тогда вам понадобится способ сообщить каждому потоку, что делать, и это должно быть спроектировано с учетом конкуренции.
- Создайте массив блокировок для различных областей массива и попросите потоки выбрать блокировку для использования в зависимости от области массива, с которой они работают. Вы по-прежнему будете получать разногласия, но в среднем их будет меньше.
- Разработайте и внедрите решение без блокировки. Это повлечет за собой ГЛУБОКОЕ ПОНИМАНИЕ модели памяти Java. И было бы очень сложно доказать / продемонстрировать, что решение без блокировки не содержит тонких недостатков параллелизма.
Наконец, рекурсивное создание потоков, вероятно, является ошибкой, так как это затруднит реализацию повторного использования потоков и меры по борьбе с блокировками.
Измените структуру вашей программы, чтобы заранее создать фиксированный ThreadPoolExecutor. Убедитесь, что вы вызываете ThreadPoolExecutor # prestartAllCoreThreads ().Попросите ваш основной метод отправить задачу для целого числа 2. Каждая задача отправит другую задачу. Поскольку вы используете пул потоков, вы не будете создавать и завершать группу потоков, а вместо этого разрешаете тем же потокам выполнять новые задачи по мере их доступности. Это снизит общие накладные расходы на выполнение.
Вы должны обнаружить, что в этом случае оптимальное количество потоков равно количеству процессоров (P) на машине. Часто бывает, что оптимальное количество потоков составляет P + 1. Это связано с тем, что P + 1 минимизирует накладные расходы от переключения контекста, а также минимизирует потери от времени ожидания / блокировки.
Сколько процессоров доступно в вашей системе? Если #threads> #processors, добавление дополнительных потоков замедлит выполнение такой задачи, связанной с вычислением, как эта.
Помните, что сколько бы потоков вы ни запустили, они все равно используют одни и те же ЦП. Чем больше времени ЦП тратит на переключение между потоками, тем меньше времени он может выполнять фактическую работу.
Также обратите внимание, что стоимость запуска потока значительна по сравнению со стоимостью проверки простого числа - вы, вероятно, можете сделать сотни или тысячи умножений за время, необходимое для запуска 1 потока.
Ключевым моментом пула потоков является поддержание активности набора потоков и их повторное использование обрабатывать задачи. Обычно шаблон состоит в том, чтобы иметь очередь задач и случайным образом выбирать один поток из пула для его обработки. Если свободного потока нет, а пул заполнен, просто подождите.
Разработанная вами проблема не подходит для решения пулом потоков, потому что вам нужно, чтобы потоки выполнялись по порядку. Поправьте меня, если я здесь не прав.
поток № 1: установить кратное 2 равным false
поток № 2: найти 3, установить кратное 3 как false
поток № 3: найти 5, установить кратное 5 в значение false
поток № 4: найти 7, задайте для кратного 7 значение false
....
Эти потоки нужно запускать по порядку, и они чередуются (как их планирует среда выполнения) имеет значение.
Например, если поток № 3 запускается до того, как поток № 1 устанавливает «4» в ложь, он найдет «4» и продолжит сбрасывать кратные 4. Это приводит к огромной дополнительной работе, хотя конечный результат будет правильным.