Hi Peter,
I guess this is the difference between developing something with a formal
model up front and without it. Erlang is nice compared with many other
alternatives, but it remains flaky as you nicely pointed out. This has
probably to do with a SDL-related history (the telecom modeling standard)
whereby you also send messages from sending tasks to mailboxes tied in with
a receiver task. The result is a long case statement at the receiver: not
scalable and whenever something needs to be changed, a lot of programming
work.
In this respect, CSP (but seen as a formal model, not an implementation) is
much better. And it was pivotal to decouple the processes via channels. The
limitations are that the channel semantics are a bit poor for real-world
protocols and systems.
Comes in the "Hub", a result of the formal development of OpenComRTOS (using
TLA+, CSP based). The hub has several faces. In its simplest form, it acts
like a channel (exchanging packets upon synchronisation). In its general
from it is more like a Guarded Action. Tasks/processes synchronise in the
hub following a boolean condition and then an action is activated. The
simplest action is that the tasks/processes reschedule, but it can be a lot
more. E.g. synchronisation is when a sensor measures a value higher than a
threshold value and the action is to start a motor. Standard services are
Events (binary), Semaphores (counting), FIFOs, Resources (like mutex),
Memory Pools, Ports, ... Very important is that the task/processes never
interact directly, but only via a hub. Hence the hub decouples
tasks/processes and as a result (also because there is an underlying comm
layer), hubs and tasks/processes can be placed anywhere in a network of
processors (you could place a hub on the moon if you had a comm link with
changing anything in the program).
This mechanism is implemented in C in OpenComRTOS, but Bernhard also made a
proof of concept in phyton. It is really language-agnostic. The C-version is
only about 5 KB/node. Download the Win32 version* if you want to play. There
is also a book from Springer*.
OK. Everything is compile-time defined (like in occam), except the
scheduling is dynamic and distributed. This is good for safety critical
applications. Nevertheless, we would like to see a more dynamic version.
Might require a name server and then we have the issue that the name server
must be distributed and the system needs to be fault tolerant . This is what
Erlang does well (and proven in use). But Erlang needs quite a lot of
resources (like so many alternatives). Can we do it in 10 KB? Formally
proven and elegant to use? Open for cooperation.
Best regards,
Eric Verhulst
*
www.altreonic.com-----Original Message-----
From: Mailing_List_Robot [mailto:sympa@xxxxxxxxxx] On Behalf Of P.H.Welch
Sent: Friday, February 24, 2012 8:34 PM
To:
matt.pedersen@xxxxxxxxCc:
crg-group@xxxxxxxxxx;
java-threads@xxxxxxxxxx;
occam-com@xxxxxxxxxx;
P.H.Welch@xxxxxxxxxx;
plas-group@xxxxxxxxxxSubject: Priority receives in Erlang
Dear Matt, PLASmids, CRGers, occam-com, java-threads, et al.,
Apologies for multiple sends - we must rationalise our mailing lists!
I'm getting to grips with Erlang. I'm puzzled by some things so am seeking
feedback on my understanding. Please respond if anything below seems wrong
or unfair! I'd be especially grateful for pointers to Erlang literature
that's relevant. Thanks.
Question 10.15 at:
http://www.erlang.org/faq/academic.htmlasks: "Can a process receive messages with varying priorities?".
The answer is "Sure" ... but what is offered looks a little wobbly:
receive -> %% code A
{priority_msg, Data1} -> priority (Data1)
after 0 ->
receive
{priority_msg, Data1} -> priority (Data1)
{normal_msg, Data2} -> normal (Data2)
end
end.
Matt: this is exactly the structure of code used in the Erlang Santa example
on our Santa website (with 'reindeer' instead of 'priority_msg'
and 'elves' instead of 'normal_msg').
Race Hazard
===========
I don't like the answer because of a classic race-hazard.
Suppose there's a 'normal_msg' sitting in the mailbox of this process and no
'priority_msg' and let the code start executing.
The poll (in the opening receive with zero timeout) fails to find a
'priority_msg'. Control returns to the program code and it heads off into
the timeout branch (another receive).
While this is happening, a 'priority_msg' arrives in the mailbox - this was
the result of parallel activity in another core/machine (or another process
could have been swapped into the core our process was using and sent the
message).
Anyway, our process eventually gets to its nested receive. 'normal_msg'
is ahead of the just-arrived 'priority_msg' in the mailbox queue and will be
the one selected by that receive.
So, we had a 'priority_msg' and a 'normal_msg' in our mailbox and chose to
take the 'normal_msg', :(. That's not good.
Now, you could argue that the 'priority_msg' was just too late for us, so
that it's OK that we didn't take it - we'll take it next time we loop back
to this code for sure.
I don't like that argument though. We've used two language primitives here
in *sequence* (assuming the opening poll fails). Anything can happen in
between those primitives being applied - circumstances can change between
the first ending and the second starting. We can assume atomicity in
dealing with circumstances by each primitive, but not by two in sequence.
The "just too late" appeal is weak. A *long* time could have passed between
the first poll and the second receive (e.g. if this process was swapped out
and there were thousands of other runnable processes to be scheduled before
our process gets back in). There could be hundreds of 'priority_msg's in
the mailbox (sent by panicking processes wondering why our process wasn't
responding) before that second receive gets going and they will all be
ignored in favour of the 'normal_msg', because they will all be behind it in
the mailbox queue.
To do this securely, Erlang needs a way to bind the sequential use of the
polling receive and timeout receive into atomic operation (unlikely) or a
Built-in-Function (BiF) that does a "pri-receive" atomically (not hard).
Performance Hazard
==================
The cost of this priority-receive pattern (code A, above) seems horrible!
The mailbox is searched twice if the poll fails, which is bad news if the
queue is lengthy. Maybe the compiler can spot the pattern and do something
clever: like record the first 'normal_msg' it finds in the queue while
searching for a 'priority_msg' ... if it doesn't find the latter, it can
immediately go for the former.
Even if it can do this, the effort of trawling through the whole queue in
the first place seems awful!
If we have a process processing 'normal_msg's all the time but always having
to look out for, and immediately deal with, a 'priority_msg', the costs look
daunting.
Compare this with occam:
PRI ALT -- code B
priority ? msg
... action
normal ? msg
... action
In the case when 'priority' is ready, the processing time between the start
of the PRI ALT and start of the 'priority' action is nanoseconds (no channel
gets enabled).
In the case when 'priority' is not ready and 'normal' is ready, the time to
get to the 'normal' action is barely a few more nanoseconds than the above
(again, no channel gets enabled).
In the case when neither channel is ready, both channels fail the initial
check and both then get enabled (assuming nothing arrives).
This takes some tens of nanoseconds - probably much less than 100?
When something arrives on either channel, both channels must be disabled
before the choice is made and relevant action started
- some tens of nanoseconds again.
Such costs rise linearly as the number of channels in the PRI ALT increases.
The Erlang costs rise super-linearly (from a high base) ... unless the
compiler and run-time are very clever indeed. The code is not pleasant to
write (I'm extending the pattern from code A, but I'm not at all sure this
is right?):
receive -> %% code C
{priority_0_msg, Data0} -> priority_0 (Data0)
after 0 ->
receive
{priority_0_msg, Data0} -> priority_0 (Data0)
{priority_1_msg, Data1} -> priority_1 (Data1)
after 0 ->
receive
{priority_0_msg, Data0} -> priority_0 (Data0)
{priority_1_msg, Data1} -> priority_1 (Data1)
{priority_2_msg, Data2} -> priority_2 (Data2)
after 0 ->
receive
{priority_0_msg, Data0} -> priority_0 (Data0)
{priority_1_msg, Data1} -> priority_1 (Data1)
{priority_2_msg, Data2} -> priority_2 (Data2)
{priority_3_msg, Data3} -> priority_3 (Data3)
end
end
end
end.
In this, we are looking to receive one of four possible message types, but
giving priority to 'priority_0_msg', then 'priority_1_msg' etc.
Race hazards are present. There are lots of scenarios (similar to, and more
than, those for code fragment A) in which a lower priority message is
selected over a higher one sitting in the mailbox. Let's ignore these for
now (since we are looking at performance).
The obvious implementation requires four sweeps through the mailbox queue,
with more complex search requests each time. Maybe a clever compiler could
get the run-time to do this in a single sweep ... but that would be pretty
clever!
In occam:
PRI ALT -- code D
priority.0 ? msg
... action
priority.1 ? msg
... action
priority.2 ? msg
... action
priority.3 ? msg
... action
The worst case (when nothing is ready) is implemented by a fast initial
check through the four channels, then an enable sweep. When/if something
arrives, there is the disable sweep.
The number of these sweeps (check/enable/disable) is independent of the
number of (prioritised) message sources. The "obvious" Erlang
implementation requires one sweep through the process mailbox for each
(prioritised) message type, with increasingly complex checks each time.
What about a replicated prioritised receive? In occam:
PRI ALT i = 0 FOR n -- code E
priority[i] ? msg
... action
In Erlang, extend the pattern from code C. Define the message structure:
{atom, level, data}
where 'atom' is some identifying atom for the messages we want to take,
'level' is a priority level (0 = highest, 1 = next highest, ...) and 'data'
is the real data in the message. Define the functions:
%% code F
pri_receive (my_atom, max_level) -> pri_receive (my_atom, 0, max_level)
pri_receive (my_atom, level, max_level) ->
if
(level < max_level) ->
receive
{my_atom, i, data} [when i <= level] -> {i, data}
after 0 ->
pri_receive (my_atom, level + 1, max_level)
end;
true ->
receive
{my_atom, i, data} [when (i <= level)] -> {i, data}
end
end.
To wait for 'n' levels of priority and, when one is received, respond with
some 'priority' action:
priority (pri_receive (my_atom, n - 1))
That's not too bad (if I've got the when-guard syntax and semantics right).
In the worst case, it still needs one sweep through the mailbox for each
priority level ... and it still suffers numerous race hazards. Implementing
'pri_receive' as a BiF could eliminate those hazards and make it *much*
faster.
By the way, the when-guards on the receive patterns above are neat. They
let a process inspect a potential match of a message in its mailbox to see
if the information it contains is acceptable: if not, the match fails and
the message is left in the mailbox. This is something that can be expressed
in CSP, but not in any existing CSP language or library.
Erlang and occam
================
Erlang processes are *a bit* like occam-pi processes that only have a single
input channel on which all messages must arrive. The other end of that
channel is SHARED and MOBILE, corresponds to the Erlang concept of unique
process identifier (pid) and must be given to any process that needs to send
it a message. To send a message to another process, it must be given the
SHARED MOBILE end (i.e. pid) of that other process.
This seems a bit constraining! If Erlang process could be equipped with
multiple named mailboxes, it could do the priority receive much more easily
(for the programmer) and much faster (for the run-time system).
Sending messages to named processes was the original CSP idea (Hoare, 1978)
This was dropped in favour of communication via channels (independent of
processes) in the revised CSP (Hoare, 1983) and occam language (May, 1983).
Erlang has not undergone such a revision.
Having single mailboxes and named target processes (with names distributed
either explicitly as 'pid's or magically as registered 'names') means there
is no code that represents process networks, which feels like a bad loss.
It means networks can grow without discipline (spaghetti). There is no
concept of networks within networks - i.e. processes whose implementation is
a network (bound within the confines of the process being implemented)
- i.e. processes with the constraints of physical components (no spaghetti).
Thoughts?
Peter.