In the tutorial, all solutions will be presented by students. Please be prepared for all questions as the exercise will focus on discussion, not on understanding the question and gathering the knowledge. Some challenging questions are usually a lot more difficult and require knowledge that was not presented in the lecture.

Lock-free

Implement double-address compare-and-swap with compare-and-swap.

Scalable Reader-Writer Locks

Fair reader-writer locks protect a critical section, such that multiple readers can enter the critical section concurrently, provided no writer is attempting to enter or holding the lock. Thereby at most one writer may be in the critical section at any point in time, provided no readers are in the critical section.

1. Reader-Writer Lock Implementation

   Implement a reader writer lock using the atomic read-modify-write instructions presented in the lecture. Make sure the lock is fair, that is, both readers and writers get the lock after a bounded time.

2. Fair Fast Scalable Reader-Writer Lock

   In their paper "A Fair Fast Scalable Reader-Writer Lock", Krieger et al. present a scalable reader-writer lock implementation based on the MCS lock presented in the lecture.

   1. Search for typos in the readerUnlock function and correct them. Justify why there is a bug. If you do not spot any errors, justify why the function is correct.
   2. Describe how the readerUnlock function works.
   3. Challenging Question: The reader-writer lock implementation is fair, though inherently unfair spin-lock implementations are used in the readerUnlock function. Why?

Material

• Orran Krieger, Michael Stumm, Ron Unrau, Jonathan Hanna: A Fair Fast Scalable Reader-Writer Lock, International Conference on Parallel Processing (ICPP), 1993
• Mellor-Crummey Scott: Algorithms for scalable synchronization on shared memory multiprocessors, ACM Transactions on Computer Systems, Volume 9, 1991