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

[Corey Minyard]

Perez-Gonzalez, Inaky wrote:

>>This is why you have to have compare-and-swap to do it in 
>>userland.  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 simplier.  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
>
Yes, my algorithm is a bit wierd, 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).  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.

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

-Corey