Rapid Identification of Shared Memory in Multithreaded Embedded Systems with Static Scheduling

Due to the non-deterministic order of interactions between concurrent threads, testing of concurrent software is a challenge. In order to cope with this challenge, researchers have proposed analysis approaches in which the dynamic-based algorithms (e.g., Happens-before, Lockset) are an irreplaceable part. One of the biggest challenges of such algorithms, and a pre-condition to the analysis, is identification of memory locations that are shared between threads. This task is a significant contributor to the overhead of the analysis algorithms. In embedded systems that use static scheduling, scheduling is the implicit synchronization mechanism. In this paper, we suggest taking an advantage of static scheduling scheme to speed up the process of finding variables shared between threads, and with it, the identification of concurrency bugs. We demonstrate this concept by introducing modification to the Lockset algorithm and its internal structure. We show that considering static scheduling reduces the execution analysis time of the Lockset algorithm.