Java Thread Live Lock
У меня есть интересная проблема, связанная с живой блокировкой потока Java. Здесь это идет.
Есть четыре глобальных замка - L1,L2,L3,L4
Есть четыре темы - T1, T2, T3, T4
T1 требует замков L1,L2,L3 T2 требует замков L2 T3 требует замков L3,L4 T4 требует замков L1, L2
Таким образом, проблема заключается в следующем: любой из потоков может работать и получать блокировки в любом порядке. Если какой-либо поток обнаруживает, что необходимая ему блокировка недоступна, он снимает все другие ранее заблокированные блокировки, ожидает в течение фиксированного времени, а затем повторяет попытку. Цикл повторяется, вызывая состояние блокировки в реальном времени.
Итак, чтобы решить эту проблему, я имею в виду два решения
1) Пусть каждый поток ждет случайный промежуток времени перед повторной попыткой.
OR,
2) Пусть каждый поток получает все блокировки в определенном порядке (даже если поток не требует всех блокировок)
Я не уверен, что это единственные доступные мне два варианта. Пожалуйста, порекомендуйте.
4 ответа
Пусть все потоки входят в один защищенный мьютексом конечный автомат всякий раз, когда им требуется, и освобождают свой набор блокировок. Потоки должны предоставлять методы, которые возвращают набор блокировок, которые им необходимы для продолжения, а также сигнализируют / ждут частный сигнал семафора. SM должен содержать bool для каждой блокировки и очередь "Ожидание" / массив / вектор / список / любой контейнер для хранения ожидающих потоков.
Если поток входит в мьютекс SM для получения блокировок и может немедленно получить свой набор блокировок, он может сбросить набор bool, выйти из мьютекса и продолжить.
Если поток входит в мьютекс SM и не может немедленно получить свою блокировку, он должен добавить себя в "Ожидание", выйти из мьютекса и ждать своего частного семафора.
Если поток входит в мьютекс SM для снятия своих блокировок, он устанавливает bool s блокировки для "возврата" своих блокировок и повторяет "Ожидание", пытаясь найти поток, который теперь может работать с доступным набором блокировок. Если он находит его, он соответствующим образом сбрасывает bool, удаляет найденный поток из "Ожидания" и сигнализирует семафор "найденный" потока. Затем он выходит из мьютекса.
Вы можете использовать алгоритм, который вы используете для согласования доступных наборов блокировок с ожидающими потоками, как вы хотите. Возможно, вам следует освободить поток, который требует наибольшего набора совпадений, или, возможно, вы хотите "повернуть" элементы контейнера "Ожидание", чтобы уменьшить голод. Вам решать.
Подобное решение не требует опроса (с использованием процессора, снижающего производительность и задержкой), а также не требует непрерывного получения / снятия нескольких блокировок.
Намного проще разработать такую схему с ОО-дизайном. Методы / функции-члены, которые сигнализируют / ждут семафор и возвращают набор необходимых блокировок, обычно могут быть вставлены где-нибудь в цепочку наследования класса потока.
Лично я никогда не слышал о Варианте 1, но я ни в коем случае не эксперт по многопоточности. Подумав об этом, звучит так, будто все будет хорошо.
Однако стандартный способ работы с потоками и блокировкой ресурсов в некоторой степени связан с вариантом 2. Для предотвращения взаимных блокировок ресурсы всегда должны быть получены в одном и том же порядке. Например, если вы всегда блокируете ресурсы в одном и том же порядке, у вас не возникнет никаких проблем.
Если для этого нет веской причины (с точки зрения производительности), я бы объединил все блокировки в одном объекте блокировки. Это похоже на предложенное вами решение 2, только на мой взгляд, более простое.
И, кстати, не только это решение более простое и менее подвержено ошибкам, производительность может быть лучше, чем решение 1, которое вы предложили.
Перейти к пункту 2а) Пусть каждый поток получает все необходимые ему блокировки (НЕ все блокировки) в определенном порядке; если поток обнаруживает блокировку, которая недоступна, он освобождает все свои блокировки
Пока потоки получают свои блокировки в том же порядке, вы не можете иметь тупик; однако у вас все еще может быть голод (поток может столкнуться с ситуацией, когда он продолжает освобождать все свои блокировки, не продвигаясь вперед). Чтобы гарантировать прогресс, вы можете назначить приоритеты потокам (0 = самый низкий приоритет, MAX_INT = самый высокий приоритет) - увеличить приоритет потока, когда он должен снять свои блокировки, и уменьшить его до 0, когда он получит все свои блокировки. Поместите ожидающие потоки в очередь и не запускайте поток с более низким приоритетом, если ему нужны те же ресурсы, что и поток с более высоким приоритетом - таким образом вы гарантируете, что потоки с более высоким приоритетом в конечном итоге получат все свои блокировки. Не реализуйте эту очередь потоков, если у вас действительно нет проблем с голоданием потоков, потому что это, вероятно, менее эффективно, чем просто запускать все ваши потоки одновременно.
Вы также можете упростить задачу, внедрив решение "конденсировать все замки в одном", которое дает Омер Шлейфер; однако, если потоки, отличные от четырех, о которых вы упомянули, не конкурируют за эти ресурсы (в этом случае вам все равно придется блокировать ресурсы от внешних потоков), вы можете более эффективно реализовать это, сняв все блокировки и поместив свои потоки. в кольцевой очереди (поэтому ваши потоки просто продолжают работать в том же порядке).