After a weeks-long hiatus around the end of last year, I’m back to the regular once-a-week schedule. The next stop in the “classical problems” chapter of “The Little Book of Semaphores” is called the “readers-writers” problem.
The book describes it thusly: “any situation where a data structure, database, or file system is read and modified by concurrent threads. While the data structure is being written or modified it is often necessary to bar other threads from reading, in order to prevent a reader from interrupting a modification in progress and reading inconsistent or invalid data.”
In other words, any number of readers can read the shared resource and
only one writer can write to it at a time. The sync package provides
exactly this functionality thru the RWMutex type: any number¹ of
readers can hold a read-only lock and exactly one writer can hold a
lock.
The implementation is such that if a number of readers are holding the lock, and a writer tries to acquire the lock, it will wait until all the readers release it and it prevents more readers from acquiring it in the meantime. This solves the exact problem introduced in the section called “Starvation”: a writer can try to acquire the lock and fails to do so because readers keep coming in and out without ever reaching the situation where all of them have released it at the same time.
The book proposes another variation where the writers have priority over the readers, making it possible for the readers to starve waiting for the lock and offers some reasoning as to why this might be desirable. This is the behavior implement in the standard library.
What sync.RWMutex does is it allows for multiple readers to acquire
the read lock (RWMutex.RLock()), but once there’s a writer trying to
acquire the write lock (RWMutex.Lock()), then no reader will get the
lock until the writer acquires it and releases it again. If writers
queue up trying to acquire the lock, they will be prioritized over the
waiting readers.
In previous posts I’ve shown that all the patterns discussed so far can be implemented using channels, and this case is no exception. You need two queues, one for the readers and one for the writers. You dequeue the writers first, and only dequeue readers if the writers queue is empty. A very naïve implementation of this is to have a helper goroutine that keeps track of the lock requests, and satisfies first those coming from writers, like this:
type RWMutex struct {
qr chan struct{} // queue of readers
qw chan struct{} // queue of writers
ra chan struct{} // reader acquire channel
rr chan struct{} // reader release channel
wa chan struct{} // writer acquire channel
wr chan struct{} // writer release channel
}
func NewRWMutex() *RWMutex {
m := &RWMutex{
qr: make(chan struct{}),
qw: make(chan struct{}),
ra: make(chan struct{}),
rr: make(chan struct{}),
wa: make(chan struct{}),
wr: make(chan struct{}),
}
go func() {
n := 0
nw := 0
for {
switch {
case n < 0:
// a writer has the lock
<-m.wr
n++
case nw > 0:
// there might be readers holding the lock
for n > 0 {
<-m.rr
n--
}
// there's a writer waiting
m.wa <- struct{}{}
n--
nw--
default:
// no writers are waiting
select {
case <-m.qw:
nw++
case <-m.qr:
m.ra <- struct{}{} // bug here
n++
case <-m.rr:
n--
}
}
}
}()
return m
}This implementation is not exactly right, since select services
channels randomly, so the fact that a writer is trying to acquire the
lock won’t prevent a reader from doing so (“bug here”), but it serves to
illustrate the point: this implementation is simple and the same
time it’s horrible (six channels?).
Why six channels? Or better yet, why three channels for readers and three channels for writers?
- It must be possible for a writer to say “I want the lock” (one channel)
- It must be possible to tell a writer that it’s got the lock (another channel)
- It must be possible for a writer to return the lock (another channel)
If you look closely, you’ll see that you can do with only two channels for writers, but it’s still necessary to have three for readers. With some effort, I’m sure someone can provide a better and cleaner implementation, but it’s worth asking: how did we get into this mess? The problem statement is very generic: “any situation where a data structure, database, or file system is read and modified by concurrent threads” It’s possible that with a more specific problem statement, a better more specific solution can be produced.
What’s the lesson here? The standard library offers some synchronization
primitives because they are needed, but don’t just assume that because
they exist, they are always the correct solution. On the flip side,
don’t just assume that because Go has channels and goroutines, they are
the best solution in every situation (examine net/http’s use of
sync.RWMutex for an example).
Next week: dining philosophers!
Footnotes:
¹ Not exactly true. There is a limit to the number of readers that can hold the read lock, but it’s high enough that if you hit it, you have a whole different class of problems.