----- Original Message ----- From: "Ralph Johnson" johnson@cs.uiuc.edu To: "The general-purpose Squeak developers list" squeak-dev@lists.squeakfoundation.org Sent: Saturday, October 27, 2007 9:00 PM Subject: Re: Concurrent Futures
What are all the classes of possible deadlocks?
The first one I thought of was the Dining Philosopher's problem. Google showed me ttp://www.erights.org/e/satan/index.html
This is the first time I've read that link.
This is an interesting article. It uses capabilities to ensure freedom from deadlock. If a philosopher has a fork for two long, the system will revoke his capability for the fork.
This problem is much more than a deadlock problem. It is a resource sharing problem which includes a liveness problem. It seems that it is classically solved with a semaphore representing each fork, as well as a strategy to ensure liveness. See the section on page 93 in http://www.greenteapress.com/semaphores/downey05semaphores.pdf
If E was automatically free from deadlock, why was this solution so complex?
There is no danger of deadlock. It is impossible, since there are no Semaphores. They still run into the problem of shared resource utilization and livelock/starvation/liveness issues. E doesn't claim the address those in its language. Perhaps its claim to avoid deadlock is reduced in importance since it can experience other concurrency problems, but I still think it's a neat feature.
I agree it seems complex, but they are revoking the fork after a delay. The classical problem states that each philosopher eats for a finite time (see above reference). They also provide an implementation for the philosopher and the act of eating, by getting shrimp from the plate with the forks, and they prevent unauthorized access. Finally, they restrict access to references to the classes, like with the protections for access to the plate: only the fork knows the plate, not the philosopher.
Note that they say this was done with a previous version of E, so it may be somewhat different in current E. I really don't know the language that well, so I couldn't say.
Here is a pared down version, that ignores a lot of other stuff and just shows the resource acquisition, but also includes the revocation after timeout. It is 5 methods, 3 on the Philosopher and 2 on the ForkDispenserMaker, which could easily be seen as methods in Smalltalk. I don't see how a language could make it easier, but a class library could.
They are doing these jobs it seems:
ResourceDispenser "ForDispenserMaker" - resourceRequestCallback "serveOther" - resourceRequest "forkPlease" ResourceConsumer "Philosopher" - resourceAcquisition "startEating" - acquisitionCallback "hereIsYourFork" - useResources "eat" oh, yes they also have thye following referenced in code: Resource - revoke
Below is my scratch code (it is incomplete, because I eliminated state variables and other methods).
Regards, Rob
def ForkDispenserMaker(mySource) { to forkPlease(who) { if (nowServing == null) { nowServing := who nowServing <- hereIsYourFork(theFork) } else if (nowServing == who) { nowServing <- hereIsYourFork(theFork) } else { myTimer after(10_000, def listener noticeTimeout() { theFork <- revoke serveOther ()) } } def serveOther() { if (nowServing == firstPhilosopher) { nowServing := secondPhilosopher } else { nowServing := firstPhilosopher } nowServing <- hereIsYourFork(theFork) } }
def NicePhilosopherMaker() { to startEating { firstForkDispenser <- forkPlease(self) secondForkDispenser <- forkPlease(self) } to hereIsYourFork(theFork) { if (firstFork == null) { firstFork := theFork } else { secondFork := theFork eat() } } def eat() { *** } }