#java #concurrency
#java #параллелизм
Вопрос:
Формулировка проблемы заключается в следующем:
Часто набор взаимодействующих потоков выполняет серию шагов в цикле и синхронизируется на барьере после каждого шага. Для этого приложения нам нужен многоразовый барьер, который блокируется после прохождения всех потоков.
Данное решение является:
1 # rendezvous
2
3 mutex.wait()
4 count = 1
5 if count == n:
6 turnstile2.wait() # lock the second
7 turnstile.signal() # unlock the first
8 mutex.signal()
9
10 turnstile.wait() # first turnstile
11 turnstile.signal()
12
13 # critical point
14
15 mutex.wait()
16 count -= 1
17 if count == 0:
18 turnstile.wait() # lock the first
19 turnstile2.signal() # unlock the second
20 mutex.signal()
21
22 turnstile2.wait() # second turnstile
23 turnstile2.signal()
Предположим, мы используем этот барьер для 2 потоков и прокачиваем 100 потоков через этот барьер. когда второй поток разблокировал турникет (7) и достиг строки 9, теперь появляется поток 3 и,
это увеличивает количество,
count > n таким образом, он освобождает мьютекс,
поскольку турникет разблокирован, он также достигает критической точки,
аналогично, поток 4, поток 5, поток 6 могут выполнить критическую точку, выполнив ее более 2 раз.
что мешает им пройти через барьер перед потоком 2? Или я здесь неправильно понимаю?
Ответ №1:
В заявлении о проблеме указано (страница 22):
Можно предположить, что существует n потоков и что это значение хранится в переменной n, которая доступна из всех потоков.
Итак, если n = 2 и существует 100 потоков, вы нарушили это предположение, и решение не будет работать.
Комментарии:
1. В этом случае мы устанавливаем барьер для ожидания двух потоков, то есть он должен пропускать два потока при поступлении второго и блокировать третий до поступления четвертого. итак, если мы пропустим через него 100 потоков, это должно позволить потокам проходить через него парами. Однако в приведенном выше примере я думаю, что он сломается и пропустит все потоки, если 2-й поток перейдет в режим ожидания в строке номер 9.
2. Кроме того, после обсуждения списка рассылки, заинтересованного в параллелизме, кажется, что в примерах книги ожидается, что барьер используется в цикле одним и тем же набором из N потоков. Это не барьер общего назначения, который может использоваться несколькими наборами из N потоков…
3. Правильно. Похоже, что вы имеете в виду барьер, который допускает потоки в критическую секцию только партиями по три и требует, чтобы три завершили работу, прежде чем допустить следующие три. В таком случае, я думаю, вам понравится глава 5. Существует несколько подобных проблем.
Ответ №2:
Возможно, это выходит за рамки вопроса, но вот что: указанное решение, насколько я могу судить, правильное, пока не более n потоков находятся внутри кода барьера. Один из способов гарантировать это — иметь всего n потоков.
В книге также представлен другой способ гарантировать, что только n потоков находятся внутри заданной области: мультиплексирование (с использованием семафора, гарантирующего, что не более n потоков используют данный ресурс одновременно). Используйте это так:
general_barrier.init(n):
occupancy = Semaphore(n)
barrier = Barrier(n)
general_barrier.enter():
occupancy.wait()
barrier.enter()
barrier.leave()
general_barrier.leave():
occupancy.signal()
Вы бы использовали это так:
shared state:
gbarrier = general_barrier(n)
each of m threads (where m > n, but in particular try m > 2*n):
while True:
gbarrier.enter()
something critical
gbarrier.leave()
В коде, приведенном в вопросе, вы могли бы поместить occupancy.wait()
в строку 2 и occupancy.signal()
в строку 24 и получить в основном это решение. Обратите внимание, что код в вопросе помещает эквивалент barrier.leave()
после критической точки, т. е. в general_barrier.leave()
, а не до, как я это сделал. Я не думаю, что это имеет значение для корректности, хотя это может иметь значение в отношении количества выполняемых переключений контекста. Возможно, в некоторых ситуациях. Читателю рекомендуется соблюдать осторожность 😉