> I can't think of a reason why deque would need to release the GIL.

Yes, in deque.append(item) and deque.popleft() are atomic.  Likewise list.append() and list.pop() are atomic.  The heappush() and heappop() operations aren't as fortunate since they call __lt__() on arbitrary Python objects.

> perhaps we should indeed follow Antoine's advice and implement
> a different queue that has fewer features but is guaranteed 
> to be usable by signal handlers and GC callbacks 
> (including __del__).

Is the idea to use a regular non-reentrant lock but write the whole thing in C to avoid running any pure python instructions (any of which could allow a signal handler to run)?

If so, it seems like the only feature that needs to be dropped is subclassing.  The maxsize feature and unfinished tasks tracking could still be supported.  Also, I suppose the guarantees would have be marked as CPython implementation details, leaving the other implementations to fend for themselves.

Or were you thinking about a pure python simplified queue class?  If so, an RLock() will likely be required (the act of assigning deque.popleft's return value to a pure python variable can allow a pending signal to be handled before the lock could be released).

One other thought:  Would it make sense get() and put() to add gc.disable() and gc.enable() whenever GC is already enabled?  That would eliminate a source of reentrancy.