Boston Python Interest Group Allen B. Downey downey@allendowney.com July 14, 2005 Three ways to think about threads: 1) A thread is (run time stack, hardware state) The run time stack is a stack of namespaces. Invoking a function pushes a namespace onto the stack. Completing function pops a namespace off the stack. Hardware state is in registers on the CPU when the thread is running. When a thread is interrupted, its hardware state is saved in memory. 2) A thread is an object. The implicit thread is created when the program execs. Other threads are created by invoking the Thread constructor. Threads are controlled by invoking methods on Thread objects. 3) A thread is the spark of life that animates a running program. It illuminates one line of code at a time as it moves through the program text. If you think of methods as blocks of text associated with objects, then you can think of the animation force moving from object to object as methods are invoked. (1) is an implementation model. (2) is the model represented by Python. (3) is a mental model I like. Two idioms for creating threads: A) subclass Thread, override run, invoke start. Thread.start invokes Thread.run import threading class HelloThread(threading.Thread): def run(self): print 'hello' ht = HelloThread() ht.start() B) create a Thread and tell it where to start executing. def entry(name): print 'hello,', name t = threading.Thread(target=entry, args=['world']) t.start() A is more consistent with the model of threads as objects. But I find it awkward to have two kinds of objects (Threads and others), and If subclasses of Thread have methods, and those methods are invoked by another thread, then (A) clashes with (3). B is more consistent with my mental model of threads. Thread objects are just handles for controlling threads; they don't have any code associated with them. The only problem with (B) is that it's ugly. 1) target? args? What were they thinking? 2) Most of the time, you start the thread immediately. Easily fixed with a wrapper class: class Thread(threading.Thread): def __init__(self, target, *args): threading.Thread.__init__(self, target=target, args=args) self.start() def entry(name): print 'hello,', name t = Thread(entry, 'world') One other small pain in the neck: multithreaded programs don't handle KeyboardInterrupts (SIGINT) well. Bad news: The interrupt might be delivered to any thread. Worse news: If it gets delivered to a blocked thread, you're hosed. This program usually can't be interrupted: def child_code(n=10): for i in range(n): print i time.sleep(1) children = [Thread(child_code) for i in range(3)] for child in children: child.join() A solution that works on UNIX and Macintosh is in "The Little Book of Semaphores", Appendix A. Threads interact primarily by modifying shared variables. 1) global variables are shared 2) objects passed to the child entry code are shared. As an idiom, I often use an object named shared to store shared variables/objects. class Shared: def __init__(self): self.counter = 0 def child_code(shared): while True: shared.counter += 1 shared = Shared() children = [Thread(child_code, shared) for i in range(2)] for child in children: child.join() With this idiom, shared variables are labelled explicitly. But in many cases it is syntactically neater to use globals. So, what's wrong with this program? Two threads are incrementing a shared variable concurrently, and increment is not a thread-safe operation. What could go wrong? Thread A Thread B -------- -------- t1 = shared.counter t3 = shared.counter t2 = t1 + 1 t4 = t3 + 1 shared.counter = t2 shared.counter = t4 If both threads read the old value before either writes the new one, we get one increment instead of two. How are we supposed to know? 1) generally, concurrent reads are ok. 2) concurrent writes (and modifying an object) are not. Most built-in types are not thread-safe, but some are: 1) Queue in the Queue module 2) Lock, Event, Condition, Semaphore in the threading module. The simplest way to protect a shared variable is with a Lock. class Shared: def __init__(self): self.counter = 0 self.lock = threading.Lock() def child_code(shared): while True: shared.lock.acquire() shared.counter += 1 shared.lock.release() The lock is like a token that can only be held by one thread. If you try to acquire while another thread holds the lock, you have to wait. Only one thread can be in the critical section at a time. This pattern is called "mutual exclusion", which is why locks are sometimes called mutexes. If more than one thread is trying to acquire, what happens when the thread that holds the lock releases it? Can the releasing thread run around and acquire again? If Thread A acquires, can Thread B release? Semaphores ---------- A semaphore is a generalization of a lock. Instead of 2 states (locked and not locked) a semaphore can have positive value (multiple "tokens") negative value (one per thread waiting) In Python, any code that works on a Lock object will work on a Semaphore object, but not the other way around. class Shared: def __init__(self): self.counter = 0 self.lock = threading.Semaphore() def child_code(shared): while True: shared.lock.acquire() shared.counter += 1 shared.lock.release() The two operations on semaphores are 1) acquire: decrement and block if the result is negative (also known as wait or P) 2) release: increment and wake on waiting thread (if any) (also known as signal or V) Basic Semaphore patterns ------------------------ 1) mutual exclusion (same as a Lock) (mutex.py) mutex = Semaphore(1) counter = 0 ## Thread code mutex.wait() # critical section counter += 1 mutex.signal() 2) signaling (similar to Event) (signal.py) initComplete = Semaphore(0) ## Thread A # perform initialization initComplete.signal() ## Thread B initComplete.wait() initComplete.signal() The Thread B code is a pattern I call a turnstile. When the semaphore is available, any number of threads can pass. When it is locked, all threads wait. 3) rendezvous / barrier (also similar to Event) No thread can proceed until all threads arrive. For two threads, a rendezvous is easy (rendez.py): Aarrived = Semaphore(0) Barrived = Semaphore(0) ## Thread A Aarrived.signal() Barrived.wait() ## Thread B Barrived.signal() Aarrived.wait() For an arbitrary, known, number of threads, a barrier is a little trickier (barrier.py) And a little trickier still to make a reusable barrier. 4) queue (similar to Condition) Imagine that threads represent ballroom dancers and that two kinds of dancers, leaders and followers, wait in two queues before entering the dance floor. When a leader arrives, it checks to see if there is a follower waiting. If so, they can both proceed. Otherwise it waits. Similarly, when a follower arrives, it checks for a leader and either proceeds or waits, accordingly. Here are the variables I used in my solution: leaders = followers = 0 mutex = Semaphore(1) leaderQueue = Semaphore(0) followerQueue = Semaphore(0) Here is the code for leaders: mutex.wait() if followers > 0: followers-- followerQueue.signal() mutex.signal() else: leaders++ mutex.signal() leaderQueue.wait() # dance! Here is the code for followers: mutex.wait() if leaders > 0: leaders-- leaderQueue.signal() mutex.signal() else: followers++ mutex.signal() followerQueue.wait() # dance! Classical synchronization problems ---------------------------------- 1) Producer-consumer (similar to Queue) # producer code event = waitForEvent() buffer.add(event) #consumer code event = buffer.get() event.process() Synchronization constraints: * access to the buffer must be exclusive, but event production and processing can and should be concurrent. * if the buffer is empty, consumers must wait * if the buffer is full, producers must wait. Assume that buffer provides a size method. mutex = Semaphore(1) items = Semaphore(0) spaces = Semaphore(buffer.size()) local event ## consumer items.wait() mutex.wait() event = buffer.get() mutex.signal() spaces.signal() event.process() ## producer event = waitForEvent() spaces.wait() mutex.wait() buffer.add(event) mutex.signal() items.signal() 2) Readers and writers In a database/data structure, it is often the case that any number of threads can read concurrently, but writers must exclude all readers and each other. readers = 0 mutex = Semaphore(1) roomEmpty = Semaphore(1) ## writers roomEmpty.wait() # go ahead and write roomEmpty.signal() ## readers mutex.wait() readers += 1 if readers == 1: roomEmpty.wait() mutex.signal() # critical section for readers mutex.wait() readers -= 1 if readers == 0: roomEmpty.signal() mutex.signal() Editorial --------- If this is your idea of fun, there is MUCH more in the Little Book of Semaphores, including: The Sushi Bar Problem The Room Party Problem The Unisex Bathroom Problem The Faneuil Hall Problem The Dining Hall Problem and on and on... http://greenteapress.com/semaphores/ You may hear rumors that Semaphores are obsolete: http://en.wikipedia.org/wiki/Semaphore_(programming) If you find yourself using a Semaphore to implement a Lock, Queue, Event, or Condition, it is probably less error-prone to use the more specific tool. But, Semaphores are versatile, and can be used to solve some very challenging problems. I think it's worth spending some time learning to use them, 1) as a pedagogic step toward the other tools, and 2) in case you need them someday, either because a) you are doing low-level system programming b) you are taking on a very hard problem. (But some people will disagree with 2b.)