1.. _Flow_Graph_Reservation:
2
3Flow Graph Basics: Reservation
4==============================
5
6
7|full_name| flow graph
8``join_node`` has four possible policies: ``queueing``, ``reserving``,
9``key_matching`` and ``tag_matching``. ``join_nodes`` need messages at
10every input before they can create an output message. The reserving
11``join_node`` does not have internal buffering, and it does not pull
12messages from its inputs until it has a message at each input. To create
13an output message it temporarily reserves a message at each input port,
14and only if all input ports succeed reserving messages will an output
15message be created. If any input port fails to reserve a message, no
16message will be pulled by the ``join_node``.
17
18
19To support the reserving ``join_node`` some nodes support
20**reservation** of their outputs. The way reservation works is:
21
22
23-  When a node connected to a reserving ``join_node`` in push state
24   tries to push a message, the ``join_node`` always rejects the push
25   and the edge connecting the nodes is switched to pull mode.
26-  The reserving input port calls ``try_reserve`` on each edge in pull
27   state. This may fail; if so, the reserving input port switches that
28   edge to push state, and tries to reserve the next node connected by
29   an edge in pull state. While the input port's predecessor is in
30   reserved state, no other node can retrieve the reserved value.
31-  If each input port successfully reserves an edge in pull state, the
32   reserving ``join_node`` will create a message using the reserved
33   messages and try to push the resulting message to any nodes connected
34   to it.
35-  If the message is successfully pushed to a successor, the
36   predecessors that were reserved are signaled that the messages were
37   used (by calling ``try_consume()``.) Those messages will be discarded
38   by the predecessor nodes, because they have been successfully pushed.
39-  If the message was not successfully pushed to any successor, the
40   predecessors that were reserved are signaled that the messages were
41   not used (by calling ``try_release()``.) At this point, the messages
42   may be pushed to or pulled by other nodes.
43
44
45Because the reserving ``join_node`` will only attempt to push when each
46input port has at least one edge in a pull state, and will only attempt
47to create and push a message if all input ports succeed reserving
48messages, at least one of the predecessors to each of the reserving
49``join_node`` input ports must be reservable.
50
51
52The following example demonstrates a reserving ``join_node``'s behavior.
53``buffer_nodes`` buffer their output, so they accept a switch of their
54output edge from push to pull mode. ``broadcast_nodes`` do not buffer
55messages and do not support ``try_get()`` or ``try_reserve()``.
56
57
58::
59
60
61   void run_example2() {  // example for Flow_Graph_Reservation.xml
62       graph g;
63       broadcast_node<int> bn(g);
64       buffer_node<int> buf1(g);
65       buffer_node<int> buf2(g);
66       typedef join_node<tuple<int,int>, reserving> join_type;
67       join_type jn(g);
68       buffer_node<join_type::output_type> buf_out(g);
69       join_type::output_type tuple_out;
70       int icnt;
71
72
73       // join_node predecessors are both reservable buffer_nodes
74       make_edge(buf1,input_port<0>(jn));
75       make_edge(bn,input_port<0>(jn));      // attach a broadcast_node
76       make_edge(buf2,input_port<1>(jn));
77       make_edge(jn, buf_out);
78       bn.try_put(2);
79       buf1.try_put(3);
80       buf2.try_put(4);
81       buf2.try_put(7);
82       g.wait_for_all();
83       while (buf_out.try_get(tuple_out)) {
84           printf("join_node output == (%d,%d)\n",get<0>(tuple_out), get<1>(tuple_out) );
85       }
86       if(buf1.try_get(icnt)) printf("buf1 had %d\n", icnt);
87       else printf("buf1 was empty\n");
88       if(buf2.try_get(icnt)) printf("buf2 had %d\n", icnt);
89       else printf("buf2 was empty\n");
90   }
91
92
93In the example above, port 0 of the reserving ``join_node`` ``jn`` has
94two predecessors: a ``buffer_node`` ``buf1`` and a ``broadcast_node``
95``bn``. Port 1 of the ``join_node`` has one predecessor, ``buffer_node``
96``buf2``.
97
98
99.. container:: fignone
100   :name: reserve_step1
101
102
103   .. container:: imagecenter
104
105
106      |image0|
107
108
109We will discuss one possible execution sequence (the scheduling of tasks
110may differ slightly, but the end result will be the same.)
111
112
113::
114
115
116       bn.try_put(2);
117
118
119``bn`` attempts to forward 2 to ``jn``. ``jn`` does not accept the value
120and the arc from ``bn`` to ``jn`` reverses. Because neither bn nor jn
121buffer messages, the message is dropped. Because not all the inputs to
122``jn`` have available predecessors, ``jn`` does nothing further.
123
124
125.. CAUTION::
126   Any node which does not support reservation will not work correctly
127   when attached to a reserving ``join_node``. This program demonstrates
128   why this occurs; connecting non-reserving nodes to nodes requiring
129   support for reservation is **not** recommended practice.
130
131
132.. container:: fignone
133   :name: reserve_step2
134
135
136   .. container:: imagecenter
137
138
139      |image1|
140
141
142::
143
144
145       buf1.try_put(3);
146
147
148``buf1`` attempts to forward 3 to ``jn``. ``jn`` does not accept the
149value and the arc from ``buf1`` to ``jn`` reverses. Because not all the
150inputs to ``jn`` have available predecessors, ``jn`` does nothing
151further.
152
153
154.. container:: fignone
155   :name: reserve_step3
156
157
158   .. container:: imagecenter
159
160
161      |image2|
162
163
164::
165
166
167       buf2.try_put(4);
168
169
170``buf2`` attempts to forward 4 to ``jn``. ``jn`` does not accept the
171value and the arc from ``buf2`` to ``jn`` reverses. Now both inputs of
172``jn`` have predecessors, a task to build and forward a message from
173``jn`` will be spawned. We assume that task is not yet executing.
174
175
176.. container:: fignone
177   :name: reserve_step4
178
179
180   .. container:: imagecenter
181
182
183      |image3|
184
185
186::
187
188
189       buf2.try_put(7);
190
191
192``buf2`` has no successor (because the arc to ``jn`` is reversed,) so it
193stores the value 7.
194
195
196.. container:: fignone
197   :name: reserve_step5
198
199
200   .. container:: imagecenter
201
202
203      |image4|
204
205
206Now the task spawned to run ``jn`` runs.
207
208
209-  ``jn`` tries to reserve ``bn``, which fails. The arc to ``bn``
210   switches back to the forward direction.
211-  ``jn`` tries to reserve ``buf1``, which succeeds (reserved nodes are
212   colored grey.) ``jn`` receives the value 3 from ``buf1``, but it
213   remains in ``buf1`` (in case the attempt to forward a message from
214   ``jn`` fails.)
215-  ``jn`` tries to reserve ``buf2``, which succeeds. ``jn`` receives the
216   value 4 from ``buf2``, but it remains in ``buf2``.
217-  ``jn`` constructs the output message ``tuple<3,4>``.
218
219
220.. container:: fignone
221   :name: reserve_step6
222
223
224   .. container:: imagecenter
225
226
227      |image5|
228
229
230Now ``jn`` pushes its message to ``buf_out``, which accepts it. Because
231the push succeeded, ``jn`` signals ``buf1`` and ``buf2`` that the
232reserved values were used, and the buffers discard those values. Now
233``jn`` attempts to reserve again.
234
235
236-  No attempt to pull from ``bn`` is made, because the edge from ``bn``
237   to ``jn`` is in push state.
238-  ``jn`` tries to reserve ``buf1``, which fails. The arc to ``buf1``
239   switches back to the forward direction.
240-  ``jn`` does not try any further actions.
241
242
243.. container:: fignone
244   :name: reserve_step7
245
246
247   .. container:: imagecenter
248
249
250      |image6|
251
252
253No further activity occurs in the graph, and the ``wait_for_all()`` will
254complete. The output of this code is
255
256
257::
258
259
260   join_node output == (3,4)
261   buf1 was empty
262   buf2 had 7
263
264
265.. |image0| image:: Images/flow_graph_reserve_buffers_1.png
266   :width: 400px
267   :height: 222px
268.. |image1| image:: Images/flow_graph_reserve_buffers_2.png
269   :width: 400px
270   :height: 222px
271.. |image2| image:: Images/flow_graph_reserve_buffers_3.png
272   :width: 400px
273   :height: 222px
274.. |image3| image:: Images/flow_graph_reserve_buffers_4.png
275   :width: 400px
276   :height: 222px
277.. |image4| image:: Images/flow_graph_reserve_buffers_5.png
278   :width: 400px
279   :height: 222px
280.. |image5| image:: Images/flow_graph_reserve_buffers_6.png
281   :width: 400px
282   :height: 222px
283.. |image6| image:: Images/flow_graph_reserve_buffers_7.png
284   :width: 400px
285   :height: 222px
286
287