This episode dives deep into locks. How do they work? And then explains how you can use this to implement a reader-writer lock.
A basic lock can be created with the “set and test” instruction. This works by reading a current memory value, setting it to one, and returning the original value. You can build a simple lock by repeatedly calling this method until it returns something other than one. You probably don’t want to go into a busy loop like this just calling the same method over and over again. The idea is to call this method though until it returns something other than one.
Then with two such locks and an integer count variable, this episode explains how you can build a reader-writer lock. Listen to the full episode or you can also read the full transcript below.
Transcript
So far, when describing multithreading, I’ve mentioned locks and also that there’s some builtin ability that makes all this possible. What is that exactly? I don’t want you thinking that there’s some magic involved. We’re going to dive deep and explore how locks really work and then what you can do with them.
Imagine for a moment an ancient meeting between several local tribe leaders. They kept interrupting each other and couldn’t get anything done. One day, a powerful leader had enough and brought his wooden club to the meeting. Not to hit other leaders. That would just start a war. But to bang the club loudly on the stone floor before speaking. This got the attention of the other leaders long enough for him to speak.
In the next meeting other leaders tried to bring their clubs too but the one leader was smart enough to recognize the threat and made a deal that only one club would be allowed in the meeting. Anybody who wanted to speak would be allowed to bang the club.
Eventually, the whole banging the wooden club on the floor thing was replaced with just the need to hold some symbol and whoever currently held the symbol would be allowed to speak.
This caveman type story can actually be used by modern processors. Some processors might have developed more sophisticated methods. I haven’t done a lot of research into all the ways locks can be implemented so maybe there are other ways. I’ll just explain this method so at least you understand how it all could work.
This system relies on possession of a physical object. That’s a problem for threads running on processor cores. What can a thread possibly hold onto? There’s really only one thing and that’s a specific value stored in some memory location.
All it requires is the ability to execute a single instruction that can’t be interrupted by any other thread or processor. In the case of multiple processors, the system will likely need to make use of a single memory manager common to the whole computer.
This single instruction needs to be very simple. It’s called a set and test instruction. The name’s a bit misleading. To me, it should have been called the set and return original value instruction. But you can probably see why set and test is a shorter and more catchy name. Here’s what it does though. The instruction goes to a specific memory address, reads the value currently stored there, and then sets the value to one. It then returns the original value. That’s it. Just go get the current value and make the value one.
The question then is what good is this? Well, it turns out that this simple instruction treats anything other than a one as a special value. Let’s start out with the value set to zero. That’ll be the initial state when no thread has a lock.
Now, let’s take two threads as an example and these two threads both want this lock. It’s a race and they each execute the set and test instruction at the same time. Only one of them will be allowed access to the memory location though. The other will get a busy response and will have to wait.
This is sort of like the old telephone systems that had busy signals. I remember when call waiting was an extra add-on that you could pay extra for. Now days, everybody has call waiting and voice mail so you rarely ever hear the busy tone.
Anyway, back to processors. The first thread will get back a zero and will set the value to hold a one. The second thread won’t wait for long at all, just a few extra clock cycles. But the second thread will find the value one at the memory and will change the value to one. this change really has no effect since the value was already one.
Each thread is looking for that special value zero though. That’s the wooden club. When a thread gets back a one, it knows that it was unsuccessful and can try again. It may decide to keep trying furiously over and over. Or it may decide to go do something useful instead and check back later. Either way, getting back a one value means that the path is blocked.
The thread that did get back the zero can proceed to do its work. It’s happy. And when it’s done, all it has to do is write the value zero back to that memory location. This is like putting the wooden club back in place so that some other thread can pick it up.
Okay, that’s a simple example of how a lock might be implemented on your system. Instead of a set and test instruction, your computer might use a compare and swap instruction. The same basic concept applies. It all comes down to who gets the wooden club.
After this message from our sponsor, I’ll explain how you can implement a reader-writer lock.
( Message from Sponsor )
There’s actually different kinds of reader-writer locks. Episode 96 described a scenario where you might want to use a reader-writer lock. It comes down to this. Sometimes it’s okay for multiple threads to access the same resources as long as they’re not changing anything. In other words, as long as they’re only reading. But the moment a writer comes along, things change. You definitely don’t want multiple writers interfering with each other. So that’s the first thing, a writer should have sole access to a resource while it’s making its changes. this includes other readers and writers. A reader though can share the resource with other readers.
Implementing this allows you to write your application with fewer blocking operations among readers. The only time you need to block threads is when you need to make a change. Now if you make changes almost all the time and rarely need to just read something, then a reader-writer lock isn’t going to help you. A reader-writer lock only helps when you have many more readers than writers.
But this brings up an interesting question and gets to the different types of reader-writer locks that I mentioned. What do you do with existing readers when a writer comes along? If we compare this with a store where the customers are the readers and a construction crew is a writer, then it’s obvious that you should wait until closing time and all the customers leave the store before you start remodeling.
The problem though is that your application doesn’t always have nice operating hours like this. Maybe you do. But probably not. If you prefer readers, then you should block all writing as long as there are readers present. This can lead to writer starvation though because you can get a series of never-ending readers that keep coming and going. As long as there’s at least one reader, then the writer is effectively blocked.
If you prefer writers, then you can’t just kick the current readers out. But you can stop other readers from entering until the writer gets a chance. Actually, you can sometimes terminate a thread, hopefully in a nice way, but that’s a bit too complicated to explain in a podcast. If I figure out a good way to explain it, then I’ll make this a future topic.
Now that you know a little about why a reader-writer lock is important, how can you use the simple locking technique to build one?
There are again several ways to do this. Here’s just one way. It requires two locks and an integer count. Let’s call the first lock r for reader and the second lock w for writer. You know, for once, I’m actually glad for that silent w at the beginning of write.
Alright let’s start out with no readers and no writers. The locks are both available and the count of readers is at zero.
Whenever a reader comes along, the first thing it does is lock r. This is important because it’s going to do other things and needs to make sure it has exclusive access. The r lock should normally only be held for a short period of time so if a reader can’t get it right away, it shouldn’t have to wait for long. The exception to this is when a writer arrives which I’ll describe soon.
Once the reader gets the r lock, it then increments the count of readers. If the count of readers is one after incrementing, then that means this is the first reader. And the first reader then locks the w lock. The reader can then release the r lock. Other readers don’t need to lock the w lock. Any other readers just increment the reader count so we have an accurate count of how many readers are currently using the resource. When that first reader tries to lock the w lock, it’s possible that this could block for some time if there’s already a writer present. This can block other readers too because that first reader thread will also keep hold of the r lock until it can finally get the w lock. I’ll explain why the first reader needs the w lock in just a moment.
What happens when a reader is done? Well, it first gets the r lock. This is important whether the reader is just arriving or leaving. Once it has the r lock, it decrements the count of readers. If after decrementing, the count of readers is zero, then that means this is the last reader and that the w lock can be released. Then the reader just releases the r lock on its way out. The w lock was first obtained by the first reader and gets released by the last reader. This makes sure that the w lock is held the entire time that any reader is present.
Okay, now for a writer. The writers are simple. They don’t need a count because even a single writer is enough to block all other threads. That’s why they don’t need two locks. The writers only care about the w lock. Whenever a writer wants access, all it has to do is lock the w lock. And when it’s done, it releases the w lock. The w lock will be available anytime there are no readers and no other writer. And also locking the w lock will stop any new readers from entering because the first reader will also try to get the w lock.
That’s it really. Your reader-writer lock just needs a couple locks and a count. You can get more fancy if you need to and this is just a basic implementation.