The dining philosophers problem is a classic computer science puzzle aimed at thinking and learning about concurrency and synchronization. The problem was originally stated in 1965 by Edsger Dijkstra as an exam exercise about resource sharing: How do you synchronize access to 5 shared tape drives across 5 computers? This problem was later generalized and reworded by Tony Hoare, resulting in the dining philosophers problem as we know it today.
The Dining Philosophers Problem
The description of the problem is best worded in Chapter 2 of Communicating Sequential Processes by Tony Hoare:
In ancient times, a wealthy philanthropist endowed a College to accommodate ﬁve eminent philosophers. Each philosopher had a room in which he could engage in his professional activity of thinking; there was also a common dining room, furnished with a circular table, surrounded by ﬁve chairs, each labelled by the name of the philosopher who was to sit in it. The names of the philosophers were PHIL0, PHIL1, PHIL2, PHIL3, PHIL4, and they were disposed in this order anticlockwise around the table. To the left of each philosopher there was laid a golden fork, and in the centre stood a large bowl of spaghetti, which was constantly replenished.
A philosopher was expected to spend most of his time thinking; but when he felt hungry, he went to the dining room, sat down in his own chair, picked up his own fork on his left, and plunged it into the spaghetti. But such is the tangled nature of spaghetti that a second fork is required to carry it to the mouth. The philosopher therefore had also to pick up the fork on his right. When we was ﬁnished he would put down both his forks, get up from his chair, and continue thinking. Of course, a fork can be used by only one philosopher at a time. If the other philosopher wants it, he just has to wait until the fork is available again.
There are many variations of the story, however the principles remain the same: Synchronization of activities centered around a set of sharable, mutually-exclusive resources.
Elixir – Erlang but Better
Last month, 15 atoms attended Strangeloop in St. Louis. As part of the pre-conference I attended the Emerging Languages Camp, which focuses on new and upcoming programming languages. All of the languages were quite impressive, however, one language in particular stood out to me as something that I must try, Elixir.
The Elixir home page describes it as “a functional meta-programming aware language built on top of the Erlang VM. It is a dynamic language with flexible syntax with macros support that leverages Erlang’s abilities to build concurrent, distributed, fault-tolerant applications with hot code upgrades.”
I have been quite intrigued with Erlang for a number of years, as it focuses around large, scalable, real-time systems with high availability concerns. The built-in support for concurrency, distributed programming and fault tolerance, make it an attractive solution for a variety of use cases. A number of successful projects and services use Erlang: document database CouchDB, AMQP message broker RabbitMQ, and many others.
While reading Learn You Some Erlang for Great Good!, I quickly discovered that Erlang’s syntax is different. I found myself spending more time on syntactic errors, and trying to make the code look pretty than I did trying to solve my problems. Enter Elixir, all the features of Erlang, paired with an easy to use and familiar syntax.
Elixir and the Dining Philosophers
Given Erlang and Elixir’s focus on concurrency and distributed programming, the dining philosophers problem is excellent for experimenting with these languages. After spending a few hours with Elixir, I found it to be quite easy and enjoyable to work with. I spent very little time struggling with syntax and trying to make my code look pretty.
Spawning actors, passing messages between actors, and implementing behaviors came with ease. If I was unable to find a needed module in Elixir’s library, I could easily and quickly drop down to Erlang and take advantage of Erlang’s mature environment. I am looking forward to working with Elixir further and watching the language grow.
I have posted my dining philosopher implementation on github. I encourage you to check out Elixir, and go through their getting started guide. I am interested to see if anyone finds this upcoming language as exciting and promising as I do.
I’m intrigued… I know zilch about Erlang but this still sounds awesome.
we consider n philosophers seated in circular desk and n forks and all of them want to eat the pasta at the front side of each one.
Comments are closed.