What Is Mutex?
I don’t know if that is just me, but for some reason, Wikipedia articles are only good when you already know the subject. If a few years ago I would open the Wikipedia article about the mutex to learn about it, I’d likely have about the same level of understanding plus the feeling that it’s all very complex and maybe I should be doing something else.
A formal definition is not a good way to learn a new concept. It’s much better to have an illustration even though it would inevitably be somehow inaccurate. But not every illustration is good.
Mutex
Take mutex, for example. What is a good way to illustrate the concept of mutex? Well, it’s also called a lock, so: a bike lock.
Is it a good illustration? Let’s read the Wikipedia problem definition and see if a picture of a lock would help us to understand what’s going on:
The problem which mutual exclusion addresses is a problem of resource sharing: how can a software system control multiple processes’ access to a shared resource, when each process needs exclusive control of that resource while doing its work? The mutual-exclusion solution to this makes the shared resource available only while the process is in a specific code segment called the critical section. It controls access to the shared resource by controlling each mutual execution of that part of its program where the resource would be used.
Ok, there is something about the access and lock helps to restrict the access, but it was about a shared resource. A bike lock is used to secure your bike, and most definitely, you can’t use a lock to get exclusive control of that resource. Also, what was that about the critical section?
There is another thing in the real world that describes mutex much better: a restroom in the cafe.
Let’s take a look at the Wikipedia paragraph one more time:
The problem which mutual exclusion addresses is a problem of resource sharing: how can a software system control multiple processes’ access to a shared resource, when each process needs exclusive control of that resource while doing its work? The mutual-exclusion solution to this makes the shared resource available only while the process is in a specific code segment called the critical section. It controls access to the shared resource by controlling each mutual execution of that part of its program where the resource would be used.
It makes a bit more sense now, isn’t it? (except for the last sentence) The problem: we want only one process (a person) to be in the critical section (a restroom) while using the shared resource (a toilet). A mutex is a way to solve this problem — we have a room with only one way in, and this way in has a lock. If some process wants to use the shared resource, but the critical section is occupied, this process would have to wait, possibly among other processes that also need to use that shared resource.
So a mutex is a lock, but it’s not a padlock. It’s a lock on a door to a room with only one entrance. Note that “only one entrance” is also important — without it, the problem won’t be solved.
So, a mutex is a restroom, right? Not quite. There are variations.
Recursive/reentrant mutex
One of the types of mutexes is recursive/reentrant mutex*. It is similar to a regular mutex but has an extra feature. Let’s try to learn what it is from Wikipedia:
In computer science, the reentrant mutex (recursive mutex, recursive lock) is a particular type of mutual exclusion (mutex) device that may be locked multiple times by the same process/thread, without causing a deadlock.
“…may be locked multiple times” — so reentrant mutex is reusable, and a regular mutex is not. If the thread used a regular mutex once — it should never touch this mutex again. Right? No, and the article clarifies that in the next paragraph:
While any attempt to perform the “lock” operation on an ordinary mutex (lock) would either fail or block when the mutex is already locked, on a recursive mutex this operation will succeed if and only if the locking thread is the one that already holds the lock
Can we use our restroom metaphor to see what it is about “perform the lock when already locked?”
Imagine the restroom door is a door opened by a badge. What would happen if someone would forget the badge inside and leave the restroom? A deadlock. The door is locked, and the badge is required to open it. But the badge is inside, so to get it, you should unlock the door first (and there is no other badge to use instead because that would defeat the whole purpose of mutex).
Ok, and how reentrant lock solves this problem? It’s possible to stretch the example and say, “the door uses face recognition, and if it’s the last person that used the restroom, the door would be unlocked,” but that would be ridiculous. Also, “forgot to unlock the mutex” (that’s equivalent of forgetting the badge inside) is not the problem reentrant lock solves.
There is a better example: a fitting room.
You are in a fitting room, and the M-size jacket turned out to be more like XL. You leave some of your things in the room, go fetch the smaller jacket, and then go back to the same fitting room you were using. While you are gone nobody would take the room, even though you are not there.
Here, a process is still a person, the critical section is a fitting room, and a shared resource is a place where you can change clothes. The mutex is your things in the room (also the room itself, and the convention that you can’t use the room if someone’s things are inside). It’s a reentrant mutex, so you are free to leave the critical section at any time and then return to it later.
Both examples are about private rooms, but what if processes in our program need exclusive control just some of the time?
Readers–writer lock
There are different situations where shared resource is something that multiple processes could use at once. And for this use case, there is another type of mutex called a readers-writer lock. Here is what Wikipedia says about it:
In computer science, a readers–writer (single-writer lock,[1] a multi-reader lock,[2] a push lock,[3] or an MRSW lock) is a synchronization primitive that solves one of the readers–writers problems. An RW lock allows concurrent access for read-only operations, while write operations require exclusive access. This means that multiple threads can read the data in parallel but an exclusive lock is needed for writing or modifying data. When a writer is writing the data, all other writers or readers will be blocked until the writer is finished writing
Previous examples don’t have these different reader and writer roles, so let’s use a different one: a display with the cafe menu.
We definitely don’t want people to read the menu one at a time, so it’s placed on a big display. Come and read at any time. Almost, the only exception is when the display is being updated. “Santa Fe chicken omelette” won’t cost $1 even though the display says so.
We also don’t want two writers to work on the same thing (they would have to coordinate).
In this example, a process is still a person, but there are two kinds of persons: cafe guests (readers) and cafe workers (writers). The critical section is a display, and the shared resource is the data on that display. Readers are welcome to use a critical section without any delay unless there is a writer, and a writer has exclusive access to the shared resource when writing.
Please note that I’m not trying to say that an illustration is better than a Wikipedia article. There is no doubt that a metaphor can’t replace a good article that uses professional terminology. An illustration is a good way to start making sense of the article for those who are new to the topic (or refreshing their knowledge).
A good illustration helps to get the idea and then explore around: Would readers-writer lock work for the cache use case, where we come as a reader but may need to become a writer if the record we are looking for is not found? How a fitting room can show that reentrant mutexes need to “unlock” as many times as they “lock”? If the mutex is a restroom, then how can we describe concurrent map data structure?
And sometimes it’s easier to see it in action than read the textual description:
* Many good engineers consider recursive locks a bad practice
