title: data structures for scheduling workflow?
body: <p>I'm wondering what kind(s) of data structures / algorithms might help facilitate handling the following situation; I'm not sure if I need a single FIFO, or a priority queue, or multiple FIFOs.</p>
  
  <p>I have N objects that must proceed through a predefined workflow. Each object must complete step 1, then step 2, then step 3, then step 4, etc. Each step is either done quickly or involves a "wait" that depends on something external to finish (like the completion of a file operation or whatever). Each object maintains its own state. If I had to define an interface for these objects, it would be something like this (written below in pseudo-Java, but this question is language-agnostic):</p>
  
  <pre><code>public interface TaskObject
  {
     public enum State { READY, WAITING, DONE };
     // READY = ready to execute next step
     // WAITING = awaiting some external condition
     // DONE = finished all steps
  
     public int getCurrentStep();
     // returns # of current step
  
     public int getEndStep();
     // returns # of step which is the DONE case.
  
     public State getState();
     // checks state and returns it. 
     // multiple calls will always be identical, 
     // except WAITING which can transition to READY or DONE.
  
     public State executeStep();
     // if READY, executes next step and returns getState().
     // otherwise, returns getState().
  
  }
  </code></pre>
  
  <p>I need to write a single-threaded scheduler that calls executeStep() on the "next" object. My problem is, I'm not sure exactly what technique I should use to determine what the "next" object is. I want it to be fair (first-come, first-serve for objects not in the WAITING state). </p>
  
  <p>My gut call is to have 3 FIFOs, READY, WAITING and DONE. In the beginning all objects are placed in the READY queue, and the scheduler repeats a loop where it takes the first object off the READY queue, calls executeStep(), and places it onto the queue that's appropriate the the result of executeStep(). Except that items in the WAITING queue need to be put into the READY or DONE queue when their state changes.... argh!</p>
  
  <p>Any advice?</p>