Last time we talked about critical sections and how we definitely want to avoid that our threads are in their critical sections at the same time. Bad things happen when threads are editing a shared resource at the same time, so we need to ensure that it does not happen. This is where mutual exclusion comes in.
With mutual exclusion we want to guarantee that no thread is in their critical section at the same time. This is only valid for threads that operate on the same resource though. All we want to avoid is overlap between threads’ critical sections. Unfortunately it is not that easy to do and there are many ways to do it.
There are many different algorithms that try to achieve mutual exclusion and I’ll be diving into some of them later on. If you’ve worked with data structures and algorithms before, you know that there is always some kind of trade off. Maybe it runs really fast but it takes up a lot of space, or it’s really efficient for the small inputs but terrible for bigger inputs. The same goes for mutual exclusion algorithms. So before I go into the specific algorithms, we’re going to talk about the different properties these algorithms can have or more specifically progress conditions.
As a basis all algorithms dealing with concurrency have to guarantee mutual exclusion. Unfortunately that doesn’t mean things can’t go horribly wrong with things like deadlock or starvation.
A common way to solve mutual exclusion is by using different types of locks. A thread tries to acquire a lock before entering it’s critical section, it enters it’s critical section upon acqucision and unlocks the lock when it exits. How a specific type of lock is implemented is a blog post for another day. However with locks you run the risk of:
Deadlock: Imagine two siblings playing together, Alice has the yellow doll and Bob has the green doll. Alice needs the green doll to play out her storyline and Bob needs the yellow doll to play how he wants to play. Neither is willing to give up their doll and so they are deadlocked. The same goes for threads, Thread A has the lock to one resource but needs the lock to another resource, which Thread B has, who is waiting for Thread A to release it’s lock. Clearly neither are going anywhere even if they’re not in their critical section at the same time.
Starvation: Now you’re in line for food in the school cafeteria and the kids in front of how keep allowing their newly arrived friends into the line in front of them. Before you know it, the entire lunch break is gone and you didn’t get your food because kids kept jumping in front of you, bummer. This is the principle of starvation. If multiple threads are sharing a lock, some threads can possibly never acquire the lock, because other threads always acquire it before the thread can. So the thread never get’s the finish it’s execution.
So of course when we’re designing mutual exclusion algorithms we want to avoid these things. So a lock can have these properties guaranteeing a threads progress:
- Deadlock-free: Some lock eventually acquires the lock.
- Starvation-free: All threads eventually acquires the lock. Notice here that starvation free is a stricter condition because all threads must acquire the lock (it doesn’t promise anything about how fast though). So if a lock is starvation free, it’s also deadlock free.
Phew, that was quite a bit, thank you for sticking with me. Next time we’ll be looking at some simple locks and their properties.