# The real difference between Mutex and Sync

**URL:** <https://www.ruby-forum.com/t/the-real-difference-between-mutex-and-sync/67512>\
**Category:** Ruby\
**Created:** [September 4, 2006, 8:18pm UTC](https://www.ruby-forum.com/t/the-real-difference-between-mutex-and-sync/67512 "2006-09-04T20:18:09Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [September 4, 2006, 8:18pm UTC](https://www.ruby-forum.com/t/the-real-difference-between-mutex-and-sync/67512/1 "2006-09-04T20:18:09Z")

</div>

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

Kirk H.

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [September 4, 2006, 8:56pm UTC](https://www.ruby-forum.com/t/the-real-difference-between-mutex-and-sync/67512/2 "2006-09-04T20:56:14Z")

</div>

On 9/4/06, removed\_email\_address@domain.invalid [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> array.c’s behavior is what needs to be examined in greater detail, here.  
> Mutex, itself, is not doing anything surprising.
> 
> Kirk H.

Good findings.

I think the problem lies in the Array#shift (rb\_ary\_shift)  
implementation. Basically, it just increments the internal pointer and  
it never modifies the size of an array. This means that if you have an  
array with 1000 elements and you ‘shift’ it 999 times, all these  
elements are still visible to the garbage collector, until you modify  
this array by triggering rb\_ary\_store method, for example.

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [September 4, 2006, 9:02pm UTC](https://www.ruby-forum.com/t/the-real-difference-between-mutex-and-sync/67512/3 "2006-09-04T21:02:15Z")

</div>

On 9/4/06, Kent S. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> I think the problem lies in the Array#shift (rb\_ary\_shift)  
> implementation. Basically, it just increments the internal pointer and  
> it never modifies the size of an array. This means that if you have an  
> array with 1000 elements and you ‘shift’ it 999 times, all these  
> elements are still visible to the garbage collector, until you modify  
> this array by triggering rb\_ary\_store method, for example.

I meant that rb\_ary\_shift never modifies the size of allocated memory.

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [September 4, 2006, 9:40pm UTC](https://www.ruby-forum.com/t/the-real-difference-between-mutex-and-sync/67512/4 "2006-09-04T21:40:17Z")

</div>

This patch will make Mutex a bit slower, but much better in terms of  
garbage collection:

# Index: lib/thread.rb

## RCS file: /src/ruby/lib/thread.rb,v retrieving revision 1.16.2.2 diff -r1.16.2.2 thread.rb 99c99 \< @waiting.push Thread.current

> ```
> @waiting.unshift Thread.current
> 
> ```

## 115c115 \< t = @waiting.shift

> ```
> t = @waiting.pop
> ```

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [September 4, 2006, 9:40pm UTC](https://www.ruby-forum.com/t/the-real-difference-between-mutex-and-sync/67512/5 "2006-09-04T21:40:17Z")

</div>

On Sep 4, 2006, at 2:50 PM, Kent S. wrote:

> Good findings.
> 
> I think the problem lies in the Array#shift (rb\_ary\_shift)  
> implementation. Basically, it just increments the internal pointer and  
> it never modifies the size of an array. This means that if you have an  
> array with 1000 elements and you ‘shift’ it 999 times, all these  
> elements are still visible to the garbage collector, until you modify  
> this array by triggering rb\_ary\_store method, for example.

Would this help?

class Array  
alias rb\_ary\_shift shift  
def shift  
@len ||= length  
@shift\_count ||= 0  
res = rb\_ary\_shift  
@shift\_count += 1  
if @shift\_count \>= @len / 2  
@shift\_count = nil  
@len = nil  
replace(dup)  
end  
res  
end  
end

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [September 5, 2006, 10:25am UTC](https://www.ruby-forum.com/t/the-real-difference-between-mutex-and-sync/67512/6 "2006-09-05T10:25:39Z")

</div>

On Tue, 5 Sep 2006, Kent S. wrote:

> * * *
> 
> > ```
> > @waiting.unshift Thread.current
> > 
> > ```
> 
> ## 115c115 \< t = @waiting.shift
> 
> > ```
> > t = @waiting.pop
> > 
> > ```

While I am not benchmarking with performance in mind, that change  
doesn’t  
seem to have any significant effect on overall speed, which doesn’t  
surprise me. Speed-wise, it is just flipping the location of the  
expensive array operation from the unlock to the lock.

And yes, that simple change does seem to make a significant difference,  
because pop will realloc the array.

Kirk H.

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [September 5, 2006, 2:46pm UTC](https://www.ruby-forum.com/t/the-real-difference-between-mutex-and-sync/67512/7 "2006-09-05T14:46:30Z")

</div>

On Sep 5, 2006, at 4:25 AM, removed\_email\_address@domain.invalid wrote:

> > 99c99  
> > doesn’t surprise me. Speed-wise, it is just flipping the location  
> > of the expensive array operation from the unlock to the lock.
> 
> And yes, that simple change does seem to make a significant  
> difference, because pop will realloc the array.

I’ve attached a trivial script that demonstrates on OS X and likely  
linux (unlikely windows because of the ps stuff) the problem. To see  
the bug, run it like:

```
ruby blowup2.rb

```

A _simple_ fix is to just remove the reference to whatever is pointed  
to by the first element. To see this work, run the script as:

```
ruby blowup2.rb fix

```

This trick will probably lead to a quicker fix (and if you are daring  
you might actually patch the C implementation of shift to do it for  
you). Might want to hear what Matz has to say about that.

Cheers,  
Bob

* * *

Bob H. – blogs at \<[http://www.recursive.ca/](http://www.recursive.ca/)  
hutch/\>  
Recursive Design Inc. – [http://www.recursive.ca/](http://www.recursive.ca/)  
Raconteur – [http://www.raconteur.info/](http://www.raconteur.info/)  
xampl for Ruby – [http://rubyforge.org/projects/xampl/](http://rubyforge.org/projects/xampl/)

$VERBOSE = nil  
STDOUT.sync = true  
trap(‘INT’){ exit }

fixit = 0 \< ARGV.size

m = 1000000  
n = 1000

all\_arrays = []  
first = true

n.times do |i|  
if 0 \< m then  
a = [“x” \* m]  
all\_arrays \<\< a  
a[0] = nil if fixit and 0 \< a.size  
a.shift  
else  
a = []  
all\_arrays \<\< a  
end

if 0 == (all\_arrays.size % 10) then  
GC.start  
stdout = `ps v -p #{ Process.pid }`  
stdout = stdout.split(%r/\n/)  
if first then  
printf(“\n %s\n”, stdout.first)  
first = false  
end  
printf(“%6d:: %s\n”, all\_arrays.size, stdout.last)  
end  
end

---

<div class="post-metadata">

**Author:** ![unknown](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/u/4bbf92/32.png) [@unknown](https://www.ruby-forum.com/u/unknown)\
**Post date:** [September 5, 2006, 4:14pm UTC](https://www.ruby-forum.com/t/the-real-difference-between-mutex-and-sync/67512/8 "2006-09-05T16:14:49Z")

</div>

On 9/5/06, Bob H. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> I’ve attached a trivial script that demonstrates on OS X and likely  
> linux (unlikely windows because of the ps stuff) the problem. To see

This is ‘windows’ version, using pslist[1]  
And, yes, it does the same under windows as well.

Jano

[1] [http://www.sysinternals.com/Utilities/PsList.html](http://www.sysinternals.com/Utilities/PsList.html)

$VERBOSE = nil  
STDOUT.sync = true  
trap(‘INT’){ exit }

fixit = 0 \< ARGV.size

m = 1000000  
n = 1000

all\_arrays = []  
first = true

n.times do |i|  
if 0 \< m then  
a = [“x” \* m]  
all\_arrays \<\< a  
a[0] = nil if fixit and 0 \< a.size  
a.shift  
else  
a = []  
all\_arrays \<\< a  
end

if 0 == (all\_arrays.size % 10) then  
GC.start  
stdout = `pslist -m #{ Process.pid }`  
stdout = stdout.split(%r/\n/)  
if first then  
printf(“\n %s\n”, stdout[7])  
first = false  
end  
printf(“%6d:: %s\n”, all\_arrays.size, stdout.last)  
end  
end