The Dining Philosophers
Emlyn
includes a full working implementation of Semaphores using the
Datastore, and implementation of flawed and successful solutions to
the classic Dining Philosophers problem using Semaphores.
http://appenginedevelopment.blogspot.com/2011/10/dining-philosophers.html
Fun for hard core comp sci types ;-)
--
Emlyn
http://my.syyn.cc - Synchonise Google+, Facebook, WordPress and Google
Buzz posts,
comments and all.
http://point7.wordpress.com - My blog
Find me on Facebook and Buzz
Kyle
implement semaphores?
-Kyle
On Oct 23, 6:23 am, Emlyn <emlynore...@gmail.com> wrote:
> Here's a new AppEngine article from me, "The Dining Philosophers". It
> includes a full working implementation of Semaphores using the
> Datastore, and implementation of flawed and successful solutions to
> the classic Dining Philosophers problem using Semaphores.
>
> Fun for hard core comp sci types ;-)
>
> --
> Emlyn
>
> Buzz posts,
> comments and all.http://point7.wordpress.com- My blog
Emlyn
> Is there a reason that you didn't use the memcached service to
> implement semaphores?
>
> -Kyle
I'm assuming you mean Memcache?
Well, two things. Firstly, as far as I know there are no transactions
or locks or anything like that for memcache, so where you need a
critical section, how will you implement it? (This is not actually a
rhetorical question; is there a way?)
Secondly, you can't trust Memcache to stick around, as far as I know.
If one task constructs a semaphore in memcache, then will that still
be there when another tasks tries to wait() on it?
Anything that is implemented in terms of Semaphores really needs to be
able to rely on them to behave. It might be good to come up with an
alternative construct that can tolerate memcache's behaviour, I'm
totally open to suggestions.
>
> On Oct 23, 6:23 am, Emlyn <emlynore...@gmail.com> wrote:
>> Here's a new AppEngine article from me, "The Dining Philosophers". It
>> includes a full working implementation of Semaphores using the
>> Datastore, and implementation of flawed and successful solutions to
>> the classic Dining Philosophers problem using Semaphores.
>>
>> http://appenginedevelopment.blogspot.com/2011/10/dining-philosophers....
>>
>> Fun for hard core comp sci types ;-)
>>
>> --
>> Emlyn
>>
>> http://my.syyn.cc- Synchonise Google+, Facebook, WordPress and Google
>> Buzz posts,
>> comments and all.http://point7.wordpress.com- My blog
>> Find me on Facebook and Buzz
>
> --
> You received this message because you are subscribed to the Google Groups "Google App Engine" group.
> To post to this group, send email to google-a...@googlegroups.com.
> To unsubscribe from this group, send email to google-appengi...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/google-appengine?hl=en.
>
>
--
Emlyn
http://my.syyn.cc - Synchonise Google+, Facebook, WordPress and Google
Buzz posts,
comments and all.
http://point7.wordpress.com - My blog
Brandon Wirtz
Rice and Chopsticks. I proposed two solutions...
One that worked on position and timing...
The other was the "Python 2.7" fix.
doonce(BreakChopSticks);
do{think;}
while(hungry!=true)
Cut the chopsticks in half and let everyone eat half as fast, but think on
their own schedule. The philosophers will be happier, and the code is
easier to write.
Murph
def add(self, key, value, time=0, min_compress_len=0, namespace=None):
"""Sets a key's value, iff item is not already in memcache.
def replace(self, key, value, time=0, min_compress_len=0, namespace=None):
"""Replaces a key's value, failing if item isn't already in memcache.
def cas(self, key, value, time=0, min_compress_len=0, namespace=None):
"""Compare-And-Set update.
def incr(self, key, delta=1, namespace=None, initial_value=None):
"""Atomically increments a key's value.
def decr(self, key, delta=1, namespace=None, initial_value=None):
"""Atomically decrements a key's value.
It seems to me the you could carefully use the above in various creative ways to implement this, if you require frequent use and the datastore costs would be prohibitive for it.
Emlyn
closely enough recently). You could absolutely build a semaphore using
those methods (cas would do the job nicely). Except of course that it
could disappear at any moment. I can't help thinking that there must
be some way to cope with that, however. Worth a ponder!
> --
> You received this message because you are subscribed to the Google Groups
> "Google App Engine" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/google-appengine/-/cAlYR6jxlogJ.
Emlyn
Assume we can implement semaphore entirely in memcache, ignoring the
fact that it can be flushed.
Then, to cope with being flushed, we could have an idea of a Semaphore
as being in one of three states; Ok, Gone and Restarting.
Ok is just normal operation
Gone is when you know it's been flushed
You detect Gone by noticing the problem when you try to touch the
Semaphore (in Wait() and Signal() calls). You restart the Semaphore.
Restarting is a period where you are trying to get back to Ok state.
Basically, the idea will be that if the Semaphore disappears, we go
into a state (Restarting) where we are going to wait for a while until
we can know that the semaphore should be unused, then reset it to it's
initial state (ie: unused) and we're good to go again. The way we'll
do this is to wait a bit for anyone who might be using the semaphore
to finish, and then once we've waiting long enough, we just assume
everyone is done and proceed. It's a timeout, and it means imposing a
maximum time length on holding the Semaphore that callers need to
obey.
Semaphores have two bits of internal state which needs to be maintained:
- Counter
- Wait List
The Wait list really needs to be in the datastore, because if it gets
flushed there's just no way to reconstitute it, Waiters will be lost
forever.
But the counter has more promise.
Try an algorithm like this:
Semaphores only have two methods which need to accomodate these states:
Wait()
Touch the semaphore. What state are we in?
OK: Proceed as normal (if the counter is above zero then decrement
it and proceed, else suspend on the wait list)
GONE: Reconstruct the semaphore in Restarting state. Suspend on the
wait list.
RESTARTING: Suspend on the wait list.
Signal()
Touch the semaphore. What state are we in?
OK: Proceed as normal (if there is anyone on the wait list, awaken
one. Otherwise, just increment the counter)
GONE: Reconstruct the semaphore in RESTARTING state. Increment the
counter. If it's equal to TokenMax, then Start the semaphore.
RESTARTING: Increment the counter. If it's equal to TokenMax, then
Start the semaphore.
Semaphores are extended as follows:
A reconstructed Semaphore in RESTARTING state is initialised with Counter = 0.
We are going to restart the semaphore by
- defining a maximum length of time that a Semaphore token can be held
(if you're using Front End tasks, just set it longer than the maximum
task length).
- when we restart, we schedule a Start task for a time in the future
equal to the maximum task length.
- When the Start task runs, it checks the Semaphore. If it's still in
RESTARTING state, it Starts the Semaphore.
- There is an ABA problem here. A Start task is scheduled, the
Semaphore restarts before the task runs, then goes back into GONE and
RESTARTING again (and another Start task is kicked off), then the
original Start task runs and prematurely wakes the Semaphore. Fix this
by adding a StartTaskID (uuid) to the Semaphore, generate a new one
each time the Start Task runs, and pass it to the Start Task. An old
StartTask will have the wrong uuid and can terminate itself based on
that.
Start the Semaphore:
Either in the Start Task, or as the result of a Signal, we've
determined that it's ok to Start the semaphore. So set the Counter to
MaxCounter and change the state to OK. If there is anyone on the Wait
List, wake as many of them as the counter allows, decrementing the
counter for each one.
===========
I think this approach can work, and the cool thing is that the counter
and the state should be implementable in Memcache. If the resource
you're using isn't normally under contention (very commonly this is
true, contention is unusual), then your most common operations will be
in Memcache and wont touch the datastore. This also assumes that cache
flushing is uncommon (if it flushed often, then it should still be
correct, but the performance will be poor, because the restarting
process is pretty slow). If the cache flushes really, really often
(sub second?) then you'll starve, but I don't think memcache does
that!
Any thoughts?
Brandon Wirtz
state to instance memory (basically free), if Memcache is flushed detect and
upload last state to memcache.
-----Original Message-----
From: google-a...@googlegroups.com
[mailto:google-a...@googlegroups.com] On Behalf Of Emlyn
Sent: Thursday, October 27, 2011 5:04 PM
To: google-a...@googlegroups.com
Subject: Re: [google-appengine] Re: The Dining Philosophers
Emlyn
> I would think that it would make more sense to store the last read Memcache
> state to instance memory (basically free), if Memcache is flushed detect and
> upload last state to memcache.
There's no way to guarantee it'd be there, is there? The task that
runs and find out that there's no memcache might be in an entirely new
instance.