I am developing algorithms that have a running-time hard to predict (they are highly input-dependent) and for some users the running-time needs to remain bounded. So I need to enhance the code with a timeout mechanism.
It is thinkable to launch the algorithm in a separate thread and wait for completion, for example with a timed mutex, and abort if necessary. But a problem is that abortion of the algorithm will stop it in an arbitrary state, possibly losing partial results already obtained, but - more problematically - leaving the objects that take part to the processing in an invalid state.
Can you advise about the methods used in practice ? How to interrupt processing ? How to make sure that interruption will not take further time ? How to make sure that the system returns to a stable state ? How to avoid busy waiting and other forms of overhead ?
I am just in a concept stage, nothing programmed so far. Thinking of soft methods (letting the code time itself) vs. hard ones (external interruption).
If you run the code in its own process, then on most modern operating systems, when the process gets killed, the kernel will automatically and reliably clean up the entire process. However, this will cause all intermediate results to get lost, unless the killed process regularily reported its intermediate results using some form of interprocess communication. Also, the process would require its own copy of the data, except for the data that is strictly read-only. The read-only data could be shared by both processes.
However, if you can trust the code that you are running to check a shared flag in sufficiently regular intervals, and to gracefully terminate in a time-bounded manner if that flag is set, then it should not be necessary to run that code in a separate process and to kill it. In the case of a graceful termination, the code should be designed in such a way that it reports its last set of valid intermediate results to the caller before terminating.