Concurrency #0: Teaser

Introduction

Concurrency (aka multithreading) is hard. No, I mean really hard. You just don’t realize how hard it is until you’ve actually done it. The upcoming posts are going to be all about how I do concurrency in .Net via message-passing. This post is a quick introduction to the series.

The "Simple" Way

It all seems so easy at first. You’re introduced to the humble lock, an easy way to make sure threads don't run over each other. Just hold the lock, and everything works, right? Then you hit your very first deadlock. Deadlocks are brutal. The simplest deadlock is when two threads acquire the same two locks, but in the opposite order. For example:
1. Thread 1 - Acquire lock 1.
2. Thread 2 - Acquire lock 2.
3. Thread 1 - Block trying to acquire lock 2, because Thread 2 has it.
4. Thread 2 - Block trying to acquire lock 1, because Thread 1 has it.
Now both threads can't make progress until the other one makes progress, so they're stuck forever. Any other threads that touch the locks are now also going to block forever.

Concurrent programming with locks is a delicate dance between ensuring the threads don't run over each other and making sure the threads don't deadlock. It's highly non-trivial, because those properties are inherently global. You can't just look at part of the program and know it is correct, you have to look at the program as a whole. Locks also don't compose, meaning if you have two methods which are synchronized using locks, the combination is not synchronized. For example if you only dequeue from a queue when it is not empty, a thread could remove the last element between the check and the dequeue.

Teaser

Don't despair, there are better ways to do concurrency! In this series, I will be focusing on message passing. I will build .Net classes for message passing, and I will give examples of using them. First up will be a lock free queue.