[cgl_discussion] Question for TEMs/ISVs/OEMs regarding pthrea d requirements

george anzinger george at mvista.com
Thu Feb 6 15:12:14 PST 2003

Corey Minyard wrote:
> Perez-Gonzalez, Inaky wrote:
>>> This is why you have to have compare-and-swap to do it in user land.  
>>> As George pointed out, it's possible to implement compare-and swap 
>>> with a very quick kernel call on a processor that doesn't have it 
>>> otherwise.
>>> Please, go to http://ssthreads.sf.net, pull the design document, and 
>>> read the mutex portion.  It talks about this in great detail.  I have 
>>> thought of a simpler algorithm (instead of a stack), but I'm not 100% 
>>> sure it's better, and it's not significantly simpler.  If the kernel 
>>> is involved, though, it simplifies things a lot.
>> I started to read it a few days ago, but I haven't finished yet [let's 
>> call
>> it management-preemption ...] -- Keep in mind I still did not finish 
>> it, but
>> the problem I see with your algorithm is it does not work with shared
>> mutexes across different processes, unless all that is somehow moved 
>> on to
>> the kernel

The "normal" way to make mutexes work across processes is to have a 
chunk of shared memory where in the mutex structure resides.
> Yes, my algorithm is a bit weird, but it has to properly handle doing 
> pthread operations inside signal handlers (that was one of the 
> requirements).  The algorithm George proposed will work.  The paper 
> brings out the issues, though.
>>> The other side of this is that if someone owns the mutex, you have to 
>>> make sure they don't release the mutex until you are done boosting 
>>> their priority.
>> When somebody's priority is raised, it means there are waiters and 
>> then the
>> futex value has been set to [in NPTL's case] 2, so release will always go
>> through the kernel - who would take care of that.
>> So, for example, the case where A[prio 6] locks, sets the futex to 1, 
>> B[10]
>> tries to lock, sets the futex to 2, boosts A to 10 and gets queued - 
>> then,
>> while waiting, B gets killed, but the futex is still 2, so when 
>> releasing,
>> it goes thru the kernel and the priority is restored.
>> Although to be correct, this case, for example, should do that when B is
>> killed and removed from the wait list, it should restore A's priority 
>> and in
>> any case, boost it to the new head of the list if any ...
> Just being sure,  you need to put your self on the wait list last, but 
> you need to mark the contention in the mutex first, before you attempt 
> any priority inheritance.
>>> also infinite loops you have to worry about, if a process deadlocks 
>>> on a mutex, you will have a circular list of threads waiting on that 
>>> mutex (and all inbetween).
>> Yeah, this criss-crosses with robust mutex support when killing the 
>> owner --
>> although deadlock detection would be nice - it should not be too 
>> difficult
>> to implement once it is possible to identify who owns which futex, as the
>> kernel can look up the different futexes looking for owners; however, 
>> that's
>> going to be expensive ...
> Priority inheritance and deadlock detection are actually almost the same 
> algorithm (you just keep going down the whole list and look for loops 
> for deadlock detection).  

Right, when you try go thru the boosting, you will end up trying to 
boost "self", a dead lock!

> The tricky part is doing it without relying on 
> a global spinlock.  I think the algorithm in my paper is correct, but 
> others should probably look at it.  This means you also have to do 
> deadlock detection on non-pi mutexes.

A problem I came on in the kernel version of the pi-mutex was how to 
actually change a tasks priority.  If we can assume that there is only 
one priority queue in the kernel, it is easy, BUT, we now have a 
second queue, i.e. the pi-mutex priority queue.  This means the 
priority change code needs to know what queue the task is in.  This is 
  especially true as the scheduler priority queue is an O(1) queue and 
I don't think we want O(1) queues for mutexes.  This may or may not be 
an issue with user land mutexes.  Depends on how the priority queuing 
is done.  I.e. exactly where is the task suspended.  There may be 
other ways to handle this...

>> God I hate priority inheritance; I will finish agreeing with Victor
>> Yodaiken.
> I hate implementing it, but it's better than the alternative :-).
> -Corey

George Anzinger   george at mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

More information about the cgl_discussion mailing list