Task Scheduling Problem

[lpw25]

It seems that a valid OpenMP implementation could deadlock on the following code:

Code: Select all

#pragma omp parallel
{
    // Task 1
    #pragma omp task
    {
        // Task 2
        #pragma omp task
        {
            doSomething();
        }

        // Taskwait 1
        #pragma omp taskwait
        doSomethingElse();
    }

    // Task 3
    #pragma omp task if(1 == 0)
    {
        // Task 4
        #pragma omp task
        {
            doAnotherThing();
        }

        // Taskwait 2
        #pragma omp taskwait
        doSomethingMore();
    }
}


Each thread decides to execute Task 1 when it is created but then decides to continue with Task 1 when Task 2 is created. When they reach Taskwait 1 each thread then decides to continue executing its implicit task. When each thread creates its Task 3 it must execute it immediately because of task scheduling constraint 1 in the API. Then the threads must create Task 4 and reach Taskwait 2. Each thread is now stuck: Task 1 and Task 3 are stuck at Taskwait 1 and Taskwait 2 respectively, Task 2 and Task 4 cannot be execute because of task scheduling constraint 2 in the API (Task 2 is not descended from Task 3 and Task 4 is not descended from Task 1).

Each of the scheduling decisions described above appear to be valid according to the API and the source code also appears to be valid. Have I misinterpreted the API or is this conforming behaviour?

[Federico]

I apologize for taking so long to answer, but I felt the need to check all discussions we had on this issue in the 3.0 Language Committee.

It was the clear intent of the Language Committee that a task switch should happen at the task switching point "immediately following the generation" (3.0 Specs, p. 62, row 5) of Task 3, to get rid of Task 2 before proceeding.
Unfortunately, we used the word "immediately" also to describe the behavior on encounter of an "if(0)ed" task. This is inappropriate in many respects (e.g.: which one is more "immediate", the task switching point or the execution?), and brought to an incorrect wording of Task Scheduling Constraint 2.

Thanks for pointing this out, I'm raising the issue with the Language Committee, to clarify and amend the specifications.

Federico Massaioli

[lpw25]

Thank you for your reply.

Just to clarify, are you saying that an implementation should treat Task 3 (and all other "if(0)ed" tasks) as subject to Task Scheduling Constraint 2, and therefore not available for scheduling until after the completion of Task 2 and Task1.

Thanks,

Leo White

[Federico]

Just to clarify, are you saying that an implementation should treat Task 3 (and all other "if(0)ed" tasks) as subject to Task Scheduling Constraint 2, and therefore not available for scheduling until after the completion of Task 2 and Task1.

Yes, this is what I'm saying.
The rationale behind Task Scheduling Constraint 2 is to avoid the possibility of a thread deadlocking with hitself. If an implicit task region can be executed from beginning to end without the executing thread going in deadlock with itself, TSC 2 ensures that this will be true even if the implicit task is split into explicit tasks.
Your example clearly shows that, according to current wording, this property doesn't hold for "if(0)ed" tasks: a deadlock could happen even with a team of only one thread.

Federico