Implementing a Synchronization Barrier in Ruby

Implementing a synchronization barrier in Ruby

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.

Zero permit semaphores?

Again from The Little Book of Semaphores, §2.2:

Listing 2.1: Semaphore initialization syntax

fred = Semaphore(1)

The function Semaphore is a constructor; it creates and returns a new Semaphore. The initial value of the semaphore is passed as a parameter to the constructor.

So in the author's pseduocode, 0 isn't the number of permits; it's the initial value of the semaphore. What does a value of zero mean? It's explained in the text immediately proceeding listing 2.1:

If the value is positive, then it represents the number of threads that
can decrement without blocking. If it is negative, then it represents the number
of threads that have blocked and are waiting. If the value is zero, it means there
are no threads waiting, but if a thread tries to decrement, it will block.

_{(emphases added)}

Related Topics