Concurrent Futures
Rob Withers
reefedjib at yahoo.com
Sun Oct 28 06:59:04 UTC 2007
----- Original Message -----
From: "Ralph Johnson" <johnson at cs.uiuc.edu>
To: "The general-purpose Squeak developers list"
<squeak-dev at 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() {
***
}
}
More information about the Squeak-dev
mailing list
|