Why does this multithreaded python program print from 0 to 99 CORRECTLY?

Question

This is the code.

from Queue import Queue
from threading import *

threadLock = Lock()

def do_stuff(q):
  while True:
    threadLock.acquire()
    print q.get()
    q.task_done()
    threadLock.release()

q = Queue(maxsize=0)
num_threads = 10

for x in range(100):
  q.put(x)

for i in range(num_threads):
  worker = Thread(target=do_stuff, args=(q,))
  worker.setDaemon(False)
  worker.start()



q.join()

When I execute this code, I get the numbers from 0 to 99 printed perfectly sorted. When I remove the locks in do_stuff, I expect the numbers from 0 to 99 to be printed unsorted, however even with some erroneour numbers here and there, it mostly prints the range sorted again from 0 to 99. Why is that? Shouldn't it be unsorted, since I'm not synchronizing the threads in any way?

Answer 1

Your function doesn't do anything else between retrieving the next number from the queue and printing it.

Python holds a lock (the GIL) while executing each bytecode, so only between bytecodes can threads switch. Looking at the function (without locks) shows us that there is only one spot where a thread switch would give another thread the chance to grab a next number and print it before the preceding thread can print theirs:

>>> import dis
>>> def do_stuff(q):
...   while True:
...     print q.get()
...     q.task_done()
... 
>>> dis.dis(do_stuff)
  2           0 SETUP_LOOP              31 (to 34)
        >>    3 LOAD_GLOBAL              0 (True)
              6 POP_JUMP_IF_FALSE       33

  3           9 LOAD_FAST                0 (q)
             12 LOAD_ATTR                1 (get)
             15 CALL_FUNCTION            0
             18 PRINT_ITEM          
             19 PRINT_NEWLINE       

  4          20 LOAD_FAST                0 (q)
             23 LOAD_ATTR                2 (task_done)
             26 CALL_FUNCTION            0
             29 POP_TOP             
             30 JUMP_ABSOLUTE            3
        >>   33 POP_BLOCK           
        >>   34 LOAD_CONST               0 (None)
             37 RETURN_VALUE        

Even if the thread switched there, another thread must then complete both the CALL_FUNCTION and the PRINT_ITEM bytecodes before control switched back, for you to see items being printed out of order.

The thread switch would have to take place between CALL_FUNCTION and PRINT_ITEM. If you introduced more instructions there, you'd increase the chances of numbers being printed out of order.