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

Perez-Gonzalez, Inaky inaky.perez-gonzalez at intel.com
Thu Feb 6 11:58:39 PST 2003

> 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

> 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 ...

> 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 ...

God I hate priority inheritance; I will finish agreeing with Victor

I'll try to finish reading your paper today and come back with more --
thanks so much for the pointers :]

Inaky Perez-Gonzalez -- Not speaking for Intel - opinions are my own [or my

More information about the cgl_discussion mailing list