Mongrel users - Sep 2006 - The real reason why Sync and Mutex behave differently

As I''ve mentioned before, Sync and Mutex are very similar, and Mutex
is very simple.

Their locking algorithm (for exclusive locking) is essentially identical.

And in some detailed examinations of Mutex''s behavior, there''s
nothing
superficially wrong with it.  It''s pure ruby, so there are no funny
memory allocations at the C level, and it essentially operates by
using an array as a queue for waiting threads.  Very little is
involved.

Sync does a bunch of other things, since it supports shared locking in
addition to exclusive, so it is much more complicated.  However, the
main difference between them, when one is using exclusive locking, is
in the way they perform unlocking.

Mutex:

    Thread.critical = true
    @locked = false
    begin
      t = @waiting.shift
      t.wakeup if t
    rescue ThreadError
      retry
    end
    Thread.critical = false
    begin
      t.run if t
    rescue ThreadError
    end
    self

With Mutex, the next thread to unlock is shifted off the beginning of the array.

With Sync, there is one key difference:

    wait = sync_waiting
    self.sync_waiting = []
    Thread.critical = false
    for w in wait
      w.run
    end

With Sync, a copy is made of the array or waiting threads, the waiting
thread queue is set to a fresh, empty array, and all of the threads
pointed to in the copy are woken up.  One will get the lock, and the
rest insert themselves back into the waiting queue.

That copy of the sync_waiting array, "wait", which is now the only
thing pointing at the original array, then gets thrown away, letting
it get garbage collected.

That''s the key to the difference, right there.

With Mutex, the shift operation reduces the size of the array, but
shift never reallocs.
With Sync, that array gets thrown away, and when gc runs, it is
cleaned up.  This whole thing with Mutex hinges on the memory
management behavior in array.c.  This is why throwing away the mutex
and creating a new one between iterations in that test script produces
a result similar to what Sync produces, too, as the net effect is that
the array that the mutex uses to track threads gets thrown away.

I made a copy of Mutex and changed it to use a linked list instead of
an array to queue waiting threads, thereby eliminating array.c from
the mix while keeping the rest of Mutex.rb intact, and I now get
completely perfect, deterministic behavior on both Linux and Win XP.

array.c''s behavior is what needs to be examined in greater detail,
here.


Kirk Haines

Kirk,

After reading your analysis, I''m interested in the custom, compiled
solution you''re talking about.

Anyway, the use of thread.critical isn''t a viable locking method, as
said by ruby-core by matz a few years back (1.6 version I think).

The really funny part is that, based on your interpretation of the
problem, why the GC of both platforms behave differently?

I know that ruby GC isn''t the fastest, nor the optimal (nor even as
good as other, simplistic GC around the net). The whole mark and sweep
method is too "intensive".

But, why the differences between platforms? even as you said what do
Mutex and what do Sync... ruby-mswin32 (stable from official build,
vc6) do garbage collect of Mutex when linux doesn''t?

On 9/4/06, Kirk Haines <wyhaines at gmail.com>
wrote:
> As I''ve mentioned before, Sync and Mutex are very similar, and
Mutex
> is very simple.
>
> Their locking algorithm (for exclusive locking) is essentially identical.
>
> And in some detailed examinations of Mutex''s behavior,
there''s nothing
> superficially wrong with it.  It''s pure ruby, so there are no
funny
> memory allocations at the C level, and it essentially operates by
> using an array as a queue for waiting threads.  Very little is
> involved.
>
> Sync does a bunch of other things, since it supports shared locking in
> addition to exclusive, so it is much more complicated.  However, the
> main difference between them, when one is using exclusive locking, is
> in the way they perform unlocking.
>
> Mutex:
>
>     Thread.critical = true
>     @locked = false
>     begin
>       t = @waiting.shift
>       t.wakeup if t
>     rescue ThreadError
>       retry
>     end
>     Thread.critical = false
>     begin
>       t.run if t
>     rescue ThreadError
>     end
>     self
>
> With Mutex, the next thread to unlock is shifted off the beginning of the
array.
>
> With Sync, there is one key difference:
>
>     wait = sync_waiting
>     self.sync_waiting = []
>     Thread.critical = false
>     for w in wait
>       w.run
>     end
>
> With Sync, a copy is made of the array or waiting threads, the waiting
> thread queue is set to a fresh, empty array, and all of the threads
> pointed to in the copy are woken up.  One will get the lock, and the
> rest insert themselves back into the waiting queue.
>
> That copy of the sync_waiting array, "wait", which is now the
only
> thing pointing at the original array, then gets thrown away, letting
> it get garbage collected.
>
> That''s the key to the difference, right there.
>
> With Mutex, the shift operation reduces the size of the array, but
> shift never reallocs.
> With Sync, that array gets thrown away, and when gc runs, it is
> cleaned up.  This whole thing with Mutex hinges on the memory
> management behavior in array.c.  This is why throwing away the mutex
> and creating a new one between iterations in that test script produces
> a result similar to what Sync produces, too, as the net effect is that
> the array that the mutex uses to track threads gets thrown away.
>
> I made a copy of Mutex and changed it to use a linked list instead of
> an array to queue waiting threads, thereby eliminating array.c from
> the mix while keeping the rest of Mutex.rb intact, and I now get
> completely perfect, deterministic behavior on both Linux and Win XP.
>
> array.c''s behavior is what needs to be examined in greater detail,
here.
>
>
> Kirk Haines
> _______________________________________________
> Mongrel-users mailing list
> Mongrel-users at rubyforge.org
> http://rubyforge.org/mailman/listinfo/mongrel-users
>

-- 
Luis Lavena
Multimedia systems
-
Leaders are made, they are not born. They are made by hard effort,
which is the price which all of us must pay to achieve any goal that
is worthwhile.
Vince Lombardi

On 9/5/06, Luis Lavena <luislavena at gmail.com> wrote:
> Anyway, the use of thread.critical isn''t a viable locking method,
as
> said by ruby-core by matz a few years back (1.6 version I think).
Thread.critical alone makes it easy to get oneself into trouble, but
both Sync and Mutex are built on top of it.
> The really funny part is that, based on your interpretation of the
> problem, why the GC of both platforms behave differently?
I think the differences observed between Linux and WinXP relate to how
each platform''s memory management interacts with Ruby.

BTW, although switching Mutex to using a linked list for the thread
queue worked great, it appears that one can get Ruby to do reasonable
things with the array by switching the push in lock and the shift in
unlock to be an unshift and a pop, respectively.  This is because pop
will realloc the array.

I haven''t yet tested that as extensively as I did the mutex with
linked list, but so far it appears solid.
> I know that ruby GC isn''t the fastest, nor the optimal (nor even
as
> good as other, simplistic GC around the net). The whole mark and sweep
> method is too "intensive".
>
> But, why the differences between platforms? even as you said what do
> Mutex and what do Sync... ruby-mswin32 (stable from official build,
> vc6) do garbage collect of Mutex when linux doesn''t?
That really just looks like a difference in platform memory management
interaction with Ruby.  The fixes (linked list or changing array
operations) both appear to work identially on Linux and WinXP, though,
without incurring the speed penalty that Sync has.

I''m doing more testing this week, though, on both Linux and WinXP.
I''ll send out updates here and on ruby-talk if I find anything else
that is useful or interesting.


Kirk