OpenMP выявляет тупик в критической конструкции

Я пытаюсь точно понять, почему возникает тупик, когда в параллельной области критическая конструкция вложена в критическую конструкцию.

Я воспользовался следующими ресурсами: этот источник пишет автор:

В OpenMP это может произойти, если внутри критической области вызывается функция, которая содержит другую критическую область. В этом случае критическая область вызываемой функции будет ждать завершения первой критической области - чего никогда не произойдет.

Хорошо, а почему бы и нет? Также от: Hager, Georg и Gerhard Wellein. Введение в высокопроизводительные вычисления для ученых и инженеров. CRC Press, 2010, стр. 149:

Когда поток встречает директиву CRITICAL внутри критической области, он блокируется навсегда.

Тот же вопрос, почему?

Наконец, Чапман, Барбара, Габриэле Йост и Рууд Ван Дер Пас. Использование OpenMP: параллельное программирование переносимой общей памяти. Vol. 10. MIT press, 2008 также приводит пример использования замков, но не с критической конструкцией.

Насколько я понимаю, существует два возможных пути возникновения тупика во вложенной критической области:

Начните с первого дубля:

Если два потока достигают вложенной критической конструкции (одна критическая область внутри другой), первый поток входит во «внешнюю» критическую область, а второй поток ожидает. Цитируя Chapman et al.

Когда поток встречает критическую конструкцию, он ждет, пока ни один другой поток не выполнит критическую область с тем же именем.

Хорошо, пока все хорошо. Теперь первый поток НЕ входит во вложенную критическую область, потому что это точка синхронизации, в которой потоки ожидают прибытия всех остальных потоков, прежде чем продолжить. А поскольку второй поток ожидает выхода первого потока из «внешней» критической области, они находятся в тупике.

Конец первого дубля.

Начните второй дубль:

Оба потока достигают «внешней» критической конструкции. Первый поток входит во «внешнюю» критическую конструкцию, второй поток ожидает. Теперь первый поток ВХОДИТ во «внутреннюю» критическую конструкцию и останавливается на подразумеваемом барьере, потому что он ждет второго потока. Второй поток, с другой стороны, ожидает выхода первого потока во «внешний» поток, поэтому оба ждут вечно.

Конец второго дубля.

Вот небольшой код на Фортране, который вызывает тупик:

  1   subroutine foo
  2 
  3     !$OMP PARALLEL 
  4     !$OMP CRITICAL 
  5       print*, 'Hallo i am just a single thread and I like it that way'
  6     !$OMP END CRITICAL
  7     !$OMP END PARALLEL 
  8 
  9   end subroutine foo
 10 
 11 program deadlock
 12   implicit none
 13   integer :: i,sum = 0
 14 
 15   !$OMP PARALLEL
 16   !$OMP DO 
 17   do i = 1, 100
 18   !$OMP CRITICAL
 19      sum = sum + i
 20      call foo()
 21   !$OMP END CRITICAL
 22   enddo
 23   !$OMP END DO
 24   !$OMP END PARALLEL
 25 
 26   print*, sum
 27 end program deadlock

Итак, мой вопрос: правильно ли одно из двух предложений или есть другая возможность, почему в этой ситуации возникает тупик.


multithreading openmp fortran critical-section
person Vincent    schedule 26.11.2014    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Не существует подразумеваемого барьера, то есть «точки синхронизации, в которой потоки ждут прибытия других потоков», связанной с КРИТИЧЕСКИМИ конструкциями. Вместо этого в начале критической конструкции потоки ждут, пока любой поток уже внутри критической конструкции с тем же именем покинет конструкцию.

Критические конструкции с тем же именем не могут быть вложенными, потому что текущие правила OpemMP говорят, что они не могут быть вложенными (см. Ограничения на вложение в OpemMP 4.0 раздел 2.16). Это действительно ответ на ваш вопрос и конец обсуждения - если вы нарушите этот запрет, может случиться все, что угодно.

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

Критические конструкции с разными именами могут быть вложенными. В случае несогласованности вложенности возможна взаимоблокировка. Учитывать:

!$OMP PARALLEL

!$OMP CRITICAL (A)
!$OMP CRITICAL (B)      ! Thread one waiting here.
!...
!$OMP OMP CRITICAL (B)
!$OMP END CRITICAL (A)

!$OMP CRITICAL (B)
!$OMP CRITICAL (A)      ! Thread two waiting here.
!...
!$OMP OMP CRITICAL (A)
!$OMP END CRITICAL (B)

!$END PARALLEL

Если это произойдет, потоки будут ждать довольно долго.

person IanH    schedule 27.11.2014
comment
Небольшой дополнительный вопрос к вашему объяснению: поэтому, когда поток один входит во внешнюю критическую область, поток два ждет снаружи. Теперь поток 1 ожидает, когда какой-либо поток покинет внутреннюю критическую область, чего не происходит, потому что только один поток за раз может войти во внешнюю критическую область. Так что он ждет, чтобы уйти. Это правильно истолковано? - person Vincent; 27.11.2014
comment
Я изменил одно слово, имеющее отношение к вашему продолжению - «любой» на «все» для правильности. Правдоподобная реализация состоит в том, что при обнаружении внутренней критической конструкции первый поток (атомарно) запрашивает, есть ли внутри критического раздела поток. Ответ положительный, поэтому поток ждет. (Если ответ был отрицательным, поток (атомарно с запросом) пометил бы, что критический раздел был занят, и перешел в раздел.) В конце поток ожидает самого себя. Второй поток не имеет значения - он может ждать на внешней границе конструкции или лететь на Луну. - person IanH; 27.11.2014
comment
Спасибо за ваш комментарий. - person Vincent; 27.11.2014