9

I admit this was asked to me in interview a long time ago, but I never bothered to check it.

The question was simple, how does Python make Queue thread-safe?

My answer was, because of Interpreter Lock (GIL), any time only 1 thread is making a call to get the element from queue while others are sleeping/waiting. I was/am still not sure if it a valid answer.

The interviewer seemed dissatisfied and asked if Queues are thread-safe in Java or .Net implementation of Python which doesn't have GIL? If so, how do they implement thread-safe feature on said data structure.

I tried looking for it, but I always seem to stumble upon how to use thread-safe queues.

So how is Queue or a simple list can be made thread-safe and avoid race conditions?

Alternatively, what algorithms or techniques used by GEvent implementation of thread-safe Queues?

4
  • @gnat I was aware of it. My question is neither too broad nor I am trying to stump anyone by an idiotic question. My problem is well defined, very specific (including the language used) and to the point. I have also provided my own answers and assumptions which clearly states that I am not demanding any spoon-feeding. I could have not written that first statement and you would have exercised caution in that case. So I request you to first read the question completely. Feb 2 '18 at 12:46
  • 2
    "If we use semaphores or locks, that defeats the purpose of making it thread-safe for concurrency." What does that even mean? Feb 2 '18 at 12:51
  • @VincentSavard I am sorry, wrong statement. let me edit it. Feb 2 '18 at 12:52
9

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.

1
  • Thank you for helping me understand GIL. I also came across Grok the GIL that also explains the same thing. Feb 2 '18 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.