Classical concurrent problems

Mark Wutka <>
Fri Feb 10 19:52:14 CET 2006


" Hi,
" 
" Where can I find erlang solutions to classical concurrent problems such as
" the dinning philosophers? I tried googling but didn't find anything
" 
" Thanks
" 

I did a version of it in Erlang, I just can't vouch for it being *good*
Erlang. It isn't too long, so I think it's probably okay to just stick
it in the message. The each chopstick and philosopher is a process. The
philosophers strategy is just to pick up the left chopstick, then try
the right. If it can't get the right, it drops the left, waits, and
tries again. You can experiment with other strategies, of course.
I put a wait_for function in chopstick to wait for a chopstick, but the
current philosopher implementation doesn't use it.
  Mark

--- chopstick.erl ---

-module(chopstick).
-export([start/0, pick_up/1, put_down/1, wait_for/1, is_available/1, chopstick/2]).

start() ->
    spawn(chopstick, chopstick, [true, []]).

chopstick(Available, WhoHas) ->
    receive

%% Allow someone to pick up the chopstick if it is available
	{pick_up, Sender} when Available ->
	    Sender ! picked_up,
	    chopstick(false, Sender);

%% If the chopstick is unavailable, don't allow it to be picked up
	{pick_up, Sender} when not Available ->
	    Sender ! not_picked_up,
	    chopstick(Available, WhoHas);
	    
%% Only allow the sender who holds the chopstick to release it
	{put_down, Sender} when Sender == WhoHas ->
	    Sender ! put_down,
	    chopstick(true, []);

%% Consume any putdown messages for someone who isn't the sender
	{put_down, Sender} when Sender /= WhoHas ->
	    chopstick(Available, WhoHas);

%% Anyone can ask whether the stick is currently available
	{is_available, Sender} ->
	    Sender ! {availability, Available},
	    chopstick(true, WhoHas);

%% Anyone can wait for the stick to be released, if it is already
%% available, just hand it over
	{wait_for, Sender} when Available ->
	    Sender ! picked_up,
	    chopstick(false, Sender);

%% If someone wants to wait for the stick and it isn't available,
%% wait for someone to put it down
	{wait_for, Sender} when not Available ->
	    chopstick_wait(Sender, WhoHas)
    end.

chopstick_wait(Waiter, WhoHas) ->
    receive
%% When the stick is put down, let the waiting person have it
	{put_down, PutDownSender} when PutDownSender == WhoHas ->
	    PutDownSender ! put_down,
	    Waiter ! picked_up,
	    chopstick(false, Waiter);

%% Allow anyone to check on the stick status during a wait
	{is_available, AvailableSender} ->
	    AvailableSender ! {availability, false},
	    chopstick_wait(Waiter, WhoHas);
    end.

%% Define functions that interact with a chopstick process

pick_up(Chopstick) ->
    Chopstick ! { pick_up, self() },
    receive
	picked_up ->
	    true;
	not_picked_up ->
	    false
    end.

put_down(Chopstick) ->
    Chopstick ! { put_down, self() }.

is_available(Chopstick) ->
    Chopstick ! { is_available, self() },
    receive
	{availability, Status} ->
	    Status
    end.

wait_for(Chopstick) ->
    Chopstick ! { wait_for, self() },
    receive
	picked_up ->
	    true
    end.

--- philosopher.erl ---

-module(philosopher).
-export([start/3, think/3]).
-define(MaxThink, 10000).
-define(MaxEat, 10000).
-define(MaxWait, 1000).

start(Left, Right, Name) ->
    spawn(philosopher, think, [Left, Right, Name]).

%% A philospher thinks for a while and then gets hungry
think(Left, Right, Name) ->
    io:format("~s is thinking...~n", [Name]),
    timer:sleep(random:uniform(?MaxThink)),
    io:format("~s is hungry!~n", [Name]),
    pick_up_left(Left, Right, Name).

%% To eat, the philosopher first tries to pick up the left chopstick
pick_up_left(Left, Right, Name) ->
    GotLeft = chopstick:pick_up(Left),
    if
	GotLeft ->
	    io:format("~s picked up left chopstick~n", [Name]),
	    pick_up_right(Left, Right, Name);
	true ->
	    %% If unable to get a chopstick, wait a little bit before trying
	    timer:sleep(random:uniform(?MaxWait)),
	    pick_up_left(Left, Right, Name)
    end.

%% Once the philosopher has the left chopstick, he tries the right
pick_up_right(Left, Right, Name) ->
    GotRight = chopstick:pick_up(Right),
    if
	GotRight ->
	    io:format("~s picked up right chopstick~n", [Name]),
	    eat(Left, Right, Name);
	true ->
	    %% If the right is unavailable, put the left down and wait a bit
	    chopstick:put_down(Left),
	    io:format("~s put down left chopstick~n", [Name]),
	    timer:sleep(random:uniform(?MaxWait)),
	    pick_up_left(Left, Right, Name)
    end.

%% Yum
eat(Left, Right, Name) ->
    io:format("~s is eating~n", [Name]),
    timer:sleep(random:uniform(?MaxEat)),
    chopstick:put_down(Left),
    chopstick:put_down(Right),
    io:format("~s put down both chopsticks~n", [Name]),
    think(Left, Right, Name).
    
--- dining.erl ---

-module(dining).
-export([start/0]).

start() ->
    %% Create the chopsticks
    C1 = chopstick:start(),
    C2 = chopstick:start(),
    C3 = chopstick:start(),
    C4 = chopstick:start(),
    C5 = chopstick:start(),

    %% Start the philosophers each with a different pair of chopsticks
    philosopher:start(C1, C2, "Lao Tzu"),
    philosopher:start(C2, C3, "Plato"),
    philosopher:start(C3, C4, "Socrates"),
    philosopher:start(C4, C5, "Descartes"),
    philosopher:start(C5, C1, "Hume").



More information about the erlang-questions mailing list