1 INTRODUOO poder computacional est a cada dia mais presente no cotidiano. Percebese isso, com o aumento no nmero de dispositivos mveis, computadores pessoais, e a computao na nuvem, que em muitos casos utiliza-se de grandes data centers. Estima-se que somente os data centers sejam responsveis por Cerca de 1,5% de eletricidade total consumida no planeta, e este montante deve crescer a menos que utilize-se mecanismos que reduzam esse consumo e ainda assim atendam aos requisitos de processamento (SHARAVANAN; POONGODI;KUMAR, 2010).Com enfoque no aquecimento global, pesquisadores de computao tmtomado conscincia sobre o consumo energtico em sistemas computacionais e os impactos causados por esses no meio ambiente, gerando ento uma rea de pesquisa ainda recente, a Computao Sustentvel (Green Computing), que tem por objetivo prover um conjunto de prticas voltadas para a computao de modo que minimize-se o impacto ambiental (KURP, 2008).Em sistemas computacionais, a eficincia energtica pode ser obtida atravs de otimizaes tanto de hardware como software, desde o projeto do circuito, passando pelo sistema operacional, compiladores, chegando at o nvel de aplicao. Contudo, tem-se como limitante da reduo de consumo que osrequisitos temporais dos aplicativos continuem sendo atendidos, mesmo quepossam ocorrer perdas no desempenho.Com o advento de arquiteturas multicore, a programao paralela tem papel fundamental na melhoria da eficincia, por fazer melhor proveito dos recursos de hardwares disponveis e aumentar o desempenho das aplicaes (MRet al., 2010). Um modelo de programao concorrente muito utilizado omultithreaded (ANDREWS, 2000). Neste modelo, o paralelismo explicitado por threads, que compartilham a memria por padro. A comunicao entre threads concorrentes feita atravs da escrita e/ou leitura em variveis compartilhadas e h necessidade de utilizar-se de mecanismos de sincronizao para garantir a integridade e consistncia de execuo entre threads concorrentes (ANDREWS, 2000).Os mecanismos de sincronizao tm sido tradicionalmente realizados atravs de mtodos baseados em locks explcitos no cdigo fonte dos programas.Embora muito utilizado, esta abordagem propensa a erros, podendo apresentar uma srie de complicaes tais como (MCKENNEY et al., 2010): instabilidade no sistema, dificuldade de composio e baixo desempenho se no empregado corretamente. Novas abstraes que facilitem o desenvolvimento de aplicaes paralelas so portanto essenciais (BALDASSIN, 2009).

1.1 ObjetivosEste trabalho tem como objetivo principal analisar mecanismos de sincronizao em ambiente de memria compartilhada sob o contexto da computao sustentvel, visando a reduo no consumo de energia e/ou maximizao do desempenho. Especificamente, tem-se como objetivos: realizar uma reviso bibliogrfica do assunto, apresentando as caractersticas (vantagens e problemas) da programao concorrente, com destaque para o mecanismo de memrias transacionais; e realizar um estudo investigativo em pesquisas j concretizadas que comparam o consumo de energia e/ou o desempenho de memrias transacionais com outros mecanismos de sincronizao.1.2 Organizao do textoO trabalho que segue est organizado em 5 Captulos. O Captulo 2 apresenta a computao sustentvel, suas origens e motivaes. O Captulo 3 tem por objetivo descrever os principais tpicos sobre comunicao e sincronizao 11 em programao concorrente, mostrando os problemas e os mecanismos de sincronizao que visam garantir a consistncia e integridade em execues concorrentes. No Captulo 4 ser apresentado uma anlise das pesquisas j desenvolvidas objetivando reduo no consumo de energia e/ou desempenho em mecanismos de sincronizao em ambiente de memria compartilhada. Por fim, no Captulo 5 sero apresentadas as concluses e os trabalhos futuros.

COMPUTAO SUSTENTVELA utilizao de sistemas computacionais faz-se cada vez mais presente em atividades das mais diferentes naturezas. Diversas reas do conhecimentoutilizam-se de aplicaes que oferecem suporte automatizado para diversastarefas, cujo suporte executivo tanto baseia-se em hardware como software.Nos lares, cresce-se de igual modo a utilizao de dispositivos mveis ecomputadores pessoais, que servem, fundamentalmente, como equipamentospara lazer e comunicao.

2.1 OrigensNos ltimos anos, a relao entre o consumo energtico em sistemascomputacionais e os impactos ambientais causados por esses cunharam o termocomputao sustentvel.Embora a computao sustentvel tenha recentemente se popularizado, suas origens conceituais vm h mais de duas dcadas (HARMON; AUSEKLIS,2009). Em 1991, a Environmental Protection Agency (Agncia de ProteoAmbiental) introduziu o programa Green Lights para promover a eficinciaenergtica em iluminao. Em seguida, introduziu-se o programa EnergyStar em 1992, o qual estabeleceu especificaes de eficiente energtica paracomputadores e monitores (HARMON; AUSEKLIS, 2009).A popularizao da computao sustentvel deveu-se principalmente aorpido crescimento de negcios baseados na internet, e os custos de energiapara suprir as demandas de infra-estruturas da tecnologia da informao (HARMON;AUSEKLIS, 2009). Apesar de o consumo energtico e seus custosassociados terem sido o fator impulsor para o surgimento da computaosustentvel, foi a partir das alteraes climticas oriundas do aquecimento globalque os benefcios gerados pelas prticas da computao sustentvel ganharamnotoriedade a nvel mundial (HARMON; AUSEKLIS, 2009).2.2 Objetivos e prticasA Computao Sustentvel consiste em um somatrio de prticas, tais que oprincipal objetivo obter uma minimizao dos impactos causados por sistemascomputacionais no meio ambiente.O meio ambiente beneficia-se da computao sustentvel por meio doconsumo eficiente de energia, na reduo de emisses de gases de efeito estufa,menor uso de materiais nocivos na fabricao de computadores, e atravs doincentivo na reutilizao e reciclagem de componentes de hardwares (MURUGESAN,2008). Tais prticas fomentam melhorias nas atividades de empresas e clientes, efetivando redues em custos e contribuem com maior preservao do meio ambiente.Em relao aos data centers, pode-se melhorar a eficincia desses utilizandosede equipamentos eficientes em termos energticos, reduzindo-se a necessidadede refrigerao, utilizando-se de softwares de gerenciamento de14 energia (MURUGESAN, 2008).Outra prtica que pode colaborar significativamente na reduo de custos eenergia a Virtualizao, pois permite particionar um nico sistema computacionalem vrios outros denominados de mquinas virtuais, reduzindo-se assima quantidade de mquinas, espao fsico, refrigerao, entre outros elementosnecessrios para o funcionamento do ambiente computacional (MURUGESAN,2008).O aumento da eficincia energtica importante em todo contexto computacional,independente de hardwares e softwares utilizados. Com o adventode arquiteturas multicore, a programao paralela tem papel fundamental namelhoria da eficincia, por fazer melhor proveito dos recursos de hardwaresdisponveis e aumentar o desempenho das aplicaes (MR et al., 2010).Uma das caractersticas de processadores multicore est relacionada amaior capacidade de processamento utilizando-se de menor frequncia deoperao. Em tais processadores, para cada 1% de ganho de desempenhoh 3% de consumo de energia (RAMANATHAN; THOMAS, 2005). Utilizandosedesta relao de maneira inversa, de se esperar que diminuindo 15% dafrequncia de operao de um determinando processador, 45% de energia sereconomizada. O consumo de energia de processadores pode ser obtido atravsda equao 1 (WECHSLER, 2006). C representa a capacitncia comutada,ou seja, a quantidade de energia que pode ser armazenada em um capacitorequivalente. V a tenso de alimentao, f a frequncia do clock. Acapacitncia comutada tem um valor fixo para cada circuito, mas a tenso dealimentao e a frequncia do clock podem ser reduzidos em certos limites.Observa-se na equao 1 a dependncia da tenso (em Volts) em relao frequncia de clock.Power = C _ V 2 _ f (1)Atravs da tcnica conhecida como DVFS (Dynamic Voltage and FrequencyScaling) (KAXIRAS; MARTONOSI, 2008), a voltagem e frequncia de operaodos ncleos de execuo de processadores podem ser reduzidas em tempode execuo, de acordo com a demanda computacional, obtendo-se assim, areduo do consumo de energia em ordem quadrtica. No entanto, a realizaodestas operaes apresenta um custo associado, podendo comprometer odesempenho global do sistema. Para a realizao de tal tcnica, primeiramente,a voltagem do processador/core deve ser alterada, para que essa possa suportara frequncia exigida, somente aps esta etapa a frequncia pode ser alteradapara a desejada. Durante a realizao destas operaes, o processador deveinterromper suas atividades e aguardar a finalizao do ajuste, acarretando emtempo de processamento perdido (UHRIG; UNGERER, 2005). Portanto, deve-selevar em considerao que tais operaes no sejam frequentes e assim tomartempo de processamento, e que o ajuste seja realizado de tal forma afim degarantir os requisitos temporais do sistema.Em arquiteturas multicore e multiprocessadas, um recurso de programaoconhecido como Afinidade permite associar threads a um, ou a um grupo, deprocessadores/cores (ARAUJO et al., 2010). O objetivo deste recurso explorara localidade de referncia a dados na memria cache. Este recurso permite15utilizar a memria cache de maneira mais eficiente, pois ocorrem menos cachemiss, pois um thread em especfico ser sempre executada sobre o mesmoprocessador/core ou grupo de processadores/cores. A explorao do recurso deAfinidade pode ser utilizada em conjunto com a tcnica de DVFS, como mostradopor Araujo et al (2010). Nesta perspectiva, observou-se que a utilizao de taistcnicas em conjunto eficiente, tanto em termos de consumo de energia quantodesempenho.A organizao e arquiteturas de processadores paralelos podem colaborarainda mais na reduo do consumo energtico. Seja atravs de componentesde hardwares que visam menor consumo de energia (low-power ), ou at mesmo,atravs do desligamento seletivo de unidades de processamento que noestejam sendo utilizadas em uma certa poro de tempo, reduzindo-se assim, oconsumo de potncia (MR et al., 2010). No contexto de arquiteturas multicore emultiprocessadas, a utilizao da programao paralela um fator determinantepara a busca da eficincia energtica, pois utiliza-se dos recursos disposiode maneira eficiente, utilizando ao mximo o uso de processadores/cores que jesto ativos, diminuindo sua ociosidade. Assim, aproveita-se a energia que estesj esto consumindo, evitando-se desta forma o uso de processadores/coresextras (MR et al., 2010).2.3 Observaes finaisEste Captulo apresentou os conceitos relacionados a computao sustentvel,os problemas e resolues devido a expanso da computao.Diversas prticas provenientes da programao paralela foram mostradascom objetivo de relacionar esta abordagem de programao computaosustentvel. Especificamente, mostrou-se que a programao paralela podereduzir o consumo de energia de sistemas computacionais, atravs de tcnicasque utilizam eficientemente os recursos de hardwares disponveis.Com a crescente demanda por recursos computacionais, eleva-se tambmo consumo de recursos ambientais. Com isso, a computao sustentvel temo propsito de otimizar a computao de modo a utilizar o mnimo necessriode recursos naturais, garantindo ainda, que as demandas de processamento erequisitos temporais dos aplicativos sejam atendidas.3 COMUNICAO E SINCRONIZAOA execuo concorrente em sistemas se torna interessante pelos seguintesaspectos (SILBERSCHATZ; GALVIN; GAGNE, 2009):_ Compartilhamento de informaes: Em sistemas multiusurio, diversosusurios podem estar interessados na mesma informao, por exemplo, umarquivo compartilhado. O sistema deve ser capaz de fornecer um ambienteque permita o acesso concorrente aos recursos compartilhados._ Processamento mais veloz: Para executar uma tarefa mais rapidamente,deve-se subdividi-la em sub-tarefas, onde cada sub-tarefa ser responsvelpela execuo de uma parte dos dados ou de uma operao especfica. Oaumento na velocidade s obtido na sub-diviso de tarefas em ambientescom mltiplos elementos de processamento._ Modularidade: A construo de sistemas de forma modular, dividindoseas funes em processos ou threads separados, em um sistemamultiprocessado se torna vantajoso, pois cada funo pode ser executadapor um determinado elemento de processamento._ Comodidade: A execuo de diversas tarefas simultneas se tornou umaprtica usual. Por exemplo, um usurio pode estar editando um texto,ouvindo msica, e gravando arquivos em algum tipo de mdia ao mesmotempo.Para que haja cooperao entre execues concorrentes em sistemas,h necessidade dessas se comunicarem. Existem dois modelos comuns decomunicao entre processos ou threads: memria compartilhada e trocade mensagens (SILBERSCHATZ; GALVIN; GAGNE, 2009). No modelo dememria compartilhada, processos utilizam-se de chamadas de sistema dotipo mapeamento da memria para obter acesso a regies da memria utilizadaspor outras tarefas. Threads por sua vez, compartilham a memria por padro.A troca de informaes entre processos/threads ocorre por meio de leiturase gravaes das reas da memria compartilhada. No modelo de trocade mensagens, a comunicao entre processos realizada atravs da trocade informaes por intermdio de um canal de comunicao. O meio decomunicao pode ser implementado de vrias formas, como por exemploum buffer ou link de uma rede de conexo. Esta abordagem apropriadapara sistemas distribudos, pois tais sistemas so compostos de vrias CPUs17contendo reas de memrias privativas, sendo essas CPUs conectadas atravsde uma rede de interconexo (SILBERSCHATZ; GALVIN; GAGNE, 2009).Este trabalho tem como objetivo realizar um estudo sobre mecanismos desincronizao em ambientes de memria compartilhada baseado no modelomultithreaded, portanto no sero discutidos maiores detalhes sobre troca demensagens no decorrer do mesmo.Nas duas prximas sees, sero respectivamente descritos o que denominasede seo crtica de um programa e os problemas que podem ocorrer durantea comunicao entre processos/threads concorrentes. Na Seo 3.3 serodescritos os mecanismos de sincronizao. E por fim, na Seo 3.4 seroapresentadas as observaes finais.3.1 Seo CrticaDenomina-se Seo Crtica a parte de cdigo de um programa em que amemria ou recurso compartilhado acessado, ou seja, os trechos de cdigoque manipulam os dados compartilhados onde possam ocasionar condies decorrida (TANENBAUM; WOODHULL, 2008).Mostra-se na Figura 1 um cdigo escrito na linguagem Java que representaa estrutura de um programa que manipula valores de uma conta bancria. Assees crticas do cdigo mostrado so aquelas em que o atributo saldo manipulado (linhas 8 e 16), pois o atributo compartilhado na estrutura doprograma, na qual diversas threads podem executar concorrentemente e utilizaro recurso compartilhado da classe Java.12 public class ContaBancaria {34 pr ivate double saldo = 0;56 public void deposi ta ( double quant ia ) {7 i f ( quant ia > 0) {8 this . saldo = this . saldo + quant ia ; / / Seo Cr t i c a9 } else {10 System. out . p r i n t l n ("A quantia do depsito deve ser maiorque ZERO.") ;11 }12 }1314 public void saque ( double quant ia ) {15 i f ( this . saldo quant ia > 0) {16 this . saldo = this . saldo quant ia ; / / Seo Cr t i c a17 } else {18 System. out . p r i n t l n ("Saldo insuficiente para o valor desaque desejado.") ;19 }20 }21 }Figura 1: Estrutura de um programa com Seo CrticaO problema da seo crtica est em garantir que somente uma tarefa possa18estar executando sua seo crtica no mesmo intervalo de tempo. A garantiaque duas ou mais tarefas no acessem simultaneamente a mesma seo crticadenomina-se de excluso mtua.Diversas primitivas que solucionam o problema da seo crtica estabelecemum protocolo onde define-se uma condio para a tarefa entrar na seo crticae outra operao que sinalize que a tarefa concluiu a execuo da seocrtica (SILBERSCHATZ; GALVIN; GAGNE, 2009).Para que tarefas concorrentes mesma seo crtica sejam executadas deforma eficiente e correta, devem ser satisfeitas quatro condies (TANENBAUM;WOODHULL, 2008):_ Excluso mtua: Duas ou mais tarefas no podem estar ao mesmo tempodentro da mesma seo crtica._ Independncia de fatores fsicos: A soluo no deve depender davelocidade de execuo das tarefas ou do nmero de processadoresdisponveis._ Progresso: Nenhuma tarefa executando fora de sua seo crtica podebloquear outras tarefas._ Espera limitada: Nenhuma tarefa pode ter seu ingresso na seo crticapostergado indefinidamente.3.2 Problemas de concorrnciaDiversos problemas podem ocorrer durante a comunicao entre processos/threads concorrentes, tem-se como soluo para tais, a utilizao demecanismos de sincronizao, que sero descritos na subseo 3.3. A seguir,sero apresentados os problemas mais conhecidos em ambiente de memriacompartilhada.3.2.1 Condio de corridaSe duas ou mais tarefas (threads ou processos) tentam alocar o mesmorecurso ou dado compartilhado ao mesmo tempo, inconsistncias de dadospodem ocorrer (TANENBAUM; WOODHULL, 2008).Denomina-se de condies de corrida as inconsistncias geradas por acessossimultneos a dados ou recursos compartilhados (TANENBAUM; WOODHULL,2008).Podem ocorrer condies de corrida em qualquer sistema onde haver acessoconcorrente a um mesmo recurso compartilhado, mas ao menos uma dasoperaes seja de escrita no recurso. Acessos de leitura concorrente a umrecurso compartilhado no geram condies de corrida, pois no alteram o valordo recurso compartilhado.Para resguardar-se da condio de corrida precisa-se garantir que somenteum processo/thread manipular o recurso compartilhado por vez, utilizando-sede mecanismos de sincronizao (SILBERSCHATZ; GALVIN; GAGNE, 2009).Demonstra-se atravs da Figura 2 a ocorrncia de condio de corrida emuma aplicao, atravs de um digrama temporal de execuo de um programa19que manipula valores de uma conta bancria, baseado na estrutura de cdigomostrado na Figura 1.Figura 2: Acesso concorrente entre threads - demonstrao de condio decorridaObserva-se na Figura 2 que a condio de corrida ocorreu pois no mesmoinstante de tempo as duas threads alocam o mesmo recurso na memria(varivel saldo), assim, o valor da varivel alocada ser inconsistente, pois umadas atualizaes de ambas threads ser perdido, desta forma o resultado finalser no-determinstico.3.2.2 Deadlock e LivelockPor definio, um conjunto de processos/threads est em deadlock (impasse)se cada processo/thread do conjunto est esperando por um evento que apenasoutro processo/thread do conjunto pode causar (TANENBAUM; WOODHULL,2008).Dessa forma, deadlocks causam bloqueios perptuos em processos/threads,pois espera-se por um evento (liberao do recurso) que nunca ir acontecer.Para que ocorram deadlocks, quatro condies devem ser verdadeiras (COFFMAN;ELPHICK; SHOSHANI, 1971):1. Condio de excluso mtua: Cada recurso ou est correntementeatribudo a exatamente um processo/thread ou est disponvel.2. Condio de posse e espera: Os processos/threads que correntementepossuem recursos garantidos anteriormente podem solicitar novos recursos.3. Ausncia de preempo: Os recursos garantidos anteriormente nopodem ser retirados fora de um processo/thread. Eles devem serliberados explicitamente pelo processo/thread que os possui.204. Condio de espera circular: Deve haver um encadeamento circular dedois ou mais processos/threads, cada um dos quais esperando por umrecurso mantido pelo prximo membro do encadeamento.As quatro condies descritas anteriormente podem ser modeladas usandografos dirigidos (HOLT, 1972). Dois tipos de ns so utilizados nos grafos:processos, mostrados como crculos, e recursos, mostrados como quadrados.Um arco de um n de processo (crculo) para um n de recurso (quadrado)significa que o processo est bloqueado, esperando por esse recurso. Um arcode um n de recurso para um n de processo significa que o recurso foi solicitadoanteriormente, foi concedido e correntemente mantido por esse processo.A Figura 3(a) mostra graficamente uma situao de deadlock. O processoP4 est bloqueado espera do recurso R2, mantido pelo processo P1. Osprocessos P1 e P3 esto bloqueados espera do recurso R1, mantido peloprocesso P4. Desta forma, P1, P3 e P4 esto em deadlock. Na Figura 3(b), oprocesso P5 est bloqueado espera do recurso R3. Entretanto, o processo P5no est em deadlock, pois o processo P2 no est bloqueado, podendo esseexecutar at o fim, liberar o recurso R3, e ento o processo P5 poder executar.Figura 3: Cenrios de alocaes de recursos compartilhados com ocorrncia dedeadlock. Fonte: (OLIVEIRA; CARISSIMI; TOSCANI, 2008)H vrias formas de eliminao de deadlocks em sistemas. Uma delas se, para cada recurso, for eliminada pelo menos uma das quatro condiesdescritas acima (TANENBAUM; WOODHULL, 2008). Uma outra forma usualpara o tratamento de deadlocks deixar acontecer, detect-lo e ento eliminlo(TANENBAUM; WOODHULL, 2008). A deteco pode ser realizada de formaautomtica ou manual. O deadlock eliminado por meio da destruio dosprocessos/threads envolvidos e da liberao dos respectivos recursos.Livelock semelhante deadlock, com a diferena que os estados dosprocessos/threads em livelock no ficam bloqueados, mas permanecem emestado de espera-ocupada (ANDREWS, 2000).Um exemplo de uma situao que ocorre livelock quando duas pessoascaminhando em um corredor estreito em direes opostas se encontram frente afrente. Ambas tentam seguir caminho em frente, porm, cada uma se move parao mesmo lado, no conseguindo progresso, pois moveram-se para o mesmolado ao mesmo tempo.Situaes como a do exemplo descrito anteriormente so comuns de acontecerem certos ambientes, porm, eventualmente, o progresso acontece (ANDREWS,2000).213.2.3 StarvationStarvation, ou inanio, refere-se ao tempo indefinido que processos/threadsaptos a execuo aguardam para executar. Tal situao pode ocorrer emalgoritmos de escalonamento por prioridades, pois processos/threads de prioridademais alta pode levar a que processos/threads de baixa prioridadeficarem esperando indefinidamente para serem escalonados e executados pelaCPU (SILBERSCHATZ; GALVIN; GAGNE, 2009). Outra situao em que ainanio pode ocorrer em sincronizao por espera-ocupada, na qual algumprocesso/thread em especfico pode sempre perder na disputa pela entrada naseo crtica (OLIVEIRA; CARISSIMI; TOSCANI, 2008).Uma soluo que resolve o problema da inanio em algoritmos de escalonamentopor prioridades a tcnica conhecida como envelhecimento, na qualincrementa-se gradualmente a prioridade dos processos/threads que aguardamem filas por longo tempo para executarem (SILBERSCHATZ; GALVIN; GAGNE,2009).3.2.4 Inverso de prioridadeDenomina-se de inverso de prioridade situaes em que processos/threadsde alta prioridade so impedidos de executar suas sees crticas por essas jestarem sendo executadas por processos/threads de mais baixa prioridade (SILBERSCHATZ;GALVIN; GAGNE, 2009). Somente aps o processo/thread debaixa prioridade concluir a execuo da seo crtica a tarefa de alta prioridadepoder prosseguir.3.3 Primitivas de sincronizaoO objetivo de mecanismos de sincronizao garantir a integridade econsistncia em execues concorrentes, controlando a ordem de execuo dasoperaes entre diferentes tarefas. Duas formas de sincronizao se fazemnecessrias em aplicaes concorrentes: condicional e excluso mtua (ANDREWS,2000). A sincronizao condicional permite postergar a execuode um processo ou thread at que alguma condio se satisfaa. A exclusomtua garante que no haver acesso simultneo em uma regio de memriacompartilhada.Mecanismos de sincronizao tm sido tradicionalmente implementados comuso de bloqueios (locks) explcitos pelo programador, onde certas variveisrepresentam a proteo (entrada e sada) da seo crtica, ou a condiopara postergao ou avano de determinadas tarefas. As implementaesde locks podem ser classificadas conforme sua caracterstica. Existem basicamenteduas classificaes: bloqueantes e espera-ocupada (TANENBAUM;WOODHULL, 2008). A caracterstica bloqueante refere-se retirar do escalonamento(suspender) os processos/threads quando esses no podem entrar emsuas sees crticas at que alguma condio se satisfaa. Na espera-ocupadao processo/thread verifica se a entrada permitida na seo crtica, se no for,o processo/thread executar um lao fechado at que seja permitido entrar.No entanto, apesar de ser muito utilizado, este modelo de programaoapresenta uma srie de problemas (JONES, 2007) (MCKENNEY et al., 2010):22_ Instabilidade: como o controle sobre a forma de sincronizao dadaatravs de locks explicitados pelo programador, torna-se comum algumassituaes acontecerem: a utilizao de locks em excesso; adquirir menoslocks do que o necessrio; adquirir locks errados; adquirir locks na ordemerrada. Tais situaes podem acarretar em: diminuio do paralelismo,condies de corrida e deadlocks. Por essas razes, como consequncia,tem-se uma complicao na criao de sistemas confiveis e escalveisbaseados em locks._ Composio: no h garantia em que trechos de cdigo corretamenteimplementados utilizando bloqueios, quando combinados, continuem vlidos.Por exemplo, uma operao que deva mover um item entre duasfilas poderia ser composta atravs de mtodos de remoo e insero,sendo requerido atomicidade na execuo (ou seja, no pode ser percebidaa ausncia do item em uma fila antes que o mesmo seja inserido emoutra). No entanto, atravs do uso de bloqueios torna-se complicado talcomposio sem que o encapsulamento do objeto seja violado ou aindaque novos bloqueios sejam introduzidos._ Gargalo serial: o fator desempenho est relacionado diretamente caracterstica conservativa dos bloqueios. Em sees crticas protegidaspor bloqueios o acesso restringido, apenas um processo/thread podeacessar por vez. Quando um processo/thread tentar acessar uma regiode cdigo protegida que j est sendo acessada, esse processo/threadficar bloqueado at o recurso ser liberado, causando gargalos seriais nosistema. Quanto maior a granularidade do cdigo protegido por um bloqueio,maior ser o impacto negativo no desempenho e na escalabilidadeda aplicao. A anlise de tal impacto pode ser obtida utilizando-se da leide Amdahl (AMDAHL, 1967), a qual relaciona o acrscimo de desempenhoesperado em um algoritmo que possui parcelas sequenciais e paralelas,dada pela equao 2. A equao descreve o speedup mximo S(p) obtidocom p processadores em um programa cuja frao de tempo de execuoserial dada por fs.S(p) =1fs + 1fsp(2)Mesmo para um nmero de processadores que tende ao infinto, o speedup limitado pela frao de cdigo serial presente em um programa.Desta forma, em uma aplicao cuja 50% do tempo de execuo sejaestritamente sequencial, o speedup mximo obtido ser 2, independentedo nmero de processadores utilizados, de acordo com a equao 3.limp!1S(p) =1fs(3)Com base nas equaes descritas anteriormente, evidencia-se que agranularidade da sincronizao e a frao serial do cdigo de um programa23so fatores determinantes no desenvolvimento de algoritmos concorrenteseficientes.Embora apresente uma srie de desvantagens, o mecanismo de locks temcomo vantagens possibilitar uma programao intuitiva e fcil de usar em muitoscasos, e diversas plataforma de hardwares existentes oferecerem suporte aomecanismo, o que evidencia o grande nmero de softwares que fazem uso destemodelo, alm de existir um grande grupo de desenvolvedores experientes queutilizam o mecanismo (MCKENNEY et al., 2010).Uma alternativa sincronizao baseada em locks a sincronizao nobloqueante,que tem por objetivo resolver os problemas intrnsecos dos locksno acesso recursos compartilhados (ANDREWS, 2000). A implementao nobloqueanteexclui qualquer uso de locks, j que esses podem induzir estado deespera (BALDASSIN, 2009).So classificados em trs nveis os algoritmos no-bloqueantes, de acordocom a garantia de progresso de suas operaes (BALDASSIN, 2009):1. Livre de espera (wait-free): Todas as operaes terminam aps umnmero finito de passos. O sistema como um todo faz progresso.2. Livre de trava (lock-free): Alguma operao termina aps um nmerofinito de passos. H pelo menos uma thread fazendo progresso.3. Livre de obstruo (obstruction-free): Alguma operao sempre terminaem um nmero finito de passos quando livre da interferncia de outrasoperaes. Uma thread, quando executada de forma isolada, sempre fazprogresso.Dessa forma, a sincronizao livre de espera garante progresso incondicional(BALDASSIN, 2009). J a livre de trava admite que determinada threadno faa progresso, cenrio denominado starvation (BALDASSIN, 2009). Porfim, como forma mais fraca, a livre de obstruo no garante progresso emcondies em que haja threads concorrentes e conflitantes. Nesse esquema possvel que threads invalidem uma o trabalho da outra sem haver progressoalgum, situao conhecida como livelock (BALDASSIN, 2009).O grande problema com a sincronizao no-bloqueante a extrema dificuldadeem projetar, implementar e verificar a corretude dos algoritmos (BALDASSIN,2009).Alguns casos reais ressaltam a dificuldade de desenvolvimento de sistemasconcorrentes. Entre 1985 e 1987, uma condio de corrida existente nosoftware para o equipamento de radiao mdico Therac-25 causou pelo menosseis mortes (LEVESON; TURNER, 1993). Em 1997, falhas sucessivas deoperao do dispositivo da misso Pathfinder em Marte foram atribudas a umproblema de inverso de prioridade no software (WILNER, 1997). Problemasdecorrentes de condio de corrida contriburam para um dos maiores blecautesda histria norte-americana em agosto de 2003, afetando cerca de 50 milhesde pessoas (POULSEN, 2004).Nas prximas 3 subsees sero descritos diferentes mtodos de sincronizao,baseados em locks. Na subseo 3.3.3, ser apresentado o mecanismo deMemrias Transacionais, na qual a caracterstica bloqueante ou no-bloqueantedepende de sua implementao.243.3.1 SemforosSemforo um mecanismo de sincronizao criado pelo matemtico holandsE. W. Dijkstra em 1965 (TANENBAUM; WOODHULL, 2008). Umsemforo S uma varivel inteira que, parte a inicializao, acessadasomente atravs de duas operaes atmicas padres: wait e signal. Estasoperaes eram originalmente designadas como P (da palavra holandesaproberen, que significa testar) e V (da palavra holandesa verhogen, significandoincrementar) (SILBERSCHATZ; GALVIN; GAGNE, 2009).As modificaes do valor inteiro do semforo sobre tais operaes e oconjunto de instrues no escopo dessas, devem ser executadas de modoindivisvel, afim de evitar-se condies de corrida (SILBERSCHATZ; GALVIN;GAGNE, 2009).Nas Figuras 4 e 5 mostram-se respectivamente as definies clssicas dasoperaes wait e signal.wai t (S) {whi le (S 0) {6 this . saldo = this . saldo + quant ia ;7 } else {8 System. out . p r i n t l n ("A quantia do depsito deve ser maiorque ZERO.") ;9 }10 }1112 public synchronized void saque ( double quant ia ) {13 i f ( this . saldo quant ia > 0) {14 this . saldo = this . saldo quant ia ;15 } else {16 System. out . p r i n t l n ("Saldo insuficiente para o valor desaque desejado.") ;17 }18 }19 }Figura 15: Exemplo de cdigo em Java utilizando monitor3.3.3 Memrias transacionaisO termo memria transacional foi cunhado em 1993 por Herlihy e Moss paradesignar: "uma nova arquitetura para microprocessadores que objetiva tornara sincronizao livre de bloqueio to eficiente (e fcil de usar) quanto tcnicas30convencionais baseadas em excluso mtua" (HERLIHY; MOSS, 1993). Estetermo define qualquer mecanismo de sincronizao que utilize o conceito detransao para coordenar acessos memria compartilhada.A memria transacional usa como principal abstrao o conceito de transao,criada e desenvolvida no contexto de sistemas de banco de dados (GRAY;REUTER, 1993). Nesse domnio, uma transao uma sequncia finita deinstrues, sendo serializadas por uma thread, satisfazendo as propriedadesACID (Atomicidade, Consistncia, Isolamento e Durabilidade).A propriedade de atomicidade define que as instrues pertencentes aoescopo da transao sero todas efetivadas com sucesso ou todas descartadas.Quando a transao for efetivada com sucesso o resultado da execuo permanente, e diz-se que a transao sofreu commit. Quando ocorrer falha natransao, diz-se que essa sofreu abort, e os valores pertencentes execuoda transao sero descartados.A propriedade de consistncia assegura a integridade dos dados, garantindoque uma transao levar o sistema de um estado consistente (prtransao)a outro estado consistente (ps-transao).O isolamento significa que transaes concorrentes no podero verificarresultados intermedirios produzidos por outras transaes, de modo que oresultado de execuo de diversas transaes seja equivalente ao resultado deexecuo dessas mesmas em ordem serial.A propriedade de durabilidade indica que as mudanas efetivadas portransaes so permanentes e resistentes a eventuais falhas no sistema.O conceito de transao no contexto de memrias transacionais basicamenteo mesmo, com exceo para a propriedade de durabilidade. O conceitode durabilidade pode ser ignorado em memrias transacionais, pois em seucontexto os dados sero armazenados em memria voltil, ao contrrio desistemas de banco de dados onde os dados so armazenados em memriapersistente.Em relao ao uso de bloqueios, a memria transacional apresenta asseguintes vantagens (MCKENNEY et al., 2010):_ Facilidade de programao: a programao torna-se mais fcil porque oprogramador no tem responsabilidade em como garantir a sincronizao,e sim em especificar quais blocos de cdigo devem ser executadosatomicamente, cabendo ao sistema transacional a implementao domecanismo de sincronizao._ Escalabilidade: Transaes que acessem um mesmo dado para leiturapodem ser executadas concorrentemente. Tambm podem ser executadasde modo paralelo as transaes que modifiquem partes distintas de umamesma estrutura de dados. Essa caracterstica tem como vantagemgarantir que mais desempenho seja obtido com o aumento do nmero deprocessadores porque o nvel de paralelismo exposto maior._ Composabilidade: Transaes suportam naturalmente a composiode cdigo. Para criar uma nova operao baseando-se em outras jexistentes, deve-se invoc-las dentro de uma nova transao. O sistematransacional ir garantir que tais operaes sejam executadas de formaatmica.31A seguir, ser apresentado a memria transacional sob a perspectiva doprogramador, em relao linguagem e semntica.3.3.3.1 Linguagem e semnticaAspectos referentes linguagem e semntica so importantes por indicaremo grau de expressividade da linguagem e definir univocamente o significado decada uma de suas construes (BALDASSIN, 2009).No contexto de memrias transacionais, as seguintes trs construes soatualmente aceitas: atomic, retry e orElse.Construo atomicA construo atomic representa o bloco atmico, o qual responsvelpor delimitar o escopo que deve ser executado por uma transao (HARRIS;FRASER, 2003). Uma grande vantagem do bloco atmico que no necessrio criar manualmente variveis especficas para controlar e bloquear aseo crtica de um programa, diferentemente de outras construes como locks.O sistema transacional ser responsvel por garantir a sincronizao do bloco,deixando a encargo do programador apenas especificar quais sero os blocosatmicos e no em como sincroniz-los.Na Figura 16 mostra-se um exemplo de implementao do bloco atmico,sendo delimitado pela palavra atomic (linha 2 at linha 8).1 public void deposi ta ( double quant ia ) {2 atomic {3 i f ( quant ia > 0) {4 this . saldo = this . saldo + quant ia ; / / Seo Cr t i c a5 } else {6 System. out . p r i n t l n ("A quantia do depsito deve sermaior que ZERO.") ;7 }8 }9 }Figura 16: Bloco atmicoA composio de transaes ilustrada na Figura 17, atravs de um mtodoque transfere um valor entre duas contas bancrias. Pelo fato da operao serefetuada de forma atmica e em isolamento, garantido que nenhuma outratransao ver o estado intermedirio na qual o valor sacado de uma conta(linha 3) ainda no tenha sido depositado na outra (linha 4). Caso haja falhaem alguma das operaes (saque ou deposito) o sistema transacional abortartoda transao, descartando as alteraes em ambas operaes.Construo retryA construo retry define que a transao seja cancelada, desfazendotodas as aes intermedirias (HARRIS et al., 2005). Quando algum dadocompartilhado recentemente acessado pela transao modificado, a transao re-executada. Por exemplo, suponha-se a remoo de elemento de um buffer.321 public void t r a n s f e r e n c i a ( ContaBancaria contaOrigem , ContaBancariacontaDestino , Double quant ia ) {2 atomic {3 contaOrigem . saque ( quant ia ) ;4 contaDest ino . deposi to ( quant ia ) ;5 }6 }Figura 17: Composio em memria transacionalSempre que um buffer estiver vazio a transao invoca a construo retry,fazendo com que a transao seja cancelada e re-executada quando a varivelitens for modificada por outro processo/thread.Afim de comparar uma construo transacional com outra abordagem deprogramao, o mesmo exemplo de remoo de elemento de um buffer serimplementado em Java utilizando de monitores, conforme mostra na Figura 19.O uso da primitiva synchronized indica que o processo/thread que invocar omtodo remover dever obter o bloqueio associado ao objeto buffer, antes deprosseguir com a operao de remoo. A aquisio e liberao de bloqueios implcita em Java, quando o mtodo for qualificado como synchronized. Omtodo wait serve para garantir que no seja removido um elemento de umbuffer vazio e o mtodo notifyAll notifica os outros processos/threads que umelemento foi removido do buffer.12 public int remover ( ) {3 atomic {4 i f ( i t e n s == 0)5 r e t r y ;6 i tens ;7 return b u f f e r [ i t e n s ] ;8 }9 }Figura 18: Remoo elemento de buffer codificada com a construo retry.Fonte: (RIGO; CENTODUCATTE; BALDASSIN, 2007)12 public synchronized int remover ( ) {3 int resul tado ;4 while ( i t e n s == 0)5 wai t ( ) ;6 i tens ;7 resul tado = b u f f e r [ i t e n s ] ;8 n o t i f y A l l ( ) ;9 return resul tado ;10 }Figura 19: Remoo elemento de buffer codificada em Java com monitor.Fonte: (RIGO; CENTODUCATTE; BALDASSIN, 2007)33A partir dos dois exemplos mostrados nas Figuras 18 e 19, observa-se umproblema comum com bloqueios: baixa concorrncia e, respectivamente, baixodesempenho. Como um bloqueio associado ao objeto buffer adquirido aoinvocar o mtodo remover, qualquer outro mtodo do objeto que eventualmenteseja invocado ser bloqueado at que o mtodo libere o bloqueio. Ou seja, duasou mais operaes no acontecero concorrentemente no buffer mesmo quandoh uma possibilidade de paralelismo. Por exemplo, possvel que uma operaode insero ocorra simultaneamente a uma de remoo se ambas acessaremelementos disjuntos no buffer. Portanto o uso de transaes consegue explorarmais paralelismo, pois a deteco de conflitos feita de forma dinmica (emtempo de execuo).Construo orElseA construo orElse permite que transaes sejam compostas como alternativaspara execuo, significando que somente uma transao ser executadaentre vrias (HARRIS et al., 2005).Por exemplo, suponha-se um sistema que remova elementos de um buffer.O mtodo de remoo pode ser bloqueado (invocar retry) se o buffer estivervazio, conforme mostrado na Figura 18. Uma implementao possvel usandoorElse para esta situao mostrada na Figura 20. Nesta implementao, osistema transacional tentar remover elementos entre dois buffers. Caso o buffer1 estiver vazio o sistema tentar remover o elemento do buffer 2. Caso os doisbuffers estiverem vazios, o bloco atmico ser bloqueado at que ao menos umdos buffers contenha um elemento para poder ser removido.12 public void exemploOrElse ( ) {3 atomic {4 { x = buf fer1 . remover ( ) ; }5 orElse6 { x = buf fer2 . remover ( ) ; }7 }8 }Figura 20: Uso da construo orElse. Fonte: (RIGO; CENTODUCATTE;BALDASSIN, 2007)Nveis de isolamentoO nvel de isolamento est relacionado interao entre cdigo transacionale cdigo no transacional. Existem dois tipos de isolamento: atomicidade forte(strong atomicity) e atomicidade fraca (weak atomicity) (BALDASSIN, 2009).No modelo com atomicidade forte o acesso a um dado compartilhado fora deuma transao consistente com os acessos efetuados ao mesmo dado dentroda transao. Em contrapartida, no modelo com atomicidade fraca o acesso aum mesmo dado compartilhado, dentro e fora de uma transao, causa condiode corrida e portanto o resultado no-determinstico.343.3.3.2 ImplementaoUm sistema de memria transacional deve garantir a consistncia e integridadede execues das transaes, satisfazendo as propriedades de atomicidade,consistncia e isolamento, descritas anteriormente.As implementaes so construdas com dois mecanismos chaves: versionamentode dados e deteco/resoluo de conflitos (RIGO; CENTODUCATTE;BALDASSIN, 2007).Versionamento de dadosO versionamento de dados lida com o gerenciamento das diferentes versesdos dados (originais e especulativas) acessados por uma transao. A versooriginal corresponde ao valor do dado antes do incio da transao. A versoespeculativa representa o valor intermedirio sendo trabalhado pela transao.Caso a transao seja efetivada, os valores especulativos tornam-se os valorescorrentes e so armazenados, e os valores originais so descartados. Docontrrio, descarta-se os especulativos e mantm-se os originais (BALDASSIN,2009).Existem duas formas de versionamento de dados: adiantado/direto (directupdate ou eager versioning) e atrasado/diferido (deferred update ou lazyversioning) (RIGO; CENTODUCATTE; BALDASSIN, 2007).No versionamento de dados adiantado, os valores so armazenadosdiretamente na memria, enquanto que os valores antigos so armazenados emum undo log. No caso de uma transao falhar, os dados que foram gravados namemria inicialmente devero ser convertidos para suas verses antigas, atravsdo undo log.No versionamento de dados atrasado, o armazenamento de novos dados realizado em um buffer local, e a memria continua com os valores antigos. Osdados so transferidos do buffer para a memria somente quando a transaofor confirmada.Ilustra-se na Figura 21 um exemplo com ambos tipos de versionamento dedados. Inicialmente, o contedo da varivel X na memria corresponde ao valor100 e os respectivos undo log e buffer esto vazios. Quando uma transaoatribui o valor 77 varivel X, o versionamento adiantado altera imediatamente ocontedo da memria e armazena o valor antigo localmente (undo log), enquantoo versionamento atrasado somente necessita salvar o novo valor em memrialocal (buffer ). No momento da efetivao da transao, a nica ao necessriano versionamento adiantado invalidar o undo log, pois o dado novo j est namemria. J o versionamento atrasado precisa primeiramente mover o valorarmazenado localmente para a memria do sistema. Uma situao inversaacontece em caso de cancelamento da transao. Nesse caso, o versionamentoadiantado precisa restaurar as mudanas efetuadas na memria, movendo paraesta o valor antigo presente no undo log. Com o versionamento atrasado s necessrio descartar os valores especulativos.Como pode ser observado na Figura 21, conclui-se que o versionamentoadiantado torna-se mais eficiente em casos em que a transao confirmada,pois os valores corretos j esto na memria. Por outro lado, quando a transao cancelada, deve-se restaurar os valores corretos para a memria, que esto35armazenados no undo log. No versionamento atrasado a situao oposta,visto que transaes confirmadas necessitam transferir os dados do buffer paraa memria, enquanto que transaes canceladas no necessitam de nenhumaoperao.Figura 21: Exemplo ilustrando versionamento adiantado (a) e atrasado (b).Fonte: (BALDASSIN, 2009)Deteco/Resoluo de conflitosDiz-se que houve conflito entre duas ou mais transaes quando essasacessam o mesmo dado compartilhado e um dos acessos de escrita (BALDASSIN,2009). O sistema transacional efetua a deteco de conflitos baseandosena granularidade de deteco de conflitos. Essa granularidade pode serem trs nveis: objeto, palavra e linha de cache (RIGO; CENTODUCATTE;BALDASSIN, 2007). A granularidade por nvel de objetos pode reduzir ooverhead em termos de espao e tempo para deteco de conflitos. No entanto,esse nvel permite detectar falsos conflitos, ou seja, casos em que o sistemadetectar conflitos quando duas transaes operam em diferentes partes de ummesmo objeto. A granularidade por nvel de palavras elimina a deteco defalsos conflitos, por outro lado, necessita-se de maior custo e espao para adeteco. A granularidade por nvel de linha de cache prov um acordo entrea frequncia de deteco de falsos conflitos e o overhead em termos de tempoe espao. No entanto, necessita-se de alteraes na estrutura de hardware paraprover a cache transacional, alterando seu protocolo de coerncia.Assim como no versionamento de dados, h dois modos de deteco deconflitos: adiantado/pessimista (pessimistic ou eager conflict detection) e atrasado/otimista (optimistc ou lazy conflict detection) (RIGO; CENTODUCATTE;BALDASSIN, 2007).No modo de deteco de conflitos adiantado, o conflito detectado nomomento em que uma posio de memria acessada. Desta forma podeseevitar que uma transao execute desnecessariamente, mas por outro lado,pode cancelar transaes, dependendo do progresso de outras, poderiam ser36confirmadas com sucesso. Para exemplificar a deteco de conflitos de formaadiantada, os cenrios mostrados na Figura 22 sero considerados. No caso1, T1 e T2 manipulam conjuntos de dados disjuntos e portanto no h nenhumconflito. No caso 2 tem-se uma operao de escrita depois de uma leitura. Atransao que escreveu (T2) faz com que a outra transao (T1) seja cencelada.O caso 3 mostra a situao em que, aps ser cancelada, T1 volta a executare por sua vez cancela a transao T2. Nesse exemplo, pode-se notar que astransaes T1 e T2 esto em estado de livelock, desta forma, a efetivao detais transaes indefinida.Figura 22: Deteco de conflitos em modo adiantado em cenrios transacionais.Fonte: (RIGO; CENTODUCATTE; BALDASSIN, 2007)Na deteco atrasada o conflito detectado somente no momento deefetivao da transao. Desta forma, essa abordagem permite que transaesconflitantes prossigam na esperana do conflito no se efetivar de fato.De modo a exemplificar a deteco de conflitos de forma atrasada, oscenrios mostrados na Figura 23 sero considerados. No caso 1, as transaesacessam um conjunto de dados disjuntos, no ocasionando conflitos. No caso2, T2 l uma varivel escrita por T1. Quando T1 sofre efetivao, T2 nota oconflito e reiniciada. No caso 3 no ocorre nenhum conflito, pois T1 apenas luma varivel que T2 est escrevendo e esta sofre efetivao aps T1. O caso 4mostra a situao em que, aps ser cancelada, T1 volta a executar. No entanto,diferentemente da deteco adiantada, este caso no gera situao de livelock,porm, poderia acontecer situao de starvation. Se T1 fosse muito longa essapoderia ser sempre cancelada por outras transaes e nunca conseguir efetivarsuas alteraes.O gerenciador de conteno o componente do sistema transacional responsvelpor resolver os conflitos dentre as transaes concorrentes. A resoluo deconflitos deve ser efetuada de tal forma a garantir progresso do sistema, ou seja,deve evitar starvation e livelock (BALDASSIN, 2009). Algumas propostas de TMpossuem um mtodo fixo para gerenciamento de conteno, ao passo que outraspropostas tratam o problema como um aspecto modular do sistema, podendo seralterado para melhorar o desempenho de um programa sob determinada cargade trabalho (KRONBAUER; RIGO, 2009).37Figura 23: Deteco de conflitos em modo atrasado em cenrios transacionais.Fonte: (RIGO; CENTODUCATTE; BALDASSIN, 2007)A escolha do gerenciador de conteno pode influenciar no desempenhoe consumo de energia de memrias transacionais, conforme ser mostradono Captulo 4. Porm, no existe um consenso na comunidade de TM sobrequal estratgia para deteco/resoluo de conflitos a mais efetiva, poisuma estratgia pode funcionar bem para algumas aplicaes mas no paraoutras (BALDASSIN, 2009).3.3.3.3 Modelos de memrias transacionaisAs implementaes de TM so comumente divididas em trs modelos:hardware, software, e hbrida (BALDASSIN, 2009). As implementaes nastrs abordagens devem prover o versionamento dos dados manipulados pelastransaes de forma atmica e isolada, e efetuar a deteco/resoluo deconflitos entre transaes.Memria Transacional em HardwareAs implementaes de memrias transacionais em hardware (HTM) usualmentefazem o versionamento de dados e deteco de conflitos atravsmodificaes e extenses em alguns componentes da arquitetura computacional(BALDASSIN, 2009).A primeira implementao de HTM foi desenvolvida por Herlihy e Moss em1993 (HERLIHY; MOSS, 1993). Para dar suporte a transaes, Herlihy e Mossestenderam a arquitetura do conjunto de instrues de um processador basecom 6 novas instrues, adicionaram uma cache especial, chamada de cachetransacional, e alteraram o protocolo de coerncia.Vrias abordagens de HTM foram desenvolvidas aps o modelo descrito porHerlihy e Moss, procurando suprir as principais deficincias da proposta inicial,a qual restringia o nmero de posies acessadas pela transao (espao)e a durao em que a transao poderia estar ativa. As principais so:TCC (Transactional Coherence and Consistency) (HAMMOND et al., 2004),UTM (Unbounded Transactional Memory) (ANANIAN et al., 2005), VTM (VirtualTransactional Memory) (RAJWAR; HERLIHY; LAI, 2005), LogTM (Log-basedTransactional Memory) (MOORE et al., 2006), PTM (Page-based Transactional38Memory) (CHUANG et al., 2006), OneTM (BLUNDELL et al., 2007) e MetaTM(RAMADAN et al., 2007). Essas propostas tm suporte para virtualizaode espao e tempo, diferenciando-se entre si pelo hardware extra exigido eestratgia adotada para versionamento e controle de conflitos.As implementaes em hardware tm como principais caractersticas garantiratomicidade forte como nvel de isolamento e granularidade por linha de cache.A principal vantagem de HTM o desempenho, pelo fato de implementar astransaes diretamente em hardware. No entanto, as implementaes emhardware ainda so consideradas complexas, tornando invivel a adoo eimplementao efetiva em algum processador comercial (BALDASSIN, 2009).Memria Transacional em SoftwareO modelo em software implementa as transaes puramente em software.Como vantagem dessa abordagem, tem-se uma maior flexibilidade na implementaoaliada execuo em mquinas atuais e subsequentemente aportabilidade deste modelo, visto que alteraes na arquitetura computacionalno fazem-se necessrias (RIGO; CENTODUCATTE; BALDASSIN, 2007).O termo Memria Transacional em Software (STM) foi cunhado por Shavite Touitou em 1995 (SHAVIT; TOUITOU, 1995), propondo uma alternativa emsoftware ao mecanismo em hardware de Herlihy e Moss (HERLIHY; MOSS,1993), de 1993. A implementao proposta mantm para cada palavra emmemria compartilhada um registro de posse, que aponta para o registro datransao detentora da palavra. O processo de efetivao das transaesbaseia-se na aquisio de posse de todas as palavras a serem alteradas,efetuao das alteraes e liberao da posse. Um conflito acontece casoalguma palavra j tenha sido adquirida por outra transao.Os sistemas de memria transacional em software usam barreiras de leiturae escrita para interceptar os acessos aos dados compartilhados e manter osconjuntos de leitura e escrita (BALDASSIN, 2009). Existem dois tipos principaisde implementaes: no-bloqueantes e bloqueantes.As primeiras implementaes de STM so no-bloqueantes, entre as principaisesto: DSTM (Dynamic STM) (HERLIHY et al., 2003), WSTM (WordbasedSTM) (HARRIS; FRASER, 2003), OSTM (Object-based STM) (FRASER,2004), HaskellTM (HARRIS et al., 2005), ASTM (Adaptive STM) (MARATHE;Scherer III; SCOTT, 2005) e RSTM (Rochester STM) (MARATHE et al., 2006).Especificamente, DSTM, ASTM e RSTM so livres de obstruo, enquantoWSTM, OSTM e HaskellTM so livres de trava. Nas implementaes livres deobstruo, o gerenciador de conteno tem um papel vital, pois o componentetransacional responsvel por determinar o progresso do sistema em situaesde conflitos. A maioria dessas implementaes trabalham com granularidade emnvel de objeto, exceto WSTM e HaskellTM que usam granularidade em nvel depalavra.Constatou-se atravs de pesquisas que as abordagens transacionais emsoftware no-bloqueantes apresentam baixo desempenho, se comparadas utilizao de bloqueios explcitos (ENNALS, 2006). A partir desse importanteresultado a maioria das implementaes propostas passaram a utilizar locks,de maneira implcita. Em especial, foram apresentadas: McRT-STM (Multi39core RunTime STM) pela Intel (SAHA et al., 2006), Bartok-STM pela Microsoft(HARRIS et al., 2006), TL2 (Transactional Locking II) pela Sun (DICE;SHALEV; SHAVIT, 2006), TinySTM pelas universidades de Neuchtel e deDresden (FELBER; FETZER; RIEGEL, 2008) e SwissTM pela Escola PolitcnicaFederal de Lausana (DRAGOJEVIC; GUERRAOUI; KAPALKA, 2009).As diversas implementaes de STM se diferenciam principalmente pelagranularidade de acesso permitido (palavra ou objeto), e pela estratgia deversionamento de dados, deteco e resoluo de conflitos (BALDASSIN, 2009).Ao contrrio de HTM, a maioria das implementaes em software garantemapenas atomicidade fraca como nvel de isolamento, devido a motivos dedesempenho, pois garantir atomicidade forte exigiria incluir barreiras tambm emcdigo no transacional (BALDASSIN, 2009).Memria Transacional HbridaA abordagem hbrida busca combinar os modelos de software e hardwarecom intuito de obter melhor resultado com a unio das duas abordagens.Nessa abordagem, transaes podem ser executadas em um dois modos: emhardware, com alto desempenho, ou software, com ilimitados recursos (RIGO;CENTODUCATTE; BALDASSIN, 2007).Nas primeiras implementaes de memrias transacionais hbridas as transaesso iniciadas em modo de hardware, mas se os recursos de hardware foremexauridos a transao poder ser reiniciada em modo de software (DAMRONet al., 2006) (KUMAR et al., 2006). O grande desafio nessa abordagem quandoexistem transaes concorrentes executando tanto em modo de hardware quantoem modo de software. Contornar esse problema geralmente requer solues quetornam as transaes em hardware mais lentas do que o desejado (BALDASSIN,2009).Posteriormente, as propostas de TM hbridas basearam-se na acelerao dosoftware atravs do suporte executivo em hardware (SAHA; ADL-TABATABAI;JACOBSON, 2006) (SHRIRAMAN et al., 2007) (MINH et al., 2007) (SHRIRAMAN;DWARKADAS; SCOTT, 2008). A principal caracterstica dessas propostas que as transaes so sempre executadas em modo de software, mas usam ohardware para acelerar tarefas crticas. Por exemplo, a validao das transaes reconhecidamente um gargalo na maioria das STMs. Uma soluo nasabordagens hbridas seria adicionar hardware para acelerar essa tarefa, comofeito por Saha et al. (SAHA; ADL-TABATABAI; JACOBSON, 2006). A grandevantagem que o hardware adicionado no especfico para TM, podendo serpotencialmente usado em outras tarefas (BALDASSIN, 2009).3.4 Observaes finaisEste Captulo apresentou os principais conceitos relacionados comunicaoe sincronizao em sistemas concorrentes, em ambiente de memriacompartilhada. Foram apresentados os problemas que podem ocorrer durantea comunicao entre fluxo de execues de sistemas, e os mecanismos desincronizao, que visam garantir a corretude das execues concorrentes.Mostrou-se que mecanismos de sincronizao baseados em bloqueios (locks)40so fceis de usar em muitos casos, e consequentemente so muito utilizado,porm, se no empregados corretamente, podem apresentar uma srie deproblemas, podendo levar o sistema a um estado de instabilidade. O mecanismode sincronizao por memrias transacionais garante maior abstrao na codificaode programas paralelos, pois tira da responsabilidade do programador omodo como as sincronizaes sero feitas, ficando a encargo do sistema queimplementa as memrias transacionais garantir a sincronizao em baixo nvel.Por implementar as sincronizaes em baixo nvel, o sistema transacional facilitaa codificao de programas paralelos, alm de suprir as dificuldades e limitaesencontradas no uso de locks.Em relao as memrias transacionais, mostrou-se que as implementaesem hardware (HTM) tm como principal vantagem o desempenho, porimplementarem o suporte executivo diretamente em hardware, a partir demodificaes na arquitetura computacional. No entanto, este modelo complexode ser projetado, dificultando assim, a adoo e implementao efetiva emprocessadores comerciais. Por outro lado, embora as implementaes emsoftware (STM) apresentem desempenho inferior em relao HTM, as STMtm como principais vantagens a flexibilidade e portabilidade da implementao,pois essas podem ser executadas diretamente em processadores atuais, emconsequncia, so atualmente alvo de muita pesquisa.4 TRABALHOS RELACIONADOSEste Captulo apresenta os principais trabalhos que levam em consideraoa medio do consumo de energia e/ou desempenho, relacionados aos mecanismosde sincronizao em ambiente de memria compartilhada, descritos noCaptulo anterior.4.1 Reduzindo o consumo de energia em um sistema multiprocessadousando HTMO trabalho de Moreshet, Bahar e Herlihy (2005) avalia o consumo de energiade HTM em comparao locks (spinlock), sendo pioneiro em avaliar o consumoenergtico em HTM.Sua implementao baseia-se no modelo original de HTM (HERLIHY; MOSS,1993), no qual h uma cache transacional completamente associativa paraarmazenar os valores especulativos. Utiliza a plataforma de simulao SIMICS(MAGNUSSON et al., 2002) para modelar um sistema com processadoresUltraSparc II conectados por barramento, assumindo dados de energia e latnciapara uma memria compartilhada off-chip, e sistema operacional Linux.Duas diferentes abordagens para a HTM utilizada foram experimentadas, naqual, a diferena entre ambas est no mtodo utilizado para manipulao deconflitos em transaes. A primeira abordagem padro da HTM utilizada, reexecutaas transaes conflitantes em paralelo (baseado em backoff randmico).A segunda, foi proposta pelos prprios autores, sendo um mecanismo paraexecuo de modo serial de todas transaes pendentes durante o o conflito.Atravs dos resultados obtidos neste trabalho mostrou-se que a verso utilizandolocks consumiu 10x mais energia que as abordagens de HTM utilizadas.Tal resultado deve-se a significativa frao de energia consumida pela hierarquiade memria. Em relao s HTM utilizadas, a que utilizou a execuo serialpara tratamento de conflitos mostrou-se mais eficiente em termos de energia.No entanto, esta uma abordagem pessimista, na qual h uma conteno doparalelismo.Embora os resultados obtidos neste trabalho mostram que HTM eficienteem termos de consumo de energia, o trabalho apresentou alguns problemasque tornam seus resultados pouco convincentes. Apenas um microbenchmark(desenvolvido pelos prprios autores) com apenas uma configurao do sistema(quatro processadores) utilizado para os experimentos. E, no descrito como implementado o mecanismo de execuo serial das transaes conflitantes.424.2 HTM x locks: uma comparao de desempenho e consumode energiaO trabalho de Moreshet, Bahar e Herlihy (2006) apresenta uma extenso dotrabalho de Moreshet, Bahar e Herlihy (2005), descrito anteriormente. Utilizandoa mesma HTM e plataforma de simulao, avalia o consumo de energia edesempenho de HTM em comparao locks (spinlock) atravs de quatrosaplicaes do benchmark SPLASH-2 (WOO et al., 1995).Neste trabalho apresentado maiores detalhes em relao execuo serialdas transaes conflitantes, visto que no trabalho anterior apenas foi citado essenovo mecanismo. Com o sistema transacional de execuo serial, um conflitoainda resulta em retornar ao estado anterior. No entanto, durante alta conteno,em vez de re-executar as transaes depois do conflito, o sistema transacional iresperar uma transao completar antes de outra comear sua execuo. Aps operodo conflitante, o sistema transacional voltar a emisso de transaes emparalelo.Inicialmente, constatou-se atravs dos resultados obtidos no benchmarkSPLASH-2 que na maioria das aplicaes onde substitui-se os locks portransaes, reduziu-se os acessos cache e a memria principal, reduzindoassim o consumo de energia e maximizando a performance. Entretanto,por considerar que as aplicaes do SPLASH-2 possuem taxas de conflitosbaixa, foi utilizado um microbenchmark, com duas configuraes para simulardiferentes cenrios de conflitos. Nas duas configuraes do microbenchmark,ambas implementaes de memria transacional (backoff e serial) superaramem termos de desempenho e eficincia energtica verso utilizando locks,cerca de 10x mais, no melhor caso.Em uma das configuraes do microbenchmark, a memria transacionalutilizando-se da execuo serial para os casos de conflito superou em termosde performance e eficincia energtica a memria transacional que utilizou atcnica de backoff para conflitos. Porm, em outra configurao, a versotransacional serial mostrou-se ligeiramente inferior em relao verso transacionalutilizando backoff, em termos de desempenho. Desta forma, o modo deexecuo serial das transaes conflitantes mostra-se conservador, incorrendoem penalidades no desempenho.Atravs dos resultados mostrados neste trabalho verificou-se que a abordagemde HTM promissora em termos de desempenho e energia. A execuoserial para transaes conflitantes em ambientes de alta conteno eficienteem termos de energia, porm, para outros casos, a produtividade do sistemapode ser reduzida. No entanto, so dados poucos detalhes em relao aomicrobenchmark e suas duas configuraes e a avaliao do modo serial feita somente neste microbenchmark, tornando novamente os resultados poucoconvincentes.4.3 McRT-STM x locks: uma comparao de desempenhoNo trabalho de Saha et al (2006) mostrado um estudo de avaliao dedesempenho entre a implementao McRT-STM e locks.Dois experimentos com base em aplicaes diferentes foram realizados. No43primeiro, utilizou-se de estruturas de dados comumente utilizadas em muitasaplicaes: hashtable, rvore de pesquisa binria, rvore B e lista ligada.No segundo, avaliou-se o desempenho de STM e locks em uma aplicaono sinttica, utilizando-se da aplicao Sendmail como base. Utilizou-se daplataforma IBM X Series 445 SMP com 16 processadores Xeon com 2.2 GHzpara execuo das aplicaes.Para o primeiro experimento, as seguintes constataes podem ser feitas,com base nos resultados obtidos. Na aplicao hashtable, observou-se atravsdos resultados que a verso de STM inicialmente (utilizando 1 processador)obtm menor performance em comparao as duas implementaes de locks(gro fino e gro grosso). No entanto, conforme aumentou-se o nmero deprocessadores, o desempenho da STM aproximou-se da verso verso de locksque obteve maior desempenho (gro fino). Na utilizao de 16 processadores, aSTM foi cerca de 1.8x menos eficiente em termos de performance em relao locks (gro fino). Na aplicao rvore de pesquisa binria balanceada, verificouseque a STM obtm melhor desempenho em comparao locks quando aproporo de atualizaes baixa. Contudo, para altas taxas de atualizao,a STM apresentou desempenho ineficiente. Isto porque o balanceamento darvore propaga mudanas em toda rvore e aumenta o nmero de cancelamentodas transaes. E, o balanceamento propaga mudanas na raiz da rvore,limitando a concorrncia. Na utilizao da rvore de pesquisa binria sembalanceamento observou-se que a STM apresentou melhor desempenho emcomparao locks, mesmo com altas taxas de atualizao. Na rvore B, aSTM mostrou melhor desempenho em comparao locks (gro fino e grogrosso) mesmo com altas taxas de atualizaes, devido a rvore B resultar empoucos cancelamentos de transaes. Na aplicao lista ligada classificada, odesempenho da STM variou conforme o nmero de atualizaes na lista. Combaixas taxas de atualizao, a STM apresentou melhor desempenho, mas como aumento de atualizaes, o desempenho torna-se ligeiramente inferior a locks,devido ao aumento do nmero de transaes canceladas. Na lista ligada noclassificada, a memria transacional apresentou desempenho inferior locks,devido a todas inseres serem feitas na frente da lista, no fornecendo destaforma nenhuma simultaneidade para as operaes de atualizao. Os resultadosobtidos para as aplicaes lista ligada e rvore de pesquisa binria mostraram aimportncia de um bom gerenciador de conteno no sistema transacional, vistoque a STM apresentou desempenho inferior em relao locks, em cenrio dealta conteno.Em relao ao segundo experimento, verificou-se que a aplicao Sendmail(baseada em locks) gasta cerca de 10% de seu tempo de execuo emsees crticas, assim, devido a seo crtica representar um tempo significante,analisou-se a utilizao de STM na aplicao, buscando reduo de tempo deexecuo para a seo crtica. Os testes foram realizados utilizando-se de umaa 8 threads para cada abordagem. Em todos os casos, verificou-se que a STMse equiparou em termos de desempenho em relao verso utilizando locks.Esse resultado preliminar fornece evidncias que at mesmo para aplicaescomerciais, a STM e locks so semelhantes em termos de desempenho.444.4 Caracterizando o consumo de energia em STMO trabalho de Baldassin et al (2009) pioneiro em caracterizar o consumo deenergia em STM.O processo de caracterizao foi conduzido em um ambiente simuladoamplamente usado na literatura, conhecido como MPARM (LOGHI; PONCINO;BENINI, 2004). Em relao a plataforma utilizada duas observaes fazemsenecessria. Primeiramente, as memrias empregadas (tanto privada comocompartilhada) so baseadas na tecnologia SRAM (Static Random AccessMemory). Segundo, os acessos feitos a memria compartilhada no so retidosna cache, visto que a implementao do barramento usado no possui suportepara coerncia de cache.As aplicaes utilizadas na caracterizao fazem parte do pacote de benchmarkSTAMP (CAO MINH et al., 2008), disponibilizado pela Universidadede Standford. Foram utilizadas as 8 aplicaes presentes no pacote, comdiferentes configuraes, visando representar diversos cenrios transacionaiscom diferentes tamanhos de transao, tempos em transao, tamanho doconjunto de leitura e escrita, e graus de conteno. De igual modo, uma versosequencial (no utilizando-se de transaes) ser executada para comparao STM.A implementao da STM utilizada nos experimentos foi a TL2 (DICE;SHALEV; SHAVIT, 2006), configurada de dois modos (ambos usados nosexperimentos): TL2-lazy (versionamento atrasado) e TL2-eager (versionamentoadiantado). Duas estratgias do gerenciamento de conteno so providas,baseadas na tcnica conhecida como backoff : aps trs cancelamentos consecutivos,uma transao postergada por um tempo (exponencial ou linear)proporcional ao nmero de cancelamentos.O procedimento de medio de energia foi dividido pelos componentesbsicos de uma STM, possibilitando assim, avaliar quais os elementos maiscustosos e orientar o projeto do algoritmo de forma a otimiz-lo.Os experimentos realizados foram executados na plataforma de simulaocom dois cenrios diferentes. Inicialmente, utilizou-se de apenas 1 processadornos experimentos, e posteriormente, para que os custos devidos aos cancelamentosdas transaes fossem contabilizados, foram utilizados 8 processadores.Mostrou-se atravs dos resultados dos experimentos que a implementaoque utiliza versionamento adiantado (TL2-eager) tem um custo de energialigeiramente menor do que a tcnica com versionamento atrasado (TL2-lazy). Noentanto, em relao a execuo sequencial, para algumas aplicaes, o custototal introduzido pelas transaes pode chegar perto de 5x, na utilizao de 1processador.Na utilizao de 8 processadores, alm das diferentes tcnicas de versionamentode dados, as duas configuraes de backoff (exponencial e linear)foram contabilizadas. De modo geral, observou-se que para aplicaes comalta taxa de cancelamento, nos casos em que o esquema de espera linear usado, o custo de cancelamentos domina. Porm, no emprego do tempo deespera exponencial, o custo de backoff passa a prevalecer. Em uma aplicaoespecfica do pacote de benchmark, utilizando-se de TL2-lazy e tempo de esperaexponencial, o custo total de energia chega a cerca de 50x o do caso sequencial.Com base nos resultados providos pela caracterizao, devido ao alto45consumo de energia em casos de alta conteno, os autores propuseram autilizao de uma estratgia que visa reduzir o consumo em casos em queestados de espera so induzidos por cancelamentos de transaes, podendoser usada em qualquer STM na qual o gerenciador de conteno adote polticasde resoluo de conflitos baseada em espera. A estratgia proposta baseadana tcnica conhecida como DVFS (KAXIRAS; MARTONOSI, 2008).A estratgia funciona da seguinte maneira: antes de entrar no modo debackoff, o processador correspondente colocado em modo de baixo consumode potncia, atravs da reduo de sua frequncia e voltagem. O processadorento cumpre seu tempo em estado de espera (linear ou exponencial) em modode baixa potncia. Quando o tempo de backoff termina, a frequncia e voltagemoriginais so restauradas. O custo para alternncia em diferentes estados noprocessador rpido, requerendo apenas 1 ciclo por mudana, na plataformautilizada.Os experimentos utilizando-se da estratgia descrita, como resultado, obtiveramuma reduo efetiva do consumo de energia para as aplicaes com altograu de conteno, em mdia de 45%, chegando a 87% de reduo para umaaplicao especfica.4.5 Avaliao de desempenho em gerenciadores de contenocom STMO trabalho de Kronbauer e Rigo (2009) avalia diferentes estratgias de gerenciadoresde conteno em STM, em termos de desempenho. Especificamente,os seguintes gerenciadores foram avaliados: Aggressive, Eruption, Greedy,Highlander, Karma, Killblocked, Polka, Polkaruption e Whpolka.Utilizou-se da verso 3 da biblioteca RSTM, em dois modos: bloqueante eno bloqueante. Foram realizadas algumas modificaes na biblioteca de modoa permitir que diferentes gerenciadores de conteno possam ser associados adiferentes transaes ou a diferentes objetos transacionais. Precisamente, foialterado a macro que delimita o incio da transao, fazendo com que recebessecomo parmetro um valor enumerado capaz de identificar o gerenciador deconteno a ser usado. O gerenciador pode desta forma ser associado ao objetoque encapsula a estrutura de dados transacional, e diferentes gerenciadores deconteno podem ser associados a diferentes estruturas de dados ou mesmo adiferentes operaes em uma mesma estrutura de dados.Trs diferentes sistemas computacionais foram utilizadas para as execues.O primeiro, um sistema baseado no processador Intel Core 2 Duo a 2.8 GHz, com2 GB de memria RAM. O segundo um sistema baseado no processador IntelCore 2 Quad, a 2.4 GHz e com 4 GB de RAM. O terceiro, um sistema com doisprocessadores Intel Core 2 Quad a 2 GHz e 4 GB de RAM. Todos os sistemasutilizaram como sistema operacional uma distribuio Linux padro (kernel 2.6).Necessitou-se portar a biblioteca RSTM para arquiteturas x86 de 32 bits, pois averso 3 da RSTM somente tem suporte para a plataforma SPARC.Utilizou-se da implementao de rvores balanceadas do tipo vermelha-epreta,do benchmark disponvel junto a implementao original da bibliotecaRSTM, como aplicao base para os experimentos. O nmero de threadsfoi variado ao longo das execues do benchmark, de uma thread at o46nmero de threads de execuo igual a quatro vezes o nmero de ncleosde processamento no sistema. Para assegurar diferentes padres de acessoa diferentes estruturas de dados, as rvores foram geradas de maneira a simulardiferentes cenrios (baixa, mista e alta conteno). Os tipos de operaesnas rvores foram particionados igualmente, sendo um tero buscas, um teroinseres e um tero remoes.Algumas afirmaes podem ser feitas com base nos resultado obtidos. Parao sistema Intel Core 2 Duo, o gerenciador de conteno Aggressive foi o queapresentou melhores resultados, tanto no cenrio de alta quanto no cenrio debaixa conteno, na utilizao de 4 ou mais threads. Para o sistema Intel Core2 Quad verificou-se que sob alta conteno, quatro gerenciadores apresentaramo melhor desempenho. Estes foram Killblocked, Karma, Eruption e Whpolka.Sob baixa conteno, o gerenciador Aggressive ofereceu o melhor desempenhode modo geral, especialmente quando o nmero de threads excede o nmerode ncleos de processamento. Sob conteno mista, o gerenciador Aggressivenovamente apresentou o melhor resultado. No sistema Intel Dual Core 2 Quad,o gerenciador Killblocked apresentou em todos os casos o melhor desempenho,tanto em ambientes de alta como baixa conteno. De maneira geral, aimplementao no-bloqueante da STM utilizada apresentou-se ligeiramenteinferior em relao a verso bloqueante, em termos de performance.Notou-se atravs dos resultados obtidos que no h um gerenciador deconteno ideal a ser utilizado como escolha padro, reafirmando os resultadosencontrados em (GUERRAOUI; HERLIHY; POCHON, 2005). Porm, verificouseque a escolha ideal do gerenciador de conteno varia conforme o nvelde conteno e plataforma de hardware. Mostrou-se neste trabalho que osgerenciadores de conteno representam uma rea interessante para a buscapela melhoria de desempenho, no entanto, novos fatores tambm devem serconsiderados na avaliao destes, como o consumo de energia.4.6 STM x locks: uma perspectiva de desempenho e consumode energiaO trabalho de Klein et al (2010) avalia o consumo de energia e desempenhode STM em comparao locks, utilizando a mesma plataforma de simulao,pacote de benchmark, metodologia e implementao de STM, apresentada notrabalho de Baldassin et al (2009), descrito na seo anterior.As aplicaes baseadas em locks foram implementadas como um tpicomecanismo de spinlock. Foi substitudo as marcaes de transaes pelasoperaes de aquisio e liberao do lock global, pois o benchmark utilizadono prove uma verso baseada em locks para as aplicaes.Os experimentos foram realizados em dois cenrios, em relao implementaobaseada em locks. No primeiro cenrio, no foram contabilizados os ciclose energia desperdiados devido a espera ocupada. No segundo, os ciclos eenergia gastos na espera ocupada foram contabilizados, atravs de penalidadesem ciclos (variando de 1k a 10k ciclos) quando o bloqueio no pode ser adquiridoprontamente.Algumas afirmaes podem ser feitas com base nos resultados obtidos. Noprimeiro cenrio, a abordagem utilizando-se de locks superou a STM em energia47e desempenho, em praticamente todas aplicaes. No entanto, para algumasaplicaes, a STM mostrou-se competitiva em termos de energia e desempenho,em especial para aplicaes com taxas de conflitos baixa. Em aplicaes comaltas taxas de conflitos, a utilizao de STM foi em mdia 3x mais ineficienteem relao aos locks, chegando cerca de 22x em uma aplicao especfica. Nosegundo cenrio, de modo geral, o desempenho da STM mostrou-se inferior emrelao utilizao de locks, no entanto, a diferena entre o desempenho deambas abordagens poderia ser reduzido quando incorrer penalidades altas parao mecanismo de locks. Alm disso, demonstrou-se que para algumas aplicaestransacionais, com baixas taxas de conflito, a utilizao de STM pode se tornaratraente dependendo dos custos relacionados as penalidades dos locks. Noentanto, para aplicaes com alta conteno, a utilizao de locks mostra-se amelhor abordagem, mesmo que elevadas penalidades sejam impostas.4.7 Avaliao de consumo de energia e desempenho de HTMem sistemas embarcados multiprocessadosO trabalho de Kunz (2010) avalia o consumo de energia e desempenhodo modelo LogTM em comparao ao mecanismo de locks, em um sistemaembarcado multiprocessado. Alm disso, avalia o desempenho e consumo deenergia de diferentes polticas de gerenciadores de conteno.A interconexo entre os ncleos de processamento foi baseada em uma arquiteturade rede chamada NoC (Network on Chip), sendo esta, uma alternativaas interconexes tradicionais como barramentos e chaves crossbar (BENINI;DE MICHELI, 2002) (BJERREGAARD; MAHADEVAN, 2006). Uma NoC umaestrutura de comunicao formada por diversos roteadores conectados entresi de acordo com determinada topologia. Cada roteador associado a algumelemento do conjunto da rede (processadores, memrias, entre outros). As NoCspermitem elevado grau de paralelismo na comunicao, pois os links da redepodem operar de modo simultneo sobre diferentes pacotes de dados. Apesardas solues tradicionais (barramentos e crossbar) apresentarem vantagens emtermos de simplicidade, compatibilidade e latncia, os limites fsicos impostospelo fio, questes relacionadas a escalabilidade e largura de banda apontampara a NoC como a melhor alternativa para futuras geraes de processadoresmany-core (BJERREGAARD; MAHADEVAN, 2006).O sistema computacional utilizado na realizao dos testes utilizou-se de 2,4, 8, 16 e 32 processadores, todos operando sobre frequncia de 100 MHz.Os tamanhos de cache L1 usadas foram de 512, 1024, 2048 e 8192 bytes,sendo essas completamente associativas e baseadas no protocolo de coernciaMSI baseado em diretrio. A configurao da NoC baseada no roteamentoXY, chaveamento Wormhole, topologia Grade (mesh), arbitragem Round-robin efrequncia de operao de 100 MHz.A implementao e os experimentos realizados neste trabalho foram feitos naplataforma virtual SIMPLE (BARCELOS; BRIO; WAGNER, 2007). O consumode energia foi obtido levando-se em considerao a energia da rede, memrias,caches e processadores do sistema. A energia da NoC foi calculada atravs dabiblioteca Orion (WANG et al., 2002), enquanto que a energia das memrias edas caches foi calculada com a ferramenta Cacti (WILTON; JOUPPI, 1996).48Para os experimentos em aplicaes de baixa conteno, trs benchmarksforam utilizados: Multiplicao de Matrizes, Codificador JPEG e Estimao deMovimento. Para o cenrio de alta conteno, uma aplicao que utiliza de altademanda de sincronizao durante a maior parte de sua execuo foi testada,LeeTM (ANSARI et al., 2008). A aplicao LeeTM possui paralelismo intrnseco,no entanto, este paralelismo difcil de expressar utilizando-se do mecanismode locks. Para avaliar o comportamento do sistema para o caso em que noh paralelismo disponvel para as transaes, desenvolveu-se neste trabalhouma modificao do LeeTM para forar artificialmente a conteno. Com amodificao realizada, a quantidade de paralelismo que a TM pode explorar a mesma que a verso baseada em locks, o que permite analisar o overheadde performance e energia de cada mecanismo (TM e locks) para o pior caso emtermos de paralelismo desta aplicao. Esta aplicao LeeTM com inibio doparalelismo chamada de LeeTM-IP.Nos experimentos realizados para aplicaes de baixa conteno, o gerenciadorde conteno da memria transacional utilizada baseou-se na tcnica debackoff com valores fixos. O tempo de espera usado foi de 5000 ciclos (para2,4 e 8 processadores), 10000 ciclos (para 16 processadores) e 25000 (para32 processadores). Atravs dos resultados obtidos para o cenrio de baixaconteno, mostrou-se que na maioria dos casos para at 4 processadores, amemria transacional apresentou-se ligeiramente inferior em relao aos locks,em termos de desempenho. Na utilizao a partir de 6 processadores obteveseum aumento de performance da memria transacional medida que onmero de processadores aumentava, superando os locks em todos os casos,chegando a 30% no melhor caso. Em relao energia consumida, nastrs aplicaes e em todas configuraes testadas, a memria transacionalapresentou-se eficiente em comparao aos locks, apresentando redues deenergia em todos os casos. De maneira geral, os resultados de energia seguemos ganhos de performance medida que o nmero de processadores do sistemafoi aumentado, e, em muitos casos, os ganhos de energia ultrapassaram os dedesempenho, indicando que a potncia mdia tambm foi reduzida.No cenrio de alta conteno, como primeiro experimento, foi feita umaanlise para encontrar o valor timo para o tempo de espera de backoff(fixo, exponencial e linear randmico) para diferentes configuraes do sistema(nmero de processadores), utilizando-se da aplicao LeeTM. Para isso,encontrou-se o parmetro que d o menor tempo de execuo para cada polticade backoff de cada configurao do sistema.Como alternativa ao encontro da melhor heurstica para ajustar o tempo deespera de backoff, os autores propuseram uma nova estratgia de gerenciamentode conteno, chamada de Abort Handshake. A soluo proposta baseada em sinalizao entre transaes de forma que a transao abortadaseja notificada quando for seguro reiniciar para evitar que ocorra o mesmoconflito. De modo a exemplificar o funcionamento, quando a transao T1 abortaaps conflitar com a transao T0, T1 envia uma mensagem sinalizando seuaborto T0 e aguarda at receber o sinal de T0 notificando o momento desua re-execuo. T0 ento adiciona T1 em sua lista de transaes abortadas.Quando finalizar a execuo, T0 envia o sinal para T1 permitindo que ela reiniciea execuo. Afim de evitar situaes de deadlock, uma transao pode esperar49apenas por uma transao de maior prioridade. Alm disso, uma transaoque tenha abortado outra pode se abortada por uma terceira transao; umair notificar a outra aps o commit e assim sucessivamente.Esta soluo serializa por completo a execuo de duas transaes quandouma delas aborta ao permitir que esta reinicie apenas aps o commit da outra. uma soluo conservadora j que a transao que abortou pode ter trabalho paraexecutar de forma independente antes de solicitar o bloco conflitante novamente.Alm disso, possvel que a transao abortada nem mesmo solicite o blococonflitante novamente se a deciso de requisitar o bloco depender de dadosalterados por uma terceira transao neste meio tempo.Em seguida, realizou-se um experimento em ambiente de alta contenocomparando as aplicaes LeeTM e LeeTM-IP, utilizando locks, memria transacionalcom o mecanismo Abort Handshake e memria transacional comos valores timos para cada poltica de backoff (fixo, exponencial e linearrandmico). Como resultados deste experimento verificou-se que no houvevantagens em termos de desempenho e energia na verso das aplicaesutilizando locks, para mais de 4 processadores. Nenhuma das polticas debackoff pode ser escolhida como vencedora, pois todas tiveram resultadosparecidos e a melhor depende de cada caso. Em situaes de alta conteno,o backoff exponencial aumenta muito o tempo de espera das transaes,prejudicando significamente a performance e elevando o consumo de energia.O mecanismo Abort Handshake apresentou ganhos de performance e energiana maioria dos resultados, atingindo redues do tempo de execuo em20% e reduo de energia de 53%, se comparados com a melhor poltica debackoff em cada caso. Entretanto, para alguns casos, algumas peculiaridadespodem afetar o desempenho do Abort Handshake. Embora que, na utilizaode 2 processadores o mecanismo Abort Handshake foi inferior em termos deenergia e desempenho em relao a todas polticas de backoff, a partir de 4processadores, na maioria dos casos, o Abort Handshake apresentou ganhossignificativos de performance e energia. No entanto, observou-se que na maioriados resultados, reduziu-se drasticamente o desempenho e elevou-se o consumode energia do mecanismo Abort Handshake, em comparao a locks e amemria transacional com backoff, na utilizao de 32 processadores. Sendoento necessrio, em um estudo futuro, analisar a eficincia do mecanismo AbortHandshake utilizando-se mais de 32 processadores.4.8 Comparao entre implementaes de semforos e memriastransacionais em relao ao consumo de energiaO trabalho de Mittal e Nitin (2011) avalia o consumo de energia e taxa decache miss de semforos (spinlock e bloqueante) e memrias transacionais, namemria cache compartilhada.Utilizou-se de uma arquitetura computacional multicore, com 4 cores, cadaum com sua memria privada e duas memrias caches compartilhadas. A arquiteturafoi simulada com base no conjunto de ferramentas SimpleScalar (BURGER;AUSTIN, 1997). Trs benchmarks foram utilizados como aplicaesbases para os testes: rvores Rubro-Negras, Transformada Rpida de Fourier eSPLASH-2 (WOO et al., 1995).50De modo geral, os resultados obtidos nos testes realizados mostraramque a sincronizao por semforos bloqueantes obteve menos cache miss emcomparao spinlocks e transaes. Em termos de consumo de energia,memrias transacionais e semforos bloqueantes tm um consumo equivalente,porm muito eficiente em comparao spinlocks.Apesar de indicar que a sincronizao por semforos bloqueantes apresentamelhores taxas de cache miss em comparao spinlocks e transaes, eque em termos de energia se equipara memrias transacionais, o trabalhoapresenta alguns problemas que tornam seus resultados pouco convincentes.No descrito quais aplicaes do benchmark SPLASH-2 foram utilizadas,apenas utilizou-se de uma arquitetura computacional (4 cores), e no foiexplicitado o tipo de memria transacional usada.4.9 Observaes finaisEste Captulo apresentou as principais pesquisas que avaliam o consumode energia e/ou desempenho de aplicaes, relacionadas a mecanismos desincronizao em ambiente de memria compartilhada.Diferentes tcnicas e implementaes de mecanismos de sincronizaoforam avaliadas atravs dos oito trabalhos descritos anteriormente. Nesta perspectiva,as seguintes constataes podem ser feitas, com base nos resultadosobtidos. Observou-se que o nvel de conteno influencia consideravelmente odesempenho e consumo de energia das aplicaes. De modo geral, altas taxasde conteno incorrem em custos adicionais em termos de energia e penalidadesem desempenho nas memrias transacionais, devido a resoluo de conflito dastransaes conflitantes e suas re-execues. Para o cenrio de alta conteno,as estratgias utilizadas pelo gerenciador de conteno em transaes garantema efetivao de redues de custos adicionais de energia e penalidades nodesempenho. No entanto, verificou-se que no h um gerenciador de contenoideal a ser utilizado em todos os casos. Porm, a escolha ideal do gerenciadorde conteno varia conforme o nvel de conteno e plataforma de hardware.Em relao a comparao entre os mecanismos de sincronizao, asimplementaes de STM, de modo geral, apresentaram desempenho inferior emaior consumo de energia se comparadas a utilizao de locks, em cenriosde alta conteno. No entanto, em aplicaes com baixo nvel de conteno,as implementaes de STM mostraram-se competitivas, superando em desempenhoe eficincia energtica a sincronizao por locks, em muitos casos. Asimplementaes de HTM, por outro lado, mostraram-se eficientes tanto emcenrios de alta quanto baixa conteno, superando a abordagem locks emmuitas vezes em termos de eficincia energtica e desempenho, na maioria doscasos.5 CONCLUSES E TRABALHOS FUTUROSEste trabalho apresentou as principais caractersticas da programao paralelaem ambiente de memria compartilhada, e relacionou-se mecanismos desincronizao utilizados para garantir a integridade e consistncia da comunicaoentre execues concorrentes computao sustentvel, especificamente,visando-se a reduo do consumo de energia em sistemas computacionais.Mecanismos de sincronizao em ambiente de memria compartilhada tmsido tradicionalmente realizados atravs de mtodos baseados em bloqueios(locks) explcitos pelo programador. No entanto, esta abordagem de sincronizao propensa a erros, e pode apresentar instabilidade no sistema. MemriasTransacionais surgiram como uma alternativa sincronizao baseada em locks,visando suprir as dificuldades e limitaes encontradas no uso de locks. Nasmemrias transacionais, diferentemente da sincronizao por locks, o controlesobre a sincronizao feito automaticamente pelo sistema transacional, o quefacilita a programao, pois o programador apenas precisa definir quais seroos blocos de cdigo a serem executados pelo sistema transacional, e esteimplementa a sincronizao em baixo nvel.A principal contribuio deste trabalho foi analisar diversas pesquisas queavaliaram o consumo de energia e/ou desempenho sobre mecanismos desincronizao em memria compartilhada, focando-se especialmente em implementaesde memrias transacionais comparadas sincronizao baseada emlocks. Atravs desta anlise constatou-se que a sincronizao por memriastransacionais promissora, mostrando-se a melhor abordagem de sincronizaoem muitos casos. No entanto, verificou-se que a eficincia das memrias transacionaisvaria conforme sua implementao e o cenrio de execuo (alta e baixaconteno). As implementaes em hardware mostram-se eficientes na maioriados casos e cenrios, porm, a eficincia do desempenho e consumo de energiade memrias transacionais em software (STM) influenciada diretamente peloambiente de execuo. De modo geral, em cenrios de alta conteno, asimplementaes em software apresentam desempenho inferior e maior consumode energia se comparadas sincronizao baseada em locks. Para este tipode cenrio, as estratgias de gerenciamento de conteno so responsveispor garantir o progresso das transaes conflitantes e por efetivar redues depenalidades no desempenho e no consumo de energia. Apesar de terem semostrado inferiores em relao aos locks em cenrios de alta conteno, as STMmostram-se competitivas aos locks em aplicaes de baixa conteno, sendosuperiores em desempenho e eficincia energtica em muitos casos.Por se tratar de uma abstrao nova, memrias transacionais ainda so52essencialmente tema de pesquisa, e ainda h muito o que ser pesquisado paramelhor caracteriz-la.No encontrou-se na literatura pesquisas que avaliam o comportamento dememrias transacionais e outros mecanismos de sincronizao para ambientesde memria compartilhada em relao arquiteturas many-core. Tal avaliaosobre mecanismos de sincronizao seria de suma importncia, pois este tipode arquitetura tendncia para um futuro prximo.Embora existam diversas estratgias e pesquisas sobre gerenciamento deconteno, grande parte das pesquisas avaliam poucas estratgias sob ummesmo contexto, especialmente quando avalia-se o consumo de energia. Destaforma, a avaliao de vrias estratgias de gerenciamento de conteno sob omesmo contexto, em termos de consumo de energia e desempenho, seria degrande valia, visto que o gerenciador de conteno um componente essencialno contexto do sistema transacional.A maioria das avaliaes de memrias transacionais so baseadas embenchmarks ou at mesmo microbenchmarks. Dentre as pesquisas analisadaspor este trabalho, apenas uma entre as oito avaliou o comportamento dememrias transacionais em uma aplicao comercial. Portanto, a caracterizaode memrias transacionais em aplicaes no sintticas poderia ser avaliada emtrabalhos futuros, sendo esta anlise de grande importncia para o desenvolvimentoefetivo de sistemas comerciais baseados em memrias transacionais.53REFERNCIASAMDAHL, G. M. Validity of the single processor approach to achieving large scalecomputing capabilities. In: APRIL 18-20, 1967, SPRING JOINT COMPUTERCONFERENCE, 1967, New York, NY, USA. Proceedings. . . ACM, 1967. p.483485. (AFIPS 67 (Spring)).ANANIAN, C. S.; ASANOVIC, K.; KUSZMAUL, B.