add threading.RWLock

[84401114-8e59-4056-83cb-632106c0b648]

BPO	8800
Nosy	@jcea, @pitrou, @kristjanvalur, @tiran, @njsmith, @asvetlov, @ofek, @elarivie
Files	rwlock.patch Added-ShrdExclLock-to-threading-and-multiprocessing.patch sharablelock.patch Added-ShrdExclLock-to-threading-and-multiprocessing-2.patch rwlock.patch rwlock.patch rwlock-sbt.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields: ```python assignee = None closed_at = None created_at = labels = ['type-feature', 'library'] title = 'add threading.RWLock' updated_at = user = 'https://github.com/kristjanvalur' ``` bugs.python.org fields: ```python activity = actor = 'asvetlov' assignee = 'none' closed = False closed_date = None closer = None components = ['Library (Lib)'] creation = creator = 'kristjan.jonsson' dependencies = [] files = ['17448', '27350', '27359', '27363', '27385', '27412', '27422'] hgrepos = [] issue_num = 8800 keywords = ['patch', 'needs review'] message_count = 63.0 messages = ['106350', '106372', '106373', '106376', '106377', '106386', '168077', '168149', '171567', '171568', '171599', '171600', '171626', '171639', '171653', '171659', '171667', '171669', '171674', '171693', '171695', '171696', '171697', '171698', '171699', '171700', '171703', '171708', '171709', '171710', '171713', '171714', '171716', '171717', '171718', '171721', '171780', '171781', '171782', '171783', '171785', '171786', '171788', '171789', '171790', '171792', '171793', '171877', '171883', '171891', '171914', '171915', '171930', '171975', '171979', '172064', '172071', '172074', '274765', '274795', '287745', '360026', '360031'] nosy_count = 15.0 nosy_names = ['jcea', 'pitrou', 'kristjan.jonsson', 'christian.heimes', 'jyasskin', 'njs', 'asvetlov', 'neologix', 'vrutsky', 'sbt', 'mklauber', 'Sebastian.Noack', 'dan.oreilly', 'Ofekmeister', 'elarivie'] pr_nums = [] priority = 'normal' resolution = None stage = 'patch review' status = 'open' superseder = None type = 'enhancement' url = 'https://bugs.python.org/issue8800' versions = [] ```

[84401114-8e59-4056-83cb-632106c0b648]

Provided is a patch, implementing a RWLock using a ConditionVariable and Lock. It has rdlock() and wrlock() methods, and an unlock() method, similar to the rwlock API in pthreads. It has context managers rdlocked() and wrlocked(). In addition, it conforms to the RLock interface, with acquire() and release() being aliases to wrlock() and unlock() respectively and when used as a context manager, it gets a wrlock() There is no documentation yet, since this is just a proposal, but there are unit tests.

See also bpo-8777 for another locking primitive, the Barrier.

[5969680d-a065-4b5f-9706-8216692d995a]

This patch doesn't apply cleanly against the py3k tree. Since Python 2.7 is in beta, and there's no 2.8, this can only go into python 3, so you should work against that tree.

It's a bit annoying that the R in RWLock stands for a different word from in RLock. But I can't think of a better name.

Hm, the test for RWLock should use a Barrier to check for multiple readers.

I wonder if it makes sense to add a DeadlockError as a subclass of RuntimeError and throw that from trying to upgrade a read-lock to a write-lock.

The docs should describe why upgrading a read-lock to a write-lock is banned, or else people will try to add the feature.

test_wrrecursion should also check pure writer recursion. Oh, no, that's tested by RLockTests. Comment that please. The name of the test should probably mention write_then_read_recursion to distinguish it from write-then-write or read-then-write.

test_readers_writers doesn't quite test enough. (Feel free to add another test rather than changing this one.) You want to test that readers can't starve writers. For example, say we have: lock = RWLock() done = False def r(): with lock.rdlocked(): if done: return _wait() def w(): nonlocal done with lock.wrlocked(): done = True readers = Bunch(r, 50) _wait() writers = Bunch(w, 1) readers.wait_for_finished() writers.wait_for_finished()

In a naive implementation, there may never be a point where no reader has the lock held, and so the writer may never get in to tell them all to exit. I believe your implementation will already pass this test.

spelling: mathced

I'm not sure that "#threads will be few" is true for a read-lock, but I don't mind for the first implementation.

Generally put a space after # when it introduces a comment, start comments with a capital letter, and end them with punctuation so we know you didn't stop typing early.

In _rdlock could you flip the "not self.nw" condition? That way the else won't be a double-negative.

Can self.rcond.wait() ever throw an exception? I suspect you should use try:finally: to guard the "self.nr -= 1"

Why must the user hold a write lock to use Condition.wait? Semantically, a waiting on a read-lock would release the current thread's recursive read-locks, and all should be well.

It looks like self.owning holds one copy of each thread's id for each re-entry by that thread. That wasn't obvious so deserves a comment.

General API questions:

1. Given that the other locking APIs use "acquire" and "release" instead of "lock" and "unlock", perhaps this class should use "rdacquire" and "wracquire"?
2. I wonder if it helps actual code to be able to just call "unlock" instead of "rdunlock" and "wrunlock". Code releasing the lock should always know which kind of lock it holds.

Otherwise, this looks basically correct. Thanks!

[pitrou]

I'm not sure it's a good idea to have a default context manager, and default acquire/release methods. "In the face of ambiguity, refuse the temptation to guess".

Is there any use in being able to use a RWLock inside a condition variable?

Docstrings should be polished (e.g. typo "must be mathced with an release"). I think wrlocked() and rdlocked() deserve a docstring too.

A style nit: generally, comments should be on their own line, before the code they comment. Also, there should be a space just after the "#" (see PEP-8 :-)).

[5969680d-a065-4b5f-9706-8216692d995a]

In this case, "acquire" isn't ambiguous. All the other lock types actually acquire a write lock, so it makes sense to have the operation with the same name they use also acquire a write lock on this object.

I realized that read/write locks are actually shared/exclusive locks, which might form the basis for a name that doesn't collide with RLock. Boost (http://www.boost.org/doc/libs/1_43_0/doc/html/thread/synchronization.html#thread.synchronization.mutex_types.shared_mutex) uses shared_mutex for the concept, so SLock or SELock? There are some algorithms that write while the lock is acquired non-exclusive, so "shared" is actually a better name for the concept, even though posix and Java used read/write.

The possibility of lock downgrading (turning an exclusive lock into a shared lock, without allowing any other exclusive acquisitions in the mean time) might inform your decision about how to name "unlock".

[pitrou]

In this case, "acquire" isn't ambiguous. All the other lock types actually acquire a write lock, so it makes sense to have the operation with the same name they use also acquire a write lock on this object.

Well, it looks like a strange kind of "consistency" to me, since other lock types are not dual. Both posix and Java APIs don't seem to imply that the write lock is the "default" lock in a RW lock. However, I'm not a synchronization specialist.

I realized that read/write locks are actually shared/exclusive locks, which might form the basis for a name that doesn't collide with RLock. Boost (http://www.boost.org/doc/libs/1_43_0/doc/html/thread/synchronization.html#thread.synchronization.mutex_types.shared_mutex) uses shared_mutex for the concept, so SLock or SELock?

SELock looks ok, but I have to say that RWLock is more obvious (I don't need to do a search to guess that RW means "read/write").

[5969680d-a065-4b5f-9706-8216692d995a]

You're definitely right that posix and java don't make these usable from the normal lock API. And I don't think it's essential that they be usable as RLocks, although it's nice for Conditions. I think what I'm actually saying is that, if you have an acquire() operation on RWLock, then it has to forward to the write lock. Forwarding to the read lock would have different semantics from RLock.acquire (2 threads could get in at once) and so would be incorrect.

I agree that RWLock is more obvious. As long as the docs mention that it's equivalent to a shared/exclusive lock, I don't care that much about the name. Just throwing out ideas.

[84401114-8e59-4056-83cb-632106c0b648]

I should add that on Windows, the new SRW that is part of Vista and Windows 7, uses locking, that is it favors neither readers or writers. It appears that nowadays the complex semantics of RWLocks have not really proven worthwile. See http://msdn.microsoft.com/en-us/magazine/cc163405.aspx

Perhaps this proposed patch is overly complex.

[pitrou]

Perhaps this proposed patch is overly complex.

I don't know. Do you think relaxing the semantics would make the implementation significantly faster? (interesting link, btw)

[328b4c07-2c93-4424-89fa-f0e929543ac9]

I would love to see a reader/writer lock implementation shipped with Python's threading (and multiprocessing) module. But I have some issues with the patch:

1. I would avoid the terms 'read' and 'write' as those terms are referring just to one of many use cases. A better and more generic name would be shared and exclusive lock.

2. If we add a new synchronization primitive to the threading module we really should add it also to the multiprocessing module, for consistency and to keep switching between threading and multiprocessing as easy as it is right now.

3. The methods rdlock() and wrlock() might even block if you call them with blocking=False. That's because of they acquire the internal lock in a blocking fashion before they would return False.

4. As Antoine already pointed out, it is a bad idea to make acquiring the exclusive (write) lock, the default behavior. That clearly violates the Zen of Python, since explicit is better than implicit.

5. The issue above only raises from the idea that the RWLock should provide the same API as the Lock and RLock primitives. So everywhere where a lock primitive is expected, you can pass either a Lock, RLock or RWLock. That is actually a good idea, but in that case you should explicitly specify, whether to pass the shared (read) or the exclusive (write) lock.

Both issues 4. and 5. only raise from the idea that a shared/exclusive lock should be implemented as a single class. But having two different lock primitives, one for the shared lock and one for the exclusive lock and a function returning a pair of those, would be much more flexible, pythonic and compatible with existing lock primitives.

def ShrdExclLock()
  class _ShrdLock(object):
    def acquire(self, blocking=True):
      ...

    def release(self, blocking=True):
      ...

    def __enter__(self):
      self.acquire()
      retrun self

    def __exit__(self, exc_value, exc_type, tb):
      self.release()

  class _ExclLock(object):
    def acquire(self, blocking=True):
      ...

    def release(self, blocking=True):
      ...

    def __enter__(self):
      self.acquire()
      retrun self

    def __exit__(self, exc_value, exc_type, tb):
      self.release()

  return _ShrdLock(), _ExclLock()

# create a shared/exclusive lock shrd_lock, excl_lock = ShrdExclLock()

[84401114-8e59-4056-83cb-632106c0b648]

Excellent points. For 3. however, I don't consider access to synchronized state to be "blocking". Blocking means to block while waiting for the lock. The internal lock is never held for any amount of time. Perhaps I'll cook up a new patch with these thoughts.

[328b4c07-2c93-4424-89fa-f0e929543ac9]

Using a lock as context manager is the same as calling lock.acquire(blocking=True) and it will in fact block while waiting for an other thread to release the lock. In your code, the internal lock is indeed just hold for a very short period of time while acquiring or releasing a shared or exclusive lock, but it might add up to a notable amount of time dependent on how much concurrent threads are using the same RWLock and how slow/busy your computer is.

But what made me reconsider my point are following facts:

1. For example, when you acquire a shared (read) lock in non-blocking mode and False is returned, you assume that an other thread is holding an exclusive (write) lock. But that isn't necessarily the case, if it also returns False, when the internal lock is acquired by an other thread for example in order to acquire or release another shared (read) lock.

2. The internal lock must be acquired also in order to release a shared/exclusive lock. And the 'release' method (at least if implemented as for Lock and RLock) don't have a 'blocking' argument, anyway.

For that reasons, I think it is ok to block while waiting for the internal lock, even if the shared/exclusive lock was acquired in non-blocking mode. At least it seems to lead to less unexpected side effects, than returning False in case the internal lock is acquired.

[328b4c07-2c93-4424-89fa-f0e929543ac9]

I've added a new patch, that implements a shared/exclusive lock as described in my comments above, for the threading and multiprocessing module.

[84401114-8e59-4056-83cb-632106c0b648]

Yes, any "blocking" on the internal lock is not semantic blocking due to the use of the Shared lock itself, but merely a technical aspect, not semantically visible to the program. It is equivalent to the operating system pausing the thread, a techical detail opaque to the user program and somethign it cannot affect or influence.

"Blocking" in the sense of the lock is due to the semantic use of the lock itself and the resources that it protects.

[e26428b1-70cf-4e9f-ae3c-9ef0478633fb]

I've added a new patch, that implements a shared/exclusive lock as described in my comments above, for the threading and multiprocessing module.

The patch does not seem to touch the threading mode and does not come with tests. I doubt the multiprocessing version is actually picklable since self._requirement is a lambda function.

Also it would be best to avoid making multiprocessing.synchronize depend on ctypes. (See implementation of multiprocessing.Barrier or Issue bpo-14953.)

Personally, I would prefer to make the shared and exclusive locks attributes of the same object, so one could do

   with selock.shared:
      ...

   with selock.exclusive:
      ...

[84401114-8e59-4056-83cb-632106c0b648]

I can't say that I'm that familiar with multiprocessing to comment on that in particular. But I do find your approach strange, to create two "lock-like" objects, in stead of the more familiar construct of having a "RWLock" (this is known from other languages) with two ways of claiming it.

Attached is a new patch. I've adopted the name "SharableLock" perhaps it is bad. It uses your idea of returning "lock-like" objects that do either shared or exclusive locking.

There are two implementations: SharableLock is much like the original patch, with two conditions and writer priority. SimpleSharableLock drops all that, and uses a single condition and ad-hoc priority. I've added unittests that show that writer-starvation does not appear to be a problem.

Createing a Multiprocessing lock using the SharableLockBase should pose no difficulties.

The use of the SharableLock with Condition objects is forced to be Exclusive, since Condition objects typcially rely on their associated lock to synchronize internal state.

[328b4c07-2c93-4424-89fa-f0e929543ac9]

I was just waiting for a comment pointing out, that my patch comes without tests. :) Note that we are still discussing the implementation and this patch is just a proof of concept. And since the way it is implemented and the API it provides could still change, its quite pointless to write tests, until we at least agreed on the API.

I have uploaded a new patch. The way it is implemented now, is more like the Barrier is implemented. The common code is shared in the threading module and the shared/exclusive lock objects can be pickled now. I have also fixed a bug related to acquiring locks in non-blocking mode.

However the code still uses c_uint, but ctypes (and multiprocessing.sharedtypes) is only imported when ShrdExclLock is called. So it is just a lazy dependency, now. However the reason why I am using ctypes instead of python integers for threading and a BufferWrapper for multiprocessing (as the Barrier does) is, because of 2 of the 4 counters need to be continuously incremented, and c_uint has the nice feature that it can overflow, in contrast to python integers and integers in arrays. Also that way the implementation is simpler and it seems that there isn't much difference under the hood between using BufferWrapper() and RawValue().

A shared/exclusive lock isn't one lock but two locks, which are synchronized, but must be acquired separately. Similar to a pipe, which isn't one file, but one file connected to another file that reads whatever you have written into the first file. So it isn't strange to create two lock objects, as it also isn't strange that os.pipe() returns two file descriptors.

Also having a separate lock object for the shared and exclusive lock, each providing the same API (as Lock and RLock), gives you huge flexibility. You can acquire both locks using the with statement or pass them separately around. So for example when you have a function, thread or child process, that should only be able to acquire either the shared or the exclusive lock, you don't have to pass both locks. That also means that existing code that expects a lock-like object will be compatible with both the shared and exclusive lock.

[84401114-8e59-4056-83cb-632106c0b648]

A shared/exclusive lock isn't one lock but two locks, which are >synchronized, but must be acquired separately. Similar to a pipe, >which isn't one file, but one file connected to another file that >reads whatever you have written into the first file. So it isn't >strange to create two lock objects, as it also isn't strange that >os.pipe() returns two file descriptors

That's one way to look at it. Another (and the more common) is to say that it is one lock, which can be in two different states. The original patch is modeled on seveal such constructs that exist in the field, such as for example the SRW locks in windows: http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx

(In fact, I am rather leaning back towards the RWLock name again, since that seems to be the most commonly used on other platforms. Oh, how tempting it is to bikeshed about such trivialities.)

Note that in my last patch, I provide the exclusive_locked() and shared_locked() methods that return exactly such locks as you describe.

I'd much rather have a single RW Lock object, with retgular locking proxies, rather than two distinct object, attached only by some shared common variables.

Also, with the structured approach I suggest, you can relatively easily create such a lock that also works across process boundaries by implementing a concrete class with SharableLockBase as a base.

[pitrou]

Ok, since we're bikeshedding, I like Richard's proposal best:

Personally, I would prefer to make the shared and exclusive locks attributes of the same object, so one could do

with selock.shared: ...

with selock.exclusive: ...

Please note, the "same object" could simply be a namedtuple instance.

Also I think "shared/exclusive" indeed conveys the semantics better than "read/write".

[e26428b1-70cf-4e9f-ae3c-9ef0478633fb]

@Sebastian: Both your patch sets are missing the changes to threading.py.

[328b4c07-2c93-4424-89fa-f0e929543ac9]

Yes, you could also look at the shared/exclusive lock as one lock with different states. But this approach is neither more common, have a look at Java's ReadWriteLock [1] for example, which works just like my patch does, except that a factory is returned instead of a tuple. Nor does it provide any of the benefits, I have mentioned before (same API as Lock and RLock, better compatibility with existing code an with statement, ability to pass the shared or exclusive lock separetly around). But maybe we could satisfy anybody, by following Richard's and Antoine's suggestion of returning a named tuple. So you could use the ShrdExclLock both ways:

# use a single object
lock = ShrdExclLock()

with lock.shared:
  ...

with lock.exclusive:
  ...

# unpack the the object into two variables and pass them separately around shrd_lock, excl_lock = ShrdExclLock()

Thread(target=reader, args=(shrd_lock,)).start() Thread(target=writer, args=(excl_lock,)).start)

The majority of us seems to prefer the terms shared and exclusive. However I can't deny that the terms read and write are more common, even though there are also notable exmples where the terms shared and exclusive are used [2] [3]. But let us ignore how other call it for now, and get to the origin of both set of terms, in order to figure out which fits best into Python:

shared/exclusive -> abstract description of what it is read/write -> best known use case

The reason why I prefer the terms shared and exculsive, is that it is more distinct and less likely to get misunderstand. Also naming a generic implementation after a specific use case is bad API design and I don't know any other case where that was done, in the Python core library.

[1] http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/locks/ReadWriteLock.html [2] http://www.postgresql.org/docs/9.2/static/explicit-locking.html [3] http://www.unix.com/man-page/freebsd/9/SX/

[328b4c07-2c93-4424-89fa-f0e929543ac9]

@richard: I'm sorry, but both of my patches contain changes to 'Lib/threading.py' and can be applied on top of Python 3.3.0. So can you explain what do you mean, by missing the changes to threading.py?

[84401114-8e59-4056-83cb-632106c0b648]

Personally, I would prefer to make the shared and exclusive locks attributes of the same object, so one could do

with selock.shared: ...

with selock.exclusive: ... Please note, the "same object" could simply be a namedtuple instance. With this, you are stuck with employing a context manager model only. You loose the flexibility to do explicit acquire_read() or acquire_write(). My latest patch has methods shared_lock(), exclusive_lock() that return proxy lock objects that can be used like context managers like you describe, but you still have the flexibility of using the lock manually.

As for the bikeshedding, let's look at the list of concrete implementations out there: Windows: SRW locks (slim reader writer) http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937(v=vs.85).aspx Pthreads: rwlock_t (reader/writer) http://publib.boulder.ibm.com/iseries/v5r2/ic2924/index.htm?info/apis/users_86.htm Java: ReadWriteLock, http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReadWriteLock.html

Am I missing anything? Don't see why we need to adopt a completly different name or idiom to what people are used to. Also, note that the java version is quite similar to Richard's proposal.

[84401114-8e59-4056-83cb-632106c0b648]

> shared/exclusive -> abstract description of what it is

If you want to argue it this way, I counter that the attributes "shared" and "exclusive" apply to the type of "access to the protected object" you are talking about, and yet, the name suggest that they are attributes of the lock itself.

In that sense, "reader lock" and "writer lock", describe attributes of the user of the lock, and the verbs "readlock" and "writelock" describe the operation being requested.

It's simply more difficult to use the more abstract concepts 'shared' and 'exclusive' as convenient and transparent descriptors of what the thing does, and likely to just brew confusion.

[e26428b1-70cf-4e9f-ae3c-9ef0478633fb]

@richard: I'm sorry, but both of my patches contain changes to 'Lib/threading.py' and can be applied on top of Python 3.3.0. So can you explain what do you mean, by missing the changes to threading.py?

I was reading the Rietveld review page

http://bugs.python.org/review/8800/#ps6111

which only shows changes to multiprocessing/init.py and multiprocessing/synchronize.py.

The patch looks like it was produced using git rather than hg, so perhaps Rietveld got confused by this. In that case it is a bug in Rietveld that it produced a partial review instead of producing no review.

unpack the the object into two variables and pass them separately around

shrd_lock, excl_lock = ShrdExclLock()

Thread(target=reader, args=(shrd_lock,)).start() Thread(target=writer, args=(excl_lock,)).start)

Although using namedtuple is probably a good idea, I don't think it really adds much flexibility. This example could just as easily be written

  selock = ShrdExclLock()

Thread(target=reader, args=(selock.shared,)).start() Thread(target=writer, args=(selock.exclusive,)).start)

[e26428b1-70cf-4e9f-ae3c-9ef0478633fb]

With this, you are stuck with employing a context manager model only.
You loose the flexibility to do explicit acquire_read() or acquire_write().

You are not restricted to the context manager model. Just use selock.shared.acquire() or selock.exclusive.acquire().

[84401114-8e59-4056-83cb-632106c0b648]

Perhaps I should have pointed out, for Sebastian's benefit, that my second patch uses "timeout" rather than "blocking" since that is the new black in python 3. Also, I think the "threading" implementation shows clearly the problem of having two independent objects that are only losely bound by some shared common variables: The threading.py version has to rely on c_types ints for the common counters. If the two locks were merely two different views of a common RWLock object, this problem could go away, and you could have the threading.RWLock and the multiprocessing.RWLock be different concrete classes derived from a common base class.

I also think it is time to drop the "writer preference" model, since it just adds complexity with doubtful benefits. Sebastian's model also does that.

I'll provide a new example patch presently.

[328b4c07-2c93-4424-89fa-f0e929543ac9]

If you want to argue it this way, I counter that the attributes "shared" and "exclusive" apply to the type of "access to the protected object" you are talking about, and yet, the name suggest that they are attributes of the lock itself.

A lock's sole purpose is to synchronize access to a protected object or context. So naming a lock after its type of protection absolutely makes sense. Those names are also not supposed to be attributes of the lock, rather two locks (a shared and an exclusive lock) should be created, that might be returned as a namedtuple for convenience.

In that sense, "reader lock" and "writer lock", describe attributes of the user of the lock, and the verbs "readlock" and "writelock" describe the operation being requested.

The user of the lock isn't necessarily a reader or writer. This is just one of many possible use cases. For example in a server application a shared/exclusive lock might be used to protect a connection to the client. So every time a thread wants to use the connection, a shared lock must be acquired and when a thread wants to shutdown the connection, the exclusive lock must be acquired, in order to ensure that it doesn't interrupt any thread still processing a request for that connection. In that case you clearly wouldn't call the users reader and writer.

The patch looks like it was produced using git rather than hg, so perhaps Rietveld got confused by this. In that case it is a bug in Rietveld that it produced a partial review instead of producing no review.

Yes, I have imported the Python 3.3.0 tree into a local git repository and created the patch that way. Since patches generated with git are still compatible with the 'patch' program in order to apply them, I hope that isn't a problem.

Although using namedtuple is probably a good idea, I don't think it really adds much flexibility. This example could just as easily be written

selock = ShrdExclLock()

Thread(target=reader, args=(selock.shared,)).start() Thread(target=writer, args=(selock.exclusive,)).start()

Yes, that is true, but in some cases it is more convenient to be able unpack the shared/exclusive lock into two variables, with a one-liner. And defining a namedtuple doesn't require any extra code compared to defining a class that holds both locks. In fact it needs less code to be implemented.

However the flexibility comes from having two lock objects, doesn't matter how they are accessed, instead as suggested by Kristján to have a single lock object, which just provides proxies for use with the with statement.

I also think it is time to drop the "writer preference" model, since it just adds complexity with doubtful benefits. Sebastian's model also does that.

I have implemented the simplest possible acquisition order. The lock acquired first will be granted first. Without that (or a more advanced policy) in applications with concurrent threads/processes that are heavily using the shared lock, the exclusive lock can never be acquired, because of there is always a shared lock acquired and before it is released the next shared lock will be acquired.

[e26428b1-70cf-4e9f-ae3c-9ef0478633fb]

I think Sebastian's algorithm does not correctly deal with the non-blocking case. Consider the following situation:

• Thread-1 successfully acquires exclusive lock. Now num_got_lock == 1.

• Thread-2 blocks waiting for shared lock. Will block until (num_got_lock == 1 and excl_count == 0). Now num_got_lock == 1.

• Thread-3 does non-blocking acquire of shared lock but fails. Now num_got_lock == 2.

Now, since num_got_lock == 2, the predicate that Thread-2 is waiting for will not happen until num_got_lock overflows.

This is probably fixable if we just prevent a failed non-blocking acquire from modifying num_acq_lock and num_got_lock. (But I don't see how to extend the algorithm to allow timeouts.)

[e26428b1-70cf-4e9f-ae3c-9ef0478633fb]

My previous comment applied to Sebastian's first patch. The second seems to fix the issue.

[tiran]

I wonder, why are you creating your own algorithm here? There must be plenty of reference implementations that are already used in production code. Don't be a shamed to copy a Java implementation! :) The entire threading module is a rip-off of the Java threading API.

[328b4c07-2c93-4424-89fa-f0e929543ac9]

I would love to see how other people would implement a shared/exclusive lock that can be acquired from different processes. However it really seems that nobody did it before. If you know a reference implementation I would be more than happy.

There are plenty of implementations for threading only, but they won't work with multiprocessing, due to the limitations in the ways you can share data between processes.

[pitrou]

On the naming front: shorthands like "Shrd" and "Excl" are a bit frown upon. Since "SharedExclusiveLock" is on the long side, I would suggest calling the API "SELock".

[tiran]

A RW lock is part of POSIX threads [1]. It's usually a good idea to either use POSIX functions or to mimic their behavior. After all POSIX is an industry standard.

Boost and Java have several lock and rw lock implementations. Wikipedia [2] is a good starting point for the various implementations. The page also mentions a seqlock which looks interesting to me as it's fast for few writers with lots of readers.

[1] http://linux.die.net/man/3/pthread_rwlock_init [2] http://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock

[pitrou]

A RW lock is part of POSIX threads [1]. It's usually a good idea to either use POSIX functions or to mimic their behavior. After all POSIX is an industry standard.

We've already departed from that. Our Lock is nothing like a mutex, for example (it's more of a binary semaphore). We follow POSIX when exposing POSIX APIs (as in the os module), but otherwise we have our own abstractions, for example the 3.x I/O stack.

[328b4c07-2c93-4424-89fa-f0e929543ac9]

Thanks, but as I already said there are a lot of implementations for shared/exclusive lock that can be acquired from different threads. But we need with threading as well as with multiprocessing.

And by the way POSIX is the standard for implementing UNIX-like systems and not an industry standard for implementing anything, including high-level languages like Python.

[79528080-9d85-4d18-8a2a-8b1f07640dd7]

The page also mentions a seqlock which looks interesting to me as it's fast for few writers with lots of readers.

A seqlock is suitable for consistent views of simple data structures (e.g. a counter in the Linux kernel), but it won't fly for a high-level language like Python. The problem is that, despite its name, it's not a lock, but it's based on retries, which means that:

• the critical section must be idempotent (no side effect like incrementing a variable, or crediting a bank account :-)
• your critical section is simple enough so that it can tolerate inconsistent views, e.g.:

with seqlock.rlock():
    z = 1/(x-y)

if the writer threads make sure that x!=y when they hold the seqlock, you can still, if you're unlucky, fall at the wrong time and x==y, then you get a nice ZeroDivisionError.

(And yes, you have the same kind of issues with transational memory, as well as others...).

Otherwise, having a rwlock would be a nice addition, but since the GIL serializes everything anyway, this isn't likely to benefit many situations (unless you do I/O, of course), on CPython at least. That's why it's definitely important to have the equivalent for multiprocessing.

Also, I prefer reader-writer lock because that's how everyone calls it (not only POSIX), and RWLock looks better than SELock (well, at least to me).

[84401114-8e59-4056-83cb-632106c0b648]

You are not restricted to the context manager model. Just use selock.shared.acquire() or selock.exclusive.acquire().

The unlock operation is the same, so now you have to arbitrarily pick one of the "lockd" and chose release(). Why take a construct which is essentially a lock that can be acquired in two different ways and force people to view it as separate objects?

I much prefer a simple RWLock primitve, such as is popular in other programming environments, and add your convenient pseudo-locks on top. That way, we are not forcing a certain myopic view of what an RWLock is down people's throat.

[84401114-8e59-4056-83cb-632106c0b648]

We've already departed from that. Our Lock is nothing like a mutex, for example (it's more of a binary semaphore).

This is not by nature of good design, but an accident. C python needed both mutex and signaling ability and decided that a single non-recursive lock were good enough for that. This is a debatable choice since all modern systems consider these two different needs and provide different primitives to satisfy them. The "Lock" was then exposed to Python and RLock grafted on top to fix the non-recursiveness problem. Then we added signaling in the form of Events, Semaphores and Condition variables. Had this ben more purposefully designed, then there would be no Lock or RLock in threading.py, only a Mutex.

[84401114-8e59-4056-83cb-632106c0b648]

I have implemented the simplest possible acquisition order. The lock acquired first will be granted first. Without that (or a more advanced policy) in applications with concurrent threads/processes that are heavily using the shared lock, the exclusive lock can never be acquired, because of there is always a shared lock acquired and before it is released the next shared lock will be acquired.

I think you got that argument backwards. The simple greedy policy you implement works well provided there are not too many readers. Otherwise, the writers will be starved, since they have to wait for an oppertune moment when no readers are active to get a foot in the door, so to speak. Your approach is similar to my "SimpleSharableLock" from my second patch in that respect, and also to Microsoft's SRW Locks (http://msdn.microsoft.com/en-us/magazine/cc163405.aspx). They specifically state:

" This means that if your application requires that data updates take priority over data reads, you might want to consider a different reader/writer lock that favors writers".

While the test_threading.py showed ok results with the simple approach, my preliminary tests on multiprocessing show that writers need to be given priority if they are not to be starved.

[e26428b1-70cf-4e9f-ae3c-9ef0478633fb]

I think you got that argument backwards. The simple greedy policy you implement works well provided there are not too many readers. Otherwise, the writers will be starved, since they have to wait for an oppertune moment when no readers are active to get a foot in the door, so to speak.

Actually, I think Sebastian's algorithm attempts to be fair to both readers and writers.

If there is a writer waiting then "self._wait_count > self._granted_count". The writer cannot be prempted by a later reader because the reader would find "waitno > self._granted_count" until after writer has been granted the lock.

[e26428b1-70cf-4e9f-ae3c-9ef0478633fb]

The unlock operation is the same, so now you have to arbitrarily pick one of the "lockd" and chose release().

That depends on the implementation. In the three implementations on

http://en.wikipedia.org/wiki/Readers-writers_problem

the unlock operateration is different for readers and writers.

Why take a construct which is essentially a lock that can be acquired in two different ways and force people to view it as separate objects?

I don't see why writing

    lock.exclusive.acquire()

really requires a different way of thinking compared to writing

    lock.exclusive_acquire()

or

    lock.acquire_exclusive()

[84401114-8e59-4056-83cb-632106c0b648]

Here is a new patch. it is complete with: threading implementation and tests multiprocessing implementation and tests.

Let's leave the naming bikeshedding a bit and focus on some practical aspects:

1) The threading version contains a RWLock and a FairRWLock. Both support recursion, although not upgrading from read to write access. This is achieved with a list of 'owning' threads. 2) the "Fair" version provides 'write' priority, blocking further first acquisitions in read mode until no writers are waiting.

Multiprocessing: Because there is no way I know to share a list of owning thread ids, this version is more limited: a) The RWLock() only contains one owing thread ID. This allows recursion but some error checking present in the threading version cannot be implemented. b) the FairRWLock() again provides writer priority. But to do that, we have to allow 'recursive' read if a writer is waiting, if we allow recursion at all. And for that, we need to know what threds own the lock in read mode. Since we don't have that information, this version of the lock disallows recursion alltogether.

Discussion: Recursion/No recursion? The Windows SRW locks disallow recursion. Their rationale is here: http://msdn.microsoft.com/en-us/magazine/cc163405.aspx: "First, regarding recursive acquires: if the locking policy you’ve designed for your application requires that synchronization objects be acquired recursively, this is very possibly a red flag telling you to re-examine your locking policy to eliminate the recursion. This is our opinion and results from the additional overhead of executing the lock acquisition and release code multiple times and, perhaps more importantly, because ensuring that the balance of lock releases with the lock acquisitions is often difficult to prove correct."

Of course the SRWLock is a "slim" lock and thus can be forgiven for not providing such functionality.

"Fair" vs "Non-fair" (Fair is not a good term, writer priority would be better). The reason I'm coming back to this being useful is tests using the multiprocessing module. The tests there show without doubt that a simple greedy locking algorithm fails miserably if there are more readers than writers. The test "test_writer_success" has been adorned with a timer, and the simple version completes in 15 seconds, while the "fair" version completes in 0.5 seconds.

Good times!

[84401114-8e59-4056-83cb-632106c0b648]

Oh, I forgot to mention: Once one gets into the domain of allowing such niceties as writer priority, surely you can agree that the implementation of both locking modes belongs in the same class instance. That is just plain good coding practice, allowing for class invariants, state assertions and such things. Two class instances coupled by a bunch of common variables is IMHO neither good style nor practice.

[328b4c07-2c93-4424-89fa-f0e929543ac9]

Exactly, with my implemantation "the lock acquired first will be granted first". There is no way that either shared nor exclusive locks can starve, and therefore it should satisfy all use cases. Since you can only share simple datastructures like integers across processes, I also found that this seems to be the only policy (except ignoring the acquisition order at all), that can be implemented for multiprocessing.

I have also looked at the seqlock algorithm, which seems to be great for use cases where the exclusive lock is acquired rather rarely and where your "reader" code is in fact read-only and therefore can be repeated. But in any other case a seqlock would break your code. However the algorithm is ultra simple and can't be implemented as lock-like object anyway. Though you could implement it as context manager, but that would hide the fact that the "reader" code will be repeated. So if you find yourself that a seqlock is that what you need for your specific use case, you can just use the algorithm like below:

lock = multiprocessing.Value(0)
count = multiprocessing.Value(0)

def do_read():
  while True:
    if count.value % 2:
      continue
    data = ...
    if count.value % 2:
      continue
    return data

def do_write(data):
  with lock:
    count.value += 1
    # write data
    count.value += 1

I have also experimented with implementing a shared/exclusive lock on top of a pipe and UNIX file locks (https://gist.github.com/3818148). However it works only on Unix and only with processes (not threads). Also it turned out that UNIX file locks don't implement an acquisition order. So exclusive locks can starve, which renders it useless for most use cases.

[328b4c07-2c93-4424-89fa-f0e929543ac9]

@Kristján: Uhh, that is a huge amount of code, more than twice as much (don't counting tests) as my implementation, to accomplish the same. And it seems that there is not much code shared between the threading and multiprocessing implementation. And for what? Ah right, to make the API suck as much as the Windows API does. Please tell me more about good coding practice. ;)

[84401114-8e59-4056-83cb-632106c0b648]

This amount of code provides recursion, context managers, condition variable compatibility, timeout functionality, error checking and conformance with the unit tests.

The actual locking code is encapsulated in the three functions acquire_read(), acquire_write, release().

The requirements and possibilities between threading and multiprocessing are many and multiple. Sharing the implementation has the drawback of imposing the shortcomings and preformance bottlenecks of the multiprocessing implementation on the threading implementation, for no good reason.

I't tell you about good programming practice, but I'm too busy trying to understand the actual locking policy in your patch. Sometimes comments in code can be helpful.

[84401114-8e59-4056-83cb-632106c0b648]

Ah, you are implementing an FIFO lock. That should have been made clear. I see it now that you grant the lock in the order that the acquisition is attempted. Ok, this is fine, but with one important caveat: Explicit handoff such as that can suffer from "lock convoying". In contested situation this can result in the protected resource being much less available than it ought to be.

In my dayjob, I write locking primitives for Stackless Python. We used to employ handoff until we found out that this caused performance problems. All the locking primitives now used by Eve Online and in Stacklesslib are 'greedy' and don't attempt fairness. This has resulted in much improvement in resource usage.

For this reason, I explicitly did not build any such mechanism into my RWLock implementation. Any thread coming in can claim the lock, provided the policy (writer priority policy) doesn't kick in. In those rare cases where a special locking policy such as FIFO fairness is _required_ it is always possible to construct such a thing in python using e.g. a queue of condition variables.

For information on this, please see the following resource: http://www.bluebytesoftware.com/blog/PermaLink,guid,e40c2675-43a3-410f-8f85-616ef7b031aa.aspx

[84401114-8e59-4056-83cb-632106c0b648]

I admit that I kind of like Java's approach to this. First off, they define an interface, ReadWriteLock: http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReadWriteLock.html There, they also discuss the different choices an implementation of the interface can make, regarding a) policy, b) reentrancy, c) upgrading or downgrading. A concrete implemention is then presented in the form of the ReentrantReadWriteLock, with documented behaviour for the above. The rest of threading is also, as previously pointed out, more or less a rip-off from Java.

Since there is no single "correct" choice for the above, and since the implementation restrictions are different between inter-process and inter-thread locks, it would make sense to adopt a similar model, where a RWLock() function is a factory function, taking an argument specify a desired class of locks.

The policies that have been seen in this thread are: a) greedy policy (no policy) b) writer preference c) 'Fair' (or in-order) preference. All have their benefits and disadvantages.

We have also seen "recursive" and "nonrecursive".

The restrictions appear more serious in the inter-process case since I don't know if it is possible to maintain a shared dynamic array of thread ids across processes.

[e26428b1-70cf-4e9f-ae3c-9ef0478633fb]

Multiprocessing: Because there is no way I know to share a list of owning thread ids, this version is more limited

Why do you need a *shared* list? I think it should be fine to use a per-process list of owning thread ids. So the current thread owns the lock if and only if it is in the current process's list of owners.

(On Unix you should probably clear the list when you fork by using multiprocessing.util.register_after_fork() in the initializer.)

[84401114-8e59-4056-83cb-632106c0b648]

Excellent point, I hadn't thought of that! Yes, it is is sufficient to test if _I_ am in the list. I'll make the necessary changes. That will make the thread/process implementation virtually identical.