task sheduling and lock

General OpenMP discussion

task sheduling and lock

Postby huizhanyi » Mon Jun 16, 2008 7:14 pm

Hi!
In Section 2.7, the spec 3.0 (p.63), I have seen the asserion that "As another example, if a lock acquire and release happen in different parts of a task
region, no attempt should be made to acquire the same lock in any part of another task that the executing thread may schedule; otherwise, a deadlock is possible."

I think it is impossible to have deadlock. According to the spec about lock function (omp_set_lock), if the lock can not be set, the task will be suspended. So the executing thread can be scheduling to another task, and finally the task having got the lock will be executed. As a result, the deadlock cannot happen.

I am right? Wish a discussion.
huizhanyi
 
Posts: 4
Joined: Wed Jun 11, 2008 8:51 pm

Re: task sheduling and lock

Postby ejd » Mon Jun 16, 2008 10:35 pm

This is another of our "fun" areas. We had a lot of debates about how tasks are executed and task switching and thread switching. While we tried to make it as clean as we could, we had a lot of problem areas.

I will try and see if I can explain this - though I don't claim to be an expert. Say that you have two tasks in the pool to be executed:

Code: Select all
task-1

    ...
  omp_set_lock(&lock);
    ...
  task scheduling point (as defined on p62) 
    ... 
  omp_unset_lock(&lock);
    ...
}

task-2
{
    ....
  omp_set_lock(&lock);
    ....
  omp_unset_lock(&lock);
    ...
}

A thread picks up task-1 to execute, acquires the lock, and then gets to the task scheduling point. At this point, an implementation may cause the thread to task switch - so the thread can switch and start executing task-2. Let's say that it does switch and now begins executing task-2. It comes to the omp_set_lock and tries to acquire the lock. Unfortunately, the lock is already set and owned by task-1. At this point, as you pointed out, in section 3.3.3 omp_set_lock, it states "each of these routines causes suspension of the task executing the routine until the specified lock is available and then sets the lock".

The key here, is that it says "causes suspension of the task executing". If you go back to section 2.7.1 Task Scheduling, task scheduling points are implied at the following locations:
  • the point immediately following the generation of an explicit task
  • after the last instruction of a task region
  • in taskwait regions
  • in implicit and explicit barrier regions
You will notice that suspension of execution while trying to obtain a lock is not one of the points listed. Therefore, you can have a deadlock. Note that the above discussion is for tied tasks. For untied tasks, an implementation may insert other scheduling points anywhere they wish.

There was a lot of discussion about where scheduling points could occur - both for tied and untied tasks. It was finally decided to limit the points where tied tasks could switch, until we had more experience with tasks.
ejd
 
Posts: 1025
Joined: Wed Jan 16, 2008 7:21 am

Re: task sheduling and lock

Postby huizhanyi » Wed Jun 18, 2008 1:22 am

Yes, I got it.
Since the contraint "2. Other 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 of every task in the set." is difficult for me to understand, I have got wrong reason why A.13.10 cannot lead to deadlock, that is to say, I think the omp_set_lock function cause the task scheduling.

Now, I understand the assertion, and thanks a lot!
huizhanyi
 
Posts: 4
Joined: Wed Jun 11, 2008 8:51 pm


Return to Using OpenMP

Who is online

Users browsing this forum: Google [Bot], Yahoo [Bot] and 11 guests