activityflow.html

Concurrent Programming in Java

    }
  }
</pre>


It's possible, and in some contexts very common to merge buffering
with stage-based Push or Pull-style processing; for example designs in
which Buffers also serve as push-style stages, attempting to pass
along held messages whenever their consumers are ready.



<h3>Choosing Forms</h3>

Most often, the context of an activity flow dictates
its form. For examples of the most straightforward cases:

<ul>
  <li> In ``demand-driven'' contexts, the flow is initiated by
      its ultimate sink (or perhaps a contiuous loop in the
      sink itself), so must use a Pull design.
  <li> In ``event-driven'' contexts, the flow is initiated
       an external event to the source (or perhaps a continuous
       loop in the source itself) so must use a Push design.
  <li> Buffered designs are needed (among other cases) when trying
       to mesh together two or more Push-driven versus Pull-driven
       flows.
</ul>

Many (perhaps most) activity flow designs involve elements of more
than one of these styles. This is one reason that these three
distinct design patterns are described as a group in this document.


<h3>Design Consequences</h3>

Choices of control styles have surprisingly large effects on the design
of participating classes. The most obvious impact is on the
interfaces, structure, and implementations of objects serving as
<em>stages</em>:

<ul>
  <li> In a Pull design, each stage possesses:
      <ol>
        <li>  Methods of the form:
            <pre> RepType take()</pre>
            (where <code>RepType</code> is some representation type or class)
            that delivers requested objects and/or information.
        <li> Zero or more links (references) to <em>predecessor</em>
             objects that (except in the case of sources) allow the
             object to pull objects and/or information necessary to
             implement its <code>take</code> methods. These links need
              not be direct. For example, the stage may have a reference
              to a single mediator or registry that maintains (producer,
              consumer) pairs for all stages.
              
      </ol>
<p>

  <li> In a Push design, each stage possesses:
      <ol>
        <li> Methods of the form:
            <pre>void put(RepType r)</pre>
            that cause it to use or transform <code>r</code>.
        <li> Zero or more links to <em>successor</em> objects
             that (except in the case of sinks) it sends the
             resulting object and/or information.
      </ol>
<p>
  <li> In Buffered designs, Buffer objects support both
      <code>put</code> and <code>take</code>, as used by objects
      of either or both of the above forms. At one extreme, there may be a
      buffer for every pair of communicating objects. At the other
      extreme, there may be a single buffer shared by all objects,
      in which case stored messages (commands, values)  must be tagged
      in some way so that objects only take the ones they need.
</ul>

<p>

<IMG SRC="pp.gif" tppabs="http://www.foi.hr/~dpavlin/java/mirrors/g.oswego.edu/dl/pats/pp.gif">

<p>

<h3>Thread Construction and Control</h3>

A second difference among these styles lies in Thread construction and control
policies, reflecting the fact that Pull-style designs place
mechanics on the Consumer side, Push-style on the Producer
side, and Buffered-style on both:

<ul>
  <li> In a multithreaded Pull design, each <em>consumer</em>-driven
      <code>take</code> request can be established as a
      <a href="service.html" tppabs="http://www.foi.hr/~dpavlin/java/mirrors/g.oswego.edu/dl/pats/service.html"> thread </a>
      with a completion callback. 

  <li> In a multithreaded Push design, each
      <em>producer</em>-driven <code>put</code> trigger can generate
      a thread to carry out the put.
      
  <li> In Buffered designs, stages can take the above forms, or
      in the most typical case where stages both produce and
      consume, <a href="auton.html" tppabs="http://www.foi.hr/~dpavlin/java/mirrors/g.oswego.edu/dl/pats/auton.html">autonomous loops</a>
      of the form:
      <pre>
        for (;;) { ... r = inbuffer.take(); ... outbuffer.put(f(r)); }
      </pre>
</ul>

<h4>Linear Flow</h4>

A purely linear flow is one in which each stage has at most one
predecessor and successor.  Because linear flows are instrinsically
sequential, only <em>one</em> thread need be associated with the entire
flow, at least for Push and Pull forms.  So rather than associating
threads with <em>every</em> stage, it suffices in a Pull design to
establish a thread only for the ultimate <em>sink</em>, and in a Push
design only for the only for the ultimate <em>source</em> stage.


<h4>
<a name="secNonLin"></a>
Non-Linear Flow
</h4>

<p> Nonlinear flows are those where stages may have more than one
direct predecessor or successor.  The two basic nonlinear forms are
<em>Splitters</em>, that have multiple successors and
<em>Mergers</em>, that have multiple predecessors:

<pre>
                  +-----------+
                  | Consumer1 |
                  +-----------+
  +----------+  /
  | Splitter | 
  +----------+  \
                  +-----------+
                  | Consumer2 |
                  +-----------+ 



  +-----------+
  | Producer1 |
  +-----------+
                \  +----------+
                   | Merger   | 
                /  +----------+
  +-----------+
  | Producer2 |
  +-----------+
</pre>

(These show only the two-connection versions, which generalize easily
to those with any number of connections.)

<p>
The impact of such stages on thread construction is pretty much
symmetrical for Push versus Pull designs. For simplicity, we'll mainly
illustrate the Push case.

<p>
The principal issue in nonlinear flows is how to keep the
activity as a whole ``alive'' at all times that it should be.
So far, we've only considered two strategies:
<ol>
  <li> For arbitrary flows, associate a Thread with <em>every</em>
      <code>put</code>.
  <li> For linear flows, associate a Thread only with an ultimate
      <em>source</em> object.
</ol>



Except perhaps in special cases, it is too wasteful and inefficient to
use the default strategy of associating a thread with each
<code>put</code>.  However, the linear strategy doesn't work at all in
some nonlinear designs; for example push-style Mergers that behave as
<code>Combiners</code>.

<p>
A Combiner is a stage that requires an input from each of its
predecessors in order to continue.  For example, consider an assembly
line where a Combiner needs one <code>RedPart</code> and one
<code>GreenPart</code> in order to assemble them. If there is only a
single thread producing both kinds of Parts, and if the Combiner
blocks (via some kind of <code>wait</code>) when it has only one kind
while waiting for the other, then the entire activity will stall.

<p> The path to a live but still economical solution requires one
further bit of diagnosis: A Combiner can only stall in this way if it
is fed by two stages that are operating within the same thread. This
can in turn happen only in designs of the form:

<pre>
                  +-----------+ 
                  | Stage1    | 
                  +-----------+ 
  +----------+  /               \ +----------+
  | Splitter |                    | Combiner |
  +----------+  \               / +----------+
                  +-----------+ 
                  | Stage2    | 
                  +-----------+

</pre>

To prevent stalls at the <em>combine</em> point, any design of this
form must construct at least one additional thread at the
<em>Split</em> point.  As a matter of design policy, you might require
that <em>all</em> Splitters in a push-driven system that includes any
Combiners create new threads.

<p> Similar kinds of reasoning apply to other nonlinear flow
designs. For example, additional threads are required in
most looping flows where successors are tied to predecessors.

<p> A conservative, safe approach is to always start out using the
default strategy of establishing Threads at each stage, and then eliminating
those that turn out not to be strictly necessary.  However, this is
much too awkward to carry out at the Java implementation level.  When
you know the full form of all activity flows in advance, it is much
simpler to plan them out on paper first, and do this kind of
back-of-the-envelope analysis before implementing things.


<h2>
Examples
</h2>

The key to designing components that can be used across these
different architectural styles is to factor out as much control
policy issues as possible in the lowest-level representation
components.  However, before getting into more abstract design issues
along these lines, please see examples of these patterns:

<ul>
  <li> Push Flow: <a href="mondrian.html" tppabs="http://www.foi.hr/~dpavlin/java/mirrors/g.oswego.edu/dl/pats/mondrian.html"> Mondrian Factory</a>
  <li> Pull Flow: <em>not yet available</em>
  <li> Buffered Flow: <em>not yet available</em>
</ul>


<p><a href="aopintro.html" tppabs="http://www.foi.hr/~dpavlin/java/mirrors/g.oswego.edu/dl/pats/aopintro.html">[Concurrent Programming in Java]</a>

<hr>
<address><A HREF="javascript:if(confirm('http://g.oswego.edu/dl  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://g.oswego.edu/dl'" tppabs="http://g.oswego.edu/dl">Doug Lea</A></address>
<!-- hhmts start -->
Last modified: Tue Feb 20 06:50:23 EST 1996
<!-- hhmts end -->
</body> </html>