I recently answered a question on Stack Overflow where someone asked for advice about making a Hash thread-safe. They indicated that performance was important and that there would be a heavy read bias. I suggested a read-write lock, but couldn't find a Ruby implementation available anywhere. The only thing I found was a blog entry from 2007 where someone said they had built one, but the link was broken.

I thought that a freely available read-write lock implementation for Ruby would be a good thing for the community, so I tried coming up with one. If you can find any bugs, or see any way to increase performance, please comment!

The latest version of this file is here. There is a forked version here, which makes queued readers and writers interleave, rather than preferring to run the queued writers first. I haven't decided whether this is a good idea or not. If I determine that it is better, I will merge the change into 'master'.

# Ruby read-write lock implementation
# Allows any number of concurrent readers, but only one concurrent writer
# (And if the "write" lock is taken, any readers who come along will have to wait)

# If readers are already active when a writer comes along, the writer will wait for
#   wait (so writers are not starved)

# Thanks to Doug Lea for java.util.concurrent.ReentrantReadWriteLock (used for inspiration)

# Usage:
# lock.with_write_lock { data.modify! }

# Implementation note: A goal for this implementation is to make the "main" (uncontended)
# Only if there is reader-writer or writer-writer contention, should locks be used

require 'atomic' # must install 'atomic' gem

def initialize
@counter      = Atomic.new(0)         # single integer which represents lock state
# 0 = free
# +1 each concurrently running reader
# +(1 << 16) for each waiting OR running writer
# so @counter >= (1 << 16) means at least one writer is waiting/running
# and (@counter & ((1 << 16)-1)) > 0 means at least one reader is running
@writer_q     = ConditionVariable.new # queue for waiting writers
@writer_mutex = Mutex.new             # to protect writer queue
end

WRITER_INCREMENT = 1 << 16              # must be a power of 2!

while(true)
c = @counter.value
if c >= WRITER_INCREMENT
end
else
break if @counter.compare_and_swap(c,c+1)
end
end

yield

while(true)
c = @counter.value
if @counter.compare_and_swap(c,c-1)
if c >= WRITER_INCREMENT && (c & MAX_READERS) == 1
@writer_mutex.synchronize { @writer_q.signal }
end
break
end
end
end

def with_write_lock(&b)
while(true)
c = @counter.value
if @counter.compare_and_swap(c,c+WRITER_INCREMENT)
@writer_mutex.synchronize do
@writer_q.wait(@writer_mutex) if @counter.value > 0
end
break
end
end

yield

while(true)
c = @counter.value
if @counter.compare_and_swap(c,c-WRITER_INCREMENT)
if c-WRITER_INCREMENT >= WRITER_INCREMENT
@writer_mutex.synchronize { @writer_q.signal }
else
end
break
end
end
end
end

if __FILE__ == \$0

# for performance comparison with ReadWriteLock
class SimpleMutex
def initialize; @mutex = Mutex.new; end
@mutex.synchronize { yield }
end
end
# for seeing whether my correctness test is doing anything...
# and for seeing how great the overhead of the test is
# (apart from the cost of locking)
class FreeAndEasy
yield # thread safety is for the birds... I prefer to live dangerously
end
end

require 'benchmark'

mutex = Mutex.new
data  = 0

result = Benchmark.measure do
mutex.synchronize { bad = true } if (data % 2) != 0
mutex.synchronize { bad = true } if (data % 2) != 0
end
end
end
end
writers = n_writers.times.collect do
writer_iterations.times do
lock.with_write_lock do
value = data
data  = value+1
sleep(writer_sleep)
data  = value+1
end
end
end
end

writers.each { |t| t.join }
puts "BAD!!! Writers overlapped!" if data != (n_writers * writer_iterations * 2)
end
puts result
end

test(SimpleMutex.new)
test(FreeAndEasy.new)
end


By the way, the performance results on my machine were:

• 17.9s for ReadWriteLock
• 33.4s for SimpleMutex
• 0.8s for FreeAndEasy

What are yours?

-
Do you have this project at github, can you share the link? :) –  Alex Kliuchnikau Feb 16 '12 at 13:41
@AlexKliuchnikau, all the Ruby code which I want to share with others is at github.com/alexdowad/showcase. I intend to upload this to GitHub after I get input from others who have a deeper knowledge of multithreading than I do. –  Alex D Feb 16 '12 at 14:21
@AlexKliuchnikau, do you have a multi-core machine? If so, can you try running this file, perhaps with n_readers, n_writers, reader_iterations and writer_iterations increased? I only have a single-core machine and think that bugs may be exposed more easily with multiple cores. –  Alex D Feb 17 '12 at 14:51
I am reviewing the code, will let you know when don and will show benchmarks for dual code –  Alex Kliuchnikau Feb 17 '12 at 15:48
Thank you!!! If you need better comments to understand the code, let me know; I can comment and post again. –  Alex D Feb 17 '12 at 15:54

I am not an expert in multithreading, but I reviewed the code and here are my thoughts:

l = ReadWriteLock.new
l.with_write_lock { puts 'passed' }


This happens because writer wait for himself to release lock (it increments @counter and then waits if @counter > 0:

while(true)
c = @counter.value
if @counter.compare_and_swap(c,c+WRITER_INCREMENT)
@writer_mutex.synchronize do
@writer_q.wait(@writer_mutex) if @counter.value > 0 # here
end
break
end
end


Looks like increment and decrement for @counter are atomic operations, but change @counter + do operation are not atomic - possible race condition, for example:

# let say we have 1 writer working and 1 reader tries to do the job:
while(true)
c = @counter.value
if c >= WRITER_INCREMENT # here @counter == WRITER_INCREMENT
if @counter.value >= WRITER_INCREMENT # here @counter == WRITER_INCREMENT
# <- but here writer decrements WRITER_INCREMENT and does @reader_q.broadcast  (there is no synchronization to protect from this)
end
end
else
break if @counter.compare_and_swap(c,c+1)
end
end


In your benchmark code I believe you wanted to write something like this

lock.with_write_lock do
value = data + 1
sleep(writer_sleep)
data  = value + 1
end


lock.with_write_lock do
value = data
data = value + 1
sleep(writer_sleep)
data  = value + 1 # 2 times assign value + 1 to data
end


I think it is too early to do performance tuning of the implementation, but here are results of the benchmark for Intel(R) Core(TM)2 Duo CPU P7570 @ 2.26GHz machine:

# MRI 1.9.2 (with global interpreter lock)
0.090000   0.140000   0.230000 (  1.419659)
Testing SimpleMutex with 20 readers and 20 writers. Readers iterate 50 times, sleeping 0.001s each time, writers iterate 50 times, sleeping 0.001s each time
0.050000   0.090000   0.140000 (  2.356187)
Testing FreeAndEasy with 20 readers and 20 writers. Readers iterate 50 times, sleeping 0.001s each time, writers iterate 50 times, sleeping 0.001s each time
0.010000   0.030000   0.040000 (  0.063878)

# MRI 1.9.3 (with global interpreter lock)
0.110000   0.100000   0.210000 (  1.405219)
Testing SimpleMutex with 20 readers and 20 writers. Readers iterate 50 times, sleeping 0.001s each time, writers iterate 50 times, sleeping 0.001s each time
0.030000   0.070000   0.100000 (  2.292269)
Testing FreeAndEasy with 20 readers and 20 writers. Readers iterate 50 times, sleeping 0.001s each time, writers iterate 50 times, sleeping 0.001s each time
0.010000   0.010000   0.020000 (  0.076124)

# Jruby 1.6.5 (with native threads)
1.783000   0.000000   1.783000 (  1.783000)
Testing SimpleMutex with 20 readers and 20 writers. Readers iterate 50 times, sleeping 0.001s each time, writers iterate 50 times, sleeping 0.001s each time
2.484000   0.000000   2.484000 (  2.484000)
Testing FreeAndEasy with 20 readers and 20 writers. Readers iterate 50 times, sleeping 0.001s each time, writers iterate 50 times, sleeping 0.001s each time
0.151000   0.000000   0.151000 (  0.151000)


Note: MRI benchmarks frequently fail with deadlock detected error (or hang in jruby).

Sidenote: I think it would be a good idead to put this project into github repo so other people can participate with pull requests/bug reports. I would participated :)

UPDATE after fix

I ran benchmarks after your fix and here are the results (I ran it several times and did not encountered a deadlock error):

READ INTENSIVE (80% read, 20% write):
Testing ReadWriteLock with 32 readers and 8 writers. Readers iterate 50 times, sleeping 0.001s each time, writers iterate 50 times, sleeping 0.001s each time
0.070000   0.080000   0.150000 (  0.557659)
WRITE INTENSIVE (80% write, 20% read):
Testing ReadWriteLock with 8 readers and 32 writers. Readers iterate 50 times, sleeping 0.001s each time, writers iterate 50 times, sleeping 0.001s each time
0.140000   0.080000   0.220000 (  2.015721)
Testing ReadWriteLock with 20 readers and 20 writers. Readers iterate 50 times, sleeping 0.001s each time, writers iterate 50 times, sleeping 0.001s each time
0.090000   0.080000   0.170000 (  1.286458)
Testing SimpleMutex with 32 readers and 8 writers. Readers iterate 50 times, sleeping 0.001s each time, writers iterate 50 times, sleeping 0.001s each time
0.080000   0.070000   0.150000 (  2.401325)
WRITE INTENSIVE (80% write, 20% read):
Testing SimpleMutex with 8 readers and 32 writers. Readers iterate 50 times, sleeping 0.001s each time, writers iterate 50 times, sleeping 0.001s each time
0.050000   0.090000   0.140000 (  2.361558)
Testing SimpleMutex with 20 readers and 20 writers. Readers iterate 50 times, sleeping 0.001s each time, writers iterate 50 times, sleeping 0.001s each time
0.070000   0.080000   0.150000 (  2.357656)
Testing FreeAndEasy with 32 readers and 8 writers. Readers iterate 50 times, sleeping 0.001s each time, writers iterate 50 times, sleeping 0.001s each time
0.030000   0.040000   0.070000 (  0.072458)
WRITE INTENSIVE (80% write, 20% read):
Testing FreeAndEasy with 8 readers and 32 writers. Readers iterate 50 times, sleeping 0.001s each time, writers iterate 50 times, sleeping 0.001s each time
0.010000   0.050000   0.060000 (  0.079889)
Testing FreeAndEasy with 20 readers and 20 writers. Readers iterate 50 times, sleeping 0.001s each time, writers iterate 50 times, sleeping 0.001s each time
0.030000   0.030000   0.060000 (  0.072672)

-
Awesome post, thanks!!! Yes, I already posted this project on GitHub, see github.com/alexdowad/showcase –  Alex D Feb 18 '12 at 14:59
Great point about the deadlock, that was a mistake. It should have been (@counter.value & MAX_READERS) > 0. (In other words, is a reader currently running?) –  Alex D Feb 18 '12 at 15:03
The second problem you suggested cannot occur, because @reader_q.broadcast happens inside a @reader_mutex.synchronize block. So if the writer finishes while the new reader is already inside that block, the writer will wait until after the reader sleeps to do @reader_q.broadcast, and the reader will be woken up. –  Alex D Feb 18 '12 at 15:05
I pushed a fix (I hope?) for the deadlock problem to GitHub. Can you try running the new code? –  Alex D Feb 18 '12 at 15:06
Sorry, that fix was bad. I am reasoning more carefully about the code and will pus a different fix soon. –  Alex D Feb 18 '12 at 15:14

Here's a simple implementation similar to yours that doesn't require any extra gems added (such as Atomic) - it uses a Queue to easily handle writer/readers signaling, though I suppose this could probably be done faster with a ConditionVariable. Not using extra gems is important in my situation because I need to easily be able to distribute to people who are not ruby-saavy.

It's based off the pseudo-code at: http://en.wikipedia.org/wiki/Readers-writers_problem

It's slightly slower, but doesn't seem to be punished as much by multiple writers. I'd be curious as to how it performs on other systems against your implementation. I believe it to be correct, and it doesn't show any errors according to your test framework.

class LimitWriters
def initialize
@noWaiting = Mutex.new
# Users are either a writer or any number of readers
@users = Queue.new
@users.push(true)
end
def with_write_lock
@noWaiting.lock
@users.pop
@noWaiting.unlock
yield
@users.push(true)
end
prev,curr = nil,nil
@noWaiting.lock
}
@users.pop if prev==0
@noWaiting.unlock
yield
}
@users.push(true) if curr==0
end
end

-

Commenting on github version 3d9881516083a831e4bd0e03aa53696a47cb2a08 :

This pattern seems unsafe (or at least the comment is wrong):

@writer_mutex.synchronize do
# So we have to do another check inside the synchronized section
# If a writer OR reader is running, then go to sleep
c = @counter.value
@writer_q.wait(@writer_mutex) if (c >= RUNNING_WRITER) || ((c & MAX_READERS) > 0)
end


You don't have a mutex protecting @counter, and You are changing it left-and-right. So @counter could change between Your checking of c and going to sleep. I have not analyzed it enough to tell if it is actually a problem.

Also, this code has serious starvation problems. Try printing "w" and "r" for each iteration of the reader and writer threads. Readers can only do some work after the writers are done.

-
thanks for reviewing the code! @counter is an Atomic (from the excellent atomic gem), and it is updated using atomic compare-and-swap operations. Atomic compare-and-swaps are the primary building block used to make code thread-safe without locks. You can learn about them here: en.wikipedia.org/wiki/Compare-and-swap –  Alex D Feb 21 '12 at 5:57
In this case, we want to sleep if a reader or another writer is running. The danger is that if we checked, found another reader/writer was running, and went to sleep, but the other reader/writer had actually finished running by that time, we could keep sleeping forever. Since this code checks the atomic variable inside the synchronized section, the other reader/writer would have to finish while we are inside the synchronized section for this to happen. –  Alex D Feb 21 '12 at 6:04
But since both readers and writers call @writer_mutex.synchronize after finishing, we are guaranteed the call to @writer_mutex.signal will execute after this code. We are also guaranteed that the other writer/reader who finishes will see that a writer is waiting, since this code runs after a successful atomic swap which increments the counter by WAITING_WRITER. –  Alex D Feb 21 '12 at 6:06