Erlang Circular Process Communication

The 1984 Chandy / Misra solution to the dining philosophers problem1 requires philosophers to communicate with each other. In Erlang, one way to do this is to have the philosophers tell the philosopher who sat before them that they are neighbors.

Below is my first Erlang program which sets up the circular communication between processes:

%% Dining Philosophers setup.
%% By Luke Hoersten
%% Public Domain (PD) No Rights Reserved.

%% This is the Chandy / Misra Dining Philosophers Solution and it
%% assumes philosophers can talk to eachother.

-module(dine_phil).
-export([dine/1,sit/1]).

%%%% Setup
dine(Places) -> sit(Places).

%%%% Fork
pickup_fork(Clean) ->
    spawn(fun() -> fork(Clean) end).

fork(IsClean) ->
    receive
        {Phil, is_clean} ->
            Phil ! IsClean,
            fork(IsClean);
        set_dirty -> fork(false);
        set_clean -> fork(true)
    end.

%%%% Sit
sit(Num) -> %% first expects last as left
    First = spawn(fun() -> greet(last, pickup_fork(true)) end),
    sit(Num-1, First, First).

sit(1, Left, First) -> %% last expects first as right
    spawn(fun() -> greet(Left, First, pickup_fork(false)) end);
sit(Num, Left, First) ->
    Current = spawn(fun() -> greet(Left, pickup_fork(false)) end),
    sit(Num-1, Current, First).

%%%% Greet
greet(Left, First, Fork) ->
    First ! {last, self()}, %% last tells first when he's seated
    greet(Left, Fork).

greet(last, Fork) -> %% first waits for his right and last to sit
    receive
        {last, Last} -> greet(Last, Fork)
    end;
greet(Left, Fork) -> %% everyone tells left when he's seated
    Left ! {right, self()},
    receive
        {right, Right} -> eat(Left, Right, Fork)
    end.
  1. In computer science, the dining philosophers problem is an illustrative example of a common computing problem in concurrency. It is a classic multi-process synchronization problem.
    Wikipedia

    []

    None Found
  • http://philharnish.tumblr.com Phil Harnish

    You might check out a benchmark erlang vs stackless python written in response to a challenge Joe Armstrong proposed to test communication performance in a ring. I came across it yesterday and I was surprised by the results.

  • https://www.humani.st Luke Hoersten

    Sahil sent me this a few days ago. I’ll give it a read and I’m excited to learn about stackless python. What better way to learn than by comparing it with Erlang I suppose =)

    Thanks Phil.

  • https://www.humani.st Luke Hoersten

    I read the article. This is simply comparing the speed at which messages are passing in Erlang vs. Stackless Python and parallelism wasn’t benchmarked at all. It looks like he went back and tried to use SMP but didn’t know what he was doing. Erlang’s compiler is explicitly not optimized for single processor speed like this example. The point is that the mass amount of parallelism in most Erlang systems will make compiler optimization a drop in the ocean.

    Bob Ippolito Says:
    August 2, 2007 at 9:32 pm

    For stuff like this compiling with HiPE will probably make a big difference too, I think you can get it from erlc with native. I don’t need to use HiPE in practice though, real-world (IO bound) Erlang code tends to run plenty fast on BEAM… and it wipes the floor with the Python/Twisted stuff we used to have. Some TCP/HTTP benchmarks would be more relevant to people actually deciding between Python and Erlang.

    Bob is a MochiMedia founder.

    The author of the article also redacted his benchmarks:

    Dear all,

    thank you very much for your comments drawing attention to a number of interesting aspects I had not covered in the article. I have learned quite a bit by exchanging views with some of you which is one of the benefits of publishing in the blogosphere :-)

    In retrospect I think it is fair to state that running the benchmark on my single-CPU system did not really do justice to Erlang which appears to have advanced capabilities when it comes to distributing processes on multi-CPU machines or even clusters.

    Furthermore, a proper benchmark would have to tackle problems that are more amenable to parallelisation in order to allow the languages/systems involved to show off their true potential.

    Anyway, it was an interesting experience, and I for one will continue to experiment with both Erlang and Python.

    Best regards — Muharem

    Still an interesting article though!

  • http://concise-software.blogspot.com/ Alain O’Dea

    It is interesting to see how concisely Erlang’s message-passing and pattern-matching addresses the Dining Philosophers problem. I would like to see how Kilim does this since it uses cooperative multi-tasking unlike Erlang which uses preemptive multi-tasking.

    I would love to try this, but the dine_phil module does not compile:
    ./dine_phil.erl:50: function eat/3 undefined

  • https://www.humani.st Luke Hoersten

    The eat function is the actual “dining” or resource sharing code. You’ll have to write that part yourself =) You could have it simply print out the neighbors to see who all can communicate with each other.

    I was more interested in the actual setup of a circular communication ring because it’s not as trivial as it seems. This was my first Erlang program so doing it cleanly was a bit of a challenge for me.

  • http://concise-software.blogspot.com/ Alain O’Dea

    Nonetheless you did brilliantly. That is a very elegant solution. I hope you keep at Erlang. It is a very important language.

  • https://www.humani.st Luke Hoersten

    Thanks a lot =)

  • http://femalenudity.blogspot.com female

    Has read with the pleasure, very interesting post, write still, good luck to you!