See 8.10 Queue — A synchronized queue class (at the top)

The Queue module implements multi-producer, multi-consumer queues. It is especially useful in threaded programming when information must be exchanged safely between multiple threads.

You are mistaken that the GIL would make a Python program threadsafe. It only makes the interpreter itself threadsafe.

For example, let's look at a super simple LIFO queue (aka. a Stack). We'll ignore that a list can already be used as a stack.

class Stack(object):
  def __init__(self, capacity):
    self.size = 0
    self.storage = [None] * capacity

  def push(self, value):
    self.storage[self.size] = value
    self.size += 1

  def pop(self):
    self.size -= 1
    result = self.storage[self.size]
    self.storage[self.size] = None
    return result

Is this threadsafe? Absolutely not, despite running under the GIL.

Consider this sequence of events:

• Thread 1 adds a couple of values

  stack = Stack(5)
  stack.push(1)
  stack.push(2)
  stack.push(3)
  

  The state is now storage=[1, 2, 3, None, None], size=3.

• Thread 1 adds a value stack.push(4) and is suspended before the size can be incremented

  self.storage[self.size] = value
  # interrupted here
  self.size += 1
  

  The state is now storage=[1, 2, 3, 4, None], size=3.

• Thread 2 removes a value stack.pop() which is 3.

  The state is now storage=[1, 2, None, 4, None], size=2.

• Thread 1 is resumed

  self.storage[self.size] = value
  # resume here
  self.size += 1
  

  The state is now storage=[1, 2, None, 4, None], size=3.

As a result, the stack is corrupted: the pushed value can't be retrieved, and the top element is empty.

The GIL only linearises data accesses, but this is almost completely useless to the ordinary Python developer because the order of operations is still unpredictable. I.e. the GIL cannot be used as a Python-level lock, it just guarantees that the values of all variables are up to date (volatile in C or Java). Python implementations without a GIL must also provide this property for compatibility, e.g. by using volatile memory accesses or using their own locks. Jython is a GIL-less implementation that specifically uses threadsafe implementations for dict, list, and so on.

Because Python does not guarantee any order of operations between threads, it comes as no surprise that thread-safe data structures must use a lock. For example, the standard library queue.Queue class @v3.6.4 has a mutex member, and a few condvars using that mutex. All data accesses are properly guarded. But note that this class isn't primarily intended a queue data structure, but as a job queue between multiple threads. A pure data structure would not usually be concerned with locking.

Of course, locks and mutexes stink for various reasons, e.g. because of the possibility of deadlocks, and because acquiring a lock is slow. As a consequence, there's lots of interest in lock-free data structures. When the hardware provides certain atomic instructions, it is possible to update a data structure with such an atomic operation, e.g. by replacing a pointer. But this tends to be rather difficult to do.

ProcessPoolExecutor uses multiprocessing.queues.Queue for the call queue and a mp_context.SimpleQueue (multiprocessing) for the result queue - which are used to communicate between a local thread and the processes.

Nice graphic of ProcessPoolExecutor

• concurrent.futures.ProcessPoolExecutor stuff uses multiprocessing Queues to communicate between threads and processes.
• The multiprocessing.queues.Queue docs specifically state it is thread and process safe
• At the bottom of the queue documentation there is a note referring to the multiprocessing.Queue object ... for use in a multi-processing (rather than multi-threading) context