10

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...

user2398029
  • 6,699
  • 8
  • 48
  • 80
  • @sawa I actually found the bug in my code show above, and got it to work but I'm open to cleaner suggestions. Is `sleep()` considered bad practice? – user2398029 Dec 07 '12 at 17:35
  • `sleep` is not a good practice. It is not something you should absolutely avoid, but try to avoid when possible. I have the feeling that you can somehow utilize `Thread#join` or use `Fiber`. – sawa Dec 07 '12 at 17:38
  • Thanks, I'll add `fiber` as a tag. – user2398029 Dec 07 '12 at 17:58

2 Answers2

8

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.

Jan
  • 11,636
  • 38
  • 47
  • Nice answer, very helpful! One question: is it necessary to synchronize when adding to the array (`array << 0`)? Would it be possible to circumvent this by using a thread-safe array implementation, which uses its own locks? Or is that necessary for this solution to work? – user2398029 Dec 08 '12 at 21:00
  • The `mtx` Mutex is here to assure that there won't be any race conditions between threads writing to the array. A thread-safe array you're describing should work fine too. – Jan Dec 08 '12 at 21:23
0

There might be merits of having the threads wait for each other. But I think that it is cleaner to have the threads actually finish at "midpoint", because your question obviously impliest that the threads need each others' results at the "midpoint". Clean design solution would be to let them finish, deliver the result of their work, and start a brand new set of threads based on these.

Boris Stitnicky
  • 12,444
  • 5
  • 57
  • 74