Are there any stochastic models of non determinism in the rate of program execution?

Question

We know that typical operating systems and high level languages (especially those with garbage collection) cannot be used for real time operating systems. Java & jet engines don't mix, and consequently a lot of study has gone into researching and developing real time operating systems.

Is there any research as to exactly why a traditional operating system and high level garbage collecting language can't be used? I'm interested in any stochastic modelling that might have been done, rather than lots of words. So as a simple example, is there a mathematical model for the execution rate of say a simple FOR /NEXT loop on something like *nix + Java? Ideally this should refer to contemporary micro processors with all their associated speculative execution, interrupt handling and other modern optimisations like memory reclamation and parallel processing.

I would also extend this reference request to any models that might try to equate the mensuration of the execution rate of such a FOR /NEXT loop, with the Observer Effect as found in quantum mechanics.

Answer 1

There is work on estimating the worst-case execution time for code (sometimes called WCET analysis). You can start with the Wikipedia article on the subject and use Google Scholar to find many research papers on that topic.

However, in traditional systems, the problem is not that the running time is random (well, that's one problem, but it's not the most serious one). The more serious one is that the running time is unpredictable. We can't even assign a probability distribution to it -- we have no basis for doing that.

For instance, in many garbage-collected languages, response time is unpredictable and real-time operation cannot be guaranteed. The garbage collector might kick in at any point and pause your program for a very long time. The point where that happens is not predictable, and the amount of time it will take is also not (usefully) predictable -- we can't even assign a stochastic model to it.

We can't really call the garbage collector random, as it might be triggered by some sequence of events that is in principle deterministic but is in practice too complex to model and thus is for all engineering purposes unpredictable. You might be tempted to say "treat the time when garbage collection happens as random and uniformly distributed", but that's not valid. For all we know, the garbage collector might kick in at the worst possible time. Maybe there is some code that does a bunch of stuff (e.g., creating lots of short-lived objects and then immediately destroying all references to them) that tends to trigger the garbage collector, right before some other code that does something really time-critical (e.g., update flight control surfaces). If you modelled the time of garbage collection as random, you would fail to recognize that the flight-control code might systematically fail at a higher probability than your stochastic model predicts. All we can safely do is assume conservatively that the garbage collector might run at the worst possible time, and take essentially forever to do its job. That renders worst-case execution time analysis impossible or unhelpful.

Similarly comments can be made about many other elements that make running time analysis hard, such as interrupts, caches, speculative execution, and so on.