mo601-115168-relatorio

Prévia do material em texto

Memória Transacional
MO601- Arquitetura de Computadores II
Walisson F. Pereira1
1Instituto de Computação – Universidade Estadual de Campinas
Av. Albert Einstein, 1251 – 13083-850 Campinas, SP
walisson@ic.unicamp.br
Abstract. Parallel computing has enabled a considerable performance gain in
the programs’ execution, dividing them into smaller pieces and concurrently sol-
ving them using multiple computational resources. This approach has brought
several benefits compared to sequential programming, allowing solve increasin-
gly complex and time dwindling. The transactional memory has emerged as a
new proposal for multiprocessor architecture that supports implementing lock-
free complex data structures in a simple and efficient way. In this work, we
discussed some basic concepts of transactional memory giving a quick overview
of some design alternatives that can be adopted.
Resumo. A computação paralela permitiu um considerável ganho de desempe-
nho na execução dos programas, dividindo-os em partes menores e resolvendo-
as concorrentemente usando múltiplos recursos computacionais. Essa abor-
dagem trouxe uma série de benefı́cios em relação a programação sequencial,
permitindo resolver problemas cada vez mais complexos e em tempo cada vez
menor. A memória transacional surgiu como uma nova proposta de arquitetura
multiprocessada que suporta a implementação lock-free de estruturas de dados
complexas de uma forma simples e eficiente. Nesse trabalho é discutido alguns
conceitos básicos das memória transacional dando uma rápida visão geral so-
bre algumas alternativas de projeto que podem ser adotadas.
1. Introdução
A memória transacional, do inglês Transactional Memory (TM), é uma nova arquitetura
multiprocessada que suporta a implementação lock-free de estruturas de dados comple-
xas de uma forma simples e eficiente [Herlihy and Moss, 1993]. Uma estrutura é dita
lock-free se as operações definidas para ela não requerem exclusão mútua sobre multi-
plas instruções [Culler et al., 1999], ou seja, se um processo é interrompido no meio da
operação, outros processos não serão impedidos de operarem nessa estrutura.
As estruturas de dados lock-free evitam problemas comuns associados as técnicas
de locks convencionais em sistemas altamente concorrentes:
• Inversão de prioridade: ocorre quando um processo de baixa prioridade é adqui-
rido por preempção enquando mantém um lock necessário pelos processos de alta
prioridade.
• Proteção: ocorre quando um processo matém um lock e é substituı́do pelo escalo-
nador, talvez por ultrapassar seu quantum, por uma falha de página, ou por algum
tipo de interrupção. Quando tal interrupção ocorre, outros processos capazes de
rodarem podem ficar ináptos de progredir.
• Deadlock: pode ocorrer se os processos tentarem travar o mesmo conjunto de
objetos em ordens diferentes. Evitar Deadlock pode ser ineficaz se os processos
puderem travarem multiplos objetos de dados, particularmente se o conjunto de
objetos não forem conhecidos de antemão.
As TM permite os programadores definirem operações read-modify-write perso-
nalizadas que aplicam a múltiplas e independetes palavras escolhidas da memória. Ela é
implementada por extensões diretas para algum protocolo de coerência de cache multi-
processada baseada em propriedade.
O conceito de transação originou-se na literatura de banco de dados [Gray, 1978],
e de acordo com [Harris et al., 2010], uma transação é uma sequência de ações que pare-
cem indivisı́veis e instantâneas para um observador externo. Em outras palavras, quando
uma transação termina corretamente, diz-se que ela efetiva-se (do inglês, commit), ou caso
ela falhe, então a transação é abortada e nenhuma de suas ações é visı́vel. Uma transação
satisfaz as seguintes propriedades:
• Serialização: transações aparentam ser executadas serialmente, significando que
cada passo de uma transação nunca aparenta ser entrelaçada com o passo de outra.
Transações concluı́das nunca são observada por processadores diferentes execu-
tando em ordens diferentes.
• Atomicidade: cada transação realiza uma sequência de tentativa de mudanças na
memória compartilhada. Quando a transação completa, ela, então, se efetiva, fa-
zendo suas mudanças visı́veis para os outros processos (efetivamente) instantane-
amente, ou então, ela aborta, fazendo suas mudanças serem descartadas.
A memória transacional é um mecanismo que promete habilitar desempenho es-
calável enquanto libera os programadores de alguns encargos para modificar seus códigos
paralelos. Os modelos de programação multithreads tradicionais geralmente oferecem
um conjunto de primitivas de baixo nı́vel, como locks, para garantir a exclusão mútua.
Os Locks são complexos para se usar e propenso a erros – especialmente quando um
programador está tentando evitar situações de deadlock ou alcançar melhor escalabili-
dade em hardware altamente paralelos usando um lock de granulação refinada. Nesse
cenário, a TM é um mecanismo promissor para lidar com este problema através da
abstração das complexidades associadas com o acesso concorrente de dados comparti-
lhados [Larus and Rajwar, 2007]. Entretanto, apesar de usar mecanismos similares as
transações de banco de dados clássicos, o principal propósito da TM é diferente: lidar
com os desafios da concorrência na memória compartilhada em chips com multiproces-
sadores.
As transações substituem os locks com unidades de execuções atômicas, tal que o
programador pode focar em determinar onde a atomicidade é necessária, ao invés de se
preocupar nos mecanismos que a reforçará. Com essa abstração, o programador identifica
as operações que formam a seção crı́tica, enquanto a implementação da TM determina
como rodar esta seção crı́tica de forma isolada de outros threads.
Geralmente, o termo “conflito” significam uma violação na ordem temporal e
“prévio” é usado no sentido da ordenação temporal [Harris et al., 2010]. Se as transações
não conflitam, então abordagens otimistas vale a pena. Como o exemplo de uma transação
que realiza apenas acessos somente para leitura de dados compartilhados e permite que to-
dos os dados possam permanecer nas caches de dados no modo compartilhado, ajudando
a escalabilidade.
Se as transações tentarem realizar acessos conflitante, então o otimismo não vale
a pena. Nesse caso, a TM deve abandonar o trabalho de uma das transações conflitantes,
garantindo que nenhum efeito colateral dessa tentativa seja visı́vel para outras threads,
antes de reexecutar a transação abandonada.
Comparado com a TM, os locks são abordagens pessimistas. Com os locks de
exclusão múltua, apenas uma thread pode ter o lock para si por vez, enquanto que a
maioria das implementações de TM, mais que uma thread pode acessar uma seção crı́tica
simultaneamente.
Devido os conflitos atuais serem raros em muitos programas, abordagens
de TM otimistas fazem mais sentido como um modelo de programação futuro
[Harris et al., 2007]. As vantagens da TM sobre os locks são:
• A TM provém uma abstração de alto nı́vel para a escrita de programas concorren-
tes;
• A TM provém um melhor trade-off entre escalabilidade e esforço de
implementação;
• A TM é inerentemente livre de deadlock;
• A TM provém atomicidade de falha.
As desvantagens da TM são:
• Devido a abstração de alto nı́vel, um algoritmo cuidadosamente projetado usando
primitivas de baixo nı́vel pode superar o desempenho de um algorı́tmo usando
TM;
• Existem muitas questões sobre como expor a TM aos programadores: exatamente
que tipo de abstração prover e que tipo de ajuste de desempenho e ferramentas de
depuração desenvolver.
O foco deste trabalho é apresentar uma visão geral sobre memória transacional.
A seção 2 apresenta uma visão geral sobre as transações em bancos de dados; a seção
3 apresenta alguns conceitos básicos da TM; a seção4 apresenta os tipos principais de
implementação da TM; a seção 5 ilustra alguns dos desafios de se projetar uma TM; e,
por último, a seção 6 conlui o trabalho com algumas considerações finais.
2. Transações em banco de dados
Apesar do paralelismo ser um problema difı́cil para a programação de propósito geral,
dependendo muito do programador, os bancos de dados conseguem explorá-lo de maneira
satisfatória. As TM compartilham muitas caracterı́sticas em comum com as transações de
banco de dados, da terminologia e similaridades sintáticas até as propriedades que elas
provêm [Felber et al., 2008].
O controle de concorrência tem sido estudado por décadas no campo dos sistemas
de banco de dados, onde operações diferentes podem acessar tabelas simultanemantes
sem observar-se interferência. Transações são um mecanismo poderoso para gerenciar
tais acessos concorrtes a um banco de dados.
As transações garantêm as quatro propriedades denominadas ACID:
• Atomicidade: uma transação executa completamente ou não executa;
• Consistência: as transações são uma transformação correta de estado;
• Isolamento: apesar das transações executarem concorrentemente, aparenta que
para cada transação T que outras transações executam tanto antes de T ou depois
de T , mas não ao mesmo tempo;
• Durabilidade: modificações realizadas por transações completadas sobrevivem às
falhas. Este comportamento é implementado pelo controlador para acessar dados
compartilhados e desfazer as ações de uma transação que não completou com
sucesso (roll-back)
3. Memória transacional
Diferentemente das transações de bancos de dados, as transações de memória são pla-
nejadas para serem atividades de curta duração que acessam um número relativamente
pequeno de locais na memória principal. O tamanho e duração ideal de uma transação é
dependente da implementação, mas, de modo geral, uma transação deve ser apta a rodar
completamente em um simples quantum de escalonamento, e o número de locais acessa-
dos não deve exceder ao tamanho da cache do processador.
Uma transação em TM é definida como uma sequência de instruções, incluindo
leituras e escritas à memória, que ou executa completamente (efetiva-se) ou que não te-
nha efeito (aborta-se). Quando uma transação efetiva, todas as suas escritas tornam-se
visı́veis, e outras transações podem usar esses valores. Quando uma transação aborta, o
sistema descarta todas as suas escritas especulativas. Para isso, o sistema de TM precisa
de um mecanismo de versionamento de dados para gravar suas escritas especulativas.
As duas abordagens mais utilizadas para implementar o versionamento de dados
são: o undo log e o buffered updates. No undo log, uma transação aplica atualizações
diretamente no endereço de memória, enquanto escreve um log com as informações ne-
cessárias para desfazer as atualizações no caso precise abortar. No buffered update, a TM
mantém o estado especulativo da transação num buffer privado até o momento de sua
efetivação. Se a efetivação ocorre, os valores originais são descartados e o conteúdo do
buffer é efetivado na memória.
Uma sequência de instruções de transação podem ser delimitadas explicitamente
ou implicitamente. É demilitada explicitamente quando tokens especiais são utiliza-
dos para indicar o inı́cio e o fim da transação, por exemplo, START TRANSACTION e
END TRANSACTION. A transação é dita ser delimitada implicitamente quando ela é ini-
ciada implicitamente após a execução de uma operação de leitura ou escrita transacional
ou imediatamente após a efetivação de outra transação no fluxo de instruções.
Um sistema de TM pode abortar transações explicitamente, através da execução de
uma instrução de abortar, ou implicitamente, devido a conflitos de dados com transações
concorrentes.
Duas questões estão relacionadas a conflitos: detecção e resolução. Para detectar e
lidar com conflitos, cada transação é associada a um conjunto de leituras e um conjunto de
escritas. Dentro da transação, a execução de cada instrução de leitura transacional adici-
ona o endereço de memória ao conjunto de leitura. Cada instrução de escrita transacional
adiciona o endereço de memória e o valor no conjunto de escrita.
A detecção de conflitos pode ser ansiosa ou preguiçosa. A detecção ansiosa veri-
fica todas as leituras e escritas individualmente para ver se há uma operação conflitante
com outra transação. A detecção de conflitos ansiosa requer os conjuntos de leitura e es-
crita de uma transação seja visı́veis para todas as outras transações no sistema. A detecção
preguiçosa espera até que a transação tente se efetivar para checar seus conjuntos de lei-
tura e escrita com outros conjuntos de escritas de outras transações.
A figura 1 mostra a linha de tempo da execução de dois pares de transações. Os
dois métodos de detecção de conflitos detectam um conflito no primeiro par de transações
(a). No segundo par de transações (b), o método de detecção de conflitos ansioso detecta
o conflito, mas o método preguiçoso permitirar que ambas as transações se efetivem. Isso
ocorre porque em ambas as sequências, o método de detecção de conflitos ansioso detecta
o conflito na leitura do endereço X por T1, pois T2 já tinha escrito no endereço X . Na
figura 1a, o método de detecção de conflitos preguiçoso detecta um conflito porque T2
tenta efetivar primeiro, implicando que T1 deveria ter usado o resultado da escrita de T2.
Na figura 1b, tanto T1 quanto T2 efetivam-se, pois T1 efetiva-se primeiro, e seu acesso a
leitura não precisa usar o resultado da escrita de T2.
Figura 1: Linha de tempo da execução de dois pares de transações
[Harris et al., 2010].
Diferentes sistemas de TM detectam conflitos em diferentes nı́veis de granulari-
dade. Podem ser a nı́vel de objetos, como vetores ou listas, como podem ser granularidade
menores como campos individuais de uma estrutura de dados ou linhas de cache. Depen-
dendo da escolha, podemos ter trade-offs baseados em ganhos de desempenho em relação
ao tempo, sobrecarga de espaço de armazenamento e false sharing.
Outro problema das TM é como resolver os conflitos uma vez que eles foram de-
tectados. A ação mais comum é abortar umas das transações envolvidas, porém a decisão
de qual transação deve ser abortada é complexa.
A figura 2 ilustra as linhas de tempo de três transações. Considerando que o sis-
tema de TM usa a detecção de conflitos ansiosa. Quando T1 realiza a leitura no endereço
X , o sistema detecta um conflito com a escrita no endereço X da transação T2, e uma
transação deve ser abortada. Agora, se a polı́tica de resolução de conflitos decidir abortar
T2, depois T1 irá conflitar novamente com T3, e outra transação precisará ser abortada.
Entretanto, se a polı́tica de resolução de conflitos decidir abortar T1, tanto T2 quanto T3
poderão concluir, e apenas uma única transação precisou ser abortada.
Outros dois conceitos importantes em TM são bloqueio e escolha. Bloqueio é
um mecanismo que explicitamente que aborta uma transação. Escolha é um conjunto de
ações transacionais empreendias como uma alternativa ao bloqueio.
4. Tipos de implementações de TM
Existem dois principais estilos de implementação de TM: baseado em hardware e baseado
em software.
4.1. Memória transacional baseada em hardware
A memória transacional baseada em hardware, do inglês Hardware Transactional
Memory (HTM), foi historicamente o primeiro projeto de TM proposto. Em geral, para
implementar a HTM, duas modificações são suficientes [Harris et al., 2010]:
• Modificar o protocolo de coerência de cache;
• Complementar o conjunto de instruções da arquitetura com um pequeno grupo de
novas instruções.
Figura 2: Linha de tempo da execução de três transações [Harris et al., 2010].
O sistema TMmantém o estado especulativo em uma cache extra, ou um buffer, até que
a transação seja efetivada ou aborte.
As adições do conjunto de instruções da arquitetura podem envolver duas
instruções para delimitar a transação: Start TRansaction (STR) e End TRansaction (ETR).
Além de versões especiais das instruções de leitura e escrita, como Transactional LoaD
(TLD) e Transactional STore (TSD) são necessárias. As adições também podem englobar
instruções especiais para abortar (ABR) e validar (VLD). Essas duas últimas instruções
permitem algumas otimizações: O ABR permite que um controle de programa possar se-
lecionar uma transação vı́tima em caso de conflito; O VLD permite poupar energia. Uma
transação bastante longa pode se beneficiar com essa instrução por não precisar executar-
se até o fim no caso de um conflito precoce, podendo abortar precocemente e retornando
ao estado inicial.
O versionamento da dados, geralmente, usa a cache ou um buffer de modificações.
Os sistemas HTM mantêm o estado das transações especulativas principalmente na cache
de dados ou num buffer. As HTM trabalham com granularidades de palavras ou linhas
de cache. As leituras e escritas transacionais ficam em uma cache separada, ou na cache
de dados convencional aumentada para o suporte transacional [Herlihy and Moss, 1993].
Nesse caso, as modificações são mı́nimas porque o suporte transacional confia em es-
tender algum protocolo de coerência de cache existente (como o MESI) para detectar
conflitos e reforçar atomicidade.
4.2. Memória Transacional baseada em Software
A memória transacional por software, do inglês Software Transactional Memory
(STM), [Shavit and Touitou, 1995] é uma variante da memória transacional
[Herlihy and Moss, 1993]. Nesta seção, olhamos o caso básico de transações não
aninhadas que atualizam a memória compartilhada dentro de um único processo mul-
tithread, focando nos problemas principais que um STM deve lidar: Prover uma visão
separada por thread das pilhas a qual as transações executam, e prover mecanismos para
detectar e resolver conflitos entre transações.
A implementação de uma STM deve prover seu próprio mecanismo de transações
concorrentes para gerenciar suas próprias visões da pilha. Desta forma um mecanismo
permite uma transação ver suas próprias escritas enquanto continua a rodar e permite que
atualizações da memória sejam descartadas se a transação, no final, abortar.
As STM podem ser caracterizadas por sua organização de memória. Uma pri-
meira abordagem pode separar os dados transacionais dos dados normais, introduzindo
um formato de memória distinta para objetos transacionais. Enquanto outra abordagem
pode permitir que os dados mantenham sua estrutura de dados normais, e o STM usa
estruturas separadas para gerenciar suas próprias metadados.
A implementação da STM usa o cabeçalho do objeto para traçar com quais
transações estão acessando concorrentemente o objeto.
A interface de programação da aplicação, do inglês Application Programming
Interface (API), deve diferenciar acessos de leituras e escritas devido múltiplas transações
concorrentes poderem compartilhar o mesmo corpo de objeto durante o perı́odo que todas
estão apenas realizando leitura. Se uma transação precisar atualizar um objeto, o comando
OpenForWriting retorna uma cópia sombra do corpo do objeto.
A Object-based STM (OSTM) [Fraser, 2004] mantém em tempo de execução um
conjunto de leituras com os objetos que uma transação lê e um conjunto de escrita com
os objetos que são atualizados. Abortar uma transação simplesmente significa descartar
alguma cópia sombra que foi criada para a escrita. Efetivar uma transação significa:
1. Atomicamente checar que nenhuma transação conflitante tenha atualizado o ob-
jeto no conjunto de leituras ou escrita, e;
2. Atualizar o cabeçalho do objeto para o objeto no conjunto de escrita, desta forma
publicando a cópia sombra privada como o novo conteúdo do objeto.
O sistema STM Bartok [Harris et al., 2006] não faz distinção de baixo nı́vel entre
dados normais de transacionais. Esta implementação matém o metadado que a STM usa
para o controle de concorrência em estruturas separadas, com a STM usando uma função
para mapear uma palavra de endereço para uma palavra do metadado transacional que
gerencia estes dados.
Há várias maneiras de implementar as API da STM. Nos projetos que usam buf-
fered updates, uma transação mantém uma cópia sombra privada de todas as palavras da
memória que ela atualizou, quase como uma HTM mantém cópias privadas delas em sua
cache de dados locais. Uma leitura deve consultar a cópia sombra e então ver se há es-
critas recentes da mesma transação. Outra alternativa de projeto usa atualizações in loco.
O comando de escrita transacional atualiza diretamente a pilha para que então chama a
leitura transacional que verá as atualizações recentes sem precisar procurar numa tabela.
Nesse caso, a escrita transacional deve manter uma undo log de todos os valores que ela
sobrescreveu. A desvantagem dessa abordagem é que ela pode introduzir contenção entre
as transações, pois apenas uma transação pode ganhar o acesso à escrita ao mesmo tempo.
Diferentemente da HTM, a detecção e resolução de conflitos na implementação
STM tende a ser mais complicada, pois apenas ações individuais de operações de memória
são atômicas. Contudo, existem várias abordagens a serem exploradas: Esquemas pes-
simista baseados em travar automaticamente dados que as transações estão acessando,
esquema otimistas não bloqueante, e vários outros esquemas hı́bridos.
Uma abordagem usada em [Liskov, 1988] emprega duas fases rigorosas de trava
de objetos. Um compilador pode prontamente automatizar essa abordagem, no qual ad-
quirir locks como uma transação executa e mantê-lo até sua efetivação. Porém, essa abor-
dagem têm péssima escalabilidade em processadores multiprocessados atuais por intro-
duzir contenção na hierarquia de memória.
Uma alternativa é usar uma atualização atômica, não bloqueante e multipalavra
para efetivar a transação. O OSTM faz isso através da realização de uma atualização
de várias palavras atômica em todo o conteúdo do cabeçalho dos objetos nos conjuntos
de leitura e escrita. A vantagem desse método é permitir uma melhor escalabilidade de
leitura transacional.
Outros trabalhos anteriores frequentemente miravam no comportamento não blo-
queante como uma meta explı́cita, pois um algoritmo não bloqueante garante que o pro-
gresso do programa não seja obstruı́do por threads que não estão executando ativamente.
Isso evita também problemas como inversão de prioridade ou de threads serem descalo-
nados enquanto mantém um lock.
4.3. Memória transacional hı́brida
Além as HTM e STM, existem outras abordagem mistas de memórias transacionais. A
memória transacional hı́brida, do inglês Hybrid Transactional Memory (HyTM), suporta
a execução da HTM, mas retorna as transações STM quando os recursos de hardware
são excedidos [Kumar et al., 2006]. A STM auxiliada por hardware, do inglês Hardware-
assisted STM (HaSTM), combina a STM com um novo suporte da arquitetura para ace-
lerar partes da implementação da STM [Shriraman et al., 2006]. Em relação ao desem-
penho, a HyTM provém um desempenho próximo a HTM para transações curtas, porém
degrada bastante o desempenho quando recorre a STM. Em contrapartida, a HaSTM
provém um desempenho mediano entre a HTM e a STM.
Para não se estender muito, neste trabalho, focaremos apenas na HyTM.
A HyTM combina o esquema otimista e pessimista usando locks de exclusão
mútua versionados, no qual suportam sermanticas de exclusão mútua normal e provém
acesso a um número de versão que conta o número de vezes o lock foi adquirido e libera-
dos.
Os projetistas usam exclusão mútua para controle de concorrência pessimistapara
dar direito a escrita dos dados protegidos pelos locks e o número de versão permite o
contole de concorrência otimista para acessos de leitura. Isto é, uma transação guarda o
número da versão antes de sua primeira leitura de um objeto e então, na hora de efetivar-
se, verifica se o número da versão mudou, caso não tenha mudado, significa que ninguém
atualizou o objeto concorrentemente com a transação.
A HyTM também pode ser flexı́vel de acordo com o projeto da STM. Os locks
podem suportar buffered updades de duas formas:
• Ansiosamente: para prevenir conflitos, embora a transação ainda faça alterações
de um log privado.
• Preguiçosamente: impedindo as transações de abortarem por causarem conflitos.
Os locks também podem suportar gerência de dados. Na STM Bartok, uma
transação adquire locks ansiosamente de objetos que ela deseja atualizar, faz as
atualizações diretamente no objeto, e gerencia um undo log para permitir que as
atualizações sejam revertidas se a transação abortar. Os locks protegem os dados de es-
critas conflitantes de transações concorrentes, e faz as atualizações in loco, o que signi-
fica as leituras transacionais verão os valores escritos pela mesma transação antecipada-
mente. Essa abordagem busca fazer as operações de leituras o mais rápido possı́vel em
três hipóteses:
• Leituras excederão o número de escritas nas transações;
• Lendo número de dados de versões durante uma transação e verificando em tempo
de efetivação será mais rápido que adquirir e liberar um lock daquele dado;
• Conflitos de transações normalmente serão raros, então é melhor acelerar as
transações sem contenção e efetivações, ao custo de um trabalho extra no caso
em que os conflitos ocorrem. Em outras palavras “É melhor desculpar-se ocasio-
nalmente do que pedir permissão frequentemente” [Herlihy, 1990].
5. Alguns desafios de projeto
Ainda existem outros desafios de projetos de uma TM. Esta seção apresenta rapidamente
algumas destes desafios.
5.1. Aninhamento aberta ou fechada
É possı́vel embutir as transações dentro de funções de programa, auxiliando o programa-
dor a escrever programas eficientes ou utilizar bibliotecas renomadas.
Nas transações de aninhamento fechadas, ou todas ou nenhuma das transações em
uma região aninhada se efetiva. Em contraste, numa transação de aninhamento aberto,
quando uma transação interna efetiva, seu efeito torna-se visı́vel para todos os threads do
sistema.
O aninhamento aberto permite que as transações liberem mais concorrência que as
transações de aninhamento fechado. Quando uma transação de aninhamento aberto se efe-
tiva, suas escritas torna-se visı́veis a todas as outras transações, então outras transações po-
dem ver modificações mais rapidamente e trabalhar com o dado modificado. Na transação
de aninhamento fechado, as modificações são visı́veis apenas quando toda a transação se
efetiva. Em contrapartida, transações de aninhamento aberto aumenta a responsabili-
dade do programador, que precisa realizar ações que devam compensar quando alguma
transação externa é efetivada e quando uma das transações aborta.
O desafio aqui é suportar um modelo de aninhamento rico com o mı́nimo de com-
plexidade de software-hardware. Uma vez que o mais simples modelo aninhamento fe-
chado requer a inclusão de alguma complexidade de hardware enquanto limita a con-
corrência e desempenho, os modelos de transações de aninhamento aberto expõem mais
concorrência, mas aumenta a complexidade para os programadores, quem deve explicitar
as efetivações de escritas e abortos lidando com códigos para suportar esses modelos.
A figura 3 ilustra um exemplo de código para transações de aninhamento aberto
e fechado: a figura 3a é o código original; a figura 3b é o código de uma transação de
aninhamento fechado; a figura 3c é o código de uma transação de aninhamento aberto.
5.2. Entrada e saı́da
A relação entre operações de Entrada e Saı́da (E/S) e transações é outra área de pes-
quisa desafiadora. Por exemplo, suponha que dentro de uma transação, uma chamada
de sistema tenta escrever um caractere no terminal. Uma solução é executar a chamada
de sistema imediatamente; contudo, isto pode ser muito problemático se esta transação
abortar depois. Tentar desfazer o E/S através da deleção do caractere sobre um aborto
pode obviamente levar a um sistema incerto (ou inseguro). Em alguns casos, uma vez
executado a operação de E/S deve ser difı́cil se o dado estiver buferizado em HTM.
Outra solução é deferir a operação de E/S até a efetivação para colocar o caractere
no terminal. Porém, isso pode levar a algum problema se o usuário está aguardando a E/S
para realizar alguma ação.
Figura 3: Exemplo de código para transações de aninhamento aberto e fechado
[Harris et al., 2010].
Uma terceira abordagem é proibir (ou restrigir) operações E/S dentro de
transações.
Uma quarta solução seria categorizar as entradas e saı́das de acordo com suas
propriedades abortivas. O programador deve tomar cuidado com o tipo de operação de
E/S que não faz sentido estarem contidos numa simples transação atômica. Por exemplo,
durante uma transação, aguardar uma entrada do usuário.
5.3. Modelos de programação e TM
Alguns modelos de programação incluem uma declaração atômica para definir os blocos
atômicos. Alguns casos, uma variável pode ser atribuı́da como atômica, desta forma,
qualquer atualização nela no código é tratado como se a atualização é uma seção curta
atômica.
Outro modelo de programação já estabelecido, como o OpenMP e MPI, que são
usados amplamente para aplicações cientı́ficas paralelizáveis, não foram desenvolvidos
com a TM em mente. Explorar como a TM pode tornar a programação paralela com esses
modelos atraente é outro desafio. Com o OpenMP, o programador deve inserir diretivas
de preprocessamento para expressar as oportunidades para explorar o processamento e
distribuir o trabalho entre os threads, sincronizar suas execuções.
A maior complexidade em escrever aplicações OpenMP é o uso de regiões crı́ticas
(locks), regiões atômicas, e barreiras de sincronização para execução das atividades para-
lelas nas threads. A forma mais simples de misturar OpenMP e TM é substitui as regiões
crı́ticas e atômicas com o código de regiões transacionais, fazendo as aplicações paralelas
mais fáceis de programar, entender, e manter. Além do mais, a TM possivelmente pode
prover outras vantagens que o modelo de programação OpenMP.
Porém, as implementações TM existentes não permitem que múltiplas threads ro-
dem em paralelo no mesmo estado transacional. Usando MPI com TM, programadores
podem alcançar a tolerância a falha encapsulando cada diretriz padrão do MPI dentro de
uma transação com código de gerência para lidar com abortos ou efetivações. O maior
desafio aqui é prover implementações que possam propriamente misturar os modelos pre-
venindo abortos em cascata.
6. Conclusão
A memória transacional provém um mecanismo natural para escrita de programa parale-
los. É uma tendência que os modelos de programação atual sejam projetados para traba-
lharem com programas concorrentes para aproveitar o máximo do paralelismo dos chips
multicores que já estão presentes nos computadores atuais, assim como a extensão dessa
escalabilidade usando nuvens computacionais. Por enquanto, o maior desafio é fazer pro-
jetos de hardware e software para que a comunidade de programadores adotarem a TM da
forma mais fácil possı́vel. Este trabalho teve como objetivo apresentar uma rápida visão
sobre as TM e seus desafios de projetos.
Referências
Culler, D., Singh, J., and Gupta, A. (1999). Parallel computer architecture: a hard-
ware/software approach. Morgan Kaufmann.
Felber, P., Fetzer, C., Guerraoui, R., and Harris, T. (2008). Transactions are back—butare they the same? ACM SIGACT News, 39(1):48–58.
Fraser, K. (2004). Practical lock-freedom. PhD thesis, PhD thesis, Cambridge University
Computer Laboratory, 2003. Also available as Technical Report UCAM-CL-TR-579.
Gray, J. (1978). Notes on data base operating systems. Operating Systems, pages 393–
481.
Harris, T., Cristal, A., Unsal, O., Ayguade, E., Gagliardi, F., Smith, B., and Valero, M.
(2007). Transactional memory: An overview. Micro, IEEE, 27(3):8–29.
Harris, T., Larus, J., and Rajwar, R. (2010). Transactional memory. Synthesis Lectures on
Computer Architecture, 5(1):1–263.
Harris, T., Plesko, M., Shinnar, A., and Tarditi, D. (2006). Optimizing memory transacti-
ons. In ACM SIGPLAN Notices, volume 41, pages 14–25. ACM.
Herlihy, M. (1990). Apologizing versus asking permission: Optimistic concurrency con-
trol for abstract data types. ACM Transactions on Database Systems (TODS), 15(1):96–
124.
Herlihy, M. and Moss, J. (1993). Transactional memory: Architectural support for lock-
free data structures, volume 21. ACM.
Kumar, S., Chu, M., Hughes, C., Kundu, P., and Nguyen, A. (2006). Hybrid transactional
memory. In Proceedings of the eleventh ACM SIGPLAN symposium on Principles and
practice of parallel programming, pages 209–220. ACM.
Larus, J. and Rajwar, R. (2007). Transactional memory. Synthesis Lectures on Computer
Architecture, 1(1):1–226.
Liskov, B. (1988). Distributed programming in argus. Communications of the ACM,
31(3):300–312.
Shavit, N. and Touitou, D. (1995). Software transactional memory. In Proceedings of
the fourteenth annual ACM symposium on Principles of distributed computing, pages
204–213. ACM.
Shriraman, A., Marathe, V., Dwarkadas, S., Scott, M., Eisenstat, D., Heriot, C., Sche-
rer III, W., and Spear, M. (2006). Hardware acceleration of software transactional
memory. In ACM SIGPLAN Workshop on Transactional Computing, Ottawa, ON,
Canada.