#threading

Kazu Toki: 'Wind, Moon and Flower' (1989)

Charlie Brown's Halloween Special:

"I got five pieces of candy!"

"I got a chocolate bar!"

"I got a quarter!"

Charlie Brown: "I got a rock."

The Clothing Store (Seekers Notes) Stimboard

"Its doors are bursting with an influx of customers as soon as they open in the morning, because there are many ladies and gentlemen who love to dress up and always keep up with the latest fashion in Darkwood. Here everyone can order themselves dresses and suits in every style and color."

Heyyyy,

So, I'm super excited to start diving into some classic computer science concepts here, especially those that pop up in the world of Linux and concurrent programming. And what better place to start than with the fascinating (and sometimes frustrating!) Dining Philosophers Problem (I learned it about two days ago so please be patient :P).

Think about it: a group of philosophers are sitting around a circular table. In front of each philosopher is a bowl of delicious spaghetti. To eat (somehow) a philosopher needs two chopsticks – one to their left and one to their right. However, there's only one chopstick between each pair of philosophers.

The philosophers have a simple life cycle: they think, they get hungry, they try to pick up their chopsticks, they eat, and then they put the chopsticks down and go back to thinking.

The tricky part arises when multiple philosophers get hungry at the same time. If everyone picks up their left chopstick simultaneously, no one can pick up their right chopstick! They all end up waiting indefinitely, holding one chopstick and starving. This, my friends, is a classic example of a deadlock (and I'm not talking about Valorant's agent ;) ).

Now, why is this relevant to Linux and programming?

Well, the Dining Philosophers Problem is a great analogy for common issues we face when dealing with concurrent processes or threads that need to access shared resources (like those chopsticks!). Chopsticks represent shared resources: Think of these as locks, mutexes, semaphores, or any other mechanism used to control access to critical sections of code (I'm going to talk about those in another posts). Philosophers represent processes or threads: These are the independent units of execution trying to use the shared resources.

The act of picking up chopsticks represents acquiring locks: A process needs to acquire the necessary locks before it can proceed with its task (eating). Deadlock in the problem mirrors deadlock in programs: Just like the philosophers can get stuck waiting for each other's chopsticks, threads can get stuck waiting for locks held by other threads, leading to a program freeze (don't try it at home).

There are several interesting ways to approach solving the Dining Philosophers Problem (and preventing deadlocks in our programs!). Some common strategies include: Introducing a resource hierarchy: Making philosophers pick up chopsticks in a specific order. Allowing a philosopher to pick up both chopsticks only if both are available. Introducing a central coordinator. Limiting the number of philosophers trying to eat at the same time.

What are your initial thoughts on the Dining Philosophers Problem?

Have you encountered similar deadlock situations in your own programming projects? Let me know!