Módulo II: Controle de Concorrência

(Aulas 1 e 7)

Clodis Boscarioli

Agenda:

� Introdução a Controle de Concorrência;� Protocolos baseados em Bloqueio;� Protocolos baseados em Timestamp;� Protocolos baseados em Validação;� Protocolos baseados em Validação;� Protocolos baseados em Granularidade Múltipla;� Esquemas de Multiversão;� Tratamento de Deadlocks.

Introdução� Uma das propriedades fundamentais de uma transação é o isolamento.

� Quando diversas transações são executadas de modo concorrente corre-se o risco de violar esta propriedade.

� É necessário que o sistema controle a interação entre transações � É necessário que o sistema controle a interação entre transações concorrentes: esse controle é alcançado por meio de uma série de mecanismos, os quais unidos, formam o controle de concorrência.

� A base dos esquemas de concorrência discutidos aqui tem por base a propriedade de serialização, ou seja, todos os esquemas devem garantir que a ordenação de processamento seja serializada.

� Por enquanto, assumir que os sistemas não incorrem em falhas.

Protocolos com Base em Bloqueio

� Uma das formas de garantir que apenas escalonamentos serializáveis sejam produzidos é obrigar que o acesso aos itens de dados seja feito de maneira mutuamente exclusiva:maneira mutuamente exclusiva:

� Enquanto uma transação acessa um item de dados, nenhuma outra transação pode modificá-lo.

� Para implementar isso pode-se usar o método de bloqueio (lock).

Bloqueios

1. Bloqueio compartilhado:

Se uma transação Ti obteve um bloqueio compartilhado (denotado por S) sobre o item de dado Q, então Ti pode ler, mas não escrever em Q.

2. Bloqueio exclusivo:

Se uma transação Ti obteve um bloqueio exclusivo (denotado por X) do item de dado Q, então Ti pode tanto ler como escrever em Q.

Toda transação precisa solicitar o bloqueio apropriado antes de executar qualquer operação sobre Q.

Esta solicitação é feita ao controlador de concorrência.

A transação só poderá executar qualquer operação sobre Qdepois que controlador de concorrência conceder (grants) o bloqueio do dado à transação.

Função de Compatibilidade de Bloqueios

� Seja A e B uma representação arbitrária dos modos de bloqueio. Suponha que uma transação Ti solicite um bloqueio do modo A sobre o item de dado Q, sobre o qual a transação Tj (Ti <> Tj) mantém um bloqueio do modo B.

� Se a transação Ti conseguir o bloqueio do modo A, mesmo com a existência do bloqueio de modo B, então dize-se que o modo A é compatível com o modo B.

� Observe a matriz comp. Um elemento comp(A,B) da matriz possui valor verdadeiro se, e somente se, o modo A é compatível com o modo B.

FalsoFalsoX

FalsoVerdadeiroS

XS

Bloqueios

� Uma transação solicita um bloqueio:� Compartilhado do item de dado Q executando a instrução lock-S(Q);� Exclusivo do item de dado Q executando a instrução lock-X(Q);

� Um item de dado pode ser desbloqueado via instrução unlock(Q).

� Uma transação pode desbloquear um item de dado a qualquer momento, mas deverá manter o bloqueio enquanto quiser operar sobre o dado.

Bloqueios

T1: lock-X(B);read(B);B := B – 50;write(B);

T2:lock-S(A);read(A);unlock(A);lock-S(B);write(B);

unlock(B);lock-X(A);read(A);A := A + 50;write(A);unlock(A);

lock-S(B);read(B);display (A + B);unlock(B);

Se A = 100 e B = 200, o valor mostrado em T2= 300.

BloqueiosT1 T2 Controle de concorrência

lock-X(B)

read(B) B := B – 50write(B);unlock(B)

lock-S(A)

read(A) unlock(A)

grant-X(B1, T1)

grant-S(A1,T2)

lock-X(A)

read(A) A := A + 50write(A) unlock(A)

unlock(A) lock-S(B)

read(B) display(A+B) unlock(B)

grant-S(B1,T2)

grant-X(A2,T1)

Bloqueios

� A escala de execução mostrada no slide anterior não é serializável em conflito e não é serializável em visão.

� A transação T2 mostra o valor 250 dólares.

� A forma como os bloqueios foram concedidos permitiu que este escalonamento fosse criado.escalonamento fosse criado.

� O controlador de concorrência pode impedir que escalonamentos errados sejam criados concedendo bloqueios de uma forma mais restrita.

� OBS.: A concessão do bloqueio, quando permitida, é feita entre o pedido de bloqueio e a execução da operação no item de dado. Assim, não serão explicitadas, nos escalonamentos, as operações de grant.

� Agora suponha que os desbloqueios sejam realizados no final das transações...

Bloqueios

T1: lock-X(B);read(B);B := B – 50;write(B);

T2:lock-S(A);read(A);lock-S(B);read(B);write(B);

lock-X(A);read(A);A := A + 50;write(A);unlock(B);unlock(A);

read(B);display (A + B);unlock(A);unlock(B);

Bloqueios

� Observe que não é possível, com as transações definidas desta forma, realizar um escalonamento como mostrado anteriormente.

T1 T2 Controle de concorrênciaT1 T2 Controle de concorrência

lock-X(B)

read(B) B := B – 50write(B);

lock-X(A)

lock-S(A)

read(A) lock-S(B)

grant-X(B1, T1)

grant-S(A1,T2)

Situação de deadlock.

Protocolos de bloqueio

� Exige-se que cada transação do sistema siga um determinado conjunto de regras, chamado de protocolo de bloqueio, indicando quando uma transação pode ou não bloquear ou desbloquear cada um dos itens de dados.

� Os protocolos de bloqueio restringem o número de escalas de execução possíveis.

� O conjunto de todas as escalas permitidas pelos protocolos de bloqueio forma um subconjunto de todas as escalas serializáveis possíveis.

Concessão de bloqueio

� Quando uma transação solicita bloqueio sobre um determinado item de dado em particular, e nenhuma outra transação mantém o mesmo item de dado bloqueado de modo conflitante, tal bloqueio pode ser concedido.

� Problema: � Suponha que a transação T2 tenha um bloqueio compartilhado sobre � Suponha que a transação T2 tenha um bloqueio compartilhado sobre um item de dado e a transação T1 solicite um bloqueio exclusivo do mesmo item.

� T1 terá que esperar até que o bloqueio compartilhado feito por T2 seja liberado.

� Enquanto isso, uma transação T3 pode solicitar o bloqueio compartilhado sobre o mesmo item de dado.

� O bloqueio pedido é compatível com o bloqueio concedido a T2, de modo que o bloqueio compartilhado pode ser concedido a T3.

� Nesta altura, T2 pode liberar o bloqueio, mas T1 terá que esperar até que T3 termine.

� Novamente, aparece uma transação T4 que ... ... ...� Logo, a transação T1 poderá nunca ser processada, sendo então chamada de starved (ou, em starvation – estagnada, em inanição).

Concessão de bloqueio

� Para evitar a inanição de transações ....�Quando uma transação Ti solicita o bloqueio do item de dados Q de um modo particular M, o bloqueio é concedido, contanto que:concedido, contanto que:

� Não haja nenhuma outra transação com bloqueio sobre Qcujo modo de bloqueio seja conflitante com M;

� Não haja nenhuma outra transação que esteja esperando um bloqueio sobre Q e que tenha feito sua solicitação de bloqueio antes de Ti.

Protocolo de bloqueio em duas fases

� Também conhecido como:� Two-phase locking protocol� Protocolo bi-fásico

� Protocolo que garante serialização.

� Este protocolo exige que cada transação emita suas solicitações de bloqueio e desbloqueio em duas fases:

1. Fase de expansão: uma transação pode obter bloqueios, mas não pode liberar nenhum.

2. Fase de encolhimento: uma transação pode liberar bloqueios, mas não consegue obter nenhum novo bloqueio.

Protocolo de bloqueio em duas fases

� As transações do slide 8 não têm duas fases.

� As transações do slide 11 têm duas fases.

� As instruções de bloqueio não precisam aparecer, necessariamente, no final da transação.necessariamente, no final da transação.

� Este protocolo garante serialização por conflito.

� ...

Protocolo de bloqueio em duas fases

� Considere qualquer transação.

� O ponto de escala no qual a transação obteve seu bloqueio final (o fim da fase de expansão) é chamado de ponto de bloqueio da transação.

� As transações podem ser ordenadas de acordo com � As transações podem ser ordenadas de acordo com seus pontos de bloqueio – essa ordenação é, de fato, uma ordenação serializada de transações.

� Este protocolo não garante a ausência de deadlock.

Algumas palavras sobre recuperação

� Se uma transação Ti falhar, por qualquer razão, é preciso desfazer seus efeitos para garantir a propriedade de atomicidade da transação. Em um sistema que permite execuções concorrentes, também é necessário assegurar que qualquer transação Tj que seja dependente de Ti (Tj leu dados escritos por Ti) também seja abortada.

� Escalas de execução recuperáveis: quando a transação que é dependente de outra não é efetivada antes que a outra o seja.

� Escalas sem Cascata: quando para cada par de transações Ti e Tj, Tjleia um item de dado previamente escrito por Ti se Ti já se efetivou.

Protocolo de bloqueio em duas fases

� Rollbacks em cascata podem ser evitados por uma modificação neste protocolo:

� Protocolo em duas fases severo: exige, em adição ao bloqueio feito em duas fases, que todos os bloqueios de modo exclusivo tomados por uma transação sejam mantidos até que a tomados por uma transação sejam mantidos até que a transação seja efetivada.

� Outra variante:

� Protocolo em duas fases rigoroso: exige que todos os bloqueio sejam mantidos até que a transação seja efetivada.

� Essas variantes são as mais usadas em implementações comerciais.

Upgrade de bloqueio

� Considere as transações:

� T8: read(A1), read(A2), ..., read(An), write(A1) � T9: read(A1), read(A2), display(A1+A2)

� Se o protocolo de bloqueio em duas fases for empregado, � Se o protocolo de bloqueio em duas fases for empregado, então T8 precisará bloquear A1 de modo exclusivo.

� Assim, qualquer execução concorrente de ambas as transações atinge uma execução serial.

� Entretanto, T8 precisa de um bloqueio exclusivo de A1 somente ao final de sua execução, quando ela escreve A1.

� Assim, se T8 estiver bloqueando A1 de modo compartilhado e depois mudar esse bloqueio para o modo exclusivo, poder-se-á obter mais concorrência.

Upgrade de bloqueio

� Conversão de bloqueio compartilhado para bloqueio exclusivo: upgrade

� Conversão de bloqueio exclusivo para bloqueio � Conversão de bloqueio exclusivo para bloqueio compartilhado: downgrade

� A promoção só pode acontecer durante a fase de expansão, e o rebaixamento só pode ocorrer durante a fase de encolhimento.

A implementação

� Quando uma transação Ti emite uma operação read(Q),o sistema emite uma instrução lock-S(Q) seguida de uma instrução read(Q).

� Quando Ti emite uma operação write(Q), o sistema verifica se Tiainda mantém um bloqueio compartilhado. Se ainda há, o sistema emite uma instrução upgrade(Q), seguida de uma instrução emite uma instrução upgrade(Q), seguida de uma instrução write(Q). De outro modo, o sistema emite uma instrução lock-X(Q), seguida de uma instrução write(Q).

� Todos os bloqueios obtidos por uma transação são desbloqueados depois da transação ser efetivada ou abortada.

Granularidade Múltipla

� Até agora, a referência a cada item de dado sempre foi como uma unidade à qual a sincronização é aplicada.

� Entretanto, diversos itens de dados podem ser tratados como uma unidade de sincronização individual.

Se uma transação precisa de todo o BD, pode aplicar o bloqueio (no � Se uma transação precisa de todo o BD, pode aplicar o bloqueio (no caso de um protocolo de bloqueio) a todo o BD, economizando na execução de código de atribuição de travas/bloqueios.

� O sistema pode implementar níveis múltiplos de granulação.� Define-se diversos tamanhos aos itens de dados e� Define-se uma hierarquia de granularidade a estes dados.

Granularidade Múltipla

DB

A1

FbFa

A2

FcFbFa

Ra1 Ra2 Ran Rb1 Rbk

Fc

Rc1 Rcn... ... ...

Quatro níveis:1. O banco de dados como um todo;2. Área: blocos que compõem o BD3. Arquivo: tabelas (nenhum arquivo está em mais de uma área) 4. Registros: dados (nenhuma tupla está em mais de um arquivo)

Bloqueios

� Cada nó da árvore pode ter bloqueio individual (exclusivo ou compartilhado).

� Quando uma transação bloqueia um nó, tanto no modo compartilhado como no modo exclusivo, a transação também bloqueará todos os descendentes daquele nó no mesmo modo de bloqueio.� Se uma transação bloqueia de forma explícita o arquivo Fc, no modo exclusivo, então ela está bloqueando de forma implícita, no modo exclusivo, todos os registros pertencentes àquele arquivo.registros pertencentes àquele arquivo.

� Se Tj quiser bloquear o registro Rb6 do arquivo Fb, Tj precisará percorrer a árvore da raiz até o registro Rb6. Se algum nó do caminho estiver bloqueado de modo incompatível, então Tj precisará esperar.

� Suponha que a transação Tk queira bloquear todo o banco de dados. Para isso, ela precisa simplesmente bloquear a raiz da árvore. Entretanto, Tk não deve conseguir o bloqueio, já que Ti já está bloqueando parte da árvore.

� Inviabilidade.

Bloqueio Intencional

� Bloqueios intencionais serão feitos em todos os antecessores do nó antes que ele seja bloqueado de forma explícita.

� Assim uma transação não precisará pesquisar a árvore inteira (ou sub-árvore) se quiser bloquear um nó. Basta iniciar o percurso e verificar se existem bloqueios intencionais. Se existir, significa que verificar se existem bloqueios intencionais. Se existir, significa que itens de granularidade mais fina estão bloqueados.

� Neste caminho, enquanto os bloqueios intencionais não são encontrados, a transação vai deixando seus bloqueios intencionais.

Bloqueio Intencional

� Bloqueio intencional associado ao modo compartilhado.� Bloqueio intencional associado ao modo exclusivo.� Bloqueio compartilhado e intencional exclusivo.� Função de compatibilidade:

XSIXSIXIS

FFFFFX

FFFFVSIX

FFVFVS

FFFVVIX

FVVVVIS

XSIXSIXIS

Protocolo de Bloqueio de Granularidade Múltipla

� Garante serialização.

� Cada transação Ti pode bloquear um nó Q, usando as seguintes regras:

� A função de compatibilidade de bloqueio precisa ser observada;� A função de compatibilidade de bloqueio precisa ser observada;� A raiz da árvore precisa ser bloqueada primeiro e pode ser bloqueada em qualquer modo;

� Um nó Q pode ser bloqueado por Ti no modo S ou IS somente se o seu pai for bloqueado por Ti no modo IX ou IS.

� Um nó Q pode ser bloqueado por Ti no modo X, SIX ou IX somente se o seu pai estiver bloqueado por Ti no modo IX ou no modo SIX.

� Ti pode bloquear um nó somente se ele não desbloqueou outro nó anteriormente (isto é, Ti tem duas fases)

� Ti pode desbloquear um nó Q somente se nenhum dos filhos de Qestiver bloqueado por Ti.

Granularidade Múltipla

� Este protocolo exige que os bloqueios sejam feitos de cima para baixo e exige que as liberações sejam feitas de baixo par cima.

� Exemplo (considera a árvore do slide 25):

� Suponha que a transação T1 leia o registro Ra2 do arquivo Fa. T1 precisa bloquear o banco de dados, a área A1, o arquivo Fa no modo IS e, bloquear o banco de dados, a área A1, o arquivo Fa no modo IS e, finalmente, bloquear Ra2 no modo S.

� Suponha que a transação T2 altere o registro Ra9 do arquivo Fa. T2precisa bloquear o banco de dados, a área A1, o arquivo Fa no modo IXe, finalmente, bloquear Ra9 no modo X.

� Suponha que a transação T3 leia todos os registros do arquivo Fa. T3precisa bloquear o banco de dados e a área A1 no modo IS e, finalmente bloquear Fa no modo S.

� Suponha que a transação T4 leia todo o BD. Então, poderá fazê-lo depois e bloquear o BD no modo S.

� T1, T3 e T4 podem manter acesso ao BD concorrentemente.� T2 pode concorrer com T1, mas não com T3 nem com T4.

Granularidade Múltipla

� Esse protocolo aumenta a concorrência e reduz o overhead por bloqueios.

� Útil para aplicações com:� Transações curtas que mantêm acesso a poucos itens de � Transações curtas que mantêm acesso a poucos itens de dados;

� Transações longas que produzem relatório a partir de um arquivo ou de um conjunto de arquivos.

� O deadlock pode ocorrer.

Ordenamento por Timestamp

� Garante seriabilidade:� Envolve o uso de timestamp para ordenar a execução das transações de forma que o escalonamento formado seja equivalente ao escalonamento serial.

� Timestamp: identificador único criado pelo SGBD para identificar uma transação. São associados na ordem em identificar uma transação. São associados na ordem em que as transações são submetidas ao sistema.

� TS(T) = timestamp da transação T.

� No escalonamento as transações tomam a ordem de seus timestamps

� Se TS(Ti) < TS(Tj), o sistema garante que o escalonamento produzido é equivalente ao escalonamento serial <Ti Tj>.

Algoritmo Básico

� Associa dois timestamps a cada item de dados X:

– Read_TS(X): o timestamp de leitura de X é o maior entre todos os timestamps de transações que leram X com sucesso;sucesso;

– Write_TS(X): o timestamp de escrita de X é o maior entre todos os timestamps de transações que escreveram Xcom sucesso;

Esses timestamps são atualizados sempre que uma instrução read(X) ou write(X) é executada.

Assegura que as operações de leitura e escrita sejam executadas por ordem de timestamp.

Algoritmo Básico

Situação 1: a transação T requer uma operação de leitura.

– Se TS(T) < Write_TS(X), então T quer ler o valor de X que já foi sobrescrito por uma transação

Exemplo

de X que já foi sobrescrito por uma transação mais nova. Assim, a operação read é rejeitada e T é desfeita.

– Se TS(T) >= Write_TS(X), a transação que requer o dado é mais nova que a última que o escreveu. Assim, a operação read é executada e o Read_TS(X) recebe o maior valor entre o atual e o TS(T).

Algoritmo Básico

Situação 2: A transação T requer uma operação de escrita

Exemplo

a. Se TS(T) < Read_TS(X), a transação é mais velha que a última transação que leu, ou seja, o valor de X que T está produzindo seria necessário antes. A operação de write é rejeitada e T é desfeita.

Algoritmo Básico

b. Se TS(T) < Write_TS(X) então T está tentando escrever um valor obsoleto em X. Logo, essa operação é rejeitada e T é desfeita.

Exemplo

desfeita.

c. De outro modo, a operação write é executada e o Write_TS(X) é atualizado como TS(T).

Observações

� O algoritmo básico de ordenamento por timestamp checa se duas operações conflitantes ocorrem na ordem incorreta. Se sim, rejeita a última das duas operações abortando a última das duas operações abortando a transação que errou.

� Garantia da seriabilidade por conflito.

Observações

� Toda vez que uma transação tenta ler ou escrever um item de dado, o algoritmo compara seu timestamp com o timestamp de leitura ou escrita de X.

� A intenção é assegurar que o ordenamento por � A intenção é assegurar que o ordenamento por timestamp não seja violado.

� Se o ordenamento por timestamp for violado, a transação será abortada.

Observações

� Uma transação abortada pode, mais tarde, ser novamente submetida ao sistema como uma nova transação, e com um novo timestamp.

� Se T é abortada e desfeita, qualquer transação que tenha usado um valor escrito por T deve ser desfeita também.

� Pode cair em starvation.

Exemplo

� T1Read(B)

Read(A)

� T2Read(B)

B := B -50

display(A+B) Write(B)

Read(A)

A := A + 50

Write(A)

display(A+B)

Exemplo

B := B - 50

Read(B)

Read(B)

T2T1

R (B) 0000

Op.W_TS(A) R_TS(A) W_TS(B) R_TS(B)

Read Write

TS_(T1) = 1 TS_(T2) = 2

display(A+B)

Write(A)

A := A+ 50

display(A+B)

Read(A)

Read(A)

Write(B)

2

W2(A) 2

R2(A) 1

R1(A) 2

W2(B) 2

R2(B) 1

R1(B) 0000

Regra de Thomas

� Modificação no algoritmo básico, que faz com que haja menos operações de escrita, aumentado as possibilidades de concorrência.

Alteração na regra 2:Alteração na regra 2:

Se Ts(T) < Write_TS(X), então T está tentando escrever um valor obsoleto para X. A operação de write pode ser ignorada.

� Deixa de garantir a seriabilidade em conflito.

Protocolos Baseados em Grafos

� Uma alternativa ao protocolo de duas fases; � Impõem uma ordenação parcial → sobre o conjunto D = {d1, d2 ,..., dn} de todos os itens de dados.

� Se di → dj então qualquer transação acessando di e djprecisam acessar d antes de acessar d .

i j i jprecisam acessar di antes de acessar dj.

� Implica que o conjunto D pode ser visto como um grafo acíclico direcionado, chamado grafo do banco de dados.

� O Protocolo de Árvore é um tipo simples de protocolo de grafo.

Protocolo em Árvore

� Somente bloqueios exclusivos são permitidos;� O primeiro bloqueio por Ti pode ser sobre qualquer item de dados.

� Subseqüentemente, um dado Q pode ser bloqueado por T somente se o pai de Q estiver atualmente bloqueado

Protocolo em Árvore

Ti somente se o pai de Q estiver atualmente bloqueado por Ti.

� Os itens de dados podem ser desbloqueados a qualquer tempo.

� Um item de dados que foi bloqueado e desbloqueado por Ti não pode ser novamente bloqueado por essa mesma transação.

� O protocolo em árvore garante serialização por conflito e assegura liberdade de deadlock.� Protocolo não garante facilidade de recuperação ou liberdade de reversão em cascata:

Protocolo em Árvore

liberdade de reversão em cascata: � Necessita introduzir dependência de commit para garantir a recuperação.

� A transação pode ter que bloquear itens de dados que ela não acessa.

� Introduz overhead de bloqueio e, adicionalmente, tempo de espera adicional, com uma potencial diminuição na concorrência.

Protocolos baseados em Validação

� A execução da transação Ti é feita em 3 fases:1. Fase de Leitura e Execução: Ti escreve apenas em variáveis temporárias locais, sem alteração no banco de dados real.2. Fase de Validação: Ti faz um “teste de validação” para determinar se variáveis locais podem ser escritas sem violar a serialização.determinar se variáveis locais podem ser escritas sem violar a serialização.3. Fase de Escrita: Se Ti for válida, as gravações são aplicadas no BD, caso contrário, Ti é revertida.

� As três fases podem ser intercaladas com outras transações concorrentes, mas em cada transação devem ocorrer nessa ordem.

� Esse protocolo também é chamado de controle de concorrência otimista, pois baseia-se no fato de que não haverá problemas na execução da transação.

� Cada transação Ti tem 3 timestamps:− Start(Ti): início da transação;− Validation(Ti): momento em que Ti entra na fase de validação;

Protocolos baseados em Validação

− Finish(Ti): momento em que Ti conclui fase de escrita.� A ordem de serialização é dada pelo momento de validação. TS(Ti) = Validation(Ti).

� Este protocolo aumenta o grau de concorrência se a probabilidade de conflitos for baixa. Isto se dá porque a ordem de serialização não é pré-definida e, relativamente, poucas transações terão que ser desfeitas.

Protocolos baseados em Validação

� Se para todas as Ti com TS (Ti) < TS (Tj) alguma das condições abaixo se mantém:1. Finish(Ti) < Start(Tj)2. Start(Tj) < Finish(Ti) < Validation(Tj) e o conjunto de itens de dados escrito por Ti não possui interseção com os dados lidos por T .dados escrito por Ti não possui interseção com os dados lidos por Tj.então a validação termina com sucesso e Tj pode ser efetivada. Caso contrário, a validação falha e Tj é abortada.

� Justificativa: Ou a 1ª condição é satisfeita e não há execução concorrente, ou a 2ª condição é satisfeita e:� as escritas de Tj não afetam as leituras de Ti pois ocorrem após Ti terminar suas

leituras.

� as escritas de Ti não afetam as leituras de Tj já que Tj não lê nenhum item escrito por Ti.

Esquema de Multiversão

� Os esquemas de controle de concorrência por bloqueio ou por timestamp garantem a serialização atrasando a operação ou abortando a transação responsável por tal operação.

� Essas dificuldades podem ser evitadas se o sistema providenciar cópias de cada item de dado.

� Em um sistema de banco de dados multiversão, cada operação write(Q) cria uma nova versão de Q. Quando é emitida uma operação read(Q), o sistema seleciona uma das versões de Q para ser lida.

� O esquema de controle de concorrência precisa garantir que a seleção da versão lida seja tal que assegure a serialização.

� Por razões de desempenho, uma transação precisa determinar de forma fácil e rápida qual a versão do item de dados que deverá ser utilizada.

Multiversão com Ordenação por Timestamp

� A cada transação Ti do sistema é associado um timestamp único e estático, denotado por TS(Ti) (associado antes do início da execução da transação).

� Para cada item de dado Q, uma seqüência de versões <Q1, Q2, ..., Q > é associada. Cada versão Q contém três campos:

1 2Qn> é associada. Cada versão Qk contém três campos:� Content: é o valor da versão Qk;� W-timestamp(Qk): é o timestamp da transação que criou a versão Qk.� R-timestamp(Qk): é o timestamp mais alto de alguma transação que tenha lido a versão Qk com sucesso.

Multiversão com Ordenação por Timestamp

� Uma transação Ti cria uma nova versão Qk do item de dado Q emitindo uma operação write(Q).

� O campo conteúdo da versão mantém o valor escrito por T . Ti.

� O W-timestamp e o R-timestamp são inicializados por TS(Ti).

� O valor de R-timestamp é atualizado sempre que uma transação Tj lê o conteúdo de Qk e R-timestamp(Qk) <TS(Tj).

Esquema:

� Suponha que uma transação Ti emita uma operação read(Q) ou write(Q). Seja Qk a versão de Q cujo timestamp de escrita é o mais alto timestamp, menor ou igual a TS(Ti).

� Se a transação T emitir um read(Q), então o valor recebido será � Se a transação Ti emitir um read(Q), então o valor recebido será o conteúdo da versão Qk.

� Se a transação Ti emitir um write(Q) e Ts(Ti) < R-timestamp(Qk), então a transação Ti será desfeita. De outro modo, se TS(Ti) = W-timestamp(Qk) o conteúdo de Qk é sobreposto; caso contrário, outra versão de Q é criada.

Esquema:

� As versões que não forem mais necessárias serão removidas conforme a regra seguinte:

� Suponha que haja duas versões, Qk e Qj de um item � Suponha que haja duas versões, Qk e Qj de um item de dados Q e que ambas as versões tenham o W-timestamp menor que o timestamp da última transação do sistema. Então, a mais antiga entre as versões Qk e Qj não será usada novamente e pode ser eliminada.

Vantagens e Desvantagens

� Vantagem:�Garante que uma solicitação de leitura nunca falhe e nunca espere.

� Desvantagem:� A leitura de um item de dados exige também a atualização do campo R-timestamp, resultando em dois acessos ao disco ao invés de apenas um.

�Os conflitos entre as transações são resolvidos por rollback, em vez da imposição do tempo de espera.

Multiversão com Bloqueio em Duas Fases

� Tenta combinar as vantagens do controle de concorrência multiversão com as vantagens do bloqueio em duas fases.

� Neste esquema:

� As transações de atualização executam um bloqueio em duas � As transações de atualização executam um bloqueio em duas fases rigoroso (mantêm todos os bloqueios até o final da transação).

� Cada item de dado possui um único timestamp, baseado em um contador, chamado ts-counter, o qual é incrementado durante o processo.

Esquema:� Marca-se os timestamps das transações somente de leitura por meio do valor corrente do contador (lendo o valor de ts-counter antes de começar a execução).

� Para leitura, esse esquema segue o protocolo de multiversão ordenada por timestamp.

� Quando uma transação Ti (somente leitura) emite um read(Q), o valor recebido é o conteúdo da versão cujo timestamp é o inferior a TS(Ti) mais próximo.

imais próximo.

� Quando uma transação de atualização lê um item de dados, ela impõe um bloqueio compartilhado ao item, e lê a sua última versão.

� Quando uma transação de atualização deseja escrever um item de dados, ela primeiro consegue o bloqueio exclusivo sobre esse item, e então, cria uma nova versão do item de dado.

� A escrita é realizada a partir da nova versão e o timestamp da nova versão recebe ∞ como valor inicial, que é maior que qualquer outro timestamp possível.

Esquema:� Quando uma transação de atualização Ti completa suas ações, ela realiza o processo de efetivação da seguinte forma:

� Ti adiciona 1 ao valor de ts-counter e transfere esse valor aos timestamps de todas as versões que criou;

� Ti adiciona 1 ao valor de ts-counter.

� Somente uma transação de atualização por vez pode realizar o processo de efetivação.de efetivação.

� Como conseqüência, as transações somente de leitura que começarem depois de Ti incrementar o ts-counter acessarão o valor atualizado por Ti, enquanto aquelas que começarem antes do incremento de ts_counter, feito por Ti, verão o valor anterior à atualização de Ti. Neste caso, as transações somente de leitura jamais precisarão esperar por bloqueios.

� As versões são eliminadas de modo similar ao esquema de multiversão com ordenação por timestamp.

Manuseio de Deadlock� Um sistema está em estado de deadlock se há um conjunto de transações, tal que toda transação deste conjunto está esperando outra transação também contida nele.

� Seja o conjunto {T0, T1, ..., Tn}. T0 está esperando um item de dados mantido por T1, T1 está esperando por um item de dados mantido por T2, ..., Tn-1 está esperando um item de dado mantido por Tn e Tn está esperando um item de dados mantido por T0.0

� Existem dois métodos principais para tratamento de deadlock:

� Prevenção de deadlock: garante que o sistema nunca entrará em tal situação. Mais utilizado quando há alta probabilidade do sistema entrar em deadlock .

� Detecção e recuperação de deadlock: permite que o sistema entre em um estado de deadlock, para então recuperá-lo.

Prevenção

� Abordagem 1: Obriga que cada transação bloqueie todos os itens de dados antes de sua execução. Ou todos os itens de dados são bloqueados de uma vez ou nenhum o será.

� Desvantagens:

� Dificuldade em prever, antes da transação começar, quais itens de dados precisarão ser bloqueados (seria necessário o uso de um esquema de informação nas transações);

� A concorrência é bastante reduzida.

Prevenção

� Abordagem 2: Caracterizada pela preempção e rollback de transações.

� Na preempção, quando uma transação T2 solicita um bloqueio que está sendo mantido pela transação T1, o bloqueio concedido a T1 pode ser revisto por meio do roolback de T1, e concedido a T2.

� Para controlar esta preempção, considera-se um único timestamp para cada transação. Eles são usados para decidir se a transação pode esperar ou será revertida.

� O bloqueio continua sendo usado para controlar o concorrência.

� Se uma transação for revertida, ela manterá seu timestamp antigoquando for reiniciada.

Esquemas

� Esperar-morrer (wait-die):

� Tem por base uma técnica de não-preempção.

� Quando uma transação Ti solicita um item de dados mantido por Tj, Tipode esperar somente se possuir um timestamp menor do que T (isto

i j ipode esperar somente se possuir um timestamp menor do que Tj (isto é, Ti é mais antiga que Tj).

� Caso contrário, Ti será revertida (morta).

� Por exemplo, suponha que as transações T2, T3 e T4 tenham timestamps 5, 10 e 15, respectivamente. Se T4 solicita um item de dados mantido por T3, então, T4 será desfeita.

Esquemas

� Ferir-esperar (wound-wait):

� Tem por base a técnica da preempção e é uma contrapartida ao esquema esperar-morrer.

Quando uma transação T solicita um item de dado mantido � Quando uma transação Ti solicita um item de dado mantido por Tj, Ti poderá esperar somente se possuir um timestampmaior que Tj (ou seja, Ti é mais nova que Tj).

� Caso contrário, Tj será desfeita (Tj é ferida por Ti).

� Retornando ao exemplo anterior. Se T2 solicita um item de dados mantido por T3, então o item de dados será liberado de T3, e T3 será desfeita. Se T4 solicitar um item de dados mantido por T3, então T4 esperará.

Prevenção

� Ambos os esquemas da segunda abordagem evitam inanição.

� Diferenças entre os dois esquemas da segunda abordagem:

� No esquema esperar-morrer, a transação mais antiga precisará esperar até que a mais nova libere seus itens de dados. Assim, quanto mais antiga a transação, maior a possibilidade de esperar. Em contraste, no esquema ferir-esperar, a transação mais antiga nunca espera a mais esquema ferir-esperar, a transação mais antiga nunca espera a mais nova.

� No esquema esperar-morrer, se uma transação Ti morre e é desfeita porque solicitou um item de dados bloqueado por uma transação Tj, então Ti pode reemitir a mesma seqüência de solicitações quando for reiniciada. Se os itens de dados ainda estiverem bloqueados por Tj, então Ti morrerá novamente. Assim, Ti poderá morrer diversas vezes antes de conseguir o item de dados necessário. No esquema ferir-esperar, a transação Ti será ferida e revertida porque Tj solicitou um item de dados bloqueado por ela. Quando Ti reinicia e solicita o item de dados bloqueado por Tj, Ti esperará. Com isso, deve haver menos reversões.

Timeout

� Uma transação que tenha solicitado um bloqueio espera por ele por um determinado período de tempo.

� Se o bloqueio não for conseguido dentro desse intervalo, é dito que o tempo da transação está esgotado. Assim ela mesma se reverte e se reinicia.

� Se de fato estiver ocorrendo um deadlock, uma ou mais transações nele � Se de fato estiver ocorrendo um deadlock, uma ou mais transações nele envolvidas terão seu(s) tempo(s) esgotado(s) e se reverterá/reverterão, permitindo a continuação de outras.

� É fácil de ser implementado, trabalha bem se as transações forem curtas, e se longa esperas forem freqüentes em função de deadlocks.

� É difícil mensurar o tempo de espera.

� Não está livre da presença de inanição.

Detecção de Deadlock e Recuperação

� Um mecanismo que examina o estado do sistema é acionado periodicamente para determinar se um deadlock está ocorrendo. Se estiver, então precisa tentar recuperá-lo.

� Para isso ele precisa:

� Manter informações sobre alocação corrente dos itens de dados para transações, assim como qualquer solicitação de itens de dados pendentes;

� Proporcionar um algoritmo que use essas informações para determinar se o sistema entrou em estado de deadlock;

� Recuperar-se de um deadlock quando o algoritmo de detecção determinar que ele ocorreu.

Detecção

� Seja o grafo G = (V,E), em que V é um conjunto de vértices e E um conjunto de arestas.

� O conjunto de vértices consiste em todas as transações do sistema.

� Cada elemento do conjunto E de arestas é um par ordenado Ti �T . Se T � T está em E, então isto implica que a transação T está Tj. Se Ti � Tk está em E, então isto implica que a transação Ti está esperando que a transação Tk libere o item de dado que ela precisa.

� A inserção e remoção de arestas no grafo são feitas de acordo com a solicitação de um item bloqueado ou da liberação de um item bloqueado.

� Há deadlock no sistema se, e somente se, o grafo contiver um ciclo.

� Cada transação envolvida no ciclo está envolvida no deadlock.

Exemplo:

� A transação T1 está esperando as transações T2 e T3.� A transação T3 está esperando a transação T2.� A transação T2 está esperando a transação T4.

T1

T2

T3

T4

Exemplo:

� Suponha agora que T4 esteja solicitando um item bloqueado por T3.

T1

T2

T3

T4

Detecção

� Quando evocar o algoritmo de detecção?

� Depende da freqüência de ocorrência de deadlocks.� Depende de quantas transações serão afetadas por um deadlock.

� Se os deadlocks ocorrem com freqüência, então o algoritmo será � Se os deadlocks ocorrem com freqüência, então o algoritmo será evocado com mais freqüência.

� Na pior das hipóteses, a chamada ao algoritmo de detecção se dará sempre que uma solicitação de alocação não puder ser imediatamente atendida .

Recuperação� Reverter uma ou mais transações para quebrar o deadlock. Devem ser tomadas três ações:

� Selecionar uma vítima (ou vítimas) de acordo como mínimo custo:� A quanto tempo a transação está em processamento e quanto tempo será ainda necessário para que a tarefa seja completada;

� Quantos itens de dados a transação usou;Quantos itens ainda a transação usará até que se complete;� Quantos itens ainda a transação usará até que se complete;

� Quantas transações serão envolvidas no rollback.

� Rollback: Determinar até que ponto a transação deve ser revertida:� Reverter totalmente;� O suficiente para quebrar o deadlock (exige informações adicionais) .

� Inanição: Deve-se garantir que uma transação seja escolhida vítima somente um número finito e pequeno de vezes.

Operações de Inserção e Remoção

� Operações adicionais:

� delete(Q): remove o item de dado Q do banco de dados;� insert(Q): insere um novo item de dado Q em um banco de dados e lhe designa um valor inicial.

� Uma transação T que queira operar um read(Q) depois da remoção � Uma transação Ti que queira operar um read(Q) depois da remoção de Q resulta em erro lógico em Ti.

� Um transação Ti que pretenda realizar uma operação de read(Q) antes da inserção de Q, também resultará em um erro lógico em Ti.

� Também será um erro lógico tentar remover um item de dado inexistente.

Remoção

� Quando uma operação de remoção entra em conflito com outras?

� Se uma transação quiser ler o item que a outra removeu;� Se uma transação quiser escrever o que a outra removeu;� Se uma transação quiser remover o que a outra removeu;� Se uma transação quer remover e outra inserir:� Se uma transação quer remover e outra inserir:

� a remoção só pode ser feita se a inserção já ocorreu ou se o dado já existia e,

� a inserção só deve ocorrer se o dado não existe.

� Se o bloqueio em duas fases for usado, é preciso um bloqueio exclusivo sobre o item de dados antes que ele possa ser removido.

� Para o protocolo timestamp é preciso um controle similar ao usado para o write.

Inserção

� A inserção entra em conflito com a remoção, como já visto.

� Nenhum read ou write pode ser realizado sobre um item de dados antes que ele exista.de dados antes que ele exista.

� A inserção é tratada de modo similar à operação write.

Fontes Bibliográficas:

� Sistemas de Banco de Dados (Cap. 16). AbrahamSilberchatz, Henry F. Korth, S Sudarshan. 5ª Ed.Elsevier, 2006.

� Sistemas de Banco de Dados (Cap. 18). RamezElmasri e Sham Navathe. 4ª Ed. Pearson, 2005.Elmasri e Sham Navathe. 4ª Ed. Pearson, 2005.

Leitura Complementar:

� Controle de Concorrência e Distribuição de Dados:A teoria clássica, suas limitações e extensõesmodernas. João Eduardo Ferreira e Marcelo Finger.São Paulo: Escola Brasileira de Computação, 2001.