UNDB
BANCO DE DADOS II
Prof. Alessandro Gonçalves
[email protected]
1
Esquemas de Seriação
Ajustar o schedule
Garantir a consistência
Como gerenciar a ordem de execução ?
2
Equivalências de Seriação
Seriação de conflito
Seriação de visão
3
Equivalência de Seriação
S1
Estado
A
S2
Estado
B
S3
= CONSISTÊNCIA
4
Execuções simultâneas
T1
read(A);
A := A -50;
Write (A);
Read (B);
B := B + 50;
Write (B);
T2
read(A);
Temp := A*0.1
A := A – temp;
Write (A);
Read (B);
B := B + temp;
Write (B);
5
Execuções simultâneas
T1
T2
read(A);
A := A -50;
read(A);
temp := A*0.1
A := A – temp;
Write (A);
Read (B);
Write (A);
Read (B);
B := B + 50;
Write (B);
B := B + temp;
Write (B);
6
Seriação de conflito
Considerando somente instruções Read e Write
Um schedule com 02 instruções consecutivas Ii e Ij, de
transações Ti e Tj
Se referirem a diferentes tipos de dados → não importa
Se forem relativos ao mesmo dado, importa
7
Seriação de conflito
Quatro situações possíveis
Situação 1:
Ii = read(Q), Ij = read(Q)
A ordem importa ?
NÃO
8
Seriação de conflito
Situação 2:
Ii = read(Q), Ij = write(Q)
Se Ii vem antes de lj então Ti não lê o valor de Q que é
escrito por Tj na instrução Ij. Se Ij vem antes de Ii, então
Ti lê o valor de Q que é escrito por Tj. Assim, a ordem
de Ii e Ij importa.
9
Seriação de conflito
Situação 3:
Ii = write(Q), Ij = read(Q)
Similar à situação 2. Assim, a ordem de Ii e Ij importa.
10
Seriação de conflito
Situação 4:
Ii = write(Q), Ij = write(Q)
Como as duas instruções são “write”, a ordem não afeta Tj ou
Tj . Contudo, o valor obtido pela próxima instrução read(Q) de
S é afetada, pois o resultado apenas da última instrução Write
é preservado no banco de dados. Se não houver outra
instrução write(Q) após Ii e Ij em S, então a ordem de Ii e Ij
afeta diretamente o valor final de Q no estado do banco de
dados que resulta do schedule S.
11
Seriação de conflito
Definição de conflito na seriação
Ii e Ij conflitam se forem operações em diferentes
transações sobre o mesmo item de dados e pelo
menos uma dessas operações for uma operação write.
12
Seriação de conflito - exemplos
Folhas anexas – 03 schedules
13
Seriação de conflito
Se um schedule S puder ser transformado em
um schedule S' por trocas de instruções não
conflitantes, dizemos que S e S' são
Equivalentes em Conflito.
14
Seriação de conflito
Se um schedule S é Equivalente em Conflito a um
schedule serial, este é Serial de Conflito.
15
Seriação de conflito
Resultados iguais significam schedules com
equivalência de conflito ?
16
Seriação de conflito
Anexo – schedule final
17
Seriação de visão
A seriação de conflito é boa mas muito rigorosa.
A seriação de visão é menos rigorosa que a
seriação de conflito
Baseia-se também em Read e Write
18
Seriação de visão
Um schedule S será serial de visão de um S’ se:
1.Para cada item de dados Q se a transação Ti ler
o valor inicial do schedule S, então a transação Ti
no schedule S’ deverá ler Q também.
19
Seriação de visão
2. Para cada item de dados Q se a transação Ti
executar Read(Q) no schedule S, e se esse
valor foi produzido por uma operação write(Q)
executada pela transação Tj então a operação
Read(Q) da transação Ti no schedule S’
também precisa ler o valor de Q que foi
produzido pela mesma operação Write(Q) de
Tj.
20
Seriação de visão
3. Para cada item de dados Q, a transação que
realiza write(Q) final (se houver) no schedule S
precisa realizar a operação write(Q) final no
schedule S’
21
Seriação de visão
Considere o Schedule S
T1
read(Q)
write(Q)
T2
T3
write(Q)
write(Q)
22
Seriação de visão
Considere o Schedule S’
T1
read(Q)
T2
T3
write(Q)
write(Q)
write(Q)
23
Seriação de visão
É Equivalente em Conflito ?
NÃO
É Serial em Conflito ?
NÃO
É Equivalente em Visão ?
SIM
É serial de Visão ?
SIM
24
Seriação de conflito x visão
Equivalente em conflito
Serial de
conflito
25
Seriação de conflito x visão
Equivalente em visão
Serial de
visão
26
Seriação de conflito x visão
Serial de visão
Serial
de
conflito
27
Falhas
Schedules garantem consistência
equivalência conflito ou visão
E em caso de falhas ?
28
Falhas – garantia de atomicidade
Se T9 for confirmada e houver falha em T8 ?
Quais os problemas ?
= Schedule NÃO RECUPERÁVEL
29
Schedule Recuperável
Definição
Se houver duas transações Ti e TJ e
Tj leia um item de dados previamente escrito por
Ti, a operação commit de Ti apareça antes do
commit de Tj
30
Schedule Recuperável
Um schedule recuperável é suficiente para
garantir atomicidade.
Mas e a performance ?
31
Schedule não em cascata
T1
read(A)
read(B)
write(A)
T2
T3
read(A)
write(A)
read(A)
Se ocorrer falha em read(A) de T3 ?
32
Resumindo
Schedules devem ser seriais de conflito ou de
visão
Devem ser recuperáveis
Não em cascata
33
Controle de concorrência
Para garantir que o esquema gera schedules
passíveis de seriação
Utiliza Testes de seriação
34
Testando a seriação de conflito
Constroi-se o gráfico de precedência
Gráfico é um par G(V, A) – vértices e arestas
Transações formam os vértices
Ligações entre as transações formam as arestas
T1
T2
35
Testando a seriação de conflito
Regras para ser uma aresta:
Ti executa read(Q) antes Tj executar write(Q)
Ti executa write(Q) antes Tj executar read(Q)
Ti executa write(Q) antes Tj executar write(Q)
36
Gráfico de precedência
T1
T2
read (A)
write (A)
read (B)
Write (B)
read (A)
write (A)
read (B)
write (B)
Como seria o gráfico de precedência ?
37
Gráfico de precedência
T1
T2
read (A)
read (A)
write (A)
read (B)
write (A)
read (B)
write (B)
write (B)
Como seria o gráfico de precedência ?
38
Gráfico de precedência
T1
T2
T3
read (A)
read (A)
write (A)
read (A)
write (A)
read (A)
read (B)
write (B)
write (B)
Como seria o gráfico de precedência ?
39
Gráfico de precedência
O gráfico do schedule do slide anterior fica assim:
T3
T1
T2
Forma ciclo !
40
Classificação topológica
41
Gráfico de precedência - final
Se formar ciclo, NÃO É SERIAL DE CONFLITO
Se não formar ciclo, É SERIAL DE CONFLITO
42
Controle de concorrência
43
Controle de concorrência
Bloqueios de itens de dados
Compartilhado – posso ler mas não escrever
Exclusivo – posso ler e escrever
Ex: bloqueei os registros de clientes para escrita.
Mas os registros de vendas, fornecedores...
Continuam livres
44
Controle de concorrência
Matriz de compatibilidade de bloqueios
Compartilhado
Exclusivo
Compartilhado
Verdadeiro
Falso
Exclusivo
Falso
Falso
45
Controle de concorrência
Quais bloqueios são gerados por:
Insert ?
Select ?
Update
Delete ?
46
Os 3 problemas da concorrência
Problema 1 – Atualização perdida
Exemplo do bônus de 10%
T1
read(A)
A = A * 1.1
T2
read(A)
A = A * 1.1
write(A)
write(A)
47
Os 3 problemas da concorrência
Problema 2 – Dependência sem commit
T1
T2
write (A)
read(A)
rollback
Ler ou escrever valores antes de COMMIT
48
Os 3 problemas da concorrência
Problema 3 – Análise inconsistente
T1
read(A)
read(B)
T2
read(C)
write(C) -> 20
read(A)
write(B) -> 50 (qual bloqueio ?)
commit
read(C)
commit
espera
espera
Originais: 40,50,30
Quanto vale (A+B+C) em cada momento
49
Controle de concorrência
O bloqueio
é
compatível
?
Não, aguarde...
Sim
Bloqueie (lock)
Execute o
comando
Libere (unlock)
50
Exemplo da conta
Anexo Bl.02 – serial
Como se comporta ?
51
Exemplo da conta – com
desbloqueio ao final de cada T
T3
lock-E(B)
read(B)
B := B – 50;
write(B)
lock-E(A)
read(A)
A:= A+ 50;
write(A)
unlock (B)
Unlock (A)
T4
lock-C(A)
read(A)
lock-C(B)
read(B)
display(A+B)
unlock(A)
unlock(B)
52
Problema de bloqueio - impasse
T3
lock-E(B)
read(B)
B := B – 50;
write(B)
T4
lock-C(A)
read(A)
lock-C(B)
read(B)
lock-E(A)
write(A)
53
Problema – impasse (deadlock)
Analise
1) É preferível estado inconsistente ou Deadlock ?
2) O que o SGBD deve fazer ao detectar ?
54
Problema – starving
Demora excessiva para executar a transação
O sistema não está em Deadlock mas demora para
conceder o bloqueio da transação
55
Problema – timeout
xx-x
Banco de dados tem um tempo limite de resposta
O sistema extrapola este tempo para conceder o bloqueio da
transação
T1
Begin trans
While not eof(cliente)
Update conta set saldo = saldo - 10
Where agencia.nome = 'Renascença' and cliente.codigo =
cliente
Loop
Commit
T2
Select saldo from conta, agencia where agencia.nome =
'Renascença' and conta.agencia = agencia.agencia
56
Problema – starving e timeout
Dicas para minimizar o problema
1. Chaves primárias pequenas (nome x código)
2. Operação através de índices (análise das queries)
3. Diminuir o bloco de comandos por transação,
executando Commits de tempos em tempos
4. Uso de Views e Views Materializadas
5. Programação dentro do banco
57
Protocolos de bloqueio
Conjunto de regras que as transações devem seguir
Restringem o número de schedules possíveis
Só estudaremos os protocolos que gerem schedules
passíveis de seriação de conflito
58
Protocolos de bloqueio
Considerações
Ti e Tj são transações de um schedule S, onde
Ti → Tj (Ti vem antes de Tj) e;
Ti usou o bloqueio “A” sobre Q
Tj usou o bloqueio “B” sobre Q
Compatibilidade(A,B) = falso
Assim, para qualquer schedule gerado a partir de S,
Ti virá antes de Tj
59
Protocolos de bloqueio
Considerações
Ti
lock-C(A)
Select nome
from cliente
Where Codigo = 1
unlock(A)
Tj
lock-E(A)
Update cliente
Set nome = 'Angelina'
Where
Codigo = 1
unlock(A)
60
Protocolos de bloqueio
Considerações
Um schedule S é legal para o protocolo se:
For possível para um conjunto de transações que
seguem as regras do protocolo do bloqueio
Protocolo de bloqueio assegura a seriação de
conflito se e somente se todos os schedules legais
forem passíveis de seriação de conflito.
Ou seja: para todos os schedules legais, a relação é
acíclica...
61
Concessão de bloqueios
T1
T2
T3
T4
lock-C(A)
lock-E(A)
lock-C(A)
lock-C(A)
...
62
Concessão de bloqueios
STATUS
1. Item A pode ser bloqueado compartilhado por T1
?
2. Item A Bloqueado por T1
3. Item A pode ser bloqueado exclusivamente por
T2 ?
4. Não. T2 entra em estado de espera
63
Concessão de bloqueios
STATUS
5. Item A pode ser bloqueado compartilhado POR
T3 ?
6. Item A bloqueado compartilhado por T3.
Operação de T3 feita.
7. Item A bloqueado compartilhado por T4.
Como ficou a transação T2 ?
64
Concessão – evitando starving
Quando Ti solicita um bloqueio sobre item de
dados Q em um modo específico M, o gerenciador
de controle de concorrência concede o bloqueio
desde que:
Não haja outra transação mantendo um bloqueio
sobre Q em um modo conflitante com M
Não exista outra transação que esteja esperando
um bloqueio sobre Q e que fez sua solicitação de
bloqueio antes de Ti
65
Protocolos de bloqueio
66
Protocolo de bloqueio em 2 fases
Assegura a seriação
1. Fase de crescimento – uma transação pode
obter bloqueios, mas não liberá-los (ponto de
bloqueio)
2. Fase de encolhimento – uma transação pode
liberar bloqueios, mas não obter novos bloqueios
Exemplo a seguir
67
Exemplo de bloqueio em 2 fases
T1
T2
lock-E(B)
read(B)
B := B -50
write (B)
lock-C (A)
read (A)
lock-C (B)
lock-E(A)
unlock(A)
unlock(B)
68
Outro exemplo
T1
T2
lock-C(A)
read(A)
lock-C(B)
read (B)
unlock(A)
unlock(B)
lock-E(B)
write(B)
unlock(B)
69
Bloqueio em 2 fases
Características
Asseguram a seriação ?
Sim
Previnem deadlock ?
Não
Previnem rollback em cascata ?
Não
Exemplo rollback em cascata a ser escrito
(anexo)
70
Bloqueio em 2 fases
Comum – segue o protocolo
Estrito – o bloqueio EXCLUSIVO é mantido até a
confirmação (Commit).
Rigoroso – TODOS os bloqueios são mantidos
até a confirmação (Commit)
Qual deles é implantado pela maioria dos SGBD ?
RIGOROSO
71
Bloqueio – o problema dos locks
sobrepostos
Uma transação Ti como abaixo:
Lock-C(A)
Read(A)
Lock-E(A)
Write(A)
O que acontece ?
72
Bloqueio – o problema dos locks
sobrepostos
Se uma transação Ti tiver o bloqueio
compartilhado em Q, pode solicitar bloqueio
exclusivo de Q
UPGRADE
Desde que seja na fase de crescimento do
bloqueio de duas fases
73
Bloqueio – o problema dos locks
sobrepostos
Se uma transação Ti tiver o bloqueio exclusivo
em Q, pode solicitar bloqueio compartilhado de Q
DOWNGRADE
Desde que seja na fase de encolhimento do
bloqueio de duas fases
74
O problema dos locks sobrepostos
Upgrade x Downgrade
T1
lock-C(A)
read(A)
lock-E(A)
unlock(A)
T2
lock-C(B)
read(B)
lock-C(A)
read(A)
lock-E(A)
write(A)
unlock(B)
lock-C(A)
75
UNDB
BANCO DE DADOS II
Prof. Alessandro Gonçalves
[email protected]
76