Implementations of Software Transactional Memory (STM) algorithms associate metadata with the memory locations accessed during a transaction’s lifetime. This metadata may be stored either in-place, by wrapping every memory cell in a container that includes the memory cell itself and the corresponding metadata; or out-place (also called external), by resorting to a mapping function that associates the memory cell address with an external table entry containing the corresponding metadata. The implementation techniques for these two approaches are very different and each STM framework is usually biased towards one of them, only allowing the efficient implementation of STM algorithms following that approach, hence inhibiting the fair comparison with STM algorithms falling into the other. In this paper we introduce a technique to implement in-place metadata that does not wrap memory cells, thus overcoming the bias by allowing STM algorithms to directly access the transactional metadata. The proposed technique is available as an extension to the DeuceSTM framework, and enables the efficient implementation of a wide range of STM algorithms and their fair (unbiased) comparison in a common STM infrastructure. We illustrate the benefits of our approach by analyzing its impact in two popular TM algorithms with two different transactional workloads, TL2 and multi-versioning, with bias to out-place and in-place respectively.

n/a

Concurrent programs may suffer from concurrency anomalies that may lead to erroneous and unpredictable program behaviors. To ensure program correctness, these anomalies must be diagnosed and corrected. This paper addresses the detection of both low- and high-level anomalies in the Transactional Memory setting. We propose a static analysis procedure and a framework to address Transactional Memory anomalies. We start by dealing with the classic case of low-level dataraces, identifying concurrent accesses to shared memory cells that are not protected within the scope of a memory transaction. Then, we address the case of high-level dataraces, bringing the programmer's attention to pairs of memory transactions that were misspecified and should have been combined into a single transaction. Our framework was applied to a set of programs, collected form different sources, containing well known low- and high-level anomalies. The framework demonstrated to be accurate, confirming the effectiveness of using static analysis techniques to precisely identify concurrency anomalies in Transactional Memory programs.

In this paper we present MoTh, a tool that uses static analysis to enable the automatic verification of concurrency anomalies in Transactional Memory Java programs. Currently MoTh detects high-level dataraces and stale-value errors, but it is extendable by plugging-in sensors, each sensor implementing an anomaly detecting algorithm. We validate and benchmark MoTh by applying it to a set of well known concurrent buggy programs and by close comparison of the results with other similar tools. The results achieved so far are very promising, yielding good accuracy while triggering only a very limited number of false warnings.

n/a

n/a

n/a

n/a

Transactional Memory (TM) is an approach to concurrency control in general pur- pose programming languages that inherits the concept of transaction from the database setting. Unlike other language constructs such as locks, TM has an optimistic approach to concurrency control by allowing more than one thread to access simultaneously the same critical section. A transaction always executes as if it is alone in the system, and in the end its effects are undone (rolled back) if it conflicts with another concurrent transac- tions. In spite of the potential for increasing scalability and performance, TM is a recent and developing programming model and still has a very limited impact in real-world applications.
Designing and developing concurrent software is difficult and error prone. Concur- rent programs exhibit concurrency anomalies that originate faults and failures. Despite some claims that TM programs are less error prone, they still exhibit concurrency anoma- lies such as high-level dataraces, i.e., wrong delimitations of transactions’ scope, and stale-value errors, that occur when the value of a shared variable jumps from an atomic block to another.
Programs with this kind of anomalies can exhibit unpredictable and wrong behaviour, not fulfilling the goals for which they were conceived.
This work aims the detection of anomalies through static analysis of transactional Java ByteCode programs that execute in strong atomicity. A extensible and flexible framework is proposed, which can be extended with plugins that detect specific types of anomalies. With this framework we expect to prove that high-level dataraces and stale-value errors can be detected with reasonable precision through static analysis.

Keywords: Atomicity Violation, High-Level Datarace, Static Analysis, Concurrency, Software Transactional Memory