On 28/10/2007, Andreas Raab andreas.raab@gmx.de wrote:
Ralph Johnson wrote:
If E was automatically free from deadlock, why was this solution so complex?
Because it's trying to illustrate three three issues at once (security, capabilities, concurrency) and consequently fails to illustrate either one very well :-(
It is trivial to solve this problem via event-loop concurrency though. Consider a class Table with operations "grabLeftFork:", "grabRightFork:" (which take a seat index as argument and return the fork or nil). You can now implement the dining philosophers "Croquet style" as follows:
Philosopher>>eat "Start eating" | leftForkPromise rightForkPromise |
"Try to aquire the left fork first" leftForkPromise := table future grabLeftFork: seat. leftForkPromise whenResolved:[:leftFork|
"If we couldn't get the left fork, we need to decide what to do. Simply retry later but use a random amount of time to avoid live-lock" leftFork ifNil:[^(self future: self randomMSecs) eat]. rightForkPromise := table future grabRightFork: seat. rightForkPromise whenResolved:[:rightFork| rightFork ifNil:[ "Same as before, but return the fork first" table future returnLeftFork: seat. ^(self future self randomMSecs) eat "still hungry" ] ifNotNil:[ "We got both forks, eat" state := #eating. "And return the forks when time is up" ^(self future: self timeToEat) returnFork: leftFork and: rightFork ]. ].
].
Note that there is no wait anywhere in the above - the only thing that exists are #future sends that schedule messages to be executed at some point later. Because of this, the philosopher never really "waits" for anything; he will happily keep thinking (or grumbling ;-) until he obtains the forks. Even *while* he is eating one could schedule an emergency request to "drop those forks" if that were necessary.
Cheers,
- Andreas
A small correction: the problem of dining philosophers are about how to share a limited resources (forks) among consumers (philosophers) effectively to prevent starvation of any of them. And your solution are based on 'nice' behavior of philosopher, which drops the first fork, when he's unable to obtain second one. Now imagine a greedy philosopher, who grabs the first fork and never hang it over until he obtain second one and done eating. This is a good illustration that you must not pass responsibility of resource management to consumers - you must manage them yourself (of course, if you want to prevent any kind of deadlocks/resource starvation).
A 'bad' behavior is much more probable , because most developers tend writing a code in simple imperative style, like: do this, after done it, do that. And understanding that they code can contain problems (deadlocks or whatever) comes in mind only after problem shows itself. And considering that deadlocks are very hard to track and reproduce they'll never know what may cause it :)