PEP 583 – A Concurrency Memory Model for Python | peps.python.org
PEP 583 – A Concurrency Memory Model for Python PEP 583 – A Concurrency Memory Model for Python Author : Jeffrey Yasskin <jyasskin at google.com> Status : Withdrawn Type : Informational Created : 22-Mar-2008 Post-History : Table of Contents Abstract Rationale A couple definitions Two simple memory models Sequential Consistency Happens-before consistency An example Surprising behaviors with races Zombie values Inconsistent Orderings A happens-before race that’s not a sequentially-consistent race Self-justifying values Uninitialized values (direct) Uninitialized values (flag) Inconsistent guarantees from relying on data dependencies The rules for Python Data-race-free programs are sequentially consistent No security holes from out-of-thin-air reads Restrict reorderings instead of defining happens-before Atomic, unordered assignments Two tiers of guarantees Sequential Consistency Adapt the x86 model Upgrading or downgrading to an alternate model Implementation Details CPython PyPy Jython IronPython References Acknowledgements Copyright Abstract This PEP describes how Python programs may behave in the presence of concurrent reads and writes to shared variables from multiple threads.
We use a happens before relation to define when variable accesses are ordered or concurrent. Nearly all programs should simply use locks to guard their shared variables, and this PEP highlights some of the strange things that can happen when they don’t, but programmers often assume that it’s ok to do “simple” things without locking, and it’s somewhat unpythonic to let the language surprise them. Unfortunately, avoiding surprise often conflicts with making Python run quickly, so this PEP tries to find a good tradeoff between the two.
Rationale So far, we have 4 major Python implementations – CPython, Jython , IronPython , and PyPy – as well as lots of minor ones. Some of these already run on platforms that do aggressive optimizations. In general, these optimizations are invisible within a single thread of execution, but they can be visible to other threads executing concurrently. CPython currently uses a GIL to ensure that other threads see the results they expect, but this limits it to a single processor.
Jython and IronPython run on Java’s or .NET’s threading system respectively, which allows them to take advantage of more cores but can also show surprising values to other threads. So that threaded Python programs continue to be portable between implementations, implementers and library authors need to agree on some ground rules. A couple definitions Variable A name that refers to an object. Variables are generally introduced by assigning to them, and may be destroyed by passing them to del .
Variables are fundamentally mutable, while objects may not be. There are several varieties of variables: module variables (often called “globals” when accessed from within the module), class variables, instance variables (also known as fields), and local variables. All of these can be shared between threads (the local variables if they’re saved into a closure). The object in which the variables are scoped notionally has a dict whose keys are the variables’ names.
Object A collection of instance variables (a.k.a. fields) and methods. At least, that’ll do for this PEP. Program Order The order that actions (reads and writes) happen within a thread, which is very similar to the order they appear in the text. Conflicting actions Two actions on the same variable, at least one of which is a write. Data race A situation in which two conflicting actions happen at the same time. “The same time” is defined by the memory model.
Two simple memory models Before talking about the details of data races and the surprising behaviors they produce, I’ll present two simple memory models. The first is probably too strong for Python, and the second is probably too weak. Sequential Consistency In a sequentially-consistent concurrent execution, actions appear to happen in a global total order with each read of a particular variable seeing the value written by the last write that affected that variable.
The total order for actions must be consistent with the program order. A program has a data race on a given input when one of its sequentially consistent executions puts two conflicting actions next to each other. This is the easiest memory model for humans to understand, although it doesn’t eliminate all confusion, since operations can be split in odd places. Happens-before consistency The program contains a collection of synchronization actions , which in Python currently include lock acquires and releases and thread starts and joins.
Synchronization actions happen in a global total order that is consistent with the program order (they don’t have to happen in a total order, but it simplifies the description of the model). A lock release synchronizes with all later acquires of the same lock. Similarly, given t = threading.Thread(target=worker) : A call to t.start() synchronizes with the first statement in worker() . The return from worker() synchronizes with the return from t.join() .
If the return from t.start() happens before (see below) a call to t.isAlive() that returns False , the return from worker() synchronizes with that call. We call the source of the synchronizes-with edge a release operation on the relevant variable, and we call the target an acquire operation. The happens before order is the transitive closure of the program order with the synchronizes-with edges. That is, action A happens before action B if: A falls before B in the program order (which means they run in the same thread) A synchronizes with B You can get to B by following happens-before edges from A.
An execution of a program is happens-before consistent if each read R sees the value of a write W to the same variable such that: R does not happen before W , and There is no other write V that overwrote W before R got a chance to see it. (That is, it can’t be the case that W happens before V happens before R .) You have a data race if two conflicting actions aren’t related by happens-before. An example Let’s use the rules from the happens-before model to prove that the following program prints “[7]”: class Queue : def __init__ ( self ): self . l = [] self . cond = threading .
Condition () def get (): with self . cond : while not self . l : self . cond . wait () ret = self . l [ 0 ] self . l = self . l [ 1 :] return ret def put ( x ): with self . cond : self . l . append ( x ) self . cond . notify () myqueue = Queue () def worker1 (): x = [ 7 ] myqueue . put ( x ) def worker2 (): y = myqueue . get () print y thread1 = threading . Thread ( target = worker1 ) thread2 = threading . Thread ( target = worker2 ) thread2 . start () thread1 . start () Because myqueue is initialized in the main thread before thread1 or thread2 is started, that initialization happens before worker1 and worker2 begin running, so there’s no way for either to raise a NameError, and both myqueue.l and myqueue.cond are set to their final objects.
The initialization of x in worker1 happens before it calls myqueue.put() , which happens before it calls myqueue.l.append(x) , which happens before the call to myqueue.cond.release() , all because they run in the same thread. In worker2 , myqueue.cond will be released and re-acquired until myqueue.l contains a value ( x ). The call to myqueue.cond.release() in worker1 happens before that last call to myqueue.cond.acquire() in worker2 .
That last call to myqueue.cond.acquire() happens before myqueue.get() reads myqueue.l , which happens before myqueue.get() returns, which happens before print y , again all because they run in the same thread. Because happens-before is transitive, the list initially stored in x in thread1 is initialized before it is printed in thread2. Usually, we wouldn’t need to look all the way into a thread-safe queue’s implementation in order to
The rest of this page is on the live site.