A bidirectional trace simplification approach based on a context switch linked list for concurrent programs

摘要

Concurrent programs are notoriously difficult to debug due to shared memory and the non-determined nature of thread scheduling. Frequent context switches add a huge burden on developers in reasoning about concurrency bugs. To alleviate this problem, we present a bidirectional trace simplification approach based on a context switch linked list. First, we calculate the dependence relations, including local dependences, synchronization dependences, and remote read/write dependences. Second, we construct a context switch linked list according to the original buggy trace. Then, we backward refactor the context switch linked list in sequence to extend thread execution intervals. Finally, we forward check the context switch linked list in sequence to ensure that no nodes can be further merged. We have conducted experiments on eight Java multi-threaded programs to evaluate our approach. The results show that our approach performs better than or is comparable to the compared static approaches in effectiveness and efficiency.