title: OpenMP uderstanding deadlock in critical construct
body: <p>I am trying to understand exactly why a deadlock occurs when in a parallel region a critical construct is nested in a critical construct.</p>
  
  <p>I have consulted the following resources: <a href="http://www.mathe.tu-freiberg.de/files/personal/253/high-performance-computing-ws2014-slides-2-openmp-gdb-gprof.pdf" rel="nofollow">this</a> source the author writes: </p>
  
  <blockquote>
    <p>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. </p>
  </blockquote>
  
  <p>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: </p>
  
  <blockquote>
    <p>When a thread encounters a CRITICAL directive inside a critical region, it will block forever.</p>
  </blockquote>
  
  <p>Same question, why? </p>
  
  <p>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.</p>
  
  <p>From my current understanding there are two different possible ways why a deadlock occurs in a nested critical region: </p>
  
  <p>Begin first take:  </p>
  
  <p>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. </p>
  
  <blockquote>
    <p>When a thread encounters a critical construct, it waits until no other thread is
    executing a critical region with the same name.</p>
  </blockquote>
  
  <p>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.</p>
  
  <p>End first take.</p>
  
  <p>Begin second take:</p>
  
  <p>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.</p>
  
  <p>End second take.</p>
  
  <p>Here is a small Fortran code that produces the deadlock:</p>
  
  <pre><code>  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
  </code></pre>
  
  <p>So my question is, is one of the two suggestions right, or is there another possibility
  why a deadlock occurs in this situation.</p>