[Python-Dev] Proposed PEP on concurrent programming support

[Mike Meyer]

PEP: XXX
Title: Interpreter support for concurrent programming
Version: $Revision$
Last-Modified: $Date$
Author: Mike Meyer <mike at mired.org>
Status: Draft
Type: Informational
Content-Type: text/x-rst
Created: 11-Nov-2011
Post-History: 


Abstract
========

The purpose of this PEP is to explore strategies for making concurrent
programming in Python easier by allowing the interpreter to detect and
notify the user about possible bugs in concurrent access. The reason
for doing so is that "Errors should never pass silently".

Such bugs are caused by allowing objects to be accessed simultaneously
from another thread of execution while they are being modified.
Currently, python systems provide no support for such bugs, falling
back on the underlying platform facilities and some tools built on top
of those.  While these tools allow prevention of such modification if
the programmer is aware of the need for them, there are no facilities
to detect that such a need might exist and warn the programmer of it.

The goal is not to prevent such bugs, as that depends on the
programmer getting the logic of the interactions correct, which the
interpreter can't judge.  Nor is the goal to warn the programmer about
any such modifications - the goal is to catch standard idioms making
unsafe modifications.  If the programmer starts tinkering with
Python's internals, it's assumed they are aware of these issues.


Rationale
=========

Concurrency bugs are among the hardest bugs to locate and fix.  They
result in corrupt data being generated or used in a computation.  Like
most such bugs, the corruption may not become evident until much later
and far away in the program.  Minor changes in the code can cause the
bugs to fail to manifest.  They may even fail to manifest from run to
run, depending on external factors beyond the control of the
programmer.

Therefore any help in locating and dealing with such bugs is valuable.
If the interpreter is to provide such help, it must be aware of when
things are safe to modify and when they are not. This means it will
almost certainly cause incompatible changes in Python, and may impose
costs so high for non-concurrent operations as to make it untenable.
As such, the final options discussed are destined for Python version 4
or later, and may never be implemented in any mainstream
implementation of Python.

Terminology
===========

The word "thread" is used throughout to mean "concurrent thread of
execution".  Nominally, this means a platform thread.  However, it is
intended to include any threading mechanism that allows the
interpreter to change threads between or in the middle of a statement
without the programmer specifically allowing this to happen.

Similarly, the word "interpreter" means any system that processes and
executes Python language files.  While this normally means cPython,
the changes discussed here should be amenable to other
implementations.


Concept
=======

Locking object
--------------

The idea is that the interpreter should indicate an error anytime an
unlocked object is mutated.  For mutable types, this would mean
changing the value of the type. For Python class instances, this would
mean changing the binding of an attribute.  Mutating an object bound
to such an attribute isn't a change in the object the attribute
belongs to, and so wouldn't indicate an error unless the object bound
to the attribute was unlocked.

Locking by name
---------------

It's also been suggested that locking "names" would be useful.  That
is, to prevent a specific attribute of an object from being rebound,
or a key/index entry in a mapping object. This provides a finer
grained locking than just locking the object, as you could lock a
specific attribute or set of attributes of an object, without locking
all of them.

Unfortunately, this isn't sufficient: a set may need to be locked to
prevent deletions for some period, or a dictionary to prevent adding a
key, or a list to prevent changing a slice, etc.

So some other locking mechanism is required.  If that needs to specify
objects, some way of distinguishing between locking a name and locking
the object bound to the name needs to be invented, or there needs to
be two different locking mechanisms.  It's not clear that the finer
grained locking is worth adding yet another language mechanism.


Alternatives
============


Explicit locking
----------------

These alternatives requires that the programmer explicitly name
anything that is going to be changed to lock it before changing it.
This lets the interpreter gets involved, but makes a number of errors
possible based on the order that locks are applied.

Platform locks
''''''''''''''

The current tool set uses platform locks via a C extension.  The
problem with these is that the interpreter has no knowledge of them,
and so can't do anything about detecting the mutation of unlocked
objects.


A ``locking`` keyword
'''''''''''''''''''''

Adding a statement to tell the interpreter to lock objects for the
attached suite would let the interpreter know which objects are
locked.  To help prevent deadlocks, such a keyword needs to imply an
order for locking objects, such that two objects locked by the a
locking statement will lock the two objects in the same order during a
single execution of the program.  This can be achieved by sorting
objects by the ``id`` of the object, since the requirements for ``id``
are sufficient for this.

While the locking order requirement is sufficient to prevent deadlocks
from non-nested locking statements, it's not sufficient if locking
statements are allowed to nest.  So either nested locking statements
need to be disallowed, or the outer statement must lock everything
that's going to need to be locked.

Either requirement is sufficiently onerous that alternatives need to
be considered.


Implicit locking
----------------

In this alternative, the interpter uses one or more heuristics to
decide when things should need locking.


Software Transactional Memory (STM)
'''''''''''''''''''''''''''''''''''

STM is a relatively new technology being experimented with in newer
languages, and in a number of 3rd party libraries (both Peak [#Peak]_
and Kamaelia [#Kamaelia]_ provide STM facilities).  A suite is marked
as a `transaction`, and then when an unlocked object is modified,
instead of indicating an error, a locked copy of it is created to be
used through the rest of the transaction. If any of the originals are
modified during the execution of the suite, the suite is rerun from
the beginning. If it completes, the locked copies are copied back to
the originals in an atomic manner.

This causes the changes seen by any threads not running the
transaction to be atomic. If two threads are updating the same object
in transactions, the one that finishes second will be restarted with
values set by the one that finished first.

The advantage of an STM is that the programmer doesn't have to worry
about what is locked, and there's no overhead for using locked objects
(after locking them, of course).

The disadvantage is that any code in a transaction must be safe to run
multiple times.  This forbids any kind of I/O.


Compiler support
''''''''''''''''

Since the point is to get the interpreter involved, we might as well
let it be involved in figuring out which things are safe and don't
need to be locked.  This could potentially eliminate a lot of locking.

Each object - whether a Python class instance or builtin type - is
created with no way to access it until it is bound.  So it is
inherently safe to modify.  Being bound to a local (or nonlocal?)
variable doesn't change this.

Being bound to a global, class or instance variable or stored in a
container does change this, as the object may now be accessed from
other threads via the module or container.

Since this analysis is being done at compile time, being passed to
another function - including methods of the object - makes it unsafe.
Likewise, yielding an object makes it unsafe for future use.
Returning it doesn't change anything, since our execution is over and
we lose access to the object.  Unfortunately, objects returned from
functions must be treated as unsafe.


Interpreter support
'''''''''''''''''''

If we instead track whether or not objects require locking in the
interpreter, then we can improve the analsysis.  The only thing that
definitely makes an object unsafe is binding to a global variable or a
variable known to be unsafe.

Passing objects to C routines exposes them to concurrent modification,
since there's no way to know what will happen inside the C routine.
Adding some way of marking C routines - or possibly the objects passed
to them - as not exposing things to concurrent modification would help
with this, allowing C modules to be called without requiring locking
everything passed to them.

Binding to class and instance variables, or adding them to a
container, is an interesting issue.  If the object in question is
safe, then anything added to it is also safe.  However, this would
mean that when an object is flagged as unsafe, all objects accessible
through it would also have to be flagged as unsafe.

This type of tracking also means that objects effectively have three
states: locked, unlocked, and safe.  Both locked and safe objects can
safely be modified without a problem. Locking and unlocking safe
objects is a nop.


Interpreter threading
---------------------

One alternative is replacing the current threading tools - which are
wrappers around the OS-provided threading - with threading support in
the interpreter.  This would allow the interpreter to control whether
or not objects are shared between threads, which isn't possible today.
The full implications of this approach have as yet to be worked out.


Mixed solutions
---------------

Most likely, any real implementation would use a number of the
techniques above, since all of them have serious shortcomings.  For
instance, combining STM with explicit locking would allow explicit
locking when IO was required, but complex multi-object changes could
be handled by STM, thus avoiding the nested locking issues.

Likewise, interpreter or compiler support could be mixed with most
other solutions to relax the requirement of locking for part of the
objects used in a program.

The implications of mixing these things together also needs to be
explored more thoroughly.


Change proposal
===============

This is 'strawman' proposal to provide a starting point for
discussion.

The proposal is to add an STM support to the python interpreter. A new
suite type - the ``transaction`` will be added to the language. The
suite will have the semantics discussed above: modifying an object in
the suite will trigger creation of a thread-local shallow copy to be
used in the Transaction. Further modifications of the original will
cause all existing copies to be discarded and the transaction to be
restarted. At the end of the transaction, the originals of all the
copies are locked and then updated to the state of the copy.


Further work
============

Requiring further investigation:

- The interpreter providing it's own threading.

- How various solutions interact when mixed.

There are also a couple tools that might be useful to build, or at
least investigate building:

- A static concurrency safety analyzer, that handled the AST of a
  function to determine which variables are safe.

- A dynamic concurrency safety analyzer, similar to coverage [#coverage]_.


Implementation Notes
====================

Not significantly impacting the performance of single-threaded code
must be of paramount importance to any implementation.

One implementation technique arose that could help with this.  Instead
of keeping track of the objects state and having methods check that
state and modify their behavior based on it, change the methods as the
object changes state. So in safe or locked mode, the objects methods
could freely modify the object without having to check it's mode.  In
unlocked mode, an attempt to do so would raise an error or
warning. Unfortunately, this doesn't work if some global or thread
state must be checked instead of just object-local state.


References
==========

.. [#Peak] "Peak, the Python Enterprise Application Kit", http://peak.telecommunity.com/

.. [#Kamaelia] "Kamaelia - Concurrency made useful, fun", http://www.kamaelia.org/

.. [#coverage] "Code coverage measurement for Python", http://pypi.python.org/pypi/coverage

Copyright
=========

This document has been placed in the public domain.


..
   Local Variables:
   mode: indented-text
   indent-tabs-mode: nil
   sentence-end-double-space: t
   fill-column: 70
   coding: utf-8
   End: