CoroutineManager


1   /*
2    * Copyright 1999-2004 The Apache Software Foundation.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    *     http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  /*
17   * $Id: CoroutineManager.java,v 1.10 2004/02/16 23:06:11 minchau Exp $
18   */
19  package com.sun.org.apache.xml.internal.dtm.ref;
20  
21  import java.util.BitSet  ;
22  
23  import com.sun.org.apache.xml.internal.res.XMLErrorResources;
24  import com.sun.org.apache.xml.internal.res.XMLMessages;
25  
26  
27  /**
28   * <p>Support the coroutine design pattern.</p>
29   * 
30   * <p>A coroutine set is a very simple cooperative non-preemptive
31   * multitasking model, where the switch from one task to another is
32   * performed via an explicit request. Coroutines interact according to
33   * the following rules:</p>
34   *
35   * <ul>
36   * <li>One coroutine in the set has control, which it retains until it
37   * either exits or resumes another coroutine.</li>
38   * <li>A coroutine is activated when it is resumed by some other coroutine
39   * for the first time.</li>
40   * <li>An active coroutine that gives up control by resuming another in
41   * the set retains its context -- including call stack and local variables
42   * -- so that if/when it is resumed, it will proceed from the point at which
43   * it last gave up control.</li>
44   * </ul>
45   *
46   * <p>Coroutines can be thought of as falling somewhere between pipes and
47   * subroutines. Like call/return, there is an explicit flow of control
48   * from one coroutine to another. Like pipes, neither coroutine is
49   * actually "in charge", and neither must exit in order to transfer
50   * control to the other. </p>
51   * 
52   * <p>One classic application of coroutines is in compilers, where both
53   * the parser and the lexer are maintaining complex state
54   * information. The parser resumes the lexer to process incoming
55   * characters into lexical tokens, and the lexer resumes the parser
56   * when it has reached a point at which it has a reliably interpreted
57   * set of tokens available for semantic processing. Structuring this
58   * as call-and-return would require saving and restoring a
59   * considerable amount of state each time. Structuring it as two tasks
60   * connected by a queue may involve higher overhead (in systems which
61   * can optimize the coroutine metaphor), isn't necessarily as clear in
62   * intent, may have trouble handling cases where data flows in both
63   * directions, and may not handle some of the more complex cases where
64   * more than two coroutines are involved.</p>
65   * 
66   * <p>Most coroutine systems also provide a way to pass data between the
67   * source and target of a resume operation; this is sometimes referred
68   * to as "yielding" a value.  Others rely on the fact that, since only
69   * one member of a coroutine set is running at a time and does not
70   * lose control until it chooses to do so, data structures may be
71   * directly shared between them with only minimal precautions.</p>
72   * 
73   * <p>"Note: This should not be taken to mean that producer/consumer
74   * problems should be always be done with coroutines." Queueing is
75   * often a better solution when only two threads of execution are
76   * involved and full two-way handshaking is not required. It's a bit
77   * difficult to find short pedagogical examples that require
78   * coroutines for a clear solution.</p>
79   * 
80   * <p>The fact that only one of a group of coroutines is running at a
81   * time, and the control transfer between them is explicit, simplifies
82   * their possible interactions, and in some implementations permits
83   * them to be implemented more efficiently than general multitasking.
84   * In some situations, coroutines can be compiled out entirely;
85   * in others, they may only require a few instructions more than a
86   * simple function call.</p>
87   *
88   * <p>This version is built on top of standard Java threading, since
89   * that's all we have available right now. It's been encapsulated for
90   * code clarity and possible future optimization.</p>
91   * 
92   * <p>(Two possible approaches: wait-notify based and queue-based. Some
93   * folks think that a one-item queue is a cleaner solution because it's
94   * more abstract -- but since coroutine _is_ an abstraction I'm not really
95   * worried about that; folks should be able to switch this code without
96   * concern.)</p>
97   * 
98   * <p>%TBD% THIS SHOULD BE AN INTERFACE, to facilitate building other
99   * implementations... perhaps including a true coroutine system
100  * someday, rather than controlled threading. Arguably Coroutine
101  * itself should be an interface much like Runnable, but I think that
102  * can be built on top of this.</p>
103  * */
104 public class CoroutineManager
105 {
106   /** "Is this coroutine ID number already in use" lookup table.
107    * Currently implemented as a bitset as a compromise between
108    * compactness and speed of access, but obviously other solutions
109    * could be applied.
110    * */
111   BitSet   m_activeIDs=new BitSet  ();
112 
113   /** Limit on the coroutine ID numbers accepted. I didn't want the
114    * in-use table to grow without bound. If we switch to a more efficient
115    * sparse-array mechanism, it may be possible to raise or eliminate
116    * this boundary.
117    * @xsl.usage internal
118    */
119   static final int m_unreasonableId=1024;
120 
121   /** Internal field used to hold the data being explicitly passed
122    * from one coroutine to another during a co_resume() operation.
123    * (Of course implicit data sharing may also occur; one of the reasons
124    * for using coroutines is that you're guaranteed that none of the
125    * other coroutines in your set are using shared structures at the time
126    * you access them.)
127    *
128    * %REVIEW% It's been proposed that we be able to pass types of data
129    * other than Object -- more specific object types, or
130    * lighter-weight primitives.  This would seem to create a potential
131    * explosion of "pass x recieve y back" methods (or require
132    * fracturing resume into two calls, resume-other and
133    * wait-to-be-resumed), and the weight issue could be managed by
134    * reusing a mutable buffer object to contain the primitive
135    * (remember that only one coroutine runs at a time, so once the
136    * buffer's set it won't be walked on). Typechecking objects is
137    * interesting from a code-robustness point of view, but it's
138    * unclear whether it makes sense to encapsulate that in the
139    * coroutine code or let the callers do it, since it depends on RTTI
140    * either way. Restricting the parameters to objects implementing a
141    * specific CoroutineParameter interface does _not_ seem to be a net
142    * win; applications can do so if they want via front-end code, but
143    * there seem to be too many use cases involving passing an existing
144    * object type that you may not have the freedom to alter and may
145    * not want to spend time wrapping another object around.
146    * */
147   Object   m_yield=null;
148 
149   // Expose???
150   final static int NOBODY=-1;
151   final static int ANYBODY=-1;
152 
153   /** Internal field used to confirm that the coroutine now waking up is
154    * in fact the one we intended to resume. Some such selection mechanism
155    * is needed when more that two coroutines are operating within the same
156    * group.
157    */
158   int m_nextCoroutine=NOBODY;
159   
160   /** <p>Each coroutine in the set managed by a single
161    * CoroutineManager is identified by a small positive integer. This
162    * brings up the question of how to manage those integers to avoid
163    * reuse... since if two coroutines use the same ID number, resuming
164    * that ID could resume either. I can see arguments for either
165    * allowing applications to select their own numbers (they may want
166    * to declare mnemonics via manefest constants) or generating
167    * numbers on demand.  This routine's intended to support both
168    * approaches.</p>
169    *
170    * <p>%REVIEW% We could use an object as the identifier. Not sure
171    * it's a net gain, though it would allow the thread to be its own
172    * ID. Ponder.</p>
173    *
174    * @param coroutineID: If >=0, requests that we reserve this number.
175    * If <0, requests that we find, reserve, and return an available ID
176    * number.
177    *
178    * @return If >=0, the ID number to be used by this coroutine. If <0,
179    * an error occurred -- the ID requested was already in use, or we
180    * couldn't assign one without going over the "unreasonable value" mark
181    * */
182   public synchronized int co_joinCoroutineSet(int coroutineID)
183   {
184     if(coroutineID>=0)
185       {
186         if(coroutineID>=m_unreasonableId || m_activeIDs.get(coroutineID))
187           return -1;
188       }
189     else
190       {
191         // What I want is "Find first clear bit". That doesn't exist.
192         // JDK1.2 added "find last set bit", but that doesn't help now.
193         coroutineID=0;
194         while(coroutineID<m_unreasonableId)
195           {
196             if(m_activeIDs.get(coroutineID))
197               ++coroutineID;
198             else
199               break;
200           }
201         if(coroutineID>=m_unreasonableId)
202           return -1;
203       }
204 
205     m_activeIDs.set(coroutineID);
206     return coroutineID;
207   }
208 
209   /** In the standard coroutine architecture, coroutines are
210    * identified by their method names and are launched and run up to
211    * their first yield by simply resuming them; its's presumed that
212    * this recognizes the not-already-running case and does the right
213    * thing. We seem to need a way to achieve that same threadsafe
214    * run-up...  eg, start the coroutine with a wait.
215    *
216    * %TBD% whether this makes any sense...
217    *
218    * @param thisCoroutine the identifier of this coroutine, so we can
219    * recognize when we are being resumed.
220    * @exception java.lang.NoSuchMethodException if thisCoroutine isn't
221    * a registered member of this group. %REVIEW% whether this is the
222    * best choice.
223    * */
224   public synchronized Object   co_entry_pause(int thisCoroutine) throws java.lang.NoSuchMethodException  
225   {
226     if(!m_activeIDs.get(thisCoroutine))
227       throw new java.lang.NoSuchMethodException  ();
228 
229     while(m_nextCoroutine != thisCoroutine)
230       {
231         try 
232           {
233             wait();
234           }
235         catch(java.lang.InterruptedException   e)
236           {
237             // %TBD% -- Declare? Encapsulate? Ignore? Or
238             // dance widdershins about the instruction cache?
239           }
240       }
241     
242     return m_yield;
243   }
244 
245   /** Transfer control to another coroutine which has already been started and
246    * is waiting on this CoroutineManager. We won't return from this call
247    * until that routine has relinquished control.
248    *
249    * %TBD% What should we do if toCoroutine isn't registered? Exception?
250    *
251    * @param arg_object A value to be passed to the other coroutine.
252    * @param thisCoroutine Integer identifier for this coroutine. This is the
253    * ID we watch for to see if we're the ones being resumed.
254    * @param toCoroutine. Integer identifier for the coroutine we wish to
255    * invoke. 
256    * @exception java.lang.NoSuchMethodException if toCoroutine isn't a
257    * registered member of this group. %REVIEW% whether this is the best choice.
258    * */
259   public synchronized Object   co_resume(Object   arg_object,int thisCoroutine,int toCoroutine) throws java.lang.NoSuchMethodException  
260   {
261     if(!m_activeIDs.get(toCoroutine))
262       throw new java.lang.NoSuchMethodException  (XMLMessages.createXMLMessage(XMLErrorResources.ER_COROUTINE_NOT_AVAIL, new Object  []{Integer.toString(toCoroutine)})); //"Coroutine not available, id="+toCoroutine);
263 
264     // We expect these values to be overwritten during the notify()/wait()
265     // periods, as other coroutines in this set get their opportunity to run.
266     m_yield=arg_object;
267     m_nextCoroutine=toCoroutine;
268 
269     notify();
270     while(m_nextCoroutine != thisCoroutine || m_nextCoroutine==ANYBODY || m_nextCoroutine==NOBODY)
271       {
272         try 
273           {
274             // System.out.println("waiting...");
275             wait();
276           }
277         catch(java.lang.InterruptedException   e)
278           {
279             // %TBD% -- Declare? Encapsulate? Ignore? Or
280             // dance deasil about the program counter?
281           }
282       }
283 
284     if(m_nextCoroutine==NOBODY)
285       {
286         // Pass it along
287         co_exit(thisCoroutine);
288         // And inform this coroutine that its partners are Going Away
289         // %REVIEW% Should this throw/return something more useful?
290         throw new java.lang.NoSuchMethodException  (XMLMessages.createXMLMessage(XMLErrorResources.ER_COROUTINE_CO_EXIT, null)); //"CoroutineManager recieved co_exit() request");
291       }
292     
293     return m_yield;
294   }
295   
296   /** Terminate this entire set of coroutines. The others will be
297    * deregistered and have exceptions thrown at them. Note that this
298    * is intended as a panic-shutdown operation; under normal
299    * circumstances a coroutine should always end with co_exit_to() in
300    * order to politely inform at least one of its partners that it is
301    * going away.
302    *
303    * %TBD% This may need significantly more work. 
304    *
305    * %TBD% Should this just be co_exit_to(,,CoroutineManager.PANIC)?
306    *
307    * @param thisCoroutine Integer identifier for the coroutine requesting exit.
308    * */
309   public synchronized void co_exit(int thisCoroutine)
310   {
311     m_activeIDs.clear(thisCoroutine);
312     m_nextCoroutine=NOBODY; // %REVIEW%
313     notify();
314   }
315 
316   /** Make the ID available for reuse and terminate this coroutine,
317    * transferring control to the specified coroutine. Note that this
318    * returns immediately rather than waiting for any further coroutine
319    * traffic, so the thread can proceed with other shutdown activities.
320    *
321    * @param arg_object A value to be passed to the other coroutine.
322    * @param thisCoroutine Integer identifier for the coroutine leaving the set.
323    * @param toCoroutine. Integer identifier for the coroutine we wish to
324    * invoke. 
325    * @exception java.lang.NoSuchMethodException if toCoroutine isn't a
326    * registered member of this group. %REVIEW% whether this is the best choice.
327    * */
328   public synchronized void co_exit_to(Object   arg_object,int thisCoroutine,int toCoroutine) throws java.lang.NoSuchMethodException  
329   {
330     if(!m_activeIDs.get(toCoroutine))
331       throw new java.lang.NoSuchMethodException  (XMLMessages.createXMLMessage(XMLErrorResources.ER_COROUTINE_NOT_AVAIL, new Object  []{Integer.toString(toCoroutine)})); //"Coroutine not available, id="+toCoroutine);
332     
333     // We expect these values to be overwritten during the notify()/wait()
334     // periods, as other coroutines in this set get their opportunity to run.
335     m_yield=arg_object;
336     m_nextCoroutine=toCoroutine;
337 
338     m_activeIDs.clear(thisCoroutine);
339 
340     notify();
341   }
342 }
343
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags