Implementing a synchronization barrier in Ruby

fibers, multithreading, ruby, thread-synchronization

Solution

Let's implement a synchronization barrier. It has to know the number of threads it will handle, n, up front. During first n - 1 calls to `sync` the barrier will cause a calling thread to wait. The call number n will wake all threads up.

class Barrier
  def initialize(count)
    @mutex = Mutex.new
    @cond = ConditionVariable.new
    @count = count
  end

  def sync
    @mutex.synchronize do
      @count -= 1
      if @count > 0
        @cond.wait @mutex
      else
        @cond.broadcast
      end
    end
  end
end

Whole body of `sync` is a critical section, i.e. it cannot be executed by two threads concurrently. Hence the call to `Mutex#synchronize`.

When the decreased value of `@count` is positive the thread is frozen. Passing the mutex as an argument to the call to `ConditionVariable#wait` is critical to prevent deadlocks. It causes the mutex to be unlocked before freezing the thread.

A simple experiment starts 1k threads and makes them add elements to an array. Firstly they add zeros, then they synchronize and add ones. The expected result is a sorted array with 2k elements, of which 1k are zeros and 1k are ones.

mtx = Mutex.new
arr = []
num = 1000
barrier = Barrier.new num
num.times.map do
  Thread.start do
    mtx.synchronize { arr << 0 }
    barrier.sync
    mtx.synchronize { arr << 1 }
  end
end .map &:join;
# Prints true. See it break by deleting `barrier.sync`.
puts [
  arr.sort == arr,
  arr.count == 2 * num,
  arr.count(&:zero?) == num,
  arr.uniq == [0, 1],
].all?

As a matter of fact, there's a gem named barrier which does exactly what I described above.

On a final note, don't use sleep for waiting in such circumstances. It's called busy waiting and is considered a bad practice.

Problem

I'm trying to "replicate" the behaviour of CUDA's `__synchtreads()` function in Ruby. Specifically, I have a set of `N` threads that need to execute some code, then all wait on each other at mid-point in execution before continuing with the rest of their business. For example: ``` x = 0 a = Thread.new do x = 1 syncthreads() end b = Thread.new do syncthreads() # x should have been changed raise if x == 0 end [a,b].each { |t| t.join } ``` What tools do I need to use to accomplish this? I tried using a global hash, and then sleeping until all the threads have set a flag indicating they're done with the first part of the code. I couldn't get it to work properly; it resulted in hangs and deadlock. I think I need to use a combination of `Mutex` and `ConditionVariable` but I am unsure as to why/how. Edit: 50 views and no answer! Looks like a candidate for a bounty...

Original source