Orientador: Guido Costa Souza de AraújoTese (doutorado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: Sistemas de Memória Transacional em Software (MTS) têm sido usados como uma abordagem para melhorar o desempenho ao permitir a execução concorrente de blocos atômicos. Porém, em cenários com alta contenção, sistemas baseados em MTS podem diminuir o desempenho consideravelmente, já que a taxa de conflitos aumenta. Políticas de gerenciamento de contenção têm sido usadas como uma forma de selecionar qual transação abortar quando um conflito ocorre. No geral, gerenciadores de contenção não são capazes de evitar conflitos, tendo em vista que eles apenas selecionam qual transação abortar e o momento em que ela deve reiniciar. Como gerenciadores de contenção agem somente após a detecção de um conflito, é difícil aumentar a taxa de transações finalizadas com sucesso. Abordagens mais pró-ativas foram propostas, focando na previsão de quando uma transação deve abortar e atrasando o início de sua execução. Contudo, as técnicas pró-ativas continuam sendo limitadas, já que elas não substituem a transação fadada a abortar por outra transação com melhores probabilidades de sucesso, ou quando o fazem, dependem do sistema operacional para essa tarefa, tendo pouco ou nenhum controle de qual transação será a substituta. Esta tese apresenta o LUTS, Lightweight User-Level Transaction Scheduler, um escalonador de transação de baixo custo em nível de usuário. Diferente de outras técnicas, LUTS provê maneiras de selecionar outra transação a ser executada em paralelo, melhorando o desempenho do sistema. Nós discutimos o projeto do LUTS e propomos uma heurística dinâmica, com o objetivo de evitar conflitos, que foi construída utilizando os métodos disponibilizados pelo LUTS. Resultados experimentais, conduzidos com os conjuntos de aplicações STAMP e STMBench7, e executando nas bibliotecas TinySTM e SwissTM, mostram como nossa heurística para evitar conflitos pode melhorar efetivamente o desempenho de sistema de MTS em aplicações com alta contençãoAbstract: Software Transaction Memory (STM) systems have been used as an approach to improve performance, by allowing the concurrent execution of atomic blocks. However, under high-contention workloads, STM-based systems can considerably degrade performance, as transaction conflict rate increases. Contention management policies have been used as a way to select which transaction to abort when a conflict occurs. In general, contention managers are not capable of avoiding conflicts, as they can only select which transaction to abort and the moment it should restart. Since contention manager's act only after a conflict is detected, it becomes harder to effectively increase transaction throughput. More proactive approaches have emerged, aiming at predicting when a transaction is likely to abort, postponing its execution. Nevertheless, most of the proposed proactive techniques are limited, as they do not replace the doomed transaction by another or, when they do, they rely on the operating system for that, having little or no control on which transaction to run. This article proposes LUTS, a Lightweight User-Level Transaction Scheduler. Unlike other techniques, LUTS provides the means for selecting another transaction to run in parallel, thus improving system throughput. We discuss LUTS design and propose a dynamic conflict-avoidance heuristic built around its scheduling capabilities. Experimental results, conducted with the STAMP and STMBench7 benchmark suites, running on TinySTM and SwissTM, show how our conflict-avoidance heuristic can effectively improve STM performance on high contention applicationsDoutoradoCiência da ComputaçãoDoutor em Ciência da Computação