The dining philosophers problem illustrates non-composability of low-level synchronization primitives like semaphores. It is a modification of a problem posed by Edsger Dijkstra.

Five philosophers, Aristotle, Kant, Spinoza, Marx, and Russell (the tasks) spend their time thinking and eating spaghetti. They eat at a round table with five individual seats. For eating each philosopher needs two forks (the resources). There are five forks on the table, one left and one right of each seat. When a philosopher cannot grab both forks it sits and waits. Eating takes random time, then the philosopher puts the forks down and leaves the dining room. After spending some random time thinking about the nature of the universe, he again becomes hungry, and the circle repeats itself.

It can be observed that a straightforward solution, when forks are implemented by semaphores, is exposed to deadlock. There exist two deadlock states when all five philosophers are sitting at the table holding one fork each. One deadlock state is when each philosopher has grabbed the fork left of him, and another is when each has the fork on his right.

There are many solutions of the problem, program at least one, and explain how the deadlock is prevented.

COMMENT
!    DEADLOCK IS PREVENTED BY REVERSING THE ORDER OF TAKING THE CHOPSTICKS FOR THE LAST PHILOSOPHER.
!    THAT MEANS ALL PHILOSOPHERS FIRST TAKE THE LEFT CHOPSTICK, THEN THE RIGHT CHOPSTICK.
!    BUT THE LAST PHILOSOPHER FIRST TAKES THE RIGHT CHOPSTICK, THEN THE LEFT.
!
!    THE DETACH STATEMENT IN CLASS PHILOSOPHER GIVES CONTROL BACK TO THE MAIN BLOCK.
!    THE MAIN BLOCK CALLS/RESUMES ALL THE PHILOSOPHERS USING THE RESUME(PHILOSOPHER) STATEMENT.
!    THIS CONTINUES THE CODE IN THE PHILOSOPHER CLASS AFTER THE LAST DETACH STATEMENT.
!    (ANOTHER NAME FOR THIS FEATURE IS THE CONCEPT OF A COROUTINE)
;
BEGIN
    INTEGER N;
    INTEGER PNR, CNR;
    INTEGER SEED;
    SEED := ININT;
    N := 5;
    BEGIN
 
        CLASS CHOPSTICK;
        BEGIN
            REF(PHILOSOPHER) OWNER;
            INTEGER ID;
            ID := CNR := CNR + 1;
        END CHOPSTICK;
 
        CLASS PHILOSOPHER(L,R);
            REF(CHOPSTICK) L,R;
        BEGIN
            INTEGER ID;
            ID := PNR := PNR + 1;
            WHILE TRUE DO
            BEGIN
                DETACH;
 
                OUTTEXT("PHILOSOPHER(");
                OUTINT(ID, 0);
                OUTTEXT(") THINKING...");
                OUTIMAGE;
                DETACH;
 
                WHILE RANDINT(0,1,SEED) = 0 DO BEGIN
                    OUTTEXT("PHILOSOPHER(");
                    OUTINT(ID, 0);
                    OUTTEXT(") THINKING DEEPER...");
                    OUTIMAGE;
                    DETACH;
                END;
 
                WHILE L.OWNER =/= NONE DO BEGIN
                    OUTTEXT("PHILOSOPHER(");
                    OUTINT(ID, 0);
                    OUTTEXT(") WAITING FOR LEFT CHOPSTICK(");
                    OUTINT(L.ID, 0);
                    OUTTEXT(") ...");
                    OUTIMAGE;
                    DETACH;
                END;
                L.OWNER :- THIS PHILOSOPHER;
                OUTTEXT("PHILOSOPHER(");
                OUTINT(ID, 0);
                OUTTEXT(") GRABBED LEFT CHOPSTICK(");
                OUTINT(L.ID, 0);
                OUTTEXT(")");
                OUTIMAGE;
 
                WHILE R.OWNER =/= NONE DO BEGIN
                    OUTTEXT("PHILOSOPHER(");
                    OUTINT(ID, 0);
                    OUTTEXT(") WAITING FOR RIGHT CHOPSTICK(");
                    OUTINT(R.ID, 0);
                    OUTTEXT(") ...");
                    OUTIMAGE;
                    DETACH;
                END;
                R.OWNER :- THIS PHILOSOPHER;
                OUTTEXT("PHILOSOPHER(");
                OUTINT(ID, 0);
                OUTTEXT(") GRABBED RIGHT CHOPSTICK(");
                OUTINT(R.ID, 0);
                OUTTEXT(")");
                OUTIMAGE;
 
                OUTTEXT("PHILOSOPHER(");
                OUTINT(ID, 0);
                OUTTEXT(") EATING...");
                OUTIMAGE;
                WHILE RANDINT(0,1,SEED) = 0 DO BEGIN
                    DETACH;
                    OUTTEXT("PHILOSOPHER(");
                    OUTINT(ID, 0);
                    OUTTEXT(") STILL EATING...");
                    OUTIMAGE;
                END;
                L.OWNER :- NONE;
                R.OWNER :- NONE;
                OUTTEXT("PHILOSOPHER(");
                OUTINT(ID, 0);
                OUTTEXT(") RELEASED LEFT CHOPSTICK(");
                OUTINT(L.ID, 0);
                OUTTEXT(")");
                OUTIMAGE;
                OUTTEXT("PHILOSOPHER(");
                OUTINT(ID, 0);
                OUTTEXT(") RELEASED RIGHT CHOPSTICK(");
                OUTINT(R.ID, 0);
                OUTTEXT(")");
                OUTIMAGE;
            END;
        END PHILOSOPHER;
 
        !---------------------------------------|
        !                                       |
        !                                       |
        !                  (3)                  |
        !             P2         P3             |
        !                                       |
        !        (2)                  (4)       |
        !                                       |
        !                                       |
        !      P1                       P4      |
        !                                       |
        !                                       |
        !         (1)              (5)          |
        !                                       |
        !                  P5                   |  only P5 takes Right first (5), then Left (1)
        !                                       |
        !---------------------------------------|
        !;
 
        REF(PHILOSOPHER) ARRAY PHILS (1:N);
        REF(CHOPSTICK) L, R;
        INTEGER I, LOOPS;
 
        R :- NEW CHOPSTICK;
        FOR I := 1 STEP 1 UNTIL N-1 DO
        BEGIN
            L :- NEW CHOPSTICK;
            PHILS(I) :- NEW PHILOSOPHER(L,R);
            R :- L;
        END;
        ! REVERSED ORDER FOR THE LAST PHILOSOPHER ;
        PHILS(N) :- NEW PHILOSOPHER(R,PHILS(1).R);
 
        FOR I := 1 STEP 1 UNTIL N DO BEGIN
            OUTTEXT("PHILOSOPHER(ID=");
            OUTINT(PHILS(I).ID, 0);
            OUTTEXT(", L=");
            OUTINT(PHILS(I).L.ID, 0);
            OUTTEXT(", R=");
            OUTINT(PHILS(I).R.ID, 0);
            OUTTEXT(")");
            OUTIMAGE;
        END;
 
        FOR LOOPS := 1 STEP 1 UNTIL 10 DO BEGIN
            FOR I := 1 STEP 1 UNTIL N DO BEGIN
                RESUME(PHILS(I));
            END;
        END;
 
    END;
END.