Protocolos de Controle de Concorrência

Prévia do material em texto

Banco de Dados II 
Aula 04 
 
Protocolos utilizados para o controle de concorrência: 
• baseados em bloqueios: 
− 2PL 
− multigranularidade de bloqueios 
− protocolos baseados em grafos 
• sem bloqueios: 
− ordenação por marcador de tempo 
 
 
1. Multigranularidade de bloqueios 
 
Visa a redução do número de bloqueios sendo mantidos, a cada momento, na tabela de 
bloqueios. 
• Inicialmente, cada item de dado era tratado individualmente, como uma unidade, 
na qual a sincronização era executada; 
• Em alguns casos é necessário agrupar diversos itens de dados a fim de tratá-los 
como uma unidade de sincronização individual: 
• Exemplo: Quando uma transação precisa utilizar o banco de dados inteiro. 
Neste caso, é mais fácil e rápido bloquear todo banco de dados que cada 
item individualmente. 
 
 - Mecanismos utilizados: 
• definir múltiplos níveis de granularidade; 
• subdividir o banco de dados em níveis para construir uma hierarquia; 
 
Representação em forma de árvore: 
 
 
 
 
 
 
 
 
 
 
 
 
 
- Tipos de Bloqueios: 
• Protocolo de Bloqueio de Duas Fases; 
itens de 
dados 
registros 
BD 
arquivo 
itens de 
dados 
registros 
arquivo 
nível de maior granularidade 
nível de menor granularidade 
• Bloqueio Partilhado (S); 
• Bloqueio Exclusivo (X). 
• Cada nodo é bloqueado individualmente; 
• Quando um nodo é bloqueado explicitamente, todos os descendentes deste nodo 
são bloqueados implicitamente (automático). 
 
- Problemas: 
• Questão (?): Uma transação precisa bloquear banco de dados inteiro. 
Implicitamente, toda o restante da árvore é também bloqueado. Mas, se existir um 
bloqueio no meio da hierarquia por outra transação? 
• Solução 1: pesquisar toda árvore antes de realizar as operações de 
bloqueio (perda de desempenho); 
• Solução 2: Bloqueio de Intenção. 
 
- Bloqueio de INTENÇÃO: 
Para evitar conflitos de aceso em granularidades diferentes 
• Significado: um bloqueio de intenção sinaliza que existe um bloqueio explícito em 
um nível inferior da hierarquia; 
• Finalidade: a transação não precisa percorrer a árvore inteira para verificar a 
existência de bloqueio; 
• Os bloqueios de intenção são colocados em todos os ancestrais de um nodo, 
implicitamente pelo sistema; 
• Modos de Bloqueio de Intenção: 
• Intenção Partilhado (IS): indica que existe um bloqueio explícito, no nível 
mais baixo da árvore, no modo partilhado; 
• Intenção Exclusivo (IX): indica que existe um bloqueio explícito, no nível 
mais baixo da árvore, no modo exclusivo ou partilhado; 
• Intenção Partilhado e Exclusivo (SIX): indica que existe uma subárvore 
com bloqueio partilhado e um dos níveis inferiores com bloqueios 
exclusivos; 
 
Cada vez que um bloqueio sobre um dado for solicitado, o scheduler consulta a tabela 
de compatibilidades: 
 
bloqueio tipo atual de bloqueio 
solicitado ls lx is ix six 
ls y n y n n 
lx n n n n n 
is y n y y y 
ix n n y y n 
six n n y n n 
 
- Regras do Protocolo de Granularidade Múltipla: 
1. As funções de compatibilidade da tabela devem ser observadas; 
2. A raiz da árvore precisa ser bloqueada primeiro, entretanto, pode ser 
desbloqueada em qualquer modo; 
3. Uma transação pode bloquear um nodo no modo S ou IS somente se os 
ascendentes estiverem bloqueados pela mesma transação nos modos IX ou IS; 
4. Uma transação pode bloquear um nodo no modo X, SIX ou IX somente se os 
ascendentes estiverem bloqueados pela mesma transação nos modos IX ou IS; 
5. As regras do protocolo de Bloqueio de Duas Fases devem ser seguidas – uma 
transação só pode realizar bloqueios enquanto não realiza nenhum desbloqueio; 
6. Um nodo pode ser desbloqueado somente se seus descendentes já foram 
desbloqueados anteriormente; 
• Bloqueios: sentido TOP-DOWN ( ò ) - raiz para as folhas (primeiro bloqueios 
de intenção, depois bloqueios); 
• Desbloqueios : sentido BOTTOM-UP (ñ ) - folhas para raiz (primeiro 
bloqueios, depois bloqueios de intenção). 
 
- Conclusões: 
• aumento de concorrência; 
• reduz sobrecarga de bloqueios. 
- Utilidades: 
• transações pequenas que utilizam poucos itens de dados; 
• transações longas que produzem relatórios de um arquivo inteiro ou de um 
conjunto de arquivos. 
- Comentários: 
• garante a serializabilidade, pois realiza bloqueios nos itens conflitantes; 
• não evita impasses. 
 
 
2. Protocolo de bloqueios baseado em grafos (árvore) 
Pode-se usar protocolos de bloqueio que não sejam de duas fases, mas é necessário ler 
informações adicionais sobre como cada transação acessará o BD. 
� Armazenamento de informações adicionais: conhecimento da ordem de acesso 
dos itens de dados no banco de dados (construção de um grafo de acesso) 
� Modo de bloqueio: Exclusivo (X). 
 
CRITÉRIOS: 
� O primeiro bloqueio de Ti pode ser em qualquer item de dado. 
� Em seguida, um item de dado A pode ser bloqueado por Ti apenas se o pai de A estiver 
bloqueado corretamente por Ti. 
� Itens de dados podem ser desbloqueados a qualquer instante. 
� Um item de dado que tenha sido bloqueado e desbloqueado por Ti não pode ser 
novamente bloqueado por Ti. 
 
T1: lx(B), lx(E), ux(E), lx(D), ux(B), lx(G), ux(D), ux(G) 
T2: lx(D), lx(H), ux(D), lx(J), ux(J), ux(H) 
T3: lx(B), lx(E), ux(E), ux(B) 
T4: lx(D), lx(H), ux(D), ux(H) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Exercício: 
 
- A seguinte execução é possível, sob o controle de um protocolo baseado em grafos? 
H = lx1(B) lx4(D) lx4(H) ux4(D) lx1(E) ux1(E) lx1(D) ux4(H) ux1(B) lx1(G) ux1(D) 
ux1(G) 
 
 
3. Ordenação por marcador de tempo ("timestamps"- TS) 
 
Realiza ordenação das transações para que as operações conflitantes apareçam 
serializáveis: o sistema associa a cada transação Ti, antes dela iniciar sua execução, um 
marcador de tempo (TS[Ti]); 
� se TS1 < TS2 então T1 → T2 
 
� Exemplo: Se uma transação Ti tem designado o marcador de tempo TS(Ti) e uma nova 
transação Tj entrar no sistema, então TS(Ti) < TS(Tj) 
 
� Existem dois métodos para implantar este esquema: 
� Relógio do Sistema; 
� Contador Cronológico. 
 
� Implantação: para cada item de dado (x) são associados dois marcadores de tempo: 
� W-TS(x): representa o maior marcador de tempo de qualquer transação que 
executa write(x) com sucesso; 
J 
I HG
F E D
C 
A 
B 
� R-TS(x): representa o maior marcador de tempo de qualquer transação que 
executa read(x) com sucesso; 
Esses TS são atualizados com a execução de operações read e write. 
 
- A ordenação por marcador de tempo assegura que qualquer operação read e write 
conflitante seja executada na ordem do marcador de tempo. 
 
- Regras de ordenação do marcador de tempo: 
� Operações de Leitura em Ti: 
� Se TS(Ti) < W-TS(x): 
� operação read rejeitada; 
� Ti refeita. 
� Se TS(Tj) >= W-TS(x): 
� operação read executada; 
� R-TS(x) ajustado. 
� Operações de Escrita em Ti: 
� Se TS(Ti) < R-TS(x): 
� operação write rejeitada; 
� Ti refeita. 
� Se TS(Tj) < W-TS(x): 
� operação write rejeitada; 
� Ti refeita. 
� Caso contrário, a operação write é executada e o W-TS(x) é ajustado. 
 
Exemplo: 
 T1: mostra a soma das contas A e B 
 T2: transfere $50 da conta A para a conta B 
 
 TS(T1) < TS(T2) 
 
 T1 T2 
 
 r(B) 
 r(B) 
 B := B-50 
 w(B) 
 r(A) 
 r(A) 
 display(A+B) 
 A := A+50 
 w(A) 
 display(A+B) 
 
R-TS (A) = 
W-TS (A) = 
 
R-TS (B) = 
W-TS (B) = 
 
 é uma execução válida, considerando o uso de marcadores de tempo? 
 
4. Problema do dado fantasma (“phantom problem”) 
 
- os BD são dinâmicos: além de read e write, há operações de insert e delete 
- 2PL não evita o problema do fantasma: uma inserção conflita com uma consulta 
mesmo quando as duas transações não solicitam tuplas comuns; 
T1 = select sum(saldo) 
from depósito 
where agência = centro 
T2 = insert in depósito 
values(João, 500) 
 
H = r1[x1] r1[x2] r1[x3] w2[x4] r2[SOMA_x] w2[SOMA_x] c2 r1[SOMA_x] c1 
 
 ls[ALL x] 
 
- respeita o 2PL(serializável): único conflito T2→T1 sobre SOMA_x 
- mas T1 lê SOMA_x incluindo x4, que não foilido inicialmente 
 
SOLUÇÕES: 
• Utilização de Bloqueio Simples: 
• Partilhado (S) para consulta; 
• Exclusivo(X) para inserção. 
• Utilização de Bloqueio Indexado: 
 bloqueia índices dos arquivos, definindo acesso exclusivo a todos os dados que tiverem 
aquele índice: a tupla torna-se disponível somente após a atualização do índice. 
 
- Problema com remoção de dados: remover dado depois que ele foi lido ou escrito 
Exemplos: assumir: I1 - delete(x) 
è I2 = read(x) 
 I1 < I2 ERRO 
 I2 < I1 SUCESSO 
è I2 = write(x) 
 I1 < I2 ERRO 
 I2 < I1 SUCESSO 
è I2 = delete(x) 
 I1 < I2 ERRO 
 I2 < I1 ERRO 
èI2 = insert(x) 
 I1 < I2 ERRO 
 I2 < I1 SUCESSO 
� Se x já existia: 
 I1 < I2 SUCESSO 
 I2 < I1 ERRO 
SOLUÇÕES: 
- utilização de protocolo de bloqueio antes da remoção 
- utilização de protocolo de marcador de tempo para ordenar as operações 
conflitantes: