[OpenMP] Task priority implementation can lead to life-lock

[jprotze]

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
int fib(int n) {
  int i, j;
  if (n<2) {
    return n;
  } else {
    #pragma omp task shared(i) priority(n/2)
    {
      printf("%i: fib(%i)\n", omp_get_thread_num(), n-1);
      i=fib(n-1);
    }
    #pragma omp task shared(j) priority(n/2)
    {
      printf("%i: fib(%i)\n", omp_get_thread_num(), n-2);
      j=fib(n-2);
    }
    #pragma omp taskwait
    return i+j;
  }
}
int main(int argc, char** argv) {
  int n = 5;
  if (argc>1) 
    n = atoi(argv[1]);
  printf("Max prio = %i\n", omp_get_max_task_priority());
  #pragma omp parallel sections
  {
    printf("fib(%i) = %i\n", n, fib(n));
  }
  return 0;
}

The code executes successfully, if OMP_MAX_TASK_PRIORITY=0 or KMP_TASK_STEALING_CONSTRAINT=0. The following command stalls after executing the first few tasks:

$ env OMP_NUM_THREADS=2 OMP_MAX_TASK_PRIORITY=2 KMP_TASK_STEALING_CONSTRAINT=1 ./a.out
Max prio = 2
0: fib(4)
0: fib(3)
1: fib(3)

At this point, only tasks with lower priority would be available for scheduling, but they are not considered because higher priority tasks are enqueued which cannot be scheduled due to the TSC.

[jprotze]

@jpeyton52, I think you are most familiar with this part of the runtime. Do you have an idea how to fix this?