ࡱ> n;T{VQHP}jPNG  IHDRvE|TsRGB0PLTEMMMhhh|||< IDATxKoEϽ$9WHhz6d=?fa1,X=bfk+vH |خGoUGuzCAdEv] ]dEv1Dv]d7.v_z` ݹHGX?VٝdWlb#t^e ߦ\'l].Gju'`||}&abyD_@.ݍ#BrKgɾbs ?6=0y" c}. dE츠OMwp;ݓ-O{Owi>o_=q(=J~w"];|9; )2߰v'j9!ǐJnwwQ 2!$"˃[fI|(l/7.X>J~ש9BAme{EJ= Cp|ʎ)r,K8|=(wLen%Ţ[J]HDZ -vn(B)-gXfPz>vvT9{$EfݶŎ}! ;ƒͲ{]HN&n^ /L,}`z[dEv]dEv] ]dEv1Dv]d tّQT^N#.Cw&IW9@V׾aӎ[vX6بNفŶZ$06v&VQ0^Rv-_9c;,|m'ud' zdboR b yd}t"ᰫԑovŖN ]Ȯkq]~]j@5mݐl6 vGb̎Ev#`H]dgT&@p&J b߶9}G&0A r"J)m闵㬬"0д,E)F*١Eh~) VnT4O0ZI/7F+wڕr6e*eO5 W_l X;]c"亖\ PU߭~ eWY56[ۅb?CTDv-Rh]!t?Yd;9Z_vh#SW M#~ &͏]"(4v!D휳.S)CeJe0 @s.g5P;V;2x]s@H]uc4xϒɫM i*MB5?_4%&+XIl }StuFnNa'e ;x]ώ;rWk&>|MX _Cz`LqKj;3NCNΔ]}9aυkŊT(gqwZSY?viˊ|Q:wM.h-^ ;Z`Uk#=5(^ ybF.Jlߞ8R6(k K~ʇ呣eӱ*ťj֚]QGv*{F6h0ط XFPeDf~Bf2#8P pqv WW:bn'ȕJQv62zj/l͌Qy "=3(vUFv٭`Н]ՕX5r[w5hzqu#Vԗ<+MZ.+`⊄hS4Zequ#VQ쳫z\ŦyFv&zv`rXOv^t1CȎ _hCYr,%zHhcG!?Pvm yyӾQ{}qYyxveAojصb9fm3v>L-Y;lWY 9bjֳݰ;gwbZȚc.c)^Hc~vx[Ɯ=(i$u:0O,k]y`GsFEv-UmeGd'.-NEnˎjZ ']aZ*k#;PgC7+_-RȮ{b4oM] ݸx+AvcׯB)1PܛR=cۮtήWl_fc*\G ]X+cqPk1u|Dh4x}2_az0_k~E ]Ev]dEv]dCdEv]dCdEv] ]dEv]DEv]dC줯ⳏQ\m[?6t3YD>`K}0>v"|&cW._hW٩*U&.;V'[[Z>   TransacesExemplo de transaco:  transferir algum dinheiro da conta A para a conta B . Uma transaco tpica comea sempre com um comando begin-of-transaction (BOT), e acaba com um comando end-of-transaction (EOT). Um EOT muitas vezes precedido por um comando commit, o qual assegura que os efeitos da transaco so guardados permanentemente na base de dados. JeZ7_  Transaces. necessrio que a propriedade  tudo-ou-nada seja satisfeita mesmo na presena de falhas. Um requerimento para as aces atmicas a durabilidade. Durabilidade significa que se uma aco concluiu com sucesso (i.e., a aco  committed ), ento os seus efeitos nunca se perdem.$  TransacestTanto o acesso concorrente como as falhas podem violar a atomicidade. Para suportar aces atmicas, tm de ser fornecidos mecanismos para lidar com ambos. No contexto das bases de dados, os mtodos de sincronizao utilizados para lidar com acesso concorrente so chamados muitas vezes Protocolos de Controlo de Concorrncia. As tcnicas para preservar a atomicidade na presena de falhas so frequentemente chamadas  recovery protocols . BZ!(Z Atomicidade e SerializaoDefinimos uma transaco T como uma sequncia de n passos. T = ((T,ai,ei))ni=1, onde T o nome da transaco, ai a operao feita no passo i (uma operao ou R (read) ou W (write)), e ei a entidade de dados sobre a qual a operao feita.  .9 Atomicidade e SerializaoConsidere m transaces concorrentes T1, T2, & , Tm. Qualquer sequncia de operaes obtida por ordenamento das operaes das diferentes transaces chama-se  schedule . Numa  schedule , a ordem das operaes de uma transaco mantida. Uma  schedule representa uma execuo possvel de transaces, na qual operaes de processos diferentes podem alternar. zjZ 7Atomicidade e SerializaozUma  schedule chamada  serial schedule se todas as operaes de uma transaco ocorrerem em simultneo (i.e., contiguamente) na  schedule . Uma  serial schedule representa uma execuo em srie das transaces nas quais a execuo de uma nova transaco iniciada somente quando a execuo da transaco anterior tiver completado. Uma  serial schedule nunca ir levar a nenhuma inconsistncia, uma vez que uma nova transaco apenas comea quando a execuo da transaco prvia tiver completado e nunca nenhuma transaco v o estado interno de outra transaco. >P>Atomicidade e SerializaofO problema da consistncia ocorre quando a alternncia de operaes entre diferentes transaces permitida ( Non-serial schedules ).  Non-serial schedules tm o potencial de levar a coleco das entidades de dados para um estado inconsistente, mas tambm permitem acesso concorrente a dados partilhados. Atomicidade e Serializao|Critrio de serializao: Duas transaces no podem parecer concorrentes e o resultado de executar transaces diferentes deve ser como se as transaces fossem executadas em srie por uma dada ordem. Serializao significa que a  schedule de transaces deve ser tal que seja equivalente a uma  schedule em srie.6ttAtomicidade e SerializaoEquivalncia de  schedules : Numa  schedule S, definimos uma relao de dependncia DEP(S) como uma relao ternria T * E * T, onde T o conjunto de transaces e E o conjunto de entidades. Um valor (T1,e,T2) DEP(S) se para qualquer i < j: S = (& , (T1,ai,e), & , (T2,aj,e), & ) e no existe nenhum k tal que i < k < j e ek = e, e um de (ou os dois) ai ou aj uma operao de escrita. ,  M    Atomicidade e SerializaoA relao DEP captura a dependncia entre operaes de diferentes transaces. Uma operao depende de outra operao que tenha ocorrido anteriormente a ela se a operao anterior for sobre a mesma entidade que esta operao . Exemplo: Se (T1,e,T2) ento T1 pode ser escrever um valor em e, o qual ir ser lido mais tarde por T2. Desde que uma leitura anterior de uma entidade no afecte uma leitura posterior, no includa na definio de DEP. ZZ    % sAtomicidade e SerializaopDuas  schedules S1 e S2 so equivalentes se DEP(S1) = DEP(S2). Uma  schedule S serializvel se DEP(S) for a mesma que a DEP de outra  schedule em srie. Com transaces, requer-se que a  schedule seja serializvel. Se a  schedule de um conjunto de transaces serializvel, isso implica que cada transaco v o mesmo estado que veria numa outra qualquer execuo de transaces em srie. Desde que se assuma que a execuo em srie de transaces leva a um estado consistente do sistema, uma  schedule em srie tambm ir levar a um estado consistente. 9Z     Atomicidade e SerializaoPara uma  schedule em srie S : se (Ti,e1,Tj) DEP(S) para uma qualquer entidade e1, ento isso implica que (Tj,em,Ti) DEPS(S) para qualquer entidade em. Esta condio implica que podemos definir uma relao binria < sobre o conjunto de transaces, tal que Ti < Tj se (Ti,e1, Tj) DEP(S) para qualquer entidade e1. Desde que uma  shedule serializvel seja equivalente a uma  schedule em srie, isso implica que as condies tambm se mantm para uma  schedule serializvel. T!#!        l      Atomicidade e Serializao(Se a serializao for preservada, ento o estado da base de dados depois de executar um conjunto de transaces consistente. A serializao restringe essencialmente o conjunto de execues vlidas possveis sobre um subconjunto de todas as execues possveis numa execuo concorrente geral. Protocolos CommitfO objectivo do comando commit assegurar que todos os efeitos da transaco se reflectem na base de dados, e que eles nunca sero desfeitos no futuro. O  protocolo commit assegura essencialmente que o log redo da transaco escrito antes do commit. LOG: Dados do log so informao redundante, que guardada para ser restaurada caso haja falhas. REDO: Resultados de algumas das transaces completadas podem ainda no ter sido guardadas na altura da falha. Essas transaces tm de ser refeitas  redone , para que os seus efeitos apaream na base de dados.\Z]ZZZ]Protocolos CommitNum sistema distribudo, a situao mais complexa. Os dados esto distribudos por vrios ns. Cada n gere algumas entidades de dados, e apenas esse n pode aceder a essas entidades. Um processo (transaco) que queira fazer uma operao sobre uma entidade tem de pedir ao n que gere essa entidade para efectuar essa operao. Daqui, operaes diferentes de uma transaco podem ser efectuadas em ns diferentes. ZProtocolos CommitAo contrrio de um sistema centralizado, onde uma falha significa falha completa (i.e., nenhum dado est disponvel), num sistema distribudo, a falha de um n no pra toda a computao da transaco. Apenas as partes da transaco que eram para ser executadas no n que falhou so afectadas. Desde que uma transaco uma operao  tudo-ou-nada , se algumas partes da transaco no poderem ser efectuadas, ento todas as actividades da transaco tm de ser desfeitas para dar a parecer que nada foi feito pela transaco.ZProtocolos CommittNum sistema distribudo, possvel que um n possa  abortar a parte da transaco que est a ser efectuada nesse n. Esse aborto pode ocorrer devido falha de um n, ou por outra razo qualquer. Se isto acontecer, ento mesmo que os outros ns possam efectuar as suas partes da transaco, a transaco inteira tm de ser abortada. Apenas se todos os ns que fazem parte da transaco quiserem fazer commit, a transaco pode fazer commit.ZProtocolos CommitCPara assegurar isto, um protocolo commit necessrio. Um protocolo commit assegura que ou que toda a transaco faz commit, i.e., todos os ns que fazem parte da transaco fazem commit, ou toda a transaco aborta, i.e., todos os ns que fazem parte da transaco abortam. Chama-se a isto a propriedade do commit atmico.8DZ Protocolo Commit das Duas Fases*Neste trabalho, iremos assumir que existe um processo em cada n que participa na transaco que efectua as actividades da transaco nesse n (incluindo a execuo das actividades do protocolo commit). O mais simples e mais popular protocolo commit o protocolo commit das duas fases (2PC). Neste protocolo, o n onde a transaco iniciada (ou o processo a executar a transaco) chamado coordenador. Os outros ns (ou processos nesses ns) que participam na aco chamam-se participantes. O protocolo das duas fases um protocolo mestre-escravo .n+Z h J; Protocolo Commit das Duas FasesO protocolo funciona em duas fases. Na primeira fase: O coordenador envia uma mensagem  commit-request a todos os participantes. Cada participante envia ento o seu voto ao coordenador acerca da sua vontade para fazer commit. Se por uma qualquer razo um participante no consegue executar a sua parte da transaco localmente, ele envia uma mensagem NO (i.e., abort), seno envia uma mensagem SIM (i.e., commit). Isto reflecte a deciso local de cada nodo.<8m,8m,>Z!9!Protocolo Commit das Duas FasesNa segunda fase: O coordenador rene as respostas de todos os participantes. Se todas elas forem SIM (e a do prprio coordenador tambm for SIM), o coordenador envia uma mensagem COMMIT a todos os participantes. De outro modo, o coordenador decide abortar e envia uma mensagem ABORT a todos os participantes que votaram SIM (os que votaram NO j decidiram localmente abortar a transaco). Cada participante espera pela deciso do coordenador. Quando recebe a mensagem, age de acordo com ela.*_"Protocolo Commit das Duas FasesEste protocolo, tal como outros protocolos commit, pode ser modelado por um conjunto de autmatos finitos (FSA), com um FSA representando um estado. O FSA para o coordenador e para o participante no 2PC mostrado na figura seguinte. #Protocolo Commit das Duas Fases $ Protocolo Commit das Duas FasesjO estado de um FSA representa o estado do protocolo num n em particular. Uma transaco num FSA consiste em receber uma ou mais mensagens, (fazer alguma computao) e enviar zero ou mais mensagens. Estes FSA s so normalmente no deterministas, e tm dois estados finais possveis (representando os dois resultados possveis para um protocolo commit): o estado commit c, e o estado abort a. Nos FSA a para o 2PC, cada FSA tem 4 estados: um estado inicial (q), um estado wait (w), um estado abort (a) e um estado commit (c). Cada transio no FSA est marcada pelas condies nas mensagens recebidas (o  numerador ) que causam a transio, e as mensagens que o FSA envia (o  denominador ). Pr;      >T%!bProtocolo Commit das Duas Fases  Aces Timeout22&* O protocolo 2PC muito vulnervel a falhas. Em muitos estados do protocolo, um processo (participante ou o coordenador) est espera que algumas mensagens cheguem. Se as mensagens no chegarem devido a uma falha na rede ou falha de envio, os processos permanecero bloqueados. Para evitar isto, so adicionadas aces timeout ao protocolo. Quando o processo est espera de mensagens, ele move-se para outro estado se ocorrer um timeout. Nos FSA s dos processos, isto reflecte-se como transies timeout. BZ;>Bi=&"bProtocolo Commit das Duas Fases  Aces Timeout22&*Consideremos diferentes stios onde o processo est espera de uma mensagem, e acontecem falhas de transio. A primeira situao quando um participante se encontra no estado inicial q, onde est espera pela mensagem  request-commit . Desde que isto acontea antes do participante ter dado o seu voto ao coordenador, e desde que nesse estado cada participante possa decidir localmente fazer abort ou commit, se ocorrer um timeout, o participante pode decidir abortar, com segurana.@5>6'#bProtocolo Commit das Duas Fases  Aces Timeout22&** A segunda situao quando o coordenador est espera no estado w por votos dos participantes. Desde que nesse estado o coordenador ainda no tenha chegado a uma deciso final (e no tenha informado nenhum participante sobre ela), ele pode decidir abortar, com segurana, se ocorrer um timeout. 8bC!($bProtocolo Commit das Duas Fases  Aces Timeout22&*A ltima situao quando um participante termina e, depois de votar SIM, est espera no estado w pela deciso final do coordenador. Por agora assumimos que se isso acontece porque o coordenador falhou. Uma consequncia do 2PC que se um processo votou NO, ele sabe que a deciso final ser abortar, mas se votou SIM, no sabe qual ser a deciso final. Ao contrrio dos outros dois casos, neste caso o participante deve consultar os outros participantes par decidir o que fazer. @_c%_)%bProtocolo Commit das Duas Fases  Aces Timeout22&*As actividades que devem ser executadas para tomar a deciso so executadas por um protocolo de terminao. Um protocolo de terminao executado por um  stio quando a execuo continuada do protocolo commit no possvel devido falha de outros  stios . O objectivo de um protocolo de terminao assegurar que todos os  stios operacionais chegam ao mesmo estado final (commit ou abort). *S&*&bProtocolo Commit das Duas Fases  Aces Timeout22&*Um protocolo possvel : Quando um participante P termina no estado w, pergunta aos outros participantes sobre qual a deciso que eles receberam. Se existir um participante operacional Q que tenha recebido uma deciso commit (e tenha votado SIM), ou tenha votado NO (e depois saiba que a deciso final ser abortar), ele pode dizer ao processo P qual a deciso final acerca do commit da transio. No entanto, na situao em que o coordenador tenha falhado depois de apenas ter sido capaz de enviar a sua deciso a alguns dos participantes, se todos esses processos que tenham votado NO ou tenham recebido a deciso final do coordenador tambm tenham falhado, no h nada que P possa fazer a no ser esperar at que um processo, que conhea a deciso final, recupere. O 2PC est sujeito a bloqueios mesmo com a utilizao de transies timeout, mesmo que s ocorram falhas de  stio . PPvPtO[vJ++'rProtocolo Commit das Duas Fases  Recuperao (Recovery)::&0Vamos considerar o segundo aspecto das falhas de stio: um stio  falhado que est a recuperar. Assumimos que um stio guarda o seu estado corrente numa memria estvel. Assim recuper-lo pode determinar o estado em que falhou. Durante o perodo em que o stio esteve inoperacional, outros stios podem ter chegado a uma deciso  visando o commit . O estado recuperado tem de se assegurar que toma uma deciso que consistente com as decises dos outros. P,(rProtocolo Commit das Duas Fases  Recuperao (Recovery)::&0 claramente desejvel que o protocolo seja tal que o estado recuperado possa decidir o estado final, baseado no seu estado local. Isto d pelo nome de recuperao independente (independent recovery). Nem sempre possvel ter um protocolo que suporte recuperao indepente. $0L, K -)rProtocolo Commit das Duas Fases  Recuperao (Recovery)::&0No 2PC, vamos considerar a falha de um processo participante P: Se P falha no estado q, desde que ainda no tenha votado SIM, e desde que saibamos que um timeout, faz com que a deciso do coordenador seja abortar, devido sua falha, P pode abortar em segurana a transaco depois de recuperar. De modo similar, se P falhar depois de enviar uma mensagem ABORT, ele pode abortar em segurana. @J=QM.*rProtocolo Commit das Duas Fases  Recuperao (Recovery)::&0cNo entanto, se P falha no estado de espera w, depois da recuperao no pode decidir sozinho se faz abort ou commit, uma vez que a deciso final pode ter sido ou abort ou commit. Esta situao exactamente similar ao caso em que P apanha um timeout no estado w. Assim P pode chegar a uma deciso usando o protocolo de terminao discutido anteriormente. ndZV>d9Kk/+rProtocolo Commit das Duas Fases  Recuperao (Recovery)::&0O protocolo commit das duas fases requer um total de 3n mensagens na ausncia de falhas, se existirem n participantes no sistema. Existem algumas variaes do protocolo para reduzir a sobrecarga de mensagens. Por exemplo o protocolo presumed commit e o protocolo early prepare. 6 , &  ` 3333ff3` 3333f33ff3` "3333̙ff3` Kf3̙` &e̙3g3f` f333̙po7` ___f3̙;/f9` ff3Lm` ff3LmNLm>?" dd@*?nAd@q<nAqFLK#M n?" dd@   @@``PR    M`2p>> 1)(    H .R? ?" `} R ]%Clique para editar o estilo do ttulo&& \  H0R? ?" ` R nClique para editar os estilos de texto do modelo global Segundo nvel Terceiro nvel Quarto nvel Quinto nvel8  o   65R #" `] `} R `*    6;R #" ``  R X*    6M #" `] `} R X*    C @ABCDE FjJ@3"0`B  s *DjJ"0 `0H  0޽h ? ___f3̙;/f9___PPT10i.  +D=' k = @B + H1_Modelo de apresentao predefinido  @(    H|? ?"@  ]%Clique para editar o estilo do ttulo&&   H(? ?"   v>Faa clique para editar o estilo do subttulo do modelo global??   6̅ #" `] `}  `*    6đ #" `]}   X*    6 #" `] `}  X*    C @ABCDE F8c@3"@B  s *DjJ"  ,$0H  0޽h ? ___f3̙;/f9___PPT10i.  +ityD=' k = @B +0 P&(    01 P    P*    0     R*  d  c $ ?  2  00  0  nClique para editar os estilos de texto do modelo global Segundo nvel Terceiro nvel Quarto nvel Quinto nvel8   o  6HN _P   P*    6 _   R*  H  0޽h ? 3380___PPT10. 0 00(  x  c $@  x  c $p ;  H  0޽h ? 3380___PPT10. $  `$(  r  S \ `}   r  S C `  H  0޽h ? ___f3̙;/f980___PPT10. yw$  p $(   r  S  `}   r  S  `  H  0޽h ? ___f3̙;/f980___PPT10. $  $$(  $r $ S  `}   r $ S  `  H $ 0޽h ? ___f3̙;/f980___PPT10.d$  ($(  (r ( S M `}  M r ( S LM ` M H ( 0޽h ? ___f3̙;/f980___PPT10.Xɗ}  ,$(  ,r , S 8 `}   r , S  `  H , 0޽h ? ___f3̙;/f9___PPT10i.7p+D=' k = @B +}  0$(  0r 0 S   `}   r 0 S  `  H 0 0޽h ? ___f3̙;/f9___PPT10i.@ɳ+D=' k = @B +}  4$(  4r 4 S 4Z `}   r 4 S Z `  H 4 0޽h ? ___f3̙;/f9___PPT10i.Б6+D=' k = @B +}  8$(  8r 8 S Xb `}   r 8 S c `  H 8 0޽h ? ___f3̙;/f9___PPT10i. m+D=' k = @B +}  <$(  <r < S  `}   r < S  `  H < 0޽h ? ___f3̙;/f9___PPT10i.@Eu+D=' k = @B +}  @$(  @r @ S pSM `}  M r @ S GM ` M H @ 0޽h ? ___f3̙;/f9___PPT10i. +D=' k = @B +}  D$(  Dr D S  `}   r D S T `  H D 0޽h ? ___f3̙;/f9___PPT10i.P{d+D=' k = @B +}  H$(  Hr H S hM `}  M r H S hM ` M H H 0޽h ? ___f3̙;/f9___PPT10i.1+D=' k = @B +}   L$(  Lr L S <:J `}  J r L S J ` J H L 0޽h ? ___f3̙;/f9___PPT10i.Rw(+D=' k = @B +}  0P$(  Pr P S $  $(  r  S  `}   r  S  `  H  0޽h ? ___f3̙;/f980___PPT10.KC$  $(  r  S aR `}  R r  S PdR ` R H  0޽h ? ___f3̙;/f980___PPT10.rޡ 8p *4>HR\fpz+Wa>  J'S0\ "4 $9YOh+'0( hp   ( 4@H8Fiabilidade de Sistemas Informticos Aces Atmicas Lus Almeidae SEdgeAlm Paula Prata59lMicrosoft Office PowerPoint@_)2@p'7@`9j. Gg  =& &&#TNPP 2OMi & TNPP &&TNPP    --- !---&/&~w@ ww0- &Gy& &4t-̙-$ ?BB@@@??--&&-̙- $||--&--Y`-- @Garamond 7ww0- f3.=2 j$Fiabilidade de Sistemas Informticos           .@Garamond ww0- f3.2 DAces Atmicas))/.---- f3@Arialw@ :ww0- .*2 #Trabalho realizado por:    . .'2 QLus Almeida n 15101    .--"System 0-&TNPP &՜.+,0    On-screen Shown-sL6, 2Arial GaramondTimes New Roman WingdingsSymbol%1_Modelo de apresentao predefinido8Fiabilidade de Sistemas Informticos Aces AtmicasAces AtmicasAces AtmicasAces Atmicas e SerializaoAces Atmicas e SerializaoAces Atmicas e SerializaoAces Atmicas e Serializao Transaces Transaces Transaces Transaces TransacesAtomicidade e SerializaoAtomicidade e SerializaoAtomicidade e SerializaoAtomicidade e SerializaoAtomicidade e SerializaoAtomicidade e SerializaoAtomicidade e SerializaoAtomicidade e SerializaoAtomicidade e SerializaoAtomicidade e SerializaoProtocolos CommitProtocolos CommitProtocolos CommitProtocolos CommitProtocolos Commit Protocolo Commit das Duas Fases Protocolo Commit das Duas Fases Protocolo Commit das Duas Fases Protocolo Commit das Duas Fases Protocolo Commit das Duas Fases Protocolo Commit das Duas Fases2Protocolo Commit das Duas Fases Aces Timeout2Protocolo Commit das Duas Fases Aces Timeout2Protocolo Commit das Duas Fases Aces Timeout2Protocolo Commit das Duas Fases Aces Timeout2Protocolo Commit das Duas Fases Aces Timeout2Protocolo Commit das Duas Fases Aces Timeout:Protocolo Commit das Duas Fases Recuperao (Recovery):Protocolo Commit das Duas Fases Recuperao (Recovery):Protocolo Commit das Duas Fases Recuperao (Recovery):Protocolo Commit das Duas Fases Recuperao (Recovery):Protocolo Commit das Duas Fases Recuperao (Recovery)  Fonts UsedDesign Template Slide Titles,#_% Paula PrataPaula Prata  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root EntrydO)PicturesCurrent UserSummaryInformation(PowerPoint Document( %DocumentSummaryInformation8