A bidirectional trace simplification approach based on a context switch linked list for concurrent programs. (28th June 2019)

• Record Type: Journal Article
• Authors: Bo, Lili; Jiang, Shujuan; Wang, Rongcun; Yu, Qiao
• Is Part Of: Concurrency and computation. Volume 32:Number 2(2020)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2019-06-28
• Subjects: concurrent program -- context switch -- program debugging -- trace simplification; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.5423
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: 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.