Designing write preferring Readers-Writer lock

In the previous article, we looked at how readers-writer lock helps multiple readers access information simultaneously but ensure only one writer can make changes at a time. We also looked at an example that uses readers-writer lock implementation provided by Golang standard library.

How about we implement our own version of readers-writer lock? Before we start with the implementation, let’s understand the difference between Read preferring and write preferring and how these two terms are relevant in this context.

Priority of Readers-Writer Lock

There are different versions of the readers-writer lock, each version providing different priority to either readers or writers. Let’s look at them in detail:

Read Preferring Lock: The read preferring lock allows for maximum concurrency. In this version, priority is given to reader threads. The writer threads will not be able to acquire the lock even if there is one reader thread present. Usually, readers-writer locks are used in read heavy scenario, so there is a high chance of at least one or more reader thread always acquiring the lock. This results in write starvation.

Write Preferring Lock: The write preferring lock gives priority to the writer threads. If a writer thread is waiting for the lock, it guarantees that the lock will be given to writer thread once all the existing reader thread releases the lock. The new readers are given the lock only if there are no writer waiting for the lock. This prevents the write starvation however this limits the concurrency.

Fair: Attempts to balance between readers and writers, ensuring that neither readers nor writers starve. This is typically implemented using queues.

In this article, we will implement a Write preferring Readers writer lock using mutex and condition variable.

Implementing the Readers-Writer lock

Step 1: Defining the Structure of the Custom Readers-writer lock

To design a write preferred lock, we need following properties:

readCounter: Initially set to 0, this indicates the number of goroutines that has currently acquired the read lock.

writeCounter: Initially set to 0, this indicates the number of goroutines waiting to acquire the write lock.

writeActive: initially set to false, this tells us if a resource is currently being updated by writer goroutines.

cond: This defines a condition Variable on top of standard mutex lock. This allows us to wait for various type of conditions, suspend the execution, and signaling between the threads.

Now that we know the properties needed, let’s define the ReadersWriter struct.

type ReadersWriter struct {
    readCounter int
    writeCounter int
    writeActive bool
    cond *sync.Cond
}

Step2: Creation

This creates the ReadersWriter with condition variable initialized. The initial value of readCounter and writeCounter is zero, whereas the writeActive flag is set to false.

func NewReaderWriter() *ReaderWriter {
	return &ReaderWriter{
		readCounter:  0,
		writeCounter: 0,
		writeActive:  false,
		cond:         sync.NewCond(&sync.Mutex{}),
	}
}

Step3: Implementing Read Lock (RLock)

If there are no writer goroutines waiting in the queue or any active write lock is acquired, the call to RLock will be successful. Otherwise, the goroutine calling the RLock would be suspended. Once the last writer goroutine releases the write lock, the suspended reader gorutine would wake up and acquire the lock.

func (rw *ReaderWriter) RLock() {
	rw.cond.L.Lock()
	for rw.writeCounter > 0 || rw.writeActive {
		rw.cond.Wait()
	}
	rw.readCounter++
	rw.cond.L.Unlock()
}

Step 4: Implementing Write Lock (Lock)

If the lock is acquired by either reader or writer goroutines, the writer goroutine calling the Lock would be suspended. Once there are no active readers or writer threads in the system acquiring the lock, the suspended Goroutine would wake up and acquire the write lock. The writeActive flag becomes true when a write lock is acquired.

func (rw *ReaderWriter) Lock() {
	rw.cond.L.Lock()
	rw.writeCounter++
	for rw.readCounter > 0 || rw.writeActive {
		rw.cond.Wait()
	}
	rw.writeCounter--
	rw.writeActive = true
	rw.cond.L.Unlock()
}

Step 4: Implementing Read Unlock (RUnlock)

This decrements the readCounter. When the value of readCounter becomes zero, it means the there are no active readers in the system and signal is broadcasted to all the waiting goroutines. This gives an opportunity to suspended writer gorutines to wake up so that one of them can get hold of the write lock.

func (rw *ReaderWriter) RUnlock() {
	rw.cond.L.Lock()
	rw.readCounter--
	for rw.readCounter == 0 {
		rw.cond.Broadcast()
	}
	rw.cond.L.Unlock()
}

Step 5: Implementing Write Unlock (Unlock)

Unlocking is straightforward. It simply involves setting the writeActive flag to false and signaling all suspended goroutines. This action allows any waiting goroutine for a write lock to obtain it. Otherwise, reader goroutines can acquire the read lock.

func (rw *ReaderWriter) Unlock() {
	rw.cond.L.Lock()
	rw.writeActive = false
	rw.cond.Broadcast()
	rw.cond.L.Unlock()
}

That’s it. Our implementation of readers-writer lock is ready. One can use this as a synchronization mechanism in read heavy scenarios. In the example featured in the previous article, you can try using this custom implementation instead of using the one provided in the sync package.

We explored the concept of readers-writer locks and the differences between read-preferring and write-preferring locks. While read-preferring locks maximize concurrency by prioritizing reader threads, they can lead to write starvation. On the other hand, write-preferring locks prioritize writer threads, ensuring they get access to the resource without waiting for too long.