[Mongrel] The real reason why Sync and Mutex behave differently

Kirk Haines wyhaines at gmail.com
Mon Sep 4 13:50:21 EDT 2006


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


More information about the Mongrel-users mailing list