[go-nuts] Dining philosophers, deadlocks and join-calculus.
Mateusz Czapliński
I've been recently exploring various non-thread-&-lock approaches to
concurrency. That led my interest especially to a construct available
in the "join-calculus" (also apparently in Erlang, and maybe generally
in the "actors model", but I'm not sure if I get it right). The
construct is a more generalised variant of Go's "select", which allows
to wait on more than one channel, and 'receive' on the whole tuple
atomically (kind of "pattern matching" - matching one of the specified
tuples of channels, where all of them can be read, and the reading is
done atomically). As far as I understand, this model is advertised as
making it easier to avoid deadlocks. Specifically, an example
described in a pdf for the LuaPi library (tarball at
http://luaforge.net/frs/?group_id=505 ), employing the "join" feature
to solve the classic Dining Philosophers Problem, looked very
attractive to me.
Now, my core question is: does Go allow for such a "pattern-matching",
multi-channel "select"? if yes, then how to do that; and if not, then
why?
And some auxiliary questions, should anybody want to elaborate:
- am I maybe just on hype and the 'join' approach has some known
problems/issues in usage or implementation, or maybe effectiveness?
- is there a solution to the Dining Philosophers Problem advised
specially for Go language? could somebody maybe provide some code?
- if I understand correctly, such a "join" would put bigger stress on
the language's concurrency scheduler. In the Philosophers Problem,
this can probably be mimicked on programmer's side by adding a
"waiter" process, controlling who receives the forks/chopsticks/... in
what order. However, I believe that such a feature in the language
would make it easier in more complicated scenarios (with more than 2
resources/channels, or even more varied configurations), taking much
burden from the programmer. And apparently they decided to do that in
Erlang, with success. Then why not?
Thanks in advance
- Mateusz Czaplinski
--
Subscription settings: http://groups.google.com/group/golang-nuts/subscribe?hl=en
Russ Cox
> multi-channel "select"? if yes, then how to do that; and if not, then
> why?
segregate different message patterns as different typed
messages on channels. The pattern matching is necessary
in languages like Erlang because there's no other way to
manage the many messages targeting a particular process.
> - is there a solution to the Dining Philosophers Problem advised
> specially for Go language?
Russ
Ian Lance Taylor
> Now, my core question is: does Go allow for such a "pattern-matching",
> multi-channel "select"? if yes, then how to do that; and if not, then
> why?
easily write a small goroutine which gathers input from channels one
by one, and, when it sees an appropriate pattern, writes the
collection to a specific output channel. If the patterns ever change,
then it can pause after collecting each pattern and read from a
control channel to see which patterns it should collect next. I may
be missing something, but at first glance that will give you the same
power at the cost of some extra code.
Ian
Mateusz Czapliński
> > Now, my core question is: does Go allow for such a "pattern-matching",
> > multi-channel "select"? if yes, then how to do that; and if not, then
> > why?
>
> segregate different message patterns as different typed
> messages on channels. The pattern matching is necessary
> in languages like Erlang because there's no other way to
> manage the many messages targeting a particular process.
But how does message typing (you mean, e.g. passing structs via
channels, yes?) apply to atomic read from varying sets of channels?
Are you saying that whatever combination of channels from whatever
third-party modules I receive, I should squeeze all the expected
signal combinations together into one struct and dump into a single
channel, with a couple of listeners waiting on it? [see the answer to
Ian for more thoughts on that, please] Or how does the first-classness
trait help me? I feel like I don't get something...
> > - is there a solution to the Dining Philosophers Problem advised
> > specially for Go language?
>
> Buy more forks.
Ah, but I'm afraid there's one problem with good philosophers: if they
see a philosophical problem, they may stick to it, thinking and trying
to find a solution so devotely, that they would ditch the additional
forks for the sake of science. And I wouldn't want to risk letting
them starve...
On 9 Kwi, 01:48, Ian Lance Taylor <i...@google.com> wrote:
> Go does not have a pattern matching select. However, you can fairly
> easily write a small goroutine which gathers input from channels one
> by one, and, when it sees an appropriate pattern, writes the
> collection to a specific output channel.
That, I think, would be what I meant as the "waiter" for the dining
philosophers. But then I must analyze all the patterns myself and
build a "multiplexer" between a bunch of input channels and a bunch of
output channels myself. And honestly I'd prefer if the computer did
that for me; and if Erlang compiler/vm or the "join calculus compiler"
does (or am I wrong?), then it seems that someone already solved this
problem. So what are the arguments against? Or, as I asked before,
does the first-classness help me here with some trick, taking away the
burden from my arms?
Thanks
- Mateusz Cz.
Ian Lance Taylor
> On 9 Kwi, 01:48, Ian Lance Taylor <i...@google.com> wrote:
>> Go does not have a pattern matching select. However, you can fairly
>> easily write a small goroutine which gathers input from channels one
>> by one, and, when it sees an appropriate pattern, writes the
>> collection to a specific output channel.
>
> That, I think, would be what I meant as the "waiter" for the dining
> philosophers. But then I must analyze all the patterns myself and
> build a "multiplexer" between a bunch of input channels and a bunch of
> output channels myself. And honestly I'd prefer if the computer did
> that for me; and if Erlang compiler/vm or the "join calculus compiler"
> does (or am I wrong?), then it seems that someone already solved this
> problem. So what are the arguments against? Or, as I asked before,
> does the first-classness help me here with some trick, taking away the
> burden from my arms?
As far as I can see, you have to analyze all the patterns yourself
anyhow, because you have to know what to ask for. If Erlang does this
for you somehow, I'd need to see a reference to that.
The fact that channels are first class helps because you can create
arbitrary multiplexers.
The argument against permitting select to match a group of channels is
that it makes the implementation significantly more complex. Consider
the case of several select statements waiting simultaneously on
different channel groupings. How do we avoid starvation?
Ian
Russ Cox
> channels, yes?) apply to atomic read from varying sets of channels?
It's hard to know exactly what you mean without
a concrete example, but this is what I meant.
Here's a model Erlang program, from p. 181 of
Armstrong's Programming Erlang.
loop(MM) ->
receive
{chan, MM, {store, K, V}} ->
kvs:store(K, V),
loop(MM);
{chan, MM, {lookup, K}} ->
MM ! {send, kvs:lookup(K)},
loop(MM);
{chan_closed, MM} ->
true
end.
In Go, the most direct translation would define some
data types for the messages:
type Store struct {
K, V string
}
type Lookup struct {
K string
C chan string
}
And then the service loop would read from three different
channels instead of doing pattern matching on reads
from a single channel:
func loop(cstore chan Store, clook chan Lookup, cquit chan bool) {
for {
select {
case req := <-cstore:
kvs.Store(req.K, req.V)
case req := <-clook:
req.C <- kvs.Lookup(req.K)
case req := <-cquit
return
}
}
}
Having first-class channels means that it's easy to use
multiple channels for multiple kinds of messages, just like
many people have separate home and work email addresses.
In Go terms, Erlang gives each process just one channel
that it is allowed to receive from, so pattern matching is
essential as a mechanism for sorting through the incoming
messages. In Go, a goroutine arranges for different kinds
of messages to be sent to different channels and lets the
system handle the sorting.
> > Buy more forks.
>
> Ah, but I'm afraid there's one problem with good philosophers: if they
> see a philosophical problem, they may stick to it, thinking and trying
> to find a solution so devotely, that they would ditch the additional
> forks for the sake of science. And I wouldn't want to risk letting
> them starve...
My reply was only partially in jest. Go puts a strong emphasis on
being practically useful, and the most practical solutions to this
problem are to sidestep it in one way or another. If you stick with
the hypothetical, then it doesn't matter much what language you use:
the solutions are all algorithmic, not linguistic.
Russ
Mateusz Czapliński
> As far as I can see, you have to analyze all the patterns yourself
> anyhow, because you have to know what to ask for. If Erlang does this
> for you somehow, I'd need to see a reference to that.
>
> that it makes the implementation significantly more complex. Consider
> the case of several select statements waiting simultaneously on
> different channel groupings. How do we avoid starvation?
Ok, thanks very much for that; implementation complexity seems, as for
me, quite a good argument against it. And the rest of your questions
are interesting points for further exploration on my side :)
On 9 Kwi, 19:45, Russ Cox <r...@golang.org> wrote:
> > But how does message typing (you mean, e.g. passing structs via
> > channels, yes?) apply to atomic read from varying sets of channels?
>
> It's hard to know exactly what you mean without
> a concrete example, but this is what I meant.
> Here's a model Erlang program, from p. 181 of
> Armstrong's Programming Erlang.
>
> [...]
>
> > > Buy more forks.
>
> > Ah, but I'm afraid there's one problem with good philosophers: if they
> > see a philosophical problem, they may stick to it, thinking and trying
> > to find a solution so devotely, that they would ditch the additional
> > forks for the sake of science. And I wouldn't want to risk letting
> > them starve...
>
> My reply was only partially in jest. Go puts a strong emphasis on
> being practically useful, and the most practical solutions to this
> problem are to sidestep it in one way or another. If you stick with
> the hypothetical, then it doesn't matter much what language you use:
> the solutions are all algorithmic, not linguistic.
>
> Russ
Thanks for patience and kind efforts to explain the matters in simpler
words.
As for your example, it feels at first glance to be a module where the
relations between the channels can be separated quite easily into
unrelated commands. On the other hand, the example and your arguments
make me start to think that this ease of separation may happen more
often than I would expect. So I'll probably resort to some further
reading, research and experimentation, maybe to knock on your door
again should I have more questions or arguments :)
As I said before, I don't have experience in multithreaded programming
apart from basic threads-&-locks (surely not in Erlang); as deadlocks
are an enemy I face quite often there, I believed the D.P. problem to
be a good theoretical abstraction of a common real-world problem. The
join-calculus solution to that, as presented in the LuaPi PDF I
mentioned, looked quite attractive (maybe even deceivingly
miraculous?), but if you say that's rather an overly theoretical
problem, then I'll try to think more about it and see if I'm able to
find any example sounding more practical.
Anyway, when you point out at the border between language and
algorithm, it sounds like it might be enough to consider creating a
library to be used in these particular problems where such a 'complex'
scheduler sounded useful (should that be a case at all).
Thanks again to you both for participation in the discussion :)
Cheers
- Mateusz Cz.
Sonia Keys
much so I thought it would be a good exercise. I started with just
the problem description at http://en.wikipedia.org/wiki/Dining_philosophers_problem
and then looked for a natural implementation in go, without
preconceptions of other languages or techniques.
My implementation is at http://pastebin.com/YFCn95nm.
I have a goroutine for each philosopher. This made sense as a
generalized process in a resource allocation problem.
I also have a goroutine for each fork. I wanted to see if I could
avoid creating a magical table that would use resource allocation
rules to "decide" whether to "release" a fork to a philosopher. I
also wanted a distributed solution that would scale well and not be
tied to a single thread at any point. My forkPlace goroutine ends up
with no representation of the fork other than the program counter, and
with logic that does no more than model the physical location of the
fork as it is moved by the philosophers.
Between goroutines are channels, of course. Three channels made sense
to me and I bundled them in a struct that obviously corresponds to a
philosopher hand. Two hands are connected to each philosopher. Two
hands can connect to each fork. The hand struct, by the way, seems to
me the closest thing to an "object" in this program.
To construct the simulation, I create channels before "connecting"
them to philosophers and forks. Connecting amounts simply to passing
hand structs to the goroutines as parameters. Goroutines get fully
working channels they can use immediately, even if they might have to
wait a bit for creation of the goroutine on the other side of the
channel.
That's the interesting problem of representation. For the other
problem--avoiding deadlock--I chose the very simple solution of making
one of the philosophers left handed. I know, it's not fair, and there
are lots of other issues of resource allocation that could be
addressed, but it was enough to make the program run and demonstrate
the working representation of goroutines and channels.