Handling Complex Wait..Until Conditions

Last Wednesday I discussed some of the internal workings of discrete-event simulations. I should also mention that all of these discussions are based on a program running in a single thread that is trying to coordinate many activities. There are ways to create systems using multiple threads but for the time being I’m keeping it simple. I specifically discussed a general wait..until construct as shown in the following timing diagram:

The condition to be evaluated is based on the result of a logical or Boolean calculation based on one or more values. The goal is not to find an efficient way to do the evaluation–that’s trivial–but to figure out an efficient time to do it. You don’t want to it more often than you have to, like after every event executes (as shown in the timing diagram), but ideally only when any of the relevant values change.

There are two parts to the mechanism as well, and evaluating the until condition is only one of them. The other is to relate the evaluation to the affected entity. If you’re coding a system on your own you can do the check where it makes sense, which means you have to identify all of the details and instances. If, however, you want a system that is more automated, an extreme example of which would be a simulation language or tool that does these things automatically, you need a standard method.

The diagram shows a collection of entities in a wait..until state. The system has to be able to identify the types of entities that can enter into such a state (there may be more than one type of entity), identify the variables involved (which may vary for every entity and state), identify where in the code or scripts or whatever those variables might be changed (they can be in any data structure in any location and may be referenced directly, indirectly, or as part of an array, variant record, or other difficult-to-identify structure), institute a mechanism that performs the evaluation when any of the variables change, and link back to the entity so its until event can be executed when the until test finally resolves to true.

There are a few ways to make the process more efficient. The system can flag tests that might be active because one or more entities is in a wait..until state so the tests aren’t performed if they will never have an effect. Changes to relevant variables can be flagged so they are only executed at the end of processing for other events. That way, if more than one relevant variable changes you only have to do the test once. If the relevant variables are themselves associated with specific entities then the mechanism has to be able to identify which entities are relevant to the state of other entities.

I can see doing something like a two-pass compilation, the first of which would flag the variables that would have to be checked, and the second of which would set the code up to execute the checks in the right places. I can also see just brute-forcing it somehow. Clearly, many mechanisms are possible.

I’m pondering these issues because they’re interesting, but also because I am moved to think about how systems might be implemented to execute logic described by the BPMN notation I discussed yesterday. The system implementation seems much more straightforward to me, and examining it may give me some insights into how it might work in a general discrete-event simulation language or system.

Business processes may spawn numerous events or tokens which traverse through different states at different times. A process ends only when all events or tokens reach end states. If all of the (we’ll simplify and just say tokens going forward) can only reach a single end state and we know how many there are then where and when they need to be processed is clear. If tokens may reach different end states the coordination problem becomes more difficult. This is especially true if any one token invalidates the rest of the process. If that is the case then the system has to decide whether it would be more efficient to seek out and eliminate the other active tokens or let them go and dispose of them when they reach their end states. The implementer also has to consider whether the accounting for live tokens might affect the accuracy of KPI monitoring.

Tomorrow I’ll illustrate the similarities and differences between business process systems and discrete-event simulations in a couple of different ways. The more I think about it the more similarities there are.

This entry was posted in Tools and methods and tagged , , , . Bookmark the permalink.

Leave a Reply