From: Joel VanderWerf <vjoel@...>
Date: 2008-07-10T15:41:37+09:00
Subject: Re: Thread-safe priority queue?


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