Abstract

The Dining Philosophers Problem

There is a group of philosophers (usually 5) who eat together at a round table. There are forks placed between the philosophers. Philosophers spend their time either thinking or eating. In order to eat, a philosopher must pick up exactly two forks, one on his immediate left, and the other on his immediate right. When he is done eating, he will put his forks down so that his neighbors may use them, and he thinks again.

The programming problem is to construct a simulation which will allow philosophers to move between their eating and thinking states while properly controlling the forks.

A typical solution has each philosopher doing something like this:

    forever {
        busy thinking
        wait for left fork
        wait for right fork
        busy eating
        drop left fork
        drop right fork
    }

If every philosopher picks up his left fork and then waits for the right fork to become available, then the system will deadlock. Computation cannot go forward because the philosophers will never get their second forks. The fact that the busy periods are of random duration may reduce the occurrence of deadlock, but it does not prevent it. Occasional deadlock is actually a bigger problem, because it is much more difficult to replicate, diagnose, and fix. Deadlock is one of the greatest programming hazards in concurrent systems.

Some solutions modify some of the philosophers, so that they always pick up their right forks first. This does avoid deadlock, but it is a special solution. It cannot be generalized to avoid deadlock in other situations. Other implementations introduce waiters, rooms, chairs, tokens, and other objects to help manage the deadlock problem. These solutions are complex, and also not sufficiently generalizable.

Most solutions depend on the philosophers behaving correctly. For example, if a philosopher picks up his forks and never puts them down, the philosophers sitting beside him will die of starvation. If either happens to be holding a fork (which is likely), then all of the other philosophers will starve, too.

So we will redefine the problem. We still want to avoid deadlock, but we also want to be able to invite anyone to code their own philosopher class, and to have it run fairly with others.

An Example of the Failure of Class Signing

It is not sufficient to simply stuff Satan's code into a sandbox. He is not giving you an applet. He is giving you a class which needs to work cooperatively, even under the cloud of mutual suspicion, with other objects.

The goal is not to keep Satan out. You want to invite Satan in, but without compromising your security. You don't want to choose between safety and the benefits of openness. You want both.

Satan offers to prove to you that his class is safe by presenting an Authenticode certificate which will certify that Satan signed the class. You could verify that the signature is truly Satan's, but proof that it came from Satan is not proof that it is safe.

Satan, pretending to be offended by your skepticism, asks "Whose signature do you trust? Just say the name, and I will have them sign my class. Would you like Microsoft to sign it? There's a guy over there who owes me a favor."

You come to the conclusion that a signature cannot by itself transform a suspect class into a fully trusted class, so you decide that you need a more credible security mechanism.

Capabilities

In fig. 1 we see an example of a capability relationship. The ovals represent objects. The arrow indicates an object reference. Object C has a reference to Object A, and therefore Object C has the capability to communicate with Object A. An object can receive a reference to an object by having the reference passed to it, or by instantiating a new object.

Assuming that Object C is not trusted, we cannot be certain that it will destroy its reference to Object A when requested to. Capabilities are not directly revokable. But they can be indirectly revocable, as can be seen in fig. 2:

Object C is given a reference to Object T. Normally, Object T will pass Object C's messages on to Object A. Object B can send a message to Object T which will cause Object T to destroy its own reference to Object A. Object C will be left with a reference to the now useless Object T. Object C's capability to communicate with Object A has been revoked. Object B doesn't need to trust Object C if it can trust Object T.

The Cast

Each philosopher is assigned two fork dispensers. Philosophers do not have the capabilities necessary to interact directly with the other philosophers, the plates of shrimp, or with the system in general.

A philosopher sends requests to its fork dispensers, which respond by sending fork capabilities. The forks contain capabilities to the plate of shrimp, which the fork dispenser can revoke.

Joining the fork dispensers in the cast are forks, plates, and philosophers, using these interfaces:

public einterface ForkDispenser {
    emethod service (Object, Philosopher, Plate);
    emethod forkPlease (Philosopher);
    emethod forkReturn (Philosopher);
}
 
public einterface Fork {
    emethod shrimpPlease (int);
    emethod hereIsYourShrimp (int);
    emethod revoke ();
}
 
public einterface Plate {
    emethod shrimpPlease (Fork theFork, int serialNr);
}
 
public einterface Philosopher {
    emethod hereIsYourForkDispenser (ForkDispenser);
    emethod hereIsYourFork (Fork);
    emethod hereIsYourShrimp (int);
}

Fork Dispenser

public eclass OurForkDispenser implements ForkDispenser {
    private Object       trusted = null;
    private Philosopher  nowServing = null;
    private Philosopher  firstPhilosopher = null;
    private Philosopher  secondPhilosopher = null;
    private Plate        firstPlate = null;
    private Plate        secondPlate = null;
    private Fork         theFork = null;
    private Timer        theTimer = new Timer();
    private int          timerSerialNr;
    private boolean      otherIsWaiting = false;
    
    public ForkDispenser (eobject trusted) {
        this.trusted = trusted;
    }

The fork dispenser sends its own reference to the philosopher. This gives the philosopher the capability to interact with the fork dispenser.

    emethod service (Object theSource, Philosopher thePhilosopher, 
            Plate thePlate) {
        if (theSource == trusted) {
            thePhilosopher <- hereIsYourForkDispenser (this);
            if (firstPhilosopher == null) {
                firstPhilosopher = thePhilosopher;
                firstPlate = thePlate;
            } else {
                secondPhilosopher = thePhilosopher;
                secondPlate = thePlate;
            }
        }
    }

If a fork is not in use, then dispense one. If the requester is the same as current fork holder, then remind him that he already has a fork. (This can occur in some recovery strategies.)

Otherwise, the situation is that a request was made for a fork while a fork is in use by another philosopher. Make a note that the other philosopher is waiting and set a watchdog timer which will start the revocation of the current fork in 10,000 milliseconds.

    emethod forkPlease (Philosopher who) {
        int thePlate;
        if (who == firstPhilosopher) {
            thePlate = firstPlate;
        } else if (who == secondPhilosopher) {
            thePlate = secondPlate;
        } else {
            return;
        }
        
        if (nowServing == null) {
            nowServing = who;
            theFork = new OurFork (nowServing, thePlate);
            nowServing <- hereIsYourFork (theFork);
        } else if (nowServing == who) {
            nowServing <- hereIsYourFork (theFork);
        } else {
            otherIsWaiting = true;
            timerSerialNr += 1;
            theTimer.in (10000, (invocation 
                    (this <- timeOut (theTimer, timerSerialNr)));
        }
    }

First, check that the person returning the fork is the recorded holder of the fork. (This prevents Satan from pretending to be the other philosopher.) Then revoke the fork. (This prevents Satan from holding on to the capability.) If the other philosopher was waiting, then issue him a new fork and cancel the timer.

    emethod forkReturn (Philosopher thePhilosopher) {
        if (nowServing == thePhilosopher) {
            theFork <- revoke ();
            if (otherIsWaiting) {
                timerSerialNr += 1;
                serveOther();
            } else {
                nowServing = null;
                theFork = null;
            }
        }
    }

    emethod timeOut (Timer theSource, int messageSerialNr) {
        if (theSource == theTimer &&
                messageSerialNr == timerSerialNr) {
            theFork <- revoke ();
            serveOther();
        }
    }

    private void serveOther () {
        if (nowServing == firstPhilosopher) {
            nowServing = secondPhilosopher;
            thePlate = secondPlate;
        } else {
            nowServing = firstPhilosopher;
            thePlate = firstPlate;
        }
        theFork = new OurFork(nowServing, thePlate);
        nowServing <- hereIsYourFork (theFork);
        otherIsWaiting = false;
    }
}

Fork

public eclass OurFork implements Fork {
    private int          previousSerialNr = Integer.MIN_VALUE;
    private Philosopher  thePhilosopher = null;
    private Plate        thePlate = null;
 
    public Fork (Philosopher thePhilosopher, Plate thePlate) {
        this.thePhilosopher = thePhilosopher;
        this.thePlate = thePlate;
    }

The fork will be unable to forward the message if its reference to the plate has been revoked.

(The serial number test will fail after 4 billion shrimp requests to a fork due to an int rollover. That could fixed by adding a rollover test here, or by changing serial numbers to long. A well formed philosopher will easily recover. It seems that this warning is requiring more effort than the fix. It is unlikely that the fix would ever be needed.)

    emethod shrimpPlease (int serialNr) {
        if (previousSerialNr < serialNr) {
            previousSerialNr = serialNr;
            if (thePlate != null) {
                thePlate <- shrimpPlease (this, serialNr);
            } else {
                thePhilosopher <- noShrimp();
            }
        } else {
            thePlate = null;
            thePhilosopher <- noShrimp();
        }
    }

    emethod hereIsYourShrimp (int serialNr) {
        if (thePlate != null) {
            thePhilosopher <- hereIsYourShrimp (serialNr);
        } else {
            thePhilosopher <- noShrimp ();
        }
    }

    emethod revoke () {
        thePlate = null;
    }
}

Plate

public eclass OurPlate implements Plate {
    private int   firstSerialNr = Integer.MIN_VALUE;
    private Fork  firstFork = null;

An E object receives one message at a time. After the plate has seen two matching serial numbers, it sends a piece of shrimp. Because a fork is unable to send the same serial number twice in succession, the plate can determine that two forks were used. Further, by confirming that the ForkDispenser references do not match, forks from two different fork dispensers were used. We prove that the first fork is still valid by using it to return the shrimp.

    emethod shrimpPlease (Fork theFork, int serialNr) {
        if (firstSerialNr != serialNr) {
            firstSerialNr = serialNr;
            firstFork = theFork;
        } else {
            firstFork <- hereIsYourShrimp (serialNr);
            firstFork = null;
            firstSerialNr = Integer.MIN_VALUE;
        }
    }
}

Nice Philosopher

public eclass NicePhilosopher implements Philosopher {
    private ForkDispenser  firstForkDispenser  = null;
    private ForkDispenser  secondForkDispenser = null;
    private Fork           firstFork  = null;
    private Fork           secondFork = null;
    private int            serialNr = Integer.MIN_VALUE;
    private int            timerSerialNr = 0;
    private Timer          theTimer = new Timer;
    private boolean        eatingMode = false;

    emethod hereIsYourForkDispenser (ForkDispenser theForkDispenser) {
        if (firstForkDispenser == null) {
            firstForkDispenser = theForkDispenser;
        } else {
            secondForkDispenser = theForkDispenser;
            busyThinking();
        }
    }

    private void busyThinking() {
        eatingMode = false;
        timerSerialNr += 1;
        theTimer.in (10 * 1000, (invocation 
                (this <- startEating (timerSerialNr)));
    }

    emethod startEating () {
        firstFork  = null;
        secondFork = null;
        firstForkDispenser  <- forkPlease (this);
        secondForkDispenser <- forkPlease (this);
        serialNr = Integer.MIN_VALUE;
        timerSerialNr += 1;
        theTimer.in (20 * 1000, (invocation 
                (this <- stopEating (timerSerialNr)));
    }

    emethod hereIsYourFork (Fork theFork) {
        if (firstFork == null) {
            firstFork = theFork;
        } else {
            secondFork = theFork;
            eatingMode = true;
            eat();
        }
    }

    void eat() {
        serialNr += 1;
        firstFork  <- shrimpPlease (serialNr);
        secondFork <- shrimpPlease (serialNr);
    }

    emethod hereIsYourShrimp (int serialNr);
        if (eatingMode) {
            eat();
        }
    }

    emethod noShrimp () {
        timerSerialNr += 1;
        this <- stopEating();
    }

    emethod stopEating () {
        firstForkDispenser  <- forkReturn (this);
        secondForkDispenser <- forkReturn (this);
        busyThinking();
    }            
}

Evil Philosopher

public eclass EvilPhilosopher implements Philosopher {
    private ForkDispenser  firstForkDispenser = null;
    private ForkDispenser  secondForkDispenser = null;
    private Fork           firstFork = null;
    private Fork           secondFork = null;
    private int            serialNr = Integer.MIN_VALUE;

    emethod hereIsYourForkDispenser (ForkDispenser theForkDispenser) {
        if (firstForkDispenser == null) {
            firstForkDispenser = theForkDispenser;
        } else {
            secondForkDispenser = theForkDispenser;
            startEating();
        }
    }

    void startEating() {
        firstFork  = null;
        secondFork = null;
        firstForkDispenser  <- forkPlease (this);
        secondForkDispenser <- forkPlease (this);
        serialNr = Integer.MIN_VALUE;
    }

    emethod hereIsYourFork (Fork theFork) {
        if (firstFork == null) {
            firstFork = theFork;
        } else {
            secondFork = theFork;
            eat();
        }
    }

    void eat () {
        serialNr += 1;
        firstFork  <- shrimpPlease (serialNr);
        secondFork <- shrimpPlease (serialNr);
    }

    emethod noShrimp () {
        startEating();
    }

    emethod hereIsYourShrimp (int serialNr);
        eat();
    }
}

Main

public class Main {
    public final static int NR_DINERS = 5;
    public final static int NR_FORKS  = NR_DINERS;
 
    public static void main (String argv[ ]) {
        ForkDispenser  forkDispensers[ ] = new ForkDispenser[NR_FORKS];
        Philosopher    thePhilosopher = null;
        Plate          thePlate = null;
 
        for (int i = 0; i < NR_FORKS; i += 1) {
            forkDispensers [i] = new OurForkDispenser(this);
        }
 
        for (int i = 0; i < NR_DINERS; i += 1) {
            if (i == 0) {
                thePhilosopher = new EvilPhilosopher();
            } else {
                thePhilosopher = new NicePhilosopher();
            }
            thePlate = new OurPlate();
            forkDispensers [i]
                    <-  service (this, thePhilosopher, thePlate);
            forkDispensers [(i + 1) % NR_FORKS] 
                    <-  service (this, thePhilosopher, thePlate);
        }
    }
}

Flow

1. The philosopher sends forkPlease requests to both fork dispensers.
2. The fork dispenser creates a new fork object with capabilities to the philosopher and the plate of shrimp.
3. The fork dispenser sends a capability to the fork in a hereIsYourFork message to the philosopher.
4. The philosopher sends a shrimpPlease message to each fork.
5. The fork determines that it has not been revoked, and that it has never seen the current serial number. If all is ok, it sends a shrimpPlease message containing a capability to itself to the plate of shrimp.
6. The plate of shrimp will receive two messages. If the serial numbers on the messages match, then it knows that two different forks were used. It sends a hereIsYourShrimp message to the fork that sent the first of the two messages to prove that the first fork is still valid.
7. If the fork has not been revoked, then send a hereIsYourShrimp message to the philosopher.

The only capabilities granted to a philosopher are the fork dispensers and forks. This prevents Satan's philosopher class from doing anything harmful.

Consumption of Resources Attack

A later version of E will provide a remedy to Consumption of Resources Attacks.

Collusion

If the philosophers are run in a machine which is not under Satan's control, then the answer is no. E's containment mechanism assures that the philosophers cannot communicate directly with each other. They can only communicate with fork dispensers (and the forks they dispense), which do not support collusion.

The answer is less clear if Satan is allowed to execute his philosopher code remotely. Because Satan can hack his own machine, he can locally break containment, allowing the evil philosophers to communicate with each other. Suppose there is a nice philosopher sitting between the two evil philosophers. By sharing information about the condition of their forks, they can play a synchronized game in which the one on the left puts his fork down then immediately requests another when the one on the right gets a fork. When it is issued, the one on the right puts down his fork and immediately requests another. In this way, they can prevent the philosopher in the middle from getting two forks at the same time.

A similar kind of collusion can be found in an online poker game. While we can have confidence that the cards are dealt fairly, we cannot be confident that some of the players will not collude. The cheaters may be communicating by telephone, or may even be a single person pretending to be multiple people. By colluding, they have more information about the distribution of cards and the state of the deck, and so may be able to shave the odds in their favor. This kind of collusion could occur without the hacking of software.

Similarly, collusion in the Dining Philosopher example could occur without the hacking of software. The conspirators are able to speak to each other, and so can say things like "I just received my fork. Put down yours and request a new one."

ForkDispenser can be modified to make such collusion less effective. If every dispenser used a different time out value, or random time out values, then the attack will fail at least occasionally, and starvation will be prevented.

References

Englin, Jessica. Edsger W. Dijkstra. <URL: http://cda.mrs.umn.edu/~englinjm/EWD.html >

Electric Communities. Dicing with the Devil. <URL: http://www.communities.com/products/tools/e/techpapers/devil.html>

Electric Communities. Introduction To Capability Based Security. <URL: http://www.communities.com/company/papers/security/index.html>

Falk, Bennett. Table Manners. <URL: http://www.dnai.com/~bfalk/dining.html>

Feldman, M.B. Introduction to Concurrent Programming <URL: http://www.seas.gwu.edu/faculty/mfeldman/cs2-book/chap15.html> from Software Construction and Data Structures with Ada 95. Addison-Wesley.

Gloyer, Brian. The Dining Philosophers. <URL: http://www.javasoft.com/applets/contest/DiningPhilosophers/>

Hardy, Norm. Capability Theory. <URL: http://www.MediaCity.com/~norm/CapTheory/>

Herring, Charles. Implementing Discrete-Event Simulation in Java. <URL: http://csl.ncsa.uiuc.edu/~herring/java.html>

Holdsworth, D. Dijkstra's Dining Philosophers. <URL: http://www.leeds.ac.uk/ucs/people/DHoldsworth/diners/diners.html>

Miller, Mark. Taxonomy of Computer Security Problems. <URL: http://www.caplet.com/security/taxonomy/index.html >

McGregor, Tony. The Dining Philosophers Problem <URL: http://byerley.cs.waikato.ac.nz/~tonym/201/sync/node15.html> from 201 - Computer Systems.