1. Обзор
В этом уроке мы рассмотрим концепцию кражи работы в Java .
2. Что Такое Кража Работы?
Кража работы была введена в Java с целью уменьшения конкуренции в многопоточных приложениях . Это делается с помощью фреймворка fork/join .
2.1. Подход “Разделяй и властвуй”
В структуре fork/join проблемы или задачи рекурсивно разбиваются на подзадачи . Затем подзадачи решаются индивидуально, а подзадачи объединяются для формирования результата:
Result solve(Problem problem) {
if (problem is small)
directly solve problem
else {
split problem into independent parts
fork new subtasks to solve each part
join all subtasks
compose result from subresults
}
}2.2. Рабочие потоки
Разбитая задача решается с помощью рабочих потоков, предоставляемых пулом потоков /. Каждый рабочий поток будет иметь подзадачи, за которые он отвечает. Они хранятся в двойных очередях ( deques ).
Каждый рабочий поток получает подзадачи из своего deque, непрерывно выталкивая подзадачу из верхней части deque. Когда deque рабочего потока пуст, это означает, что все подзадачи были удалены и завершены.
На этом этапе рабочий поток случайным образом выбирает одноранговый поток threadpool, из которого он может “украсть” работу. Затем он использует подход “первый вход, первый выход” (FIFO) для выполнения подзадач из хвостовой части deque жертвы.
3. Реализация фреймворка Fork/Join
Мы можем создать пул потоков, крадущих работу, используя либо Класс ForkJoinPool или Класс исполнителей :
ForkJoinPool commonPool = ForkJoinPool.commonPool(); ExecutorService workStealingPool = Executors.newWorkStealingPool();
Класс Executors имеет перегруженный метод newWorkStealingPool , который принимает целочисленный аргумент, представляющий уровень параллелизма .
Executors.newWorkStealingPool является абстракцией ForkJoinPool.commonPool . Единственное различие заключается в том, что Executors.newWorkStealingPool создает пул в асинхронном режиме, а ForkJoinPool.commonPool этого не делает.
4. Синхронные и Асинхронные пулы потоков
4. Синхронные и Асинхронные пулы потоков использует конфигурацию очереди “последний вход-первый выход” (LIFO), в то время как использует конфигурацию очереди “последний вход-первый выход” (LIFO), в то время как использует первый вход, первый выход (FIFO).
Согласно Doug Lea , подход FIFO имеет эти преимущества перед LIFO:
- Это уменьшает конкуренцию за счет того, что похитители работают на противоположной стороне дека в качестве владельцев
- Он использует свойство рекурсивных алгоритмов ” разделяй и властвуй “для ранней генерации” больших ” задач
Второй пункт выше означает, что можно дополнительно разбить более старую украденную задачу потоком, который ее украл.
Согласно документации Java , установка асинхронного режима в true может быть подходящей для использования с задачами в стиле событий, которые никогда не объединяются.
5. Рабочий Пример – Нахождение Простых Чисел
Мы будем использовать пример поиска простых чисел из набора чисел, чтобы показать преимущества времени вычислений фреймворка кражи работы . Мы также покажем различия между использованием синхронных и асинхронных пулов потоков.
5.1. Проблема простых чисел
Поиск простых чисел из набора чисел может быть вычислительно дорогостоящим процессом. В основном это связано с размером набора чисел.
Класс Простые числа помогает нам находить простые числа:
public class PrimeNumbers extends RecursiveAction {
private int lowerBound;
private int upperBound;
private int granularity;
static final List GRANULARITIES
= Arrays.asList(1, 10, 100, 1000, 10000);
private AtomicInteger noOfPrimeNumbers;
PrimeNumbers(int lowerBound, int upperBound, int granularity, AtomicInteger noOfPrimeNumbers) {
this.lowerBound = lowerBound;
this.upperBound = upperBound;
this.granularity = granularity;
this.noOfPrimeNumbers = noOfPrimeNumbers;
}
// other constructors and methods
private List subTasks() {
List subTasks = new ArrayList<>();
for (int i = 1; i <= this.upperBound / granularity; i++) {
int upper = i * granularity;
int lower = (upper - granularity) + 1;
subTasks.add(new PrimeNumbers(lower, upper, noOfPrimeNumbers));
}
return subTasks;
}
@Override
protected void compute() {
if (((upperBound + 1) - lowerBound) > granularity) {
ForkJoinTask.invokeAll(subTasks());
} else {
findPrimeNumbers();
}
}
void findPrimeNumbers() {
for (int num = lowerBound; num <= upperBound; num++) {
if (isPrime(num)) {
noOfPrimeNumbers.getAndIncrement();
}
}
}
public int noOfPrimeNumbers() {
return noOfPrimeNumbers.intValue();
}
} Несколько важных вещей, которые следует отметить об этом классе:
- Он расширяет RecursiveAction , что позволяет нам реализовать метод compute , используемый в вычислительных задачах с использованием пула потоков
- Он рекурсивно разбивает задачи на подзадачи на основе значения детализации
- Конструкторы принимают нижние и верхние граничные значения, которые управляют диапазоном чисел, для которых мы хотим определить простые числа
- Это позволяет нам определять простые числа, используя либо пул рабочих потоков, либо один поток
5.2. Более быстрое решение проблемы с пулами потоков
Давайте определим простые числа однопоточным способом, а также с помощью пулов потоков, крадущих работу.
Во-первых, давайте рассмотрим однопоточный подход :
PrimeNumbers primes = new PrimeNumbers(10000); primes.findPrimeNumbers();
А теперь, ForkJoinPool.commonPool подход :
PrimeNumbers primes = new PrimeNumbers(10000); ForkJoinPool pool = ForkJoinPool.commonPool(); pool.invoke(primes); pool.shutdown();
Наконец, мы рассмотрим Executors.newWorkStealingPool подход :
PrimeNumbers primes = new PrimeNumbers(10000); int parallelism = ForkJoinPool.getCommonPoolParallelism(); ForkJoinPool stealer = (ForkJoinPool) Executors.newWorkStealingPool(parallelism); stealer.invoke(primes); stealer.shutdown();
Мы используем метод invoke класса ForkJoinPool для передачи задач в пул потоков. Этот метод принимает экземпляры подклассов RecursiveAction . Используя Java Microbench Harness , мы сравниваем эти различные подходы друг с другом с точки зрения среднего времени на операцию:
# Run complete. Total time: 00:04:50 Benchmark Mode Cnt Score Error Units PrimeNumbersUnitTest.Benchmarker.commonPoolBenchmark avgt 20 119.885 ± 9.917 ms/op PrimeNumbersUnitTest.Benchmarker.newWorkStealingPoolBenchmark avgt 20 119.791 ± 7.811 ms/op PrimeNumbersUnitTest.Benchmarker.singleThread avgt 20 475.964 ± 7.929 ms/op
Понятно, что и ForkJoinPool.commonPool , и Executors.newWorkStealingPool позволяют определять простые числа быстрее, чем при однопоточном подходе.
Структура пула fork/join позволяет нам разбить задачу на подзадачи. Мы разбили коллекцию из 10 000 целых чисел на партии по 1-100, 101-200, 201-300 и так далее. Затем мы определили простые числа для каждой партии и сделали общее количество простых чисел доступным с помощью нашего метода noOfPrimeNumbers .
5.3. Кража работы для вычисления
С асинхронным пулом потоков ForkJoinPool.commonPool помещает потоки в пул до тех пор, пока задача все еще выполняется. В результате уровень кражи работы не зависит от уровня детализации задачи.
Асинхронный Executors.newWorkStealingPool является более управляемым, позволяя уровню выполнения работы зависеть от уровня детализации задачи.
Мы получаем уровень кражи работы с помощью getStealCount класса ForkJoinPool :
long steals = forkJoinPool.getStealCount();
Определение количества краж работы для Executors.newWorkStealingPool и ForkJoinPool.commonPool дает нам разное поведение:
Executors.newWorkStealingPool -> Granularity: [1], Steals: [6564] Granularity: [10], Steals: [572] Granularity: [100], Steals: [56] Granularity: [1000], Steals: [60] Granularity: [10000], Steals: [1] ForkJoinPool.commonPool -> Granularity: [1], Steals: [6923] Granularity: [10], Steals: [7540] Granularity: [100], Steals: [7605] Granularity: [1000], Steals: [7681] Granularity: [10000], Steals: [7681]
Когда степень детализации изменяется от тонкой до грубой (от 1 до 10 000) для исполнителей.newWorkStealingPool , уровень кражи работы уменьшается . Таким образом, количество краж равно единице, когда задача не разбита на части (степень детализации 10 000).
ForkJoinPool.commonPool имеет другое поведение. Уровень воровства работы всегда высок и не сильно зависит от изменения детализации задач.
Технически говоря, наш пример простых чисел-это тот, который поддерживает асинхронную обработку задач в стиле событий. Это происходит потому, что наша реализация не обеспечивает объединение результатов.
Можно привести пример, что Executors.newWorkStealingPool предлагает наилучшее использование ресурсов для решения проблемы.
6. Заключение
В этой статье мы рассмотрели воровство работы и то, как его применять с помощью фреймворка fork/join. Мы также рассмотрели примеры кражи работы и то, как это может улучшить время обработки и использование ресурсов.
Как всегда, полный исходный код примера доступен на GitHub .