Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?

share|improve this question
    
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
show 2 more comments

3 Answers

up vote 3 down vote accepted

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)
share|improve this answer
    
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
show 5 more comments

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
share|improve this answer
add comment

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.

share|improve this answer
    
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
    
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 Feb 21 '12 at 6:08
    
+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? –  Alex D Feb 21 '12 at 6:16
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.