Critique my two implementations of the dining philosophers problem

[Adit Bhargava]

Here are two solutions to this classic problem.

In the first one, the forks are actors. The way I pick up two forks is by calling `fork.future.lock` and then waiting for the result:

https://gist.github.com/egonSchiele/5565704

This one seems more idiomatic, but I'm blocking when I take the forks, correct? So this implementation *could* deadlock (although I haven't seen this happen yet).

In this second one, the forks are mutexes. If I can't lock the mutex, I just try again later instead of blocking:

https://gist.github.com/egonSchiele/5565713

But this seems wrong because Celluloid is supposed to shield me from mutexes.

So my question is, how would I make these more idiomatic and correct?

Thanks for your help!

Adit

[Adit Bhargava]

Looking this over, I guess I could generalize this question by asking: how do I synchronize two resources using actors? That's not a celluloid-specific question, but this seems like a good place to ask it.

[Tim Carey-Smith]

On May 13, 2013, at 1:58 PM, Adit Bhargava <blueman...@gmail.com> wrote:

> Here are two solutions to this classic problem.
> In the first one, the forks are actors. The way I pick up two forks is by

> calling `*fork.future.lock*` and then waiting for the result:
>
> *https://gist.github.com/egonSchiele/5565704
> *

>
> This one seems more idiomatic, but I'm blocking when I take the forks,
> correct? So this implementation *could* deadlock (although I haven't seen
> this happen yet).
>
> In this second one, the forks are mutexes. If I can't lock the mutex, I
> just try again later instead of blocking:
>

> *https://gist.github.com/egonSchiele/5565713
> *

>
> But this seems wrong because Celluloid is supposed to shield me from
> mutexes.
>
> So my question is, how would I make these more idiomatic and correct?
>
> Thanks for your help!

An interesting discussion point indeed!

I would suggest that Celluloid is providing a new way of developing concurrent/parallel applications.

Given this, you'd want to first consider using the high-level constructs, Actors combined with sync and async calls and futures.

If these constructs do not meet your needs, then dropping down and using the primitives inside Celluloid.
These are Conditions, Calls, Mailboxes and friends.

Using the Mutex to manage the locking is breaking the underlying assumptions of Celluloid and using a primitive which Celluloid primitives use themselves.

The first solution is a better solution in my opinion as it uses very high-level constructs.
A more efficient solution might be to use a Condition instead of a Future.

A sidebar would be that over the next while (2 weeks to a month) we'll be hopefully making changes which can show some of the more idiomatic uses of Celluloid primitives.
One of these is the question of bare actors without an object. https://gist.github.com/tarcieri/5550447
The other would be a Pool/Router built on this bare actor. https://github.com/halorgium/celluloid-coordinator

I have some examples which I have written and listed on our wiki.
https://github.com/celluloid/celluloid/wiki/Elsewhere-on-the-Internet

I hope this helps. I'd love to see an example of this solution implemented using Condition.

Ciao,
Tim

[Adit Bhargava]

An interesting discussion point indeed!

I would suggest that Celluloid is providing a new way of developing concurrent/parallel applications.

Given this, you'd want to first consider using the high-level constructs, Actors combined with sync and async calls and futures.

If these constructs do not meet your needs, then dropping down and using the primitives inside Celluloid.
These are Conditions, Calls, Mailboxes and friends.

Using the Mutex to manage the locking is breaking the underlying assumptions of Celluloid and using a primitive which Celluloid primitives use themselves.

The first solution is a better solution in my opinion as it uses very high-level constructs.
A more efficient solution might be to use a Condition instead of a Future.

A sidebar would be that over the next while (2 weeks to a month) we'll be hopefully making changes which can show some of the more idiomatic uses of Celluloid primitives.
One of these is the question of bare actors without an object. https://gist.github.com/tarcieri/5550447
The other would be a Pool/Router built on this bare actor. https://github.com/halorgium/celluloid-coordinator

I have some examples which I have written and listed on our wiki.
https://github.com/celluloid/celluloid/wiki/Elsewhere-on-the-Internet

I hope this helps. I'd love to see an example of this solution implemented using Condition.

Ciao,
Tim

Thanks for your response, Tim! So if the first solution is better, why doesn't it deadlock? Because we could go into a situation where every Philosopher is holding a left fork and waiting for a right fork, correct? What am I missing?

[Adit Bhargava]

Ok, after thinking about this for a while, I'm realizing that this problem is ill-suited for actors. Actors are all about unshared state, and this problem involves shared state: the forks. So actors don't give you much in this scenario; you can still have deadlock while trying to get two forks for a philosopher. What I was really looking for was something like `Concurrency::join` as used here[1] but that has nothing to do with actors afaict.

[1] http://msdn.microsoft.com/en-us/magazine/dd882512.aspx#id0400008

[Tony Arcieri]

On Mon, May 13, 2013 at 6:05 PM, Adit Bhargava <blueman...@gmail.com> wrote:

Ok, after thinking about this for a while, I'm realizing that this problem is ill-suited for actors.

That isn't true at all. The problem is that you're not using actors to represent all of the concurrent state holders in the system.

Try making Table an actor, since it's holding an awful lot of relevant state. Here's an example that does this... may not be the greatest, but it shows you the idea:

https://gist.github.com/bugant/4984042

--
Tony Arcieri

[Adit Bhargava]

Oh duh. Thank you!

[Adit Bhargava]

Armed with this knowledge, I wrote up a blog post: http://adit.io/posts/2013-05-15-Locks,-Actors,-And-STM-In-Pictures.html

Thanks a lot for your help!

Adit

[Ben Lovell]

This is way beyond awesome.

--
You received this message because you are subscribed to the Google Groups "Celluloid" group.
To unsubscribe from this group and stop receiving emails from it, send an email to celluloid-rub...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Tony Arcieri]

Wow! That's some amazing why-esque stuff :D

--
Tony Arcieri

[Tim Carey-Smith]

Love it.
I want more!