Finding primes with Rinda::TupleSpace

Eric Hodel | Sat, 19 Aug 2006 09:09:00 GMT

Posted in DRb, Hacking, Ruby

While at FOSCON 2006 I watched Lucas Carlson's presentation on Rinda and DRb, but he barely scratched the surface of Rinda's capabilities with his prime finding implementation.

Rinda::TupleSpace is more powerful than just a name service for DRb. Since a TupleSpace has synchronized access to all its items, you can use a TupleSpace to coordinate processes as well.

I started rewriting Lucas' DRb using prime finder at FOSCON, but wasn't able to finish it until now. This version coordinates all the activities of the prime finding via the TupleSpace. No locking is necessary in any of the code because the TupleSpace takes care of it for us.

Here's the server:

require 'rinda/ring'
require 'rinda/tuplespace'

class TupleSpacePrimeFinder

  def self.run
    DRb.start_service
    new.run
  end

  def initialize
    @ts = Rinda::TupleSpace.new
  end

  ##
  # Lists primes as they are added to the TupleSpace.

  def list_primes
    Thread.start do
      notifier = @ts.notify 'write', [:prime, nil]

      puts "primes found:"
      notifier.each do |_, t|
        puts t.last
      end
    end
  end

  def run
    list_primes

    @ts.write [:prime, 2] # seed prime
    @ts.write [:current, 2] # next value to search
    @ts.write [:step, 100] # range of values to search

    rp = Rinda::RingProvider.new :TSPF, @ts, 'PrimeFinder using TupleSpace'
    rp.provide

    DRb.thread.join
  end

end

TupleSpacePrimeFinder.run

It doesn't do much besides place some seed values in the TupleSpace and print out the primes as they get added to the TupleSpace. The service is published to the RingServer (download ringserver.rb from my tutorial on tutorial on Rinda::Ring) and everything is ready to go.

And next the client:

require 'rinda/ring'
require 'rinda/tuplespace'

class PrimeFinder

  def self.run
    DRb.start_service
    new.find
  end

  def initialize
    ts = Rinda::RingFinger.primary.read([:name, :TSPF, DRbObject, nil])[2]
    @ts = Rinda::TupleSpaceProxy.new ts # for safety
  end

  def find
    loop do
      start = @ts.take([:current, nil]).last # start of our search space
      finish = start + @ts.read([:step, nil]).last # items in our search space
      @ts.write [:current, finish] # write it back

      primes = @ts.read_all([:prime, nil]).map { |_,v| v } # read all primes

      start.upto finish do |candidate|
        next unless prime_in? candidate, primes

        top = Math.sqrt(candidate).to_i

        next unless prime_in? candidate, (start..top)

        @ts.write [:prime, candidate] # add to the found list
        primes << candidate
      end
    end
  end

  def prime_in?(candidate, range)
    range.all? do |value|
      value < candidate and candidate % value != 0
    end
  end

end

PrimeFinder.run

The client runs in a loop and grabs the current unsearched prime candidate from the TupleSpace, increments it, then puts it back into the TupleSpace. This take/write operation forms a Mutex. Only one client will be allowed to remove :current at a time, and the rest will block. No need to worry about any synchronization, TupleSpace takes care of that for us. no comments

Comments