[dmd-concurrency] Shutdown protocol

[Kevin Bealer]

On Thu, Jan 21, 2010 at 1:41 AM, Andrei Alexandrescu <andrei at erdani.com>wrote:

> Sean Kelly wrote:
>
>> On Jan 20, 2010, at 3:54 PM, Andrei Alexandrescu wrote:
>>
>>  Sean Kelly wrote:
>>>
>>>> On Jan 20, 2010, at 11:26 AM, Andrei Alexandrescu wrote:
>>>>
>>>>> I don't think so. When the two instances of the copy threads finish
>>>>> reading and sending messages to their writers, they return. As a
>>>>> consequence, wait returns. As a consequence, main finishes.
>>>>>
>>>>> At this critical point, we have the following situation:
>>>>>
>>>>> (a) main has finished, therefore the shutdown mode is in effect
>>>>>
>>>>> (b) There are a number of messages in flight containing buffers waiting
>>>>> to be written in the two files.
>>>>>
>>>>> The important thing to do is to NOT throw shutdown as long as calls to
>>>>> receive() would not block.
>>>>>
>>>> That sounds like a horrible race problem.
>>>>
>>>
>>> Not at all. On the contrary, it's the stark opposite of a race:
>>>
>>> * Readers only finish after they have sent all messages they had to send.
>>>
>>> * Application doesn't shutdown until all sent messages have been acted
>>> upon.
>>>
>>
>> If the reader is slower than the writer it's entirely possible that the
>> writer will block on receive() during processing.  The receiver really only
>> knows that it's done when it receives a message to that effect from the
>> reader thread. If the threads were linked then this might be a "normal"
>> shutdown message, for example.  Funny now that we're talking about this how
>> many use cases I'm thinking of for bidirectional linking.
>>
>
> I don't think so. Say the reader is moving at 1 byte/millenium and the
> writer is moving at 1 petabyte/femtosecond. So the writer will spend
> virtually all of its time blocked in receive().
>
> At the point the reader is finishing, the following actions happen in
> causal order:
>
> 1. The reader sends the last data message to the writer
>
> 2. The reader's function returns to main
>
> 3. main returns
>
> Regardless of the relative speeds of the reader and the writer, causality
> above stays the same. There can be no race.
>
>
> Andrei
>

Assuming one reader.  What about a scenario where there are several each of
readers and writers, maybe the data flow of 'diff' as a simple example?

In this case we should assume that main knows the tids of all the readers
rather than running them directly as in the two thread file copy example.
More generally, for any set of queues, main would need to knows about the
side that has to finish for completeness to be guaranteed, which seems like
it will be the side that is filling the queue, right?

So lets say that threads will normally fall into the three camps, that I'll
call producers, filters and processors.  Producers are anything that
produces data into the message passing system but is not feeding from a
queue to get its orders.  Filters are anything that is queue or
message-event driven but also write their results to a queue / mailbox, and
consumers, anything queue-fed but not sending output into queues.  Queue fed
here means not just that they read from queues some of the time but that
they can always be expected to look at the queue for their next input and
aren't going to be done until the queue is 'dry' or contains a shutdown
command.

Given that blob of definitions, what does main need to do?  I would say that
we can treat the whole graph of components as directional.  The consumers
are downstream, the filters are upstream, and the producers are as far up
the creek as you can get.  I think main needs the tids of all the producers
and needs to either wait on all of them for shutdown messages or tell them
all to shut down when needed.

Hmmm...

Maybe we can allow the threads to tell us these relationships -- threads
could specify other threads they depend on or simply are watching.  When any
(or all, configurably?) of a thread's dependencies disappear the thread gets
an OOB message which it can handle if needed.  All threads default to
depending on main; however, main could store its Tid somewhere and maybe a
Thread could even use this to intentionally remove this dependency (e.g. it
doesn't wanna die when main goes away).  Similarly, a thread could find out
which other threads depend on it.

Main could check if it has any dependents, if desired... (these last bits is
kind of off the cuff, so maybe there are huge problems with them.)

Kevin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/dmd-concurrency/attachments/20100121/74e8f6d2/attachment-0001.htm>