State Machine Managers

Do you have a system where you need to maintain a bunch of state that needs to respond to multiple concurrent events?

Let's talk about how these things can be put together while trying to keep complexity under control.

TL:DR: borrowing the operating system's approach for handling interrupts to manage other systems where state is coordinated from multiple concurrent sources is a handy, well-understood shorthand.

Patterns

Here are some useful building blocks you can look at to get a sense of the breadth and depth of options and prior art that exist.

• State machines. I've written about these in the past, and they remain as always an excellent tool to tame complexity.
• Interrupt handling. This is very well understood at this point, where we have decades and decades of experience dealing with these sort of things. The common pattern of minimal processing and deferring work allows for minimizing impact outside of more predictable execution contexts and simplifying overall design. For our purposes, we can think of an event handler as capturing data into either a state-machine-specific work queue (if you can cross-reference that directly), into a more global queue, or simply by updating state for some other timer-based or already-scheduled work.
• Work scheduling for the "process later" portion comes in many forms: work queues as seen in Linux or Windows, .NET's various SynchronizationContext classes, any kind of message queue although distributed ones are a special case for this use case.

Keeping event ("interrupt") handlers split into capture and processing helps preserve the 'state transitions are atomic' property that you want in your state machines. Where you can't maintain that property (because say an event signals a cancelation that needs to be processed immediately), you can introduce additonal states and transitions to capture these as independent events.

An Example

To avoid making this too abstract, here is a classic implementation you might see. I'm using the Win32 threadpool APIs for simplicity, and I'm setting it to an at-most one thread to make sure there is no chance of concurrent access (ref).

// Put your state machine in one of these.
struct FooState { int id; int state; int data; int newData; };

// We implement a manager with a single-threaded consumer.
struct FooManager {
  // Keep state in array, vector, list, etc.
  FooState[MAX_FOO_STATES] states;
  // Support for scheduling work on-demand and on timer.
  PTP_POOL pool;
  PTP_TIMER timer;
  PTP_WORK work;
  // Simple 'manager' flag
  bool running;

  // start processing state machines
  void start() {
    pool = CreateThreadpool();
    SetThreadpoolThreadMaximum(pool, 1);
    // create a work item to be posted to do work
    work = CreateThreadpoolWork(do_work_fn, this, nullptr);
    // start a timer to do work regularly (for timeouts and such)
    timer = CreateThreadpoolTimer(do_work_fn, this, nullptr);
    SetThreadpoolTimer(timer, next_due_time(), 1000, 100); // recur every seond with 100ms allowed delay
    running = true;
  }

  // pack and go home
  void stop() {
    running = false;
    CloseThreadpoolWork(work);
    CloseThreadpoolTimer(timer);
    CloseThreadpool(pool);
  }

  // API for event handlers to register new data
  void updateNewData(int id, int newData) {
    // capture the new state but don't process right away;
    // we could wait for the timer to process this, but here we
    // schedule something right away as well
    find_state(id)->newData = newData;
    if (running) {
      // could check to avoid over-scheduling, but ok for this case
      SubmitThreadpoolWork(work);
    }
  }

  // look at all state machines and handle any transitions
  void do_work(){
    // we get to do whatever we want with state, single-threaded
    for (size_t i = 0; i < MAX_FOO_STATES; ++i) {
      if (states[i].newData != 0) {
        // do something with the new data
        states[i].newData = 0; // you might want to make this thread-safe
      }
    }
  }

  // turn a C callback into a C++ one
  static void CALLBACK do_work_fn(PTP_CALLBACK_INSTANCE instance, void* ctx, PTP_TIMER t) {
    (FooManager*)(instance)->do_work();
  }
};

// Handle events like this:
FooManager g_FooManager;
void onSomeEvent(int fooId, int newData) {
  g_FooManager.updateNewData(fooId, newData);
}


I should really write the moral equivalent to this level of threadpool functionality in STL-based C++ someday, and maybe flesh it out fully so I can show how to manage startup/shutdown safely - this isn't robust if events and start/stop requests can come in concurrently or reordered. But hopefully this gets the idea across.

Here I'm managing events by simply recording it in the state machine and 'grooming' them regularly. In real code, I might want to have the ability to read/write lock the whole thing or just the 'new data' portion to avoid losing updates. Alternatively there might be a queue on each state machine (or at the manager level) on what work needs to be done, and then the worker can grab the whole list atomically.

Yet another alternative could be to keep the data in each state-machine (if I can guarantee it's bound, so I can keep the data there), and then build a worklist of the entries that need processing via an intrusive linked list. This design makes it efficient to only walk the elements that need any work or some particular kind of work; depending on your needs, you might keep the items on a list that's reflective of their state or their upcoming work needs.

While the sort of 'new data' approach is usually simpler to reason about in terms of resource utilization (because they are bounded), you end up needing lists of events when the order is important and must be preserved. In the general case, that opens you up for queue handling considerations (reordering, coalescing, pacing, throttling reception, applying backpressure), but that's a tale for another day.

Why this is simpler

• You can write all the message-passing once (or reuse it from a library) and not worry about concurrent / conflicting updates, and instead process your state machine events and updates in a single-threaded context.
• Your transitions can be handled in a single place, rather than scattered across the various event-firing systems.
• You can move work to less performance-sensitive components and not get in the way of the event-firing systems (which might be firing events synchronously).
• You have years and years of experience and literature and codebases at your disposal on how to tweak things to make various tradeoffs.

React Patterns thoughts

I've used React a bit and I'm somewhat familiar with some of the patterns, although I wouldn't consider myself an expert by any stretch. React is also very much about state management and responding to events, and so I think some thoughts are still reasonable to lay down.

You could certainly build something like React with the design mentioned above, however React has stronger opinions on a number of things (and thus precludes some options where it has already made a tradeoff).

• React is much more functional. State machines can be implemented in a functional style or with mutable state - the latter is the more classic approach.
• React really offers a single thread of execution. While this is a useful simplification, and event/interrupt handling allows you to support but minimize concurrency, and you're of course still free to have different kinds of scheduling like multiple work queues (you could even have worker thread per state-machine for example if you needed that compute availability).
• React aims to build a declarative tree of elements that is then processed by a different system. This of course may or may not be the aim of the system you're otherwise designing; for other domains, you're still on the hook for applying state, side-effects and anything else ("hook" - ha!)

Happy state management!

Tags:  design perf

Home