FAQ
Hi Folks:

This is not directly a Go question but here goes. Besides this is the only
mailing list where I see a lot of people talking about (synchronous)
channel semantics :-)

My question is how useful are join patterns? However I thought I would
bounce off the Go-Nuts crowd some ideas about implementing join patterns
within a synchronous channel model.

Over a year ago, I read about join patterns in this mailing list. The
post is
https://groups.google.com/forum/?fromgroups=#!topic/golang-nuts/221X2qenpuU:
Dining Philosophers, deadlocks and Join-Calculus

Some background:

At the time, based on the algorithm in the "Implementation of Newsqueak"
and the Plan9 channel code, I implemented select for Stackless Python.
Stackless Python's channel model is based on Limbo. The main difference is
channels are a library not a language feature. I prototyped used PyPy's
stackless.py, so I can write Python with Python. I just wanted development
speed. The main point is that I am familiar with how Go channels work.

My implementation steals from the Plan9 implementation.

Using the aforementioned implementation as a base, I implemented a subset
of Polyphonic C#'s join pattern that I thought would make sense for a
Stackless Python/Go channel model. I really wanted a shorter, non function
programming implementation of the Santa Claus Problem. It also seemed that
join patterns made the DIning Philosopher Problem trivial.

A join pattern shares the same interface as a chanop (receive, send). A
join pattern internally is a conjunction of chanops. A join pattern can
consist ONLY of receive chanops.

A join pattern is ready if and only if all its chanops are ready. Ready
means that an operation will not block. At this time, data transferred. The
semantics are all-or-nothing: data is transferred from all the
participating channels or no data is transferred.

Now this allows a join pattern to be used with the select algorithm without
change. Select now can support something that I believe is called
disjunctive-normal-form. Good for saying I want to wait for all nine
reindeer channels to complete OR the 10 Choose 3 combinations of a group of
three from a team of ten elf channels (yes I wrote this for the Santa Claus
Problem).

maybe in Go, a join pattern could look like

select {
case r[0] = <- dasher & r[1] = <- dancer & r[2] <- prancer .... r[8]
= <- rudolph:
// process reindeer
case e[0] = <- elf[0] & e[1] <- elf[1] & e[2] <- elf[2]:
// process a group
case e[0] = <- elf[0] & e[1] <- elf[1] & e[3] <- elf[3]:
// you get the idea.

To avoid race conditions, inside the "scheduler," I implement the following
strategies:

1) postpone rendezvous - that is if there is there is a sender for a
receiver that is participating in a join pattern, then I
delay/defer/postpone the rendezvous (if rendezvous is the right term). I
don't cause a data transfer. Rather I will increment the join pattern
count, mark the sender as participating in a join pattern and block it.

2) Message steal (this trick is mentioned in papers but not well described
so I improvised):I if there is a blocked sender participating in join
pattern and a receiver comes along, the sender is removed from the join
pattern and its count is decremented. A data transfer occurs as if a normal
channel rendezvous.

( 3 - I thought about banning selects that have a case with a channel.send
and the same channel participating in a join pattern)

Again, I have implemented a subset of join patterns tuned for synchronous
channels. The work is far from finished. I have implemented problems I have
seen in papers ( Dining Philosophers and Santa Claus). However this does
not mean it is necessarily a good idea (i.e., in stackless circles, one has
to explain why select is needed).

Thoughts?

I also thought about writing a version for Go.

Cheers,
Andrew

--

Search Discussions

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedOct 23, '12 at 7:44p
activeOct 23, '12 at 7:44p
posts1
users1
websitegolang.org

1 user in discussion

Andrew Frances: 1 post

People

Translate

site design / logo © 2021 Grokbase