Java Thread Live Lock

Question

У меня есть интересная проблема, связанная с прямыми прямыми потоками Java. Вот оно.

Есть четыре глобальных замков - L1, L2, L3, L4

Есть четыре потока - Т1, Т2, Т3, Т4

Т1 требует блокировки L1, L2, L3, Т2 требует блокировки L2 T3 необходимые блокировки L3, L4 T4 требует блокировки L1, L2

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

Таким образом, чтобы решить эту проблему, у меня есть два решения в виде

1) Пусть каждый нить ожидание случайного периода времени перед повтором.

OR, 

2) Пусть каждый поток приобретает все замки в определенном порядке (даже если поток не требует всех замков)

Я не уверен, что это единственные два варианта доступен меня. Пожалуйста, порекомендуйте.

Answer 1

Если у вас нет веской причины (исполнение разумно), Я бы объединил все блокировки в один объект блокировки. Это похоже на решение 2, которое вы предложили, только более простым, на мой взгляд.

И, кстати, не только это решение является более простым и менее пропущенным, Производительность может быть лучше, чем решение 1, которое вы предложили.

Answer 2

Лично я никогда не слышал о Варианте 1, но я ни в коем случае не специалист по многопоточности. Подумав об этом, похоже, что все будет хорошо.

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

Answer 3

Пойдите с 2a) Пусть каждая нить приобретает все блокировки, которые ему нужны (не все замки) в определенном порядке; если поток встречает блокировку, которая недоступна, то она освобождает все свои блокировки

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

Вы также можете упростить работу, реализовав решение omer schleifer's condense-all-locks-one-one; однако, если для этих ресурсов не существуют потоки, отличные от указанных вами четырех (в этом случае вам по-прежнему нужно будет блокировать ресурсы из внешних потоков), вы можете более эффективно реализовать это, удалив все блокировки и помещая ваши потоки в круговой очереди (так что ваши потоки продолжают работать в одном порядке).

Answer 4

Все нити входят в одну государственную машину, защищенную мьютексом, каждый раз, когда требуется, и отпустите свой набор блокировок. Потоки должны выставлять методы, которые возвращают набор блокировок, которые им требуются для продолжения, а также для сигнала/ожидания для частного семафорного сигнала. SM должен содержать bool для каждой блокировки и «Waiting» queue/array/vector/list/any container для хранения ожидающих потоков.

Если нить входит в мьютексу SM, чтобы получить блокировки и может сразу установить свой замок, он может сбросить свой набор bool, выйти из мьютекса и продолжить.

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

Если нить входит в мьютексу SM, чтобы освободить его блокировки, она устанавливает блокировку, чтобы «вернуть» свои блокировки и повторяет «Ожидание», пытаясь найти поток, который теперь может работать с набором доступных замков. Если он найдет один, он сбрасывает bools соответствующим образом, удаляет поток, который он нашел из «Waiting», и сигнализирует «найденный» поток семафора. Затем он выходит из мьютекса.

Вы можете использовать алгоритм, который вы используете, чтобы соответствовать доступным настройкам блокировки bools с ожидающими потоками, как вы пожелаете. Возможно, вам следует освободить поток, требующий наибольшего набора совпадений, или, возможно, вы хотите «повернуть» элементы контейнера «Ожидание», чтобы уменьшить голод. Вам решать.

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

Гораздо проще разработать такую ​​схему с дизайном OO. Методы/функции-члены для сигнализации/ожидания семафора и возврата набора необходимых блокировок обычно могут быть заполнены где-то в цепочке наследования класса потоков.