Queue.get_nowait() sometimes bogusly returns Empty

[Geoffrey Talvola]

Tim Peters wrote:
> 
> [Geoffrey Talvola]
> > ... suppose that I actually did want the behavior I described above
> > -- a reliable "if the queue is empty, raise the Empty exception,
> > otherwise remove and return an item from the queue".
> 
> If you're also not willing to block, you can't.  You could 
> start by trying
> 
>     if the_queue_looks_empty_right_now:
>         raise Empty
>     else:
>         ???
> 
> If it takes the "if" branch, the queue may well become 
> non-empty by the time
> the calling thread sees the exception.  OTOH, if it takes the 
> "else" branch,
> what are you going to do?  There's no guarantee that the 
> queue is *still*
> non-empty by the time you get to the "???" part.  You have to 
> grab a lock to
> say anything for sure, and as soon you try to grab a lock the 
> possibility
> for blocking comes with it.
> 
> > How would I write it?  Do I need to busy-loop like
> > this (untested):
> >
> > 	def get_nowait_reliable(self):
> > 		while 1:
> > 			try:
> > 				return self.get_nowait()
> > 			except Empty:
> > 				# Let's see if it's really 
> empty.  If not,
> > try again.
> > 				if self.empty():
> > 					raise
> >
> > or is there a better way?
> 
> Sorry, that it isn't even *a* way.  One problem is that it 
> can block forever
> (unlikely, but possible, for another thread to put something 
> on the queue
> every time you get to the "if self.empty()", but take it away 
> again every
> time before you get back to the self.get_nowait()" -- then 
> you spin in an
> infinite loop).
> 
> The other problem is that it's quite possible that 
> self.get_nowait() raises
> Empty, and self.empty() returns True, and that 100 other 
> threads then put
> things back on the queue between then and the time your 
> thread gets around
> to doing the "raise".  So it's got the same problem you're 
> trying to solve,
> but worse in that it can block for an arbitrarily long time.
> 
> The inherent problem is that "empty" makes no sense except 
> with respect to a
> specific observer at a specific time.  Locks let you freeze 
> the state so
> that the lock-holding observer can know the state for certain 
> while it holds
> the lock, but getting the lock can block, and without a lock 
> you can't know
> the state for certain -- you can only know what the state was 
> the last time
> you looked at it, and "in theory", without *some* sort of 
> hard synch gimmick
> an unbounded amount of time can pass between when you gather 
> the info and
> when you're able to act on it.  So long as you're working 
> outside a synched
> area, all you can know is what some state was in the past.

I understand what you're saying.  Would it make a difference if I told you
that for this application, it's OK if the "get_nowait_reliable" operation
blocks for "a little while"?  In other words, I don't mind if it blocks
while 17 other threads manipulate the queue.  What I care about is that once
the queue is no longer being manipulated in other threads, I either get an
Empty exception or an object out of the queue.  For my purposes if the queue
was empty at any point during the operation then raising the Empty exception
is OK.

My requirements are a bit fuzzier than the strict no-blocking requirement of
Queue.get_nowait() so maybe it's possible to implement this.

In case you're wondering, this is in Webware's WebKit application server
where there is a pool of N threads, and a queue of (non-thread-safe) servlet
instances acting as a cache.  We only want to create servlet instances when
all existing instances are in-use.  When a given thread needs a servlet, it
basically does:

	try:
		instance = cache.get_nowait()
	except Queue.Empty:
		instance = new_instance()
	# use the instance...
	cache.put(instance)

The problem is that every once in a while get_nowait() returns Empty when
the queue isn't actually empty, so the size of the cache grows slowly and
unboundedly over time.  But I'd prefer for the cache to contain at most N
instances where N is the number of threads.

- Geoff