From: Brent Roman <brent@...>
Date: 2006-11-12T17:38:42+09:00
Subject: Re: fast mutexes for 1.8?


>On Sun, 2006-11-12 at 07:05 +0900, MenTaLguY wrote:
>> On Wed, 2006-11-08 at 16:47 +0900, Brent Roman wrote:
>> > #BUT...the Mutex is unlocked at this point!!!
>> > #so Ruby's thread scheduler can (and sometimes does)
>> > #allow another thread to lock this mutex
>> > #before thread t runs
>>=20
>> In other words, a non-waiting thread could potentially "jump the queue"
>> and acquire the lock before a waiting thread.
>>=20
>> I've addressed this in my own Mutex implementation and am looking into
>> what might need to be done for condition variables along similar lines.
>
>Addendum: doing some research, it looks like both the Java language
>specification and the pthreads manpages permit threads not in the wait
>set to acquire the lock.
>
>I'm going to revert the changes in my Mutex class, since it's probably
>better if I don't offer guarantees that can't otherwise be met in any of
>stock Ruby 1.8, YARV, or JRuby.
>
>  
>
I was surprised to hear this, so I, too, did some digging.
It's refreshing that this issue
is finally being discussed here on ruby-core!

The way of determining which thread first acquires
a Mutex lock when there are multiple waiters is itself quite
"contentious", as demonstrated by this thread on
comp.programming.threads:

http://groups.google.com/group/comp.programming.threads/browse_thread/thread/d3703aae792a7d18/16c01eac398a1139?&hl=en#16c01eac398a1139

The fast approach is to release the lock, wake all the waiting threads
and let
the thread scheduler (more or less randomly) choose which runs first. 
The fair approach is to pass the lock from the thread releasing it,
directly to the thread that had been waiting the longest for the it. 
It appears that both approaches have been tried at various times
in the history Linux threading library (in glibc). 

I'll take your word that the pthread and Java specs remain silent on
this issue.
My point is that specifying this behavior is critical sometimes.
Even acknowledged threading gurus cannot agree on which approach is
generally superior.  Therefore, I believe Ruby should continue to
allow programmers to define thread sychronization primitives in Ruby,
at some expense of implementation efficiency over native ones.

Unlike Mutexes, the exact semantics of Test-and-Set operations
are simple and unambiguous.  Test-and-Set is
easy to implement and provides the same detailed
level of control over thread sychronization
that Thread.critical otherwise would.

Note that this does not preclude also having a built-in, optimized,
Mutex class
that calls native pthread or Java libraries.  The exact behavior of this
built-in
Ruby Mutex class will, however, be platform dependent.  Some
applications will break on various platforms as a result.

>*MenTaLguY wrote:*
>
>It's worth pointing out that a locking primitive implemented atop a
>"native" mutex and condition variable(s) would likely be faster than one
>implemented atop an atomic test-and-set operation in Ruby, because in
>the latter case you'd need to incur a lot of method calls to do all your
>wait queue management in Ruby (one of the reasons the current Mutex is
>so slow).
>
>  
>
Implementing a "fair" mutex atop a native mutex would require
that the native library and Ruby both manage queues of waiting threads.
So, I cannot see how it will be faster than a "fair" mutex atop O(1)
test-and-set operations, although, the overhead for the
native library's thread queue management will admittedly be quite
small compared to Ruby's.

Am I missing an important point here?

-- 
 Brent Roman
 mailto:brent@mbari.org  http://www.mbari.org/~brent