-
-
Save tylerneylon/a7ff6017b7a1f9a506cf75aa23eacfd6 to your computer and use it in GitHub Desktop.
# -*- coding: utf-8 -*- | |
""" rwlock.py | |
A class to implement read-write locks on top of the standard threading | |
library. | |
This is implemented with two mutexes (threading.Lock instances) as per this | |
wikipedia pseudocode: | |
https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock#Using_two_mutexes | |
Code written by Tyler Neylon at Unbox Research. | |
This file is public domain. | |
""" | |
# _______________________________________________________________________ | |
# Imports | |
from contextlib import contextmanager | |
from threading import Lock | |
# _______________________________________________________________________ | |
# Class | |
class RWLock(object): | |
""" RWLock class; this is meant to allow an object to be read from by | |
multiple threads, but only written to by a single thread at a time. See: | |
https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock | |
Usage: | |
from rwlock import RWLock | |
my_obj_rwlock = RWLock() | |
# When reading from my_obj: | |
with my_obj_rwlock.r_locked(): | |
do_read_only_things_with(my_obj) | |
# When writing to my_obj: | |
with my_obj_rwlock.w_locked(): | |
mutate(my_obj) | |
""" | |
def __init__(self): | |
self.w_lock = Lock() | |
self.num_r_lock = Lock() | |
self.num_r = 0 | |
# ___________________________________________________________________ | |
# Reading methods. | |
def r_acquire(self): | |
self.num_r_lock.acquire() | |
self.num_r += 1 | |
if self.num_r == 1: | |
self.w_lock.acquire() | |
self.num_r_lock.release() | |
def r_release(self): | |
assert self.num_r > 0 | |
self.num_r_lock.acquire() | |
self.num_r -= 1 | |
if self.num_r == 0: | |
self.w_lock.release() | |
self.num_r_lock.release() | |
@contextmanager | |
def r_locked(self): | |
""" This method is designed to be used via the `with` statement. """ | |
try: | |
self.r_acquire() | |
yield | |
finally: | |
self.r_release() | |
# ___________________________________________________________________ | |
# Writing methods. | |
def w_acquire(self): | |
self.w_lock.acquire() | |
def w_release(self): | |
self.w_lock.release() | |
@contextmanager | |
def w_locked(self): | |
""" This method is designed to be used via the `with` statement. """ | |
try: | |
self.w_acquire() | |
yield | |
finally: | |
self.w_release() |
Just another note: In general, it would be nice if a low-level Lock
object had the ability to shout, "Hey! I've been waiting 300 years!" if it was waiting a while. I'd use that while building a system to help gain visibility into any bad behavior, which could help find deadlock cases, or in general to make good decisions like that between a queued and queueless lock.
A forked version with support for with
blocks https://gist.github.com/Eboubaker/6a0b807788088a764b2a4c156fda0e4b
Hi @Eboubaker ! As a friendly fyi, this gist does include support for with
blocks (this is done via contextmanager
).
Example usage:
from rwlock import RWLock
rwlock = RWLock() # This is a lock for my_obj.
# When reading from my_obj:
with rwlock.r_locked():
do_read_only_things_with(my_obj)
# When writing to my_obj:
with rwlock.w_locked():
mutate(my_obj)
def update_things():
with rwlock.w_locked():
# update state
with rwlock.r_locked():
# read state
if some_confition:
update_things()
this example will hang in your implementation if the same thread was doing the work,
you have to move lock from update_things
, but this method is being called from multiple places, and you have to keep adding with rwlock.w_locked():
before each call to the method, code will be less readable
Thanks for explaining. You've designed your lock to be reentrant, which is cool. If I have time I may add this feature here, but for now it is not a reentrant lock.
@tylerneylon, I think your implementation is based on the assumption that a mutex acquired by one thread can be released by another. Please look at the first implementation in the below link, it is similar to yours: https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock
I believe my implementation does not have this problem I have a list of thread ids that are reading, and my release method will not do anything if the current thread did not call acquire_read before
@Nibbetts So if I understand correctly, as long as any readers are reading, more can be added on even if there is a writer waiting. Perhaps you could avoid this potentially infinite wait by having w_acquire acquire num_r_lock, and w_release release it?
in my implementation i used a condition lock for the read_ready_state
any writer or reader will need to acquire the state before they can do read or write requests, so there will be a queue which is managed by the languge and will give the lock by the order of callers. so when the writer requests the state other read requests will have to be after when the writer has released the state
use time.sleep(1) to give them a chance to gain the lock
import threading
import time
# from rwlock import RWLock
marker = RWLock()
WEEKDAYS = ['Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday']
today = 0
def calendar_reader(id_number):
global today
name = 'Reader-' + str(id_number)
while today < len(WEEKDAYS)-1:
# print(today)
with marker.r_locked():
print(name, 'sees that today is', WEEKDAYS[today])
time.sleep(1)
def calendar_writer(id_number):
global today
name = 'Writer-' + str(id_number)
while today < len(WEEKDAYS)-1:
with marker.w_locked():
today = (today + 1) % 7
print(name, 'updated date to ', WEEKDAYS[today])
time.sleep(1)
if __name__ == '__main__':
for i in range(10):
threading.Thread(target=calendar_reader, args=(i,)).start()
for i in range(2):
threading.Thread(target=calendar_writer, args=(i,)).start()
result:
Reader-0 sees that today is Sunday
Reader-1 sees that today is Sunday
Reader-2 sees that today is Sunday
Reader-3 sees that today is Sunday
Reader-4 sees that today is Sunday
Reader-5 sees that today is Sunday
Reader-6 sees that today is Sunday
Reader-7 sees that today is Sunday
Reader-8 sees that today is Sunday
Reader-9 sees that today is Sunday
Writer-0 updated date to Monday
Writer-1 updated date to Tuesday
Reader-4 sees that today is Tuesday
Reader-6 sees that today is Tuesday
Reader-0 sees that today is Tuesday
Reader-7 sees that today is Tuesday
Reader-3 sees that today is Tuesday
Reader-5 sees that today is Tuesday
Reader-2 sees that today is Tuesday
Reader-8 sees that today is Tuesday
Reader-1 sees that today is Tuesday
Reader-9 sees that today is Tuesday
Writer-0 updated date to Wednesday
Writer-1 updated date to Thursday
Reader-9 sees that today is Thursday
Reader-4 sees that today is Thursday
Reader-2 sees that today is Thursday
Reader-7 sees that today is Thursday
Reader-1 sees that today is Thursday
Reader-0 sees that today is Thursday
Reader-5 sees that today is Thursday
Reader-6 sees that today is Thursday
Reader-3 sees that today is Thursday
Reader-8 sees that today is Thursday
Writer-1 updated date to Friday
Writer-0 updated date to Saturday
The advantage of a queueless lock is that readers don't have to wait for each other. The advantage of a queued lock is that writers won't be starved.
@tylerneylon, If you put queue on r_acquire
only (not the whole operation), readers will not block each other. This is called "fair" order.
Here is example with more detailed explanation https://en.wikipedia.org/wiki/Readers%e2%80%93writers_problem#Third_readers%E2%80%93writers_problem.
Hi @Nibbetts , thanks for the link to the alternative approach, which looks useful! I'll call that other approach a
queued
lock and this one (the gist above)queueless
. (I just made up those names, but they make sense to me.)When do we want a write request to take precedence over later read requests? (ie use a
queued
lock vs aqueueless
lock?)The advantage of a
queueless
lock is that readers don't have to wait for each other. The advantage of aqueued
lock is that writers won't be starved.Consider the situation where we have a number of incoming readers, and each reader and each writer holds the lock for 1 full second (a long time for a cpu). Suppose we receive requests very quickly in this order, R for read, W for write:
R R R W R R R
, and then nothing for a while.queueless
lock, then all 6 reads happen in about 1 second, since they are simultaneous; then the write occurs. The average read wait is 0 seconds, and the total time is 2 seconds.queued
lock, then the first 3 reads happen together in a concurrent second, then the write occurs, then the next 3 reads. The average read wait is 1 second (avg of 0,0,0,2,2,2), and the total time is 3 seconds.If we wanted, we could look at specific R/W orderings like
R W*n R*m
for large values ofn
andm
and produce more pronounced differences.All of the above is to say that each lock type may be better to use depending on your use case. My take on how to choose between them is:
queued
lock; otherwise goqueueless
.