Concurrency P3: One at a time, mutual exclusion

17 Sep 2018

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.

Mutual exclusion

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:

Starvation

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:

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.

-----------------------------------------------------------------