[m-dev.] Is this a semaphore bug or comprehension failure on my part?

[Ralph Becket]

The code below does odd things:

%-----------------------------------------------------------------------
-------%
% philo3.m
% Ralph Becket <rbeck at microsoft.com>
% Mon May 14 14:32:29 BST 2001
% vim: ts=4 sw=4 et tw=0 wm=0 ff=unix ft=mercury
%
% The dining philosophers using semaphores.
%
%-----------------------------------------------------------------------
-------%

:- module philo3.

:- interface.

:- import_module io.



:- pred main(io__state::di, io__state::uo) is cc_multi.

%-----------------------------------------------------------------------
-------%
%-----------------------------------------------------------------------
-------%

:- implementation.

:- import_module string, list.
:- import_module semaphore, spawn.

%-----------------------------------------------------------------------
-------%

main -->
    semaphore__new(Fork0), semaphore__signal(Fork0),
    semaphore__new(Fork1), semaphore__signal(Fork1),
    semaphore__new(Fork2), semaphore__signal(Fork2),
    semaphore__new(Fork3), semaphore__signal(Fork3),
    semaphore__new(Fork4), semaphore__signal(Fork4),
    spawn(philosopher("Plato",      0, Fork0, 1, Fork1)),
    spawn(philosopher("Aristotle",  2, Fork2, 1, Fork1)),
    spawn(philosopher("Descartes",  2, Fork2, 3, Fork3)),
    spawn(philosopher("Calvin",     4, Fork4, 3, Fork3)),
          philosopher("Hobbes",     4, Fork4, 0, Fork0).



:- pred
philosopher(string,int,semaphore,int,semaphore,io__state,io__state).
:- mode philosopher(in, in, in, in, in, di, uo) is cc_multi.

philosopher(Name, A, SemA, B, SemB) -->

    io__format("%s is thinking\n", [s(Name)]),
    io__flush_output,
    rand_sleep(3),

    semaphore__wait(SemA),
    io__format("%s has acquired fork %d\n", [s(Name), i(A)]),
    io__flush_output,

    semaphore__wait(SemB),
    io__format("%s has acquired fork %d\n", [s(Name), i(B)]),
    io__flush_output,

    io__format("%s is eating\n", [s(Name)]),
    io__flush_output,
    rand_sleep(2),

    semaphore__signal(SemB),
    io__format("%s has relinquished fork %d\n", [s(Name), i(B)]),
    io__flush_output,

    semaphore__signal(SemA),
    io__format("%s has relinquished fork %d\n", [s(Name), i(A)]),
    io__flush_output,

    philosopher(Name, A, SemA, B, SemB).

%-----------------------------------------------------------------------
-------%

:- pred rand_sleep(int::in, io__state::di, io__state::uo) is det.
:- pragma c_code(rand_sleep(Int::in, IO0::di, IO::uo),
        [thread_safe, will_not_call_mercury], "{
    sleep(rand() % Int);
    IO =  IO0;
}").

%-----------------------------------------------------------------------
-------%
%-----------------------------------------------------------------------
-------%

It generates output like this:

Hobbes is thinking
Hobbes has acquired fork 4
Hobbes has acquired fork 0        <- (A) and
Hobbes is eating
Plato is thinking
Plato has acquired fork 0         <- (A) shouldn't be the case 
Plato has acquired fork 1         <- (B) and
Plato is eating
Aristotle is thinking
Aristotle has acquired fork 2
Aristotle has acquired fork 1     <- (B) shouldn't be the case
Aristotle is eating
Descartes is thinking
Calvin is thinking
Hobbes has relinquished fork 0
Plato has relinquished fork 1     <- (C) and
Aristotle has relinquished fork 1 <- (C) shouldn't be the case, etc...
Calvin has acquired fork 4
Calvin has acquired fork 3
Calvin is eating
Hobbes has relinquished fork 4
Hobbes is thinking
Plato has relinquished fork 0
Plato is thinking
Plato has acquired fork 0
Plato has acquired fork 1
Plato is eating

My understanding of semaphores is that they constitute mutexes
in the case where each semaphore counter can only be either 0 or 1.
>From what I can see, my code above does apply the 0/1 restriction,
yet the output is clearly wrong.

Have I misunderstood semaphores (pray God not, that would be
embarrassing) or is this a bug?

Another point is that if I recode main//0 as

main -->
    semaphore__new(Fork0), semaphore__signal(Fork0),
    semaphore__new(Fork1), semaphore__signal(Fork1),
    semaphore__new(Fork2), semaphore__signal(Fork2),
    semaphore__new(Fork3), semaphore__signal(Fork3),
    semaphore__new(Fork4), semaphore__signal(Fork4),
    spawn(philosopher("Plato",      0, Fork0, 1, Fork1)),
    spawn(philosopher("Aristotle",  2, Fork2, 1, Fork1)),
    spawn(philosopher("Descartes",  2, Fork2, 3, Fork3)),
    spawn(philosopher("Calvin",     4, Fork4, 3, Fork3)),
    spawn(philosopher("Hobbes",     4, Fork4, 0, Fork0)).

then the program terminates immediately, even though there are
runnable threads lying around.  Shurely shome mishtake?

Cheers,

Ralph

--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------