João Lourenço

Software Transactional Memory (STM) algorithms correctness rely on metadata associated with the memory locations accessed during the transaction life-time. STM implementations may store this metadata either in-place, by wrapping the memory cells in a container that includes the memory cell itself and the corresponding metadata, or out-place, by resorting to a mapping function that associates the memory cell address to an external table with 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 algorithms that fall into the appropriate category, and inhibiting the fair comparison with STM algorithms falling into the other. In this paper we introduce a technique that supports the use of in-place metadata without requiring to wrap memory cells, thus providing STM algorithms with direct access to the transactional metadata and overcoming the bias. The proposed technique is available as an extension to the DeuceSTM framework and allows the efficient implementation of a wide range of STM algorithms, thus enabling 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, which bias to out-place and in-place respectively.

A set of methods defining an API (Application Programming Interface) are to be made thread safe; thus running any subset of these methods in parallel should not create races or deadlocks. Originally, the set of methods were not designed to be thread safe, so races and deadlocks are expected when running them in parallel. The number of possible interleavings when running methods from this API in parallel is huge, and this work focuses on the identification of the high level data races introduced by such interleavings. We propose an analysis that avoids the exhaustive exploration of all possible interleavings. For a concurrent program P, the closure of P, clos(P), is defined. Roughly speaking, we can say that the clos(P) is obtained by adding threads to P in such a way that high level data races resulting from running P in parallel to other programs are exposed statically. A set of methods representing the API is then modeled as a set of concurrent programs and their closure is analysed to identify high level data races. These high level data races are then inspected and removed to make the API thread safe. We illustrate the application of this methodology with a simple use case.

This paper presents an automatic verification technique for transactional memory Java programs executing under snapshot isolation level. We certify which transactions in a program are safe to execute under snapshot isolation without triggering the write-skew anomaly, opening the way to run-time optimizations that may lead to considerable performance enhancements. Our work builds on a novel deep-heap analysis technique based on separation logic to statically approximate the read- and write-sets of a transactional memory Java program. We implement our technique and apply our tool to a set of micro benchmarks and also to one benchmark of the STAMP package. We corroborate known results, certifying some of the examples for safe execution under snapshot isolation by proving the absence of write-skew anomalies. In other cases our analysis has identified transactions that potentially trigger previously unknown write-skew anomalies.>

Uma das estratégias para tirar partido dos múltiplos processadores disponíveis nos computadores atuais passa por adaptar código legado, inicialmente concebido para ser executado num contexto meramente sequencial, para ser agora executado num contexto multithreading. Nesse processo de adaptação é necessário proteger apropriadamente os dados que são agora partilhados e acedidos por diferentes threads concorrentes. A proteção dos dados com locks usando uma granulosidade grossa inibe a concorrência e opõe-se ao objetivo inicial de explorar o paralelismo suportado por múltiplos processadores. Por outro lado, a utilização de uma granulosidade fina pode levar à ocorrência de anomalias próprias da concorrência, como deadlocks e violações de atomicidade (high-level data races). Este artigo discute o conceito de fecho de um programa e uma metodologia que, quando aplicados em conjunto, permitem adaptar código legado para o tornar thread-safe, garantindo a ausência de violações de atomicidade na versão corrente do software e antecipando algumas violações de atomicidade que poderão ocorrer em versões futuras do mesmo software.

As técnicas e algoritmos desenvolvidos sobre diferentes infraestruturas específicas dificilmente podem ser comparados entre si. Este princípio também se aplica às infraestruturas para execução de Memória Transacional Distribuída (MTD), pois não só são muito escassas aquelas que permitem o desenvolvimento, teste e comparação de vários algoritmos e técnicas de implementação, como fornecem uma interface intrusiva para o programador. Sem uma comparação justa, não é possível aferir quais as técnicas e algoritmos mais apropriados em cada contexto de utilização (workload). Neste artigo propomos uma infraestrutura generalista, muito flexível, que possibilita a experimentação de várias estratégias de MTD, permitindo o desenvolvimento de uma grande variedade de algoritmos e de técnicas de implementação eficientes e otimizadas. Através da sua utilização, é agora possível a comparação de técnicas e algoritmos em diferentes contextos de utilização (workloads), recorrendo a uma única infraestrutura e com implicações mínimas no código da aplicação.

Concurrent programs that are free of unsynchronized ac- cesses to shared data may still exhibit unpredictable concurrency errors called atomicity violations, which include both high-level dataraces and stale-value errors. Atomicity violations occur when programmers make wrong assumptions about the atomicity scope of a code block, incorrectly splitting it in two or more atomic blocks and allow them to be interleaved with other atomic blocks. In this paper we propose a novel static analysis algorithm that works on a dependency graph of program variables and detects both high-level dataraces and stale-value errors. The algorithm was implemented for a Java Bytecode analyzer and its effectiveness was evaluated with some well known faulty programs. The results obtained show that our algorithm performs better than previous approaches, achieving higher precision for small and medium sized programs, making it a good basis for a practical tool.

Software transactional memory (STM) algorithms associate metadata with the memory locations accessed during a transaction's lifetime. This metadata may be stored in an external table by resorting to a mapping function that associates the address of a memory cell with the table entry containing the corresponding metadata (out-place or external strategy). Alternatively, the metadata may be stored adjacent to the associated memory cell by wrapping the cell and metadata together (in-place strategy). The implementation techniques to support 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 which suit one of the approaches and inhibiting a fair comparison with STM algorithms suiting the other. In this paper, we introduce a technique to implement in-place metadata that does not wrap memory cells, thus overcoming the bias and allowing STM algorithms to directly access the transactional metadata. The proposed technique is available as an extension to Deuce and enables the efficient implementation of a wide range of STM algorithms and their fair (unbiased) comparison in a common STM framework. We illustrate the benefits of our approach by analyzing its impact in two popular transactional memory algorithms with several transactional workloads, TL2 and multiversioning, each befitting out-place and in-place, respectively.

n/a

n/a

n/a

Os sistemas de memória transacional distribuída atuais recorrem essencialmente à distribuição ou à replicação total para distribuir os seus dados pelos múltiplos nós do sistema. No entanto, estas estratégias de replicação de dados apresentam limitações. A distribuição não oferece tolerância a falhas e a replicação total limita a capacidade de armazenamento do sistema. Nesse contexto, a replicação parcial de dados surge como uma solução intermédia, que combina o melhor das duas anteriores com o intuito de mitigar as suas desvantagens. Esta estratégia tem sido explorada no contexto das bases de dados distribuídas, mas tem sido pouco abordada no contexto da memória transacional e, tanto quanto sabemos, nunca antes tinha sido incorporada num sistema de memória transacional distribuída para uma linguagem de propósito geral. Assim, neste artigo propomos e avaliamos uma infraestrutura para replicação parcial de dados para programas Java bytecode, que foi desenvolvida com base num sistema já existente de memória transacional distribuída. A modularidade da infraestrutura que apresentamos permite a implementação de múltiplos algoritmos e, por conseguinte, avaliar em que contextos de utilização (workloads, número de nós, etc.) a replicação parcial se apresenta como uma alternativa viável a outras estratégias de replicação de dados.

n/a

A programação concorrente obriga o programador a sincronizar os acessos concorrentes a regiões de memória partilhada, contudo esta abordagem não é suficiente para evitar todas as anomalias que podem ocorrer num cenário concorrente. Executar uma sequência de operações atómicas pode causar violações de atomicidade se existir uma correlação entre essas operações, devendo o programador garantir que toda a sequência de operações é executada atomicamente. Este problema é especialmente comum quando se usam operações de pacotes ou módulos de terceiros, pois o programador pode identificar incorretamente o âmbito das regiões de código que precisam de ser atómicas para garantir o correto comportamento do programa. Para evitar este problema o programador do módulo pode criar um contrato que especifica quais as sequências de operações do módulo que devem ser sempre executadas de forma atómica. Este trabalho apresenta uma análise estática para verificação destes contratos.

Os serviços Web são frequentemente suportados por sistemas com uma arquitetura em camadas, sendo utilizadas bases de dados relacionais para armazenamento dos dados. A replicação dos diversos componentes tem sido uma das formas utilizadas para obter melhorarias de escalabilidade destes serviços. Adicionalmente, a utilização de bases de dados em memória permite alcançar um desempenho mais elevado. No entanto é conhecida a fraca escalabilidade das bases de dados com o número de núcleos em máquinas multi-núcleo. Neste artigo propomos uma nova abordagem para lidar com este problema, intitulada MacroDDB. Utilizando uma solução de replicação hierárquica, a nossa proposta, replica a base da dados em vários nós, sendo que cada nó, por sua vez, executa um conjunto de réplicas da base de dados. Esta abordagem permite assim lidar com a falta de escalabilidade das bases de dados relacionais em máquinas multi-núcleo, o que por sua vez melhora a escalabilidade geral dos serviços.

Transactional memory (TM) is an increasingly popular technique for synchronising threads in multi-threaded programs. To address both correctness and performance-related issues of TM programs, one needs to monitor and analyse their execution. However, monitoring concurrent programs (including TM programs) may have a non-negligible impact on their behaviour, which may hamper the objectives of the intended analysis. In this paper, we propose several approaches for monitoring TM programs and study their impact on the behaviour of the monitored programs. The considered approaches range from specialised lightweight monitoring to generic heavyweight monitoring. The implemented monitoring tools are publicly available to the scientific community, and the implementation techniques used for lightweight monitoring of TM programs may be used as an inspiration for developing other specialised lightweight monitors.

In this paper we address a solution for detecting and tolerating one of the most typical concurrency bugs: atomicity violations. More specifically, we address High-Level Atomicity Violations (HLAV). High-level atomicity violations result from the misspecification of the scope of an atomic block, by splitting it in two or more atomic blocks which may be interleaved with other atomic blocks. Figure 1 shows an example of this type of atomicity violation. The intuitive idea behind HLAV is that if two shared data items (e.g., memory locations) were both accessed inside an atomic block, they are interrelated and probably the programmer intention is that there shall be no interleavings between these two accesses. Therefore, if (in the same program) this two addresses are accessed separately in different atomic blocks, an unfortunate interleaving may cause an atomicity violation.

n/a

Os protocolos de replicação parcial de dados apresentam um grande potencial de escalabilidade. O SCORe é um protocolo para replicação parcial proposto recentemente que faz uso de controlo de concorrência multi-versão. Neste artigo abordamos um dos problemas principais que afeta o desempenho deste tipo de protocolos: a localidade dos dados, i.e., pode-se dar o caso do nó local não ter uma cópia dos dados a que pretende aceder, e nesse caso é necessário realizar uma ou mais operações de leitura remota. Assim, a não ser que se empreguem técnicas para melhorar a localidade no acesso aos dados, o número de operações de leitura remota aumenta com o tamanho do sistema, acabando por afetar o desempenho do mesmo. Nesse sentido, introduzimos um mecanismo de caching que permite replicar cópias de dados remotos de maneira a que seja poss{\'ı}vel servir localmente dados remotos enquanto que se mantém a consistência dos mesmos e a escalabilidade oferecida pelo protocolo. Avaliamos o mecanismo de caching com um benchmark conhecido da literatura e os resultados experimentais mostram resultados animadores com algum aumento no desempenho do sistema e uma redução considerável da quantidade de operações de leitura remota.

n/a

Multi-threaded programs allow one to achieve better performance by doing a lot of work in parallel using multiple threads. Such parallel programs often contain code blocks that a thread must execute atomically, i.e., with no interference from the other threads of the program. Failing to execute these code blocks atomically leads to errors known as atomicity violations. However, frequently it not obvious to tell when a piece of code should be executed atomically, especially when that piece of code contains calls to some third-party library functions, about which the programmer has little or no knowledge at all. One solution to this problem is to associate a contract with such a library, telling the programmer how the library functions should be used, and then check whether the contract is indeed respected. For contract validation, static approaches have been proposed, with known limitations on precision and scalability. In this paper, we propose a dynamic method for contract validation, which is more precise and scalable than static approaches.

Neste artigo apresentamos um protocolo de controlo de concorrência que garante que a execução concorrente de transações é equivalente à sua execução sequencial por uma ordem predefinida. Isto permite executar programas que usam transações de forma determinista. O protocolo (1) permite, pela primeira vez, a execução determinista de programas que usam memória transacional por hardware; e (2) garante a execução determinista de programas que usam memória transacional por software com um desempenho claramente superior ao estado da arte.

Software Transactional Memory algorithms associate metadata with the memory locations accessed during a transactions lifetime. This metadata may be stored in an external table and accessed by way of a function that maps the address of each memory location with the table entry that keeps its metadata (this is the out-place or external scheme); or alternatively may be stored adjacent to the associated memory cell by wrapping them together (the in-place scheme). In transactional memory multi-version algorithms, several versions of the same memory location may exist. The efficient implementation of these algorithms requires a one-to-one correspondence between each memory location and its list of past versions, which is stored as metadata. In this chapter we address the matter of the efficient implementation of multi-version algorithms in Java by proposing and evaluating a novel in-place metadata scheme for the Deuce framework. This new scheme is based in Java Bytecode transformation techniques and its use requires no changes to the application code. Experimentation indicates that multi-versioning STM algorithms implemented using our new in-place scheme are in average 6 × faster than when implemented with the out-place scheme.

Software developers are expected to protect concurrent accesses to shared regions of memory with some mutual exclusion primitive that ensures atomicity properties to a sequence of program statements. This approach prevents data races but may fail to provide all necessary correctness properties.The composition of correlated atomic operations without further synchronization may cause atomicity violations. Atomic violations may be avoided by grouping the correlated atomic regions in a single larger atomic scope. Concurrent programs are particularly prone to atomicity violations when they use services provided by third party packages or modules, since the programmer may fail to identify which services are correlated. In this paper we propose to use contracts for concurrency, where the developer of a module writes a set of contract terms that specify which methods are correlated and must be executed in the same atomic scope. These contracts are then used to verify the correctness of the main program with respect to the usage of the module(s). If a contract is well defined and complete, and the main program respects it, then the program is safe from atomicity violations with respect to that module. We also propose a static analysis based methodology to verify contracts for concurrency that we applied to some real-world software packages. The bug we found in Tomcat 6.0 was immediately acknowledged and corrected by its development team.

Distributed transactional memory (DTM) presents itself as a highly expressive and programmer friendly model for concurrency control in distributed programming. Current DTM systems make use of both data distribution and replication as a way of providing scalability and fault tolerance, but both techniques have advantages and drawbacks. As such, each one is suitable for different target applications, and deployment environments. In this paper we address the support of different data replication models in DTM. To that end we propose ReDstm, a modular and non-intrusive framework for DTM, that supports multiple data replication models in a general purpose programming language (Java). We show its application in the implementation of distributed software transactional memories with different replication models, and evaluate the framework via a set of well-known benchmarks, analysing the impact of the different replication models on memory usage and transaction throughput.

Given the proliferation and enhanced capabilities of mobile devices, their computational and storage resources can now be combined in a wireless cloud of nearby mobile devices, a mobile edge-cloud. These clouds are of particular interest in low connectivity scenarios, e.g., sporting events and disaster scenarios. In these dynamic clouds it is necessary to reliably disseminate and share data, and also to offload data processing computations to other devices in the edge-cloud. We are particularly interested in supporting storage services in these new type of edge-clouds, as a mean to enable data sharing, dissemination and querying, as well as to serve as a distributed file system for offloaded computations. In this Ph.D. thesis, we propose to address these questions by researching on the usage of ad-hoc clouds of mobile devices to develop an efficient storage service capable of providing high availability and reliability.