A mechanism for increased State Machine throughput based upon pre-emptive guard evaluation
Original Publication Date: 2004-Mar-25
Included in the Prior Art Database: 2004-Mar-25
A technique is disclosed for increasing State Machine throughput based on pre-emptive guard evaluation.
A mechanism for increased State Machine throughput based upon pre -emptive guard evaluation
When a customer wishes to use a State Machine to model and execute a business process and use a guard which is expensive to calculate, the State Machine is forced to wait until the guard or choice evaluation is complete.
Currently known solutions are to model a guard that spawns an asynchronous process and then to continue to evaluate a single branch. When the guard outcome is known an event is sent back into the State Machine. A transition is made back to the guard and it is re-evaluated with the known outcome to determine the correct branch. Then either the current branch is undone by running a series of actions to undo all the work performed on that branch or the State Machine continues from the state it was in before it received the outcome from the guard.
The drawbacks of this solution are: Only a single branch can continue to be evaluated at any one time when there may be no reason why multiple branches should not be evaluated in parallel.
When the guard's outcome is known the State Machine may be in a Run to Completion step and not be able to react immediately and possibly be wasting CPU time if the current branch is incorrect.
The modeller must model the logic using extra transitions, guards and actions. This will complicate the design and must all be determined at modelling time.
The initial guard must check the event data it receives to determine whether the data is the result of a callback by an asynchronous process or to spawn a process to determine the appropriate outcome. This complicates the guard logic.
"OMG Unified Modeling Language Specification Version 2.0 3rd Revised Submission" describes a graphical language for modelling the syntax and semantics for statechart diagrams.
"Rational Rose RealTime" allows the design and execution of State Machines based upon UML.
"Transaction Processing: Concepts and Techniques" by Jim Gray and Andreas Reuter, Chapter 4 describes various transactional models when dealing with work done by multiple related transactions such as compensation and save points.
When an expensive guard is evaluated the State Machine will proceed to evaluate actions associated with the branches for the guard. Events continue to be received by the State Machine and are cloned and sent to each branch in parallel.
If a branch is determined to be incorrect all the work done on that branch must be compensated if multiple transactions were used or rolled back if only a single transaction was used.
If one br...