ESTUDO SOBRE MEMÓRIA TRANSACIONAL EM SOFTWARE.
José Gonçalves Dias Neto
Universidade Estadual de Mato Grosso do Sul (UEMS), Unidade de Nova Andradina
[email protected]
Irineu Sotoma
FACOM – Universidade Federal de Mato Grosso do Sul, Campus Campo Grande
[email protected]
Resumo: O crescente desenvolvimento da arquitetura multi-core, ampliou-se a possibilidade
de execução de rotinas paralelamente. O atual desenvolvimento multithreading permite
explorar este paralelismo, porém a utilização de programação baseada em locks dificulta a
tarefa do programador de tirar o máximo proveito desta arquitetura e facilita o aparecimento
de problemas como deadlock e starvation. Memória Transacional veio para tentar diminuir a
complexidade de programação paralela e tentar aproveitar ao máximo os núcleos disponíveis
aumentando a vazão (throughput) do sistema, utilizando basicamente gerentes de contenção
para tratar conflitos, sendo esta uma abordagem unicamente reativa. Abordagens mais
recentes utilizam formas pró-ativas que apenas trazem benefícios em cenários muito
específicos e utilizam um mecanismo até certo ponto simplista de adaptatividade para tentar
manter o mínimo de desempenho nos demais cenários. Através deste trabalho, objetivamos o
desenvolvimento de uma política pró-ativa de escalonamento de transações, que utilize-se de
heurísticas de baixa sobrecarga, para evitar conflitos em memória transacional em software e
que propicie uma melhor adaptatividade em cenários diversos.
Palavras-chave: Medidas Pró-ativas, Escalonamento Pró-ativo, Memória Transacional,
Memória Transacional em Software, STM, Software Transaction Memory.
Introdução
Com o advento de novas arquiteturas, em especial a multi-core, a qual disponibiliza
um sistema com mais de um núcleo de processamento, intensificou-se a busca pelo
desenvolvimento de programas que sejam capazes de executar instruções paralelamente,
permitindo maior vazão de instruções executadas no sistema. A programação multithreading
utiliza-se bem desta estrutura de múltiplos núcleos e permite que threads executem
concomitantemente em núcleos diferentes.
Para permitir que as diversas threads que encontram-se em execução não interfiram
em dados compartilhados, este modelo faz uso de bloqueios (locks) e variáveis condicionais.
Isto proporciona segurança ao acesso de dados compartilhados porém, acarreta uma série de
desvantagens. Devido a sua maior complexidade de programação, exige-se muito conheci-
2
mento e atenção por parte do programador, pois qualquer erro de sincronização pode levar a
situações de deadlock ou starvation (Tanenbaum, 2010).
Com o intuito de facilitar este tipo de programação surgiu o conceito de Memória
Transacional (Tansactional Memory - TM). Esta abordagem visa a criação de blocos
indivisíveis de comandos, denominados transações, que possuem a propriedade de execução
atômica, similarmente a operações realizadas em sistemas de banco de dados.
As transações podem gerar conflitos quando tentam efetuar alterações em áreas de
memória utilizadas por outra transação. Para evitar que esses conflitos gerem problemas
posteriores, é utilizado um módulo denominado Gerente de Contenção, o qual indica qual(ais)
transação(ões) deve(em) ser abortada(s), para que alguma seja confirmada (Herlihy, Shavit,
2008).
Surgiram então 3 (três) abordagens de memória transacional: Memória Transacional
em Hardware (Hardware Transactional Memory – HTM), Memória Transacional em Software
(Software Transactional Memory – STM) e Memória Transacional Híbrida (Hybrid
Transactional Memory – HyTM). O presente estudo restringe-se a Memória Transacional em
Software devido principalmente a maior simplicidade e baixo custo de desenvolvimento de
plataforma.
Benchmarks são utilizados para mensurar o desempenho de cada solução. Dentre os
mais utilizados estão o STAMP, STMBench7 e os Microbenchmarks de Árvores Rubronegras.
Nosso objetivo com este trabalho é propor uma abordagem pró-ativa de baixa
sobrecarga no sistema transacional, para aumentar o desempenho global em cenários de alta
contenção. Além disso pretendemos desenvolver uma técnica adaptativa multinível, para
melhor aproveitamento dos diversos cenários possíveis que o sistema possa vir a sofrer
alternância.
Objetivos
Estudar as diversas abordagens pró-ativas relevantes presentes na literatura e propor
um sistema de heurísticas que gere baixa sobrecarga (overhead) em STM.
Desenvolver uma solução que trabalhe pró-ativamente, utilizando um maior número
de informações referentes ao estado atual do sistema e possivelmente do catálogo de
3
transações correntes, que seja capaz de se adaptar a diversos cenários que possam ocorrer em
um sistema STM convencional.
Metodologia
O início do desenvolvimento do presente projeto deu-se a partir da realização da
revisão bibliográfica, o que nos permitiu estudar e comparar trabalhos relacionados em artigos
e periódicos, além de livros que melhor explanem conceitos básicos sobre a área escolhida. A
partir do levantamento e realização de estudos sobre diferenças, potencialidades de
deficiências de cada técnica contemplada, será possível a execução das próximas etapas a
seguir:
1.
Implementar algumas das técnicas estudadas a fim de compreender mais a
fundo a forma de atuação destas e na execução de testes comparativos, para no futuro
comprovar se a solução final do trabalho terá ou não benefícios em relação às abordagens
atuais. Como plataforma STM será utilizada a STM Builder desenvolvida por Duarte (2012)
que é uma derivação da SwissTM, esta última considerada por pesquisadores como uma
plataforma ainda em estado da arte.
2.
Estudar meios de tomar decisões diferentes no caso de conflitos escrita/escrita
(eager) e leitura/escrita (lazy) usando possivelmente informações diferentes: A partir da
premissa de que conjuntos de leitura e de escrita possuem características diferentes e que as
instruções de escrita podem distintos dentro de uma transação, o estudo dos momentos em que
os conflitos são identificados poderia gerar uma nova técnica que auxiliar a no ganho de
desempenho de nossa solução.
3.
Estudar como definir os momentos de adaptação das técnicas: Estudar os
diversos cenários específicos que podem ocorrer durante a execução de cargas de trabalho
STM, propondo e implementando uma solução de adaptação multinível. Confrontar
resultados obtidos em benchmarks a partir da forma atual de adaptação contra resultados
obtidos a partir da nova solução de adaptação multinível.
Resultados e Considerações Parciais
Notamos que os esforços para construção e melhorias em gerentes de contenção têm
incrementando o desempenho em sistemas de alta contenção, porém a abordagem pró-ativa,
4
que visa evitar que um conflito seja deflagrado, nos apresentou maior vantagem por utilizar
técnicas que tentam evitar o desperdício de recursos como o tempo de CPU.
Através do estudo de abordagens que utilizam formas de adaptação, foi identificado
que a maioria destas abordagens se restringe a alternância binária, ou seja, divide os possíveis
cenários que o sistema possa se encontrar em unicamente dois estágios (alta e baixa contenção
ou transações curtas e longas). Uma proposta que nos apresenta interessante é efetuar uma
maior divisão, objetivando o refinamento das possíveis situações do sistema em cenários mais
específicos.
O mecanismo de estabilização nos parece bastante vantajoso por economizar
alternâncias entre cenários em casos onde os limiares responsáveis pela verificação do estado
atual do sistema ficam por vezes muito próximos à fronteira entre dois cenários distintos,
além de aparentemente ser uma implementação leve e simples de ser efetuada. Assim a
proposta que nos parece ser adequada, seria a utilização deste mecanismo entre todos os
possíveis cenários que forem identificados e implementados.
Referências
DUARTE, Thales Farias. Uma Plataforma Para Desenvolvimento E Avaliação De Memória
Transacional Em Software. Dissertação de mestrado apresentada à Universidade Federal do
Mato Grosso do Sul - Faculdade de Computação, Agosto 2012.
HERLIHY, Maurice, SHAVIT, Nir. The Art of Multiprocessor Programming. Morgan
Kaufmann Publishers, 2008.
TANENBAUM, Andrew S. . Sistemas operacionais modernos 3a edição. Pearson Prentice
Hall, 2010.