Java Fork/Объяснить использование стека

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

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

Как я знаю, JVM не поддерживает оптимизацию хвостовых вызовов (которая может служить в этой ситуации для удаления фрейма стека метода соединения) Я считаю, что при выполнении сложной операции с большим количеством вилок и объединении потока может StackOverflowError.

Я прав, или они нашли какой-нибудь классный способ предотвратить это?

EDIT

Вот сценарий, который поможет прояснить вопрос: Скажите (для простоты), что у нас есть только один поток в пуле forkjoin. В какой-то момент времени поток вилки и затем звонки соединяются. В то время как в методе соединения поток обнаруживает, что он может выполнить разветвленную задачу (как она найдена в ее очереди), поэтому она вызывает следующую задачу. Эта задача, в свою очередь, вилки, а затем вызывает join - поэтому при выполнении метода соединения поток найдет разветвленную задачу в своей очереди (как и раньше) и вызовет ее. на этом этапе стек вызовов будет содержать по крайней мере кадры для двух соединений и двух задач.

поскольку вы можете видеть, что каркас fork join преобразован в обычную рекурсию. Поскольку java не поддерживает оптимизацию хвостового вызова - каждая рекурсия в java может вызвать StackOverflowError, если она будет достаточно глубокой.

Мой вопрос в том, что разработчик инфраструктуры fork/join нашел классный способ предотвратить эту ситуацию.

Ответ 1

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

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

Ответ 2

Как правило, каждая новая задача, наложенная на стек, вдвое меньше предыдущей. Таким образом, объем работы растет экспоненциально с размером стека. Даже с крошечным стеком вы сможете поместиться на более чем достаточно работы, чтобы вы были заняты в течение некоторого времени.

Ответ 3

Надеюсь, я правильно понимаю вас.

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

Очень интересным местом для метода fork является ForkJoinWorkerThread.pushTask с использованием небезопасных объектов, поэтому вам следует обратить внимание на то, что массив используется для хранения задач.

EDIT: Первое и простое - когда вы находитесь на вершине очереди, вы просто раскалываете и выполняете, и возвращается retult. (Forkjointask.java:353)

При наличии зависимостей используется другой подход, в этом случае управление возвращается WorkerThread, который затем отвечает за обнаружение цепей и их выполнение. Первый работник проверяет местную очередь на любые незавершенные задачи, и если такие задачи не выполняются, то передается задание и возвращается результат, иначе он переходит к следующему случаю. Это помогает крадущикам несколько раз. Ничто не могло помочь... Повторные попытки, которые на первом шаге равны MAX_HELP, теперь равны нулю - управление передается в пул, который выполняет несколько проверок и выполняет tryAwaitDone. И в этом методе wait вызывается для ожидания завершения задачи.

Это означало бы, что пул объединения fork завершится несколькими шагами, пытаясь оптимизировать скорость и время, избегая ожидающих вызовов. Однако это может закончиться в ожидании, тогда это означало бы начало процесса синхронизации, что очень дорого.

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