Date: Tue, 05 Nov 1996 20:57:28 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Thu, 31 Oct 1996 21:38:54 GMT Content-length: 7757
Disclaimers:
In today's class (Oct 9), Joni Baker pointed out that this particular scenario cannot occur if the code is carefully written to prevent duplicate requests, as in the sample code I wrote on the blackboard. B.putForks() only calls A.giveFork() if B has previously requested the fork from B, but A.takeForks() only calls B.requestFork() if A has not previously requested it. In class, I said that a more complicated scenario could be devised to show that deadlock is still possible, but couldn't think of one on the spot. It seems to require at least three philosophers.
Consider a circular pattern of philosophers, A, B, and C, each pair sharing one fork (i.e., a three-philosopher version of the original dining philosophers problem). Assume B is eating, so he has the forks he shares with A and C, and A has the fork she shares with C. Let tA, tB, and tC represents the threads for philosophers A, B, and C. Suppose C gets hungry just before B finishes eating, and A gets hungry just after. The following sequence of events is possible.
Here is the example I couldn't show this morning because there was no projector. This is the original version of takeForks() from the TA's solution to the project.
private synchronized void takeForks() { state = HUNGRY; int forksHave = 0; // Number of forks currently owned while (forksHave < forks.length) { for (int i = 0; i < forks.length; i++) { if (forks[i].have) forksHave++; else if (!forks[i].haveRequested) { if (phil[forks[i].neighborId].requestFork(forks[i].forkId)){ forks[i].clean = true; forks[i].have = true; forksHave++; } else forks[i].haveRequested = true; } } } if (forksHave < forks.length) { forksHave = 0; try { wait(); } catch (InterruptedException e) {} } } state = EATING; }The trick is to split takeForks into two pieces. The first, called forksNeeded(), is a synchronized procedure that does all the necessary manipulation of shared variables. The remaining code does not touch any shared variables that ever change, so it does not have to be synchronized.
/* This procedure finds a fork that this philosopher doesn't have and needs to request and returns its index. If no such fork exists because all forks are here it returns -1 and sets the local state to EATING. If no such fork exists because all absent forks have already been requested, it waits and tries again. */ private synchronized int neededFork() { state = HUNGRY; for (;;) { int forksHave = 0; // Number of forks currently owned for (int i = 0; i < forks.length; i++) { if (forks[i].have) forksHave++; else if (!forks[i].haveRequested) { forks[i].haveRequested = true; return i; } } if (forksHave == forks.length) { state = EATING; return -1; } try { wait(); } catch (InterruptedException e) {} } } private void takeForks() { for (;;) { int i = neededFork(); if (i == -1) return; if (phil[forks[i].neighborId].requestFork(forks[i].forkId)) giveFork(forks[i].forkId); // give myself the fork } }At the end of class, Patrick Gaffney pointed out that there's still a danger of a race condition. What happens if thread tA is preempted in A.takeForks() after its call to B.requestFork() has returned true but before it gets a chance to call A.giveFork()? At this point neither A nor B thinks it has the fork. The call B.requestFork() has updated B's data structure to indicate that B does not have it, but A.giveFork() has not had a chance to update A's variables to show that A has it. This is not necessarily a problem, but the code has to be carefully written so that it can cope with this unusual situation. For example, if tB is allowed to run next, it may become hungry, and seeing that it no longer has the fork, it may call A.requestFork(), which will find that A doesn't have the fork that is being requested. At this point, neither philosopher thinks he has the fork.