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
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.
Thread.critical = true
@locked = false
t = @waiting.shift
t.wakeup if t
Thread.critical = false
t.run if t
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
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 (1.8.4 and 1.8.5) and Win XP (one-click ruby 1.8.4 and cygwin ruby 1.8.5)
array.c's behavior is what needs to be examined in greater detail, here.
Mutex, itself, is not doing anything surprising.