20_Readers_and_Writers

1 .Lecture 20 – Readers and Writers Describe the readers-writers problem , and the concept of a shared lock Give a real-world example where shared locks should be applied Develop pseudo-code for a shared lock implementation and argue how and why it works Differentiate between read-priority , write-priority , and fair-priority shared locks, and list the advantages and disadvantages/pitfalls of each Describe the Read-Copy-Update pattern, and how it differs from shared locks Give a real-world example where RCU should be applied Outline pseudo-code for implementing RCU for a given application Learning Goals © Paul Davies, C. Antonio Sanchez. Not to be copied, used, or revised without explicit written permission from the copyright owner.

2 .Mutual Exclusion Until now, we’ve been insistent on the following rules for mutual exclusion: If a shared variable is NEVER modified, no need for mutex If a shared variable is EVER modified, yes need for mutex readers need to acquire mutex before reading writers need to acquire mutex before writing Readers and Writers 2 How many readers can access the resource at a time? How many writers can access the resource at a time? 1 1

3 .Mutual Exclusion Imagine if Wikipedia worked this way… Readers and Writers 3

4 .Mutual Exclusion In cases where reading is much more frequent than writing, this can lead to inefficient use of the resource. Q1: Can any harm come from having multiple threads only reading a variable concurrently (i.e. no writers)? Q2: Can any harm come from having multiple threads only writing a variable concurrently (i.e. no readers)? Readers and Writers 4

5 .Mutual Exclusion Readers and Writers 5 If one process/thread is reading from a resource, then we must prevent any other process/thread from writing to it at the same time. If one process/thread is writing , we must prevent all other processes/threads ( both reading and writing ) from accessing the resource at the same time. However, if all the processes/threads are simply reading (i.e. they will not attempt to update or write to the resource during that access), then we can have an unlimited number to be simultaneously active without problems. Ordinary mutexes do not differentiate between reading and writing operations. This is a significant drawback , since in the field of concurrent programming, reading from a resource is performed, in general, far more frequently than writing to it.

6 .Example: Airline Reservation System Thousands of vacationers/agents checking prices simultaneously, hoping for that deal-of-a-lifetime price drop. Imagine if everyone had to wait their turn… An agent needing to change/update the information in the database, such as making a reservation, needs to wait for exclusive access. Create a solution that would allow unlimited numbers of reader processes/threads to be simultaneously active, but enforce full mutual exclusion when a writer is using the resource. Readers and Writers 6

7 .Readers-Writers Problem Readers and Writers 7 Readers/Writers Mutex w aitToRead() d oneReading() w aitToWrite() d oneWriting() Resource Reader Process or Thread Writer Process or Thread Set of Mutex Interface Functions for a Reader Set of Mutex Interface Functions for a Writer A new kind of mutex is required with separate Wait/Signal interfaces for Reader and Writer processes. When multiple process/thread share access, we say the mutex is locked in read or shared mode When a single process requires exclusive access, we say the mutex is locked in write or exclusive mode

8 .Shared Locks In C++14, the standard introduced shared_timed_mutex In C++17, the standard introduced shared_mutex Readers and Writers 8 http://en.cppreference.com/w/cpp/thread/shared_mutex

9 .Shared Locks std::shared_mutex : Readers and Writers 9 allows shared access via lock_shared() / unlock_shared() allows exclusive access via lock() / unlock() std::shared_timed_mutex : allows shared access via lock_shared() / unlock_shared() allows exclusive access via lock() / unlock() also has timed versions std::shared_lock<SharedMutexType> : similar to unique_lock , but locks the underlying mutex in shared mode #include <shared_mutex>

10 .Shared Locks Readers and Writers 10 std::shared_mutex mutex; // reader { std::shared_lock< decltype (mutex)> lock(mutex); // locked in "shared" mode (internally calls lock_shared() ) } // writer { std::unique_lock< decltype (mutex)> lock(mutex); // locked in "exclusive" mode (internally calls lock() ) }

11 .Readers and Writers 11 D D D Resource Shared Mutex ‘S’ Protecting Resource Resource A A Reader Performs S.lock_shared() to Gain Entry Reading A B B B C C C Writer Process Executes S.lock() to Gain Entry Blocked by Reader Reader Process Performs S.unlock_shared() to Leave No Writers Present: Reader Permitted to Enter Writing Writer gains Entry E E E Writer Blocked by other Writer Reader Blocked by Writer Writer Process Performs S.unlock() to Leave Writer gains Entry because no more Readers accessing resource Resource is FREE to Both Readers and Writers Resource is BUSY to Reader and Writer Threads Resource is BUSY to Writer Threads but Open to Reader Threads

12 .Readers and Writers 12 Exercise: Shared Locks How would you implement it? How many synchronization primitives do you need? What kind of primitives should they be? To gain access in shared mode , must wait until no other thread holds exclusive lock To gain access in exclusive mode , must wait until no other thread holds exclusive or shared lock

13 .Implementation Ingredients: One “global” binary semaphore for exclusive access: resource One “local” mutex for read counts: mutex A counter to store the number of readers: readers Methods: Readers and Writers 13 Write: resource.wait(); // do write resource.notify(); Read: mutex.lock(); ++readers; if (readers == 1) { resource.wait(); } mutex.unlock(); // do read mutex.lock(); --readers; if (readers == 0) { resource.notify(); } mutex.unlock();

14 .Implementation First reader will wait until resource is available and acquire it Future readers will go through without waiting Next writer will wait until final reader notifies resource Readers and Writers 14 Write: resource.wait(); // do write resource.notify(); Read: mutex.lock(); ++readers; if (readers == 1) { resource.wait(); } mutex.unlock(); // do read mutex.lock(); --readers; if (readers == 0) { resource.notify(); } mutex.unlock(); 1, 2 3

15 .Shared Locks: Priority Given that a resource is already locked in shared mode, should a new “reader” that comes along automatically be given the rights to lock in shared mode? Readers and Writers 15 This is known as a read-priority or read-preferring lock Imagine readers constantly coming along, then trying to lock in write mode. An exclusive lock can only be acquired once all readers have left. A constant stream of readers may cause write-starvation . This is known as a write-priority or write-preferring lock A constant stream of writers may cause read-starvation . To counter this, we can make a writer to block out any new incoming readers.

16 .Exercise: Write-Preferring Shared Lock When a writer (exclusive access) attempts to acquire a lock, it waits until all existing readers complete and release the resource If there is any writer, it takes precedence over all future readers (shared access) Readers and Writers 16 How would you implement it? How many synchronization primitives do you need? What kind of primitives should they be?

17 .Exercise: Write-Preferring Shared Lock Approach: track # of readers accessing, readers # writers waiting, writers Read: Wait until no writers waiting increment # readers, if # readers == 1, acquire resource … read … decrement # readers if # readers == 0, release resource Readers and Writers 17 Write: increment # writers waiting acquire resource decrement # writers waiting … write … release resource cv wmutex sem rmutex rmutex sem cv wmutex wmutex sem sem

18 .Implementation Readers and Writers 18 Write: wmutex.lock(); ++writers; wmutex.unlock(); sem.wait(); // do write sem.notify(); wmutex.lock(); --writers; wmutex.unlock(); cv.notify(); Read: wmutex.lock(); cv.wait(wmutex, writers == 0); rmutex.lock(); ++readers; if (readers == 1) { sem.wait(); } rmutex.unlock(); wmutex.unlock(); // do read rmutex.lock(); --readers; if (readers == 0) { sem.notify(); } rmutex.unlock(); writers > 0 Future writers blocked at wmutex Guaranteed not to block Release resource wake readers

19 .Fair Priority Readers and Writers 19 Both read-preferred and write-preferred locks can lead to starvation . A fair priority lock alternates between letting readers through and writers through. If we could guarantee that when waiting on semaphores/CVs that threads are awoken in the same order that they call the wait() function, then we can use this to let readers/writers pass in order of arrival. However, in general, we cannot make this assumption. This leaves two options: Manually maintain and manage a FIFO queue of waiting threads Find some other way…

20 .Fair Priority: Batches A common solution is to alternate: Let one writer through Let a batch of readers through If a reader arrives with no writers present, it adds one to the current batch of readers executing ( current_batch++ ). If a reader arrives with one or more writers present (waiting or executing), it adds one to the next batch of readers to execute ( next_batch++ ). After the current batch of readers finishes executing ( current_batch == 0 ), it signals the next writer to go through After a writer finishes executing, it signals the next batch of readers to go through ( current_batch = next_batch , next_batch = 0 ) Readers and Writers 20 current_batch next_batch write completion triggers swap

21 .Fair Priority: Batches Is this fair priority approach safe from starvation? Readers and Writers 21 NO! “Next writer” and “next reader” may not mean the next one that arrived, only next one to wake up . It is still possible that a reader or writer continuously gets left behind. If all threads have the same priority , the chances of this are exceedingly rare (though may still be possible depending on the OS). If one thread has a lower priority, however, it can be quite likely. The fix? Manually track order of arrival of threads in a FIFO queue.

22 .Readers-Writers Mutex The implementation in C++14/17 has fair priority , but only works between threads of a single process. For other priorities, see cpen333::thread::shared_mutex_exclusive (exclusive-access preferred) cpen333::thread::shared_mutex_shared (shared-access preferred) cpen333::thread::shared_mutex_fair (fair priority) For inter-process use, see cpen333::process::shared_mutex_exclusive (exclusive-access preferred) cpen333::process::shared_mutex_shared (shared-access preferred) cpen333::process::shared_mutex_fair (fair priority) Readers and Writers 22

23 .Shared Locks Summary Shared locks allow multiple “ readers ” simultaneous access to a resource. To gain exclusive access, we must wait until there are no other current accesses. When both potential readers and writers are waiting for access, we can prefer to give priority to one class, or try to balance between the two: read-preferred locks give priority to waiting readers write-preferred locks give priority to waiting writers fair locks try to balance the two If a resource is locked with exclusive (write) access, this blocks out all others . Readers and Writers 23

24 .Shared Locks are great, but… Imagine if Wikipedia worked this way… Readers and Writers 24

25 .Ready-Copy-Update Rather than block out all readers while we are modifying a resource, we can instead make a copy of the resource, modify the copy , then atomically swap the old resource with the new. This pattern is called Read-Copy-Update (RCU) . This allows readers to still access the resource while the modification is taking place. Requirements: Pointer to resource for existing readers to keep access to original unmodified copy Mutex for only allowing one writer at a time Method of atomically switching pointer to updated resource (or mutex to enforce mutual exclusion) Readers and Writers 25

26 .Read-Copy-Update Readers and Writers 26 Resource R1 ptr ptr R2 ptr W1 Copy nptr R3 ptr modify R4 nptr

27 .Read-Copy-Update Readers and Writers 27 static std::mutex rmutex; static std::mutex wmutex; Resource* resource_ptr = new Resource(); // safely grab pointer to current resource Resource* local_resource_ptr = nullptr ; { std::lock_guard< decltype (rmutex)> lock(rmutex); local_resource_ptr = resource_ptr; } // do what you want with local_resource_ptr Read: // lock out other writers { std::lock_guard< decltype (wmutex)> wlock(wmutex); // copy resource Resource* copy_ptr = new Resource(); *copy_ptr = *resource_ptr; // modify copy ... // safely replace original { std::lock_guard< decltype (rmutex)> rlock(rmutex); resource_ptr = copy_ptr; } } Write: Common:

28 .Read-Copy-Update Ideal when writes are rare , want to ensure read access even when writing. If we can guarantee atomic setting of pointers , read access requires no lock at all . Read performance increased compared to shared locks, but at expense of space . Memory-management issues: can only free old copies of resource once all readers accessing it have completed. Can be alleviated using std::shared_ptr . Still typically only allows one writer at a time . Possible to allow multiple writers, but then need method of merging results and dealing with conflicts, typically requires user intervention (e.g. Git, Wikipedia). Readers and Writers 28

29 .Read-Copy-Update Readers and Writers 29 http://www.rdrop.com/users/paulmck/RCU/linuxusage.html Usage in the Linux Kernel: