OpenMP uderstanding deadlock in critical construct

critical-section, fortran, multithreading, openmp

Solution

There is no implied barrier, i.e. no "synchronization point where threads wait for other threads to arrive" associated with CRITICAL constructs. Instead, at the start of a critical construct, threads wait for any thread already inside a critical construct of the same name to leave the construct.

Critical constructs with the same name cannot be nested, because the current OpemMP rules say they can not (see the restrictions on nesting in OpemMP 4.0 section 2.16). That's really the answer to your question and the end of the discussion - if you break that prohibition then anything can happen.

Practically, this prohibition allows implementations to assume that critical constructs with the same name will not be nested. One common implementation choice is then that a thread encountering a critical construct will wait for all threads including itself to leave the construct. If it is waiting a thread cannot be leaving. That results in a deadlock.

Critical constructs with different names can be nested. Deadlock is possible in that case if the nesting is not consistent. Consider:

!$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

If this situation occurs the threads will be waiting quite a while.

Problem

I am trying to understand exactly why a deadlock occurs when in a parallel region a critical construct is nested in a critical construct. I have consulted the following resources: this source the author writes: In OpenMP this can happen if inside a critical region a function is called which contains another critical region. In this case the critical region of the called function will wait for the first critical region to terminate - which will never happen. Alright, but why not? Furthermore from: Hager, Georg, and Gerhard Wellein. Introduction to high performance computing for scientists and engineers. CRC Press, 2010, p. 149: When a thread encounters a CRITICAL directive inside a critical region, it will block forever. Same question, why? Finally, Chapman, Barbara, Gabriele Jost, and Ruud Van Der Pas. Using OpenMP: portable shared memory parallel programming. Vol. 10. MIT press, 2008 also provide an example using locks, however not with the critical construct. From my current understanding there are two different possible ways why a deadlock occurs in a nested critical region: Begin first take: If two threads arrive at a nested critical construct (one critical region inside another), thread one enters the "outer" critical region and thread two waits. Quoting Chapman et al. When a thread encounters a critical construct, it waits until no other thread is executing a critical region with the same name. Alright, so far so good. Now, thread one DOES NOT enter the nested critical region, because it is a synchronization point where threads wait for all other threads to arrive before proceeding. And since the second thread is waiting for the first thread the exit the "outer" critical region they are in a deadlock. End first take. Begin second take: Both threads arrive at the "outer" critical construct. Thread one enters the "outer" critical construct, thread two waits. Now, thread one ENTERS the "inner" critical construct and stops at it's implied barrier, because it waits for thread two. Thread two on the other hand waits for thread one to exit to "outer" thread and so both are waiting forever. End second take. Here is a small Fortran code that produces the deadlock: ``` 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 ``` So my question is, is one of the two suggestions right, or is there another possibility why a deadlock occurs in this situation.

Original source