Parallel programs often are non-deterministic in their nature, what greatly complicates testing, debugging, verifying and analyzing such programs. On a uniprocessor, interleaving actions of the system scheduler (thread switches) can be thought of as source of nondeterminism. The precise detection of these actions helps many tasks, especially the schedule-based execution replay – the technique for robust debugging of non-deterministic programs. Known solutions to detection of thread switches are either specific to system schedulers providing this information, or require modification of the scheduler. For the system scheduler in the OS Windows, all these solutions are inapplicable.

The paper presents an OS-independent algorithm for detection of thread switches in a multithreaded program running on a uniprocessor based on the primitive thread operations such as suspending a thread, accessing its context, etc. The correctness of the algorithm is proven on the low-level abstract model of multithreaded programs that is also presented in the article.

mogilev.pdf167.31 KB