4.4 Task Scheduling Constraints

The OpenMP specification lists several task scheduling constraints which an OpenMP task scheduler must follow.

1. An included task is executed immediately after it is generated.

2. Scheduling of new tied tasks is constrained by the set of task regions that are currently tied to the thread and that are not suspended in a barrier region. If this set is empty, any new tied task may be scheduled. Otherwise, a new tied task may be scheduled only if it is a descendant task of every task in the set.

3. A dependent task shall not be scheduled until its task dependences are fulfilled.

4. When an explicit task is generated by a construct containing an if clause for which the expression evaluates to false and the previous constraints are already met, the task is executed immediately after it is generated.

A program relying on any other assumptions about task scheduling is non-conforming.

Constraints 1 and 4 are two cases where an OpenMP task should be executed immediately.

Constraint 2 is for preventing deadlock. In Example 4. Tasks A, B, and C are tied tasks. The thread that is executing Task A is about to enter the critical taskyield region and the thread has ownership of the lock associated with the critical region. Because taskyield is a task scheduling point, the thread executing Task A may choose to suspend Task A and execute another task instead. Suppose Tasks B and C are in the task pool. According to constraint 2, the thread executing Task A cannot execute Task B because Task B is not a descendant of Task A. Only Task C can be scheduled at this point, because Task C is a descendant of Task A.

If Task B were to be scheduled while Task A is suspended, then the thread to which Task A is tied cannot enter the critical region in Task B because the thread already holds the lock associated with that critical region. Therefore, a deadlock occurs. The purpose of constraint 2 is to avoid this kind of deadlock when the code is conforming.

Note that deadlock can also occur if the programmer nests a critical section inside Task C, but that would be a programming error.

Example 4  Illustrating Task Scheduling Constraint 2

#pragma omp task // Task A
{
    #pragma omp critical
    {
        #pragma omp task // Task C
        {
        }
        #pragma omp taskyield
     }
}

#pragma omp task // Task B
{
    #pragma omp critical
     {
     }
}