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