Bruno Teixeira (2010)

MSc Student

in

MSc dissertation: Static Detection of Anomalies in Transactional Memory Programs  
Period: February 2009 — April 2010
Grade: 19/20
Project: Byzantium (funded by the National Science Foundation, PI: Prof. Nuno Preguiça)
Papers: ComSIS 8:(2)'11 (DOI), InForum'10, PADTAD'10 (DOI)

Transactional Memory (TM) is an approach to concurrent programming based on the transactional semantics borrowed from database systems. In this paradigm, a transaction is a sequence of actions that may execute in a single logical instant, as though it was the only one being executed at that moment. Unlike concurrent systems based in locks, TM does not enforce that a single thread is performing the guarded operations. Instead, like in database systems, transactions execute concurrently, and the effects of a transaction are undone in case of a conflict, as though it never happened. The advantages of TM are an easier and less error-prone programming model, and a potential increase in scalability and performance. In spite of these advantages, TM is still a young and immature technology, and has still to become an established programming model. It still lacks the paraphernalia of tools and standards which we have come to expect from a widely used programming paradigm. Testing and analysis techniques and algorithms for TM programs are also just starting to be addressed by the scientific community, making this a leading research work is many of these aspects. This work is aimed at statically identifying possible runtime anomalies in TM programs. We addressed both low-level dataraces in TM programs, as well as high-level anomalies resulting from incorrect splitting of transactions. We have defined and implemented an approach to detect low-level dataraces in TM programs by converting all the memory transactions into monitor protected critical regions, synchronized on a newly generated global lock. To validate the approach, we have applied our tool to a set of tests, adapted from the literature, that contain well documented errors. We have also defined and implemented a new approach to static detection of high-level concurrency anomalies in TM programs. This new approach works by conservatively tracing transactions, and matching the interference between each consecutive pair of transactions against a set of defined anomaly patterns. Once again, the approach was validated with well documented tests adapted from the literature.

Keywords: Transactional Memory, Concurrent Programming, Concurrency Anomalies, Pro- gram Testing, Program Validation, Static Analysis, Program Transformation.