Read-write lock implementation for Ruby

Question

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
# all the readers to finish before going ahead
# But any additional readers who come when the writer is already waiting, will also
# wait (so writers are not starved)
# Written by Alex Dowad
# Thanks to Doug Lea for java.util.concurrent.ReentrantReadWriteLock (used for inspiration)
# Usage:
# lock = ReadWriteLock.new
# lock.with_read_lock { data.retrieve }
# lock.with_write_lock { data.modify! }
# Implementation note: A goal for this implementation is to make the "main" (uncontended)
# path for readers lock-free
# Only if there is reader-writer or writer-writer contention, should locks be used
require 'atomic' # must install 'atomic' gem
require 'thread'
class ReadWriteLock
 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
 @reader_q = ConditionVariable.new # queue for waiting readers
 @reader_mutex = Mutex.new # to protect reader queue
 @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!
 MAX_READERS = WRITER_INCREMENT - 1
 def with_read_lock
 while(true)
 c = @counter.value
 raise "Too many reader threads!" if (c & MAX_READERS) == MAX_READERS
 if c >= WRITER_INCREMENT
 @reader_mutex.synchronize do 
 @reader_q.wait(@reader_mutex) if @counter.value >= 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
 @reader_mutex.synchronize { @reader_q.broadcast }
 end
 break
 end
 end
 end
end
if __FILE__ == 0ドル
# for performance comparison with ReadWriteLock
class SimpleMutex
 def initialize; @mutex = Mutex.new; end
 def with_read_lock
 @mutex.synchronize { yield }
 end
 alias :with_write_lock :with_read_lock
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
 def with_read_lock
 yield # thread safety is for the birds... I prefer to live dangerously
 end
 alias :with_write_lock :with_read_lock
end
require 'benchmark'
def test(lock, n_readers=20, n_writers=20, reader_iterations=50, writer_iterations=50, reader_sleep=0.001, writer_sleep=0.001)
 puts "Testing #{lock.class} with #{n_readers} readers and #{n_writers} writers. Readers iterate #{reader_iterations} times, sleeping #{reader_sleep}s each time, writers iterate #{writer_iterations} times, sleeping #{writer_sleep}s each time"
 mutex = Mutex.new
 bad = false
 data = 0
 result = Benchmark.measure do
 readers = n_readers.times.collect do
 Thread.new do
 reader_iterations.times do
 lock.with_read_lock do
 mutex.synchronize { bad = true } if (data % 2) != 0
 sleep(reader_sleep)
 mutex.synchronize { bad = true } if (data % 2) != 0
 end
 end
 end
 end
 writers = n_writers.times.collect do
 Thread.new 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
 readers.each { |t| t.join }
 writers.each { |t| t.join }
 puts "BAD!!! Readers+writers overlapped!" if mutex.synchronize { bad }
 puts "BAD!!! Writers overlapped!" if data != (n_writers * writer_iterations * 2)
 end
 puts result
end
test(ReadWriteLock.new)
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?

• Aliaksei Kliuchnikau: Do you have this project at github, can you share the link? :)
• Alex D: @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: @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.
• Aliaksei Kliuchnikau: I am reviewing the code, will let you know when don and will show benchmarks for dual code
• Alex D: Thank you!!! If you need better comments to understand the code, let me know; I can comment and post again.

Answer 1

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

The following code leads to deadlock:

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 
 raise "Too many reader threads!" if (c & MAX_READERS) == MAX_READERS
 if c >= WRITER_INCREMENT # here @counter == WRITER_INCREMENT
 @reader_mutex.synchronize do
 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)
 @reader_q.wait(@reader_mutex) # then we wait until writer will broadcast, but it will not happen -> deadlock
 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

instead of

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
BAD!!! Writers overlapped!
 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
BAD!!! Writers overlapped!
 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
BAD!!! Writers overlapped!
 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)
BALANCED (50% read, 50% write):
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)
READ INTENSIVE (80% read, 20% write):
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)
BALANCED (50% read, 50% write):
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)
READ INTENSIVE (80% read, 20% write):
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
BAD!!! Readers+writers overlapped!
BAD!!! Writers overlapped!
 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
BAD!!! Readers+writers overlapped!
BAD!!! Writers overlapped!
 0.010000 0.050000 0.060000 ( 0.079889)
BALANCED (50% read, 50% write):
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
BAD!!! Readers+writers overlapped!
BAD!!! Writers overlapped!
 0.030000 0.030000 0.060000 ( 0.072672)

• Alex D: Awesome post, thanks!!! Yes, I already posted this project on GitHub, see github.com/alexdowad/showcase
• Alex D: 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: 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: I pushed a fix (I hope?) for the deadlock problem to GitHub. Can you try running the new code?
• Alex D: Sorry, that fix was bad. I am reasoning more carefully about the code and will pus a different fix soon.

Answer 2

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)
 @readers = 0
 @readersSem = Mutex.new
 end
 def with_write_lock
 @noWaiting.lock
 @users.pop
 @noWaiting.unlock
 yield
 @users.push(true)
 end
 def with_read_lock
 prev,curr = nil,nil
 @noWaiting.lock
 @readersSem.synchronize {
 prev = @readers
 @readers += 1
 }
 @users.pop if prev==0
 @noWaiting.unlock
 yield
 @readersSem.synchronize {
 @readers -= 1
 curr = @readers
 }
 @users.push(true) if curr==0
 end
end

Answer 3

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.

• Alex D: 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: 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: 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: About the starvation problem, the concept of a read-write lock is that all readers must wait if a writer is running. If readers could work when writers were not done, that would be a bug. You can learn about read-write locks here: en.wikipedia.org/wiki/Readers%E2%80%93writer_lock. Please note also that read-write locks are designed to be used where most accesses are reads. (If you ran the benchmark, you probably saw that the performance of ReadWriteLock trounces Mutex in read-intensive situations.)
• Alex D: +1 for the suggestion to print "w" and "r". The problem here is that queued writers are always run before queued readers. But if we did it the opposite way, writers could be starved. Maybe this will work: when a writer thread finishes, it will prefer to wake up readers if any are queued. When all reader threads finish, they will prefer to wake up writers if any are queued. What do you think?