07. Controle de Concorrência

Prévia do material em texto

26/08/2013
Banco de Dados - Prof. Jorge Soares 1
Sistemas de Bancos de Dados
Prof. Jorge Soares
jasoares@uerj.br
Tema
Controle de Concorrência em SGBDs
Agenda
• Bloqueios binários
• Bloqueio em duas fases (2PL)
• Granularidade múltipla
• Ordenação por marcas de tempo (Timestamp
Ordering)
• Deadlocks em transações
Banco de Dados – Prof. Jorge Soares 2
26/08/2013
Banco de Dados - Prof. Jorge Soares 2
Bloqueios
• Variável associada a um item de dado de um BD
• Descreve o status daquele item com respeito a
operações possíveis que podem ser aplicadas
ao mesmo
• Usados como meio de sincronizar o acesso de
transações concorrentes aos itens de um BD
Banco de Dados – Prof. Jorge Soares 3
Bloqueios
• Tipos
– Bloqueio compartilhado (shared lock)
– Bloqueio exclusivo (exclusive lock)
– Desbloqueio (unlock)
Banco de Dados – Prof. Jorge Soares 4
26/08/2013
Banco de Dados - Prof. Jorge Soares 3
Bloqueios
• O simples uso de bloqueios não garante a
serialização de escalas!
Exemplo:
T1: r(Y); r(X); X:=X+Y; w(X)
T2: r(X); r(Y); Y:=Y+X; w(Y)
Banco de Dados – Prof. Jorge Soares 5
Bloqueios
Para X=20 e Y=30 �
T1→→→→T2: X=50 e Y=80
T2→→→→T1: X=70 e Y=50
• Transações com bloqueios:
T1: rl(Y); r(Y); u(Y); wl(X); r(X); X:=X+Y; w(X); u(X);
T2: rl(X); r(X); u(X); wl(Y); r(Y); Y:=Y+X; w(Y); u(Y);
Banco de Dados – Prof. Jorge Soares 6
26/08/2013
Banco de Dados - Prof. Jorge Soares 4
Bloqueios
• Execução concorrente:
Para X=20 e Y=30 �
X=50 e Y=50 !!
Banco de Dados – Prof. Jorge Soares 7
Protocolo de Bloqueio Bifásico Básico
(2PL – Two-phase locking)
• Composto por duas fases: a de expansão e a de
encolhimento.
• No exemplo
T1: rl(Y); r(Y); wl(X); r(X); X:=X+Y; w(X); u(Y); u(X);
T2: rl(X); wl(Y); r(X); u(X); r(Y); Y:=Y+X; w(Y); u(Y);
Banco de Dados – Prof. Jorge Soares 8
26/08/2013
Banco de Dados - Prof. Jorge Soares 5
Protocolo de Bloqueio Bifásico Básico
(2PL – Two-phase locking)
• Características:
– Garantia da serialização do esquema
– Limitação do grau de concorrência
– Possibilidade de criação de deadlocks
Banco de Dados – Prof. Jorge Soares 9
Granularidade de itens
• Itens podem ser
– campos
– registros
– tabelas
– blocos
– páginas
– arquivos
– índices
– o próprio BD!
Banco de Dados – Prof. Jorge Soares 10
26/08/2013
Banco de Dados - Prof. Jorge Soares 6
Granularidade de itens
• Esquema ilustrativo
Banco de Dados – Prof. Jorge Soares 11
Granularidade de itens
• Afim de poder atender às demandas de diferentes
granularidades das transações, surgem os
conceitos de intenções de bloqueios.
• Estes são outros bloqueios que indicam que itens
existentes abaixo na hierarquia estão sendo
modificados.
• Utilizada em transações muito curtas que acessam
poucos itens, ou longas que acessam arquivos.
Banco de Dados – Prof. Jorge Soares 12
26/08/2013
Banco de Dados - Prof. Jorge Soares 7
Granularidade de itens
• Tipos:
– compartilhamento intencional (IS): um lock é
requerido para algum nó descendente
– intencional exclusivo (IX): lock exclusivo para algum
nó descendente
– intencional exclusivo compartilhado (SIX): nó corrente
é bloqueado em modo compartilhado, mas lock
exclusivo será requerido para um nó descendente
Banco de Dados – Prof. Jorge Soares 13
Granularidade de itens
• Matriz de compatibilidades
Banco de Dados – Prof. Jorge Soares 14
26/08/2013
Banco de Dados - Prof. Jorge Soares 8
Granularidade de itens
Protocolo utilizado:
1. Bloqueios conflitantes não podem ser concedidos
2. A raiz da árvore deve ser bloqueada primeiro em qq modo
3. Um nó N pode ser bloqueado por uma transação T em modo compartilhado(S)
ou IS somente se o nó pai N já estiver bloqueado por T nos modos IS ou IX
4. Um nó N pode ser bloqueado por uma trans. T em modo X,IX ou SIX somente
se o nó pai N já estiver bloqueado por T nos modos IX ou SIX
5. Uma transação T pode bloquear um nó somente se não tiver desbloqueado
nenhum nó (protocolo 2PL)
6. Uma transação T pode desbloquear um nó N somente se nenhum dos nós
filhos de n estiver bloqueado por T
Banco de Dados – Prof. Jorge Soares 15
Protocolo de ordenação por marcas de tempo
(Timestamp Ordering)
• Garantia da serialização da escala sem a existência de
bloqueios
• O conceito de timestamp é chave no processo!
– Timestamps físicos X lógicos
• Quanto mais antiga for a transação, menor será o seu
timestamp
Banco de Dados – Prof. Jorge Soares 16
26/08/2013
Banco de Dados - Prof. Jorge Soares 9
Protocolo de ordenação por marcas de tempo
(Timestamp Ordering)
• Baseado em dois elementos:
– Read_TS(X): operação de leitura do TS de X: maior
TS (Transação mais nova) dentre todos os TS das
transações que tiveram sucesso na leitura de X
– Write_TS(X): operação de gravação do TS de X:
maior TS (transação mais nova) dentre todos os TS
das transações que tiveram sucesso na gravação de
X
Banco de Dados – Prof. Jorge Soares 17
Protocolo de ordenação por marcas de tempo
(Timestamp Ordering)
• Algoritmo:
1- T tenta efetuar operação de read(x):
se TS(T) >= write_TS(x)
então executa read(x); TS(T) ← read_TS(x) se for o caso
senão aborta T
2- T tenta efetuar operação de write(x):
se TS(T) >= read_TS(x) E se TS(T) >= write_TS(X)
então executa write_item(x); TS(T) ← write_TS(X)
senão aborta T
Banco de Dados – Prof. Jorge Soares 18
26/08/2013
Banco de Dados - Prof. Jorge Soares 10
Deadlocks em transações
• Situação onde 2 ou mais transações estão
simultaneamente em estado de espera, com
dependência entre elas.
• Exemplo:
Banco de Dados – Prof. Jorge Soares 19
Deadlocks em transações
• Protocolos de prevenção:
– 2PL conservador
– Bloqueio de itens por ordem
– Espera cuidadosa
– Timeout
– Esperar-morrer (wait-die)
– Ferir-esperar (wound-wait)
Banco de Dados – Prof. Jorge Soares 20
26/08/2013
Banco de Dados - Prof. Jorge Soares 11
Deadlocks em transações
Supor que uma transação Ti tente bloquear X porém não consegue porque X
já está bloqueado por outra transação Tj
• Protocolo Esperar-morrer (wait-die)
se TS(Ti) < TS(Tj) (Ti é mais antiga que Tj)
então Ti espera
senão Ti aborta e recomeça + tarde com o mesmo TS
• Protocolo Ferir-esperar (wound-wait)
se TS(Ti) < TS(Tj)
então Tj aborta e recomeça + tarde
senão Ti espera
� podem causar sucessivos abort/restart
Banco de Dados – Prof. Jorge Soares 21