Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > Thread-safe priority queue?

Reply
Thread Tools

Thread-safe priority queue?

 
 
Sean O'Halpin
Guest
Posts: n/a
 
      07-09-2008
Hi,

Does anyone know of a solid, thread-safe priority queue implementation in Ruby?

The only one I can find is Joel Vanderwerf's
(http://groups.google.com/group/comp....9db98931e4a74f)
which doesn't work with more recent versions of ruby (because Queue
implementation changed from Ruby to C).

Cheers,
Sean

 
Reply With Quote
 
 
 
 
Robert Dober
Guest
Posts: n/a
 
      07-09-2008
Sean I seem to fail to understand why that change should have any
impact on Jo=EBl's work, can you elaborate please?

Cheers
Robert

--=20
http://ruby-smalltalk.blogspot.com/

---
AALST (n.) One who changes his name to be further to the front
D.Adams; The Meaning of LIFF

 
Reply With Quote
 
 
 
 
Trans
Guest
Posts: n/a
 
      07-09-2008


On Jul 9, 9:08=A0am, "Sean O'Halpin" <(E-Mail Removed)> wrote:
> Hi,
>
> Does anyone know of a solid, thread-safe priority queue implementation in=

Ruby?
>
> The only one I can find is Joel Vanderwerf's
> (http://groups.google.com/group/comp..../thread/9d...=

)
> which doesn't work with more recent versions of ruby (because Queue
> implementation changed from Ruby to C).


Hmm... I'm not sure if Facets implementation is thread safe. It's may
be worth a look. If I recall correctly, Olivier Renaud was the last to
work on it, so he may know more. If it isn't thread safe, btw, it
would make a nice patch.

T.

 
Reply With Quote
 
Sean O'Halpin
Guest
Posts: n/a
 
      07-09-2008
On Wed, Jul 9, 2008 at 6:34 PM, Robert Dober <(E-Mail Removed)> wrote=
:
> Sean I seem to fail to understand why that change should have any
> impact on Jo=EBl's work, can you elaborate please?
>
> Cheers
> Robert
>


I didn't explain that very well, did I? Joel's version inherits from
Queue and directly references an instance variable (@waiting) which
isn't there in the C version.

 
Reply With Quote
 
Sean O'Halpin
Guest
Posts: n/a
 
      07-09-2008
On Wed, Jul 9, 2008 at 6:50 PM, Trans <(E-Mail Removed)> wrote:
>
> Hmm... I'm not sure if Facets implementation is thread safe. It's may
> be worth a look. If I recall correctly, Olivier Renaud was the last to
> work on it, so he may know more. If it isn't thread safe, btw, it
> would make a nice patch.


Thanks for the pointer but the Facets version isn't thread-safe.
Still searching...

 
Reply With Quote
 
Roger Pack
Guest
Posts: n/a
 
      07-09-2008
Sean O'halpin wrote:
> On Wed, Jul 9, 2008 at 6:50 PM, Trans <(E-Mail Removed)> wrote:
>>
>> Hmm... I'm not sure if Facets implementation is thread safe. It's may
>> be worth a look. If I recall correctly, Olivier Renaud was the last to
>> work on it, so he may know more. If it isn't thread safe, btw, it
>> would make a nice patch.

>
> Thanks for the pointer but the Facets version isn't thread-safe.
> Still searching...


Could throw a mutex around the facets version.
--
Posted via http://www.ruby-forum.com/.

 
Reply With Quote
 
Joel VanderWerf
Guest
Posts: n/a
 
      07-10-2008
Sean O'Halpin wrote:
> Hi,
>
> Does anyone know of a solid, thread-safe priority queue implementation in Ruby?
>
> The only one I can find is Joel Vanderwerf's
> (http://groups.google.com/group/comp....9db98931e4a74f)
> which doesn't work with more recent versions of ruby (because Queue
> implementation changed from Ruby to C).


It's pretty easy to work around, I think. Try the following code. It's
based on something I'm using in live code and it seems to pass the test
referenced in the above link.

Btw, it's great that RBTree is a gem now. Thanks to whoever did that.



require 'thread'
require 'rbtree'

class PriorityQueue
def size
@tree.size
end

def initialize(*)
super
@tree = MultiRBTree.new
@que = Queue.new
@mutex = Mutex.new
end

# Push +obj+ with priority equal to +pri+ if given or, otherwise,
# the result of sending #queue_priority to +obj+. Objects are
# dequeued in priority order, and first-in-first-out among objects
# with equal priorities.
def push(obj, pri = obj.queue_priority)
@mutex.synchronize do
if @que.num_waiting > 0
@que << obj
else
@tree.store(pri, obj)
end
end
end

def pop(non_block=false)
@mutex.synchronize do
if (last=@tree.last)
return @tree.delete(last[0]) # highest key, oldest first
end

if non_block
raise ThreadError, "priority queue empty"
end
end
@que.pop # wait
end
end


--
vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407

 
Reply With Quote
 
Martin DeMello
Guest
Posts: n/a
 
      07-10-2008
On Wed, Jul 9, 2008 at 11:17 PM, Joel VanderWerf
<(E-Mail Removed)> wrote:
>
> Btw, it's great that RBTree is a gem now. Thanks to whoever did that.


Ooh, seconded! Stand up and be thanked

martin

 
Reply With Quote
 
Joel VanderWerf
Guest
Posts: n/a
 
      07-10-2008

Looks like a race condition in that...

Joel VanderWerf wrote:
> require 'thread'
> require 'rbtree'
>
> class PriorityQueue
> def size
> @tree.size
> end
>
> def initialize(*)
> super
> @tree = MultiRBTree.new
> @que = Queue.new
> @mutex = Mutex.new
> end
>
> # Push +obj+ with priority equal to +pri+ if given or, otherwise,
> # the result of sending #queue_priority to +obj+. Objects are
> # dequeued in priority order, and first-in-first-out among objects
> # with equal priorities.
> def push(obj, pri = obj.queue_priority)
> @mutex.synchronize do
> if @que.num_waiting > 0
> @que << obj
> else
> @tree.store(pri, obj)
> end
> end
> end
>
> def pop(non_block=false)
> @mutex.synchronize do
> if (last=@tree.last)
> return @tree.delete(last[0]) # highest key, oldest first
> end
>
> if non_block
> raise ThreadError, "priority queue empty"
> end
> end


### Race happens here: if someone else calls #push, then
### this thread will wait even though data is available.

> @que.pop # wait
> end
> end


Will try to fix....

--
vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407

 
Reply With Quote
 
Joel VanderWerf
Guest
Posts: n/a
 
      07-10-2008
Joel VanderWerf wrote:
>
> Looks like a race condition in that...


Proposed fix, using a condition var... still needs some eyeballing and
some tests:

require 'thread'
require 'rbtree'

class PriorityQueue
def size
@tree.size
end

def initialize(*)
super
@tree = MultiRBTree.new
@que = [] # should never have more than one entry
@num_waiting = 0
@mutex = Mutex.new
@cond = ConditionVariable.new
end

# Push +obj+ with priority equal to +pri+ if given or, otherwise,
# the result of sending #queue_priority to +obj+. Objects are
# dequeued in priority order, and first-in-first-out among objects
# with equal priorities.
def push(obj, pri = obj.queue_priority)
@mutex.synchronize do
if @num_waiting > 0
@que << obj
@cond.signal
else
@tree.store(pri, obj)
end
end
end

def pop(non_block=false)
@mutex.synchronize do
if (last=@tree.last)
return @tree.delete(last[0]) # highest key, oldest first
end

if non_block
raise ThreadError, "priority queue empty"
end

@num_waiting += 1
@cond.wait(@mutex)
@num_waiting -= 1
@que.pop
end
end
end



--
vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
efficient priority queue for a few descrete priority levels Marcel Müller C++ 3 04-27-2009 03:22 PM
D300 BUG in Aperture Priority & Shutter Priority Mode Chico Digital Photography 21 06-23-2008 01:55 PM
Shutter Priority Vs. Aperture Priority Question mutefan@yahoo.com Digital Photography 13 09-14-2006 03:51 PM
Should I use shutter-priority or appurature-priority? ½ Confused Digital Photography 4 02-22-2006 09:48 AM
Question about Aperture priority and Shutter Priority John Edwards Digital Photography 8 01-05-2005 04:58 PM



Advertisments