PBD - 05 - Controle de Concorrência

Prévia do material em texto

Práticas de
Banco de Dados
Parte 5 – Controle de Concorrência
Professor Eduardo Xavier
Técnicas de Controle de 
Concorrência
 Técnicas Pessimistas
– Supõem que sempre ocorre interferência entre transações e 
garantem a serializabilidade enquanto a transação está ativa
– Técnicas:
● Bloqueio (locking)
● Timestamp
 Técnicas Otimistas
– Supõem que Supõem que quase nuncaquase nunca ocorre interferência entre transações e ocorre interferência entre transações e 
verificam a serializabilidade somente ao final de uma transaçãoverificam a serializabilidade somente ao final de uma transação
– TécnicaTécnica
● Validação
Bloqueios (Locking)
 BloqueiosBloqueios, ou , ou lockingslockings, são técnicas utilizada para controlar a , são técnicas utilizada para controlar a 
execução concorrente de transações.execução concorrente de transações.
 São as mais utilizadas pelos SGBDs relacionais modernos.São as mais utilizadas pelos SGBDs relacionais modernos.
 Um Um bloqueiobloqueio ou ou locklock é uma variável é uma variável associada a cada item de associada a cada item de 
dadodado que descreve o estado do item em relação às operações que descreve o estado do item em relação às operações 
que podem ser aplicadas ao mesmo.que podem ser aplicadas ao mesmo.
 Bloqueios são usados como um meio de Bloqueios são usados como um meio de sincronizar acessos sincronizar acessos 
concorrentesconcorrentes aos itens do banco de dados aos itens do banco de dados
Bloqueios (Locking)
 Princípio de funcionamentoPrincípio de funcionamento
– Controle de operações de Controle de operações de leituraleitura ( ( read(X)read(X) ), ), escritaescrita 
( ( write(X)write(X) ) e ) e postergaçãopostergação (através de bloqueio) de algumas (através de bloqueio) de algumas 
dessas operações de modo a dessas operações de modo a evitar conflitoevitar conflito..
 Todo dado possui um Todo dado possui um status de bloqueiostatus de bloqueio, que pode ser:, que pode ser:
– liberadoliberado ( (UnlockedUnlocked - U) - U)
– com com bloqueio compartilhadobloqueio compartilhado ( (SharedShared locklock - S) - S)
– com com bloqueio exclusivobloqueio exclusivo ( (eXclusiveeXclusive locklock - X) - X)
Bloqueios (Locking)
 Bloqueio CompartilhadoBloqueio Compartilhado (S) (S)
– Solicitado por uma transação que deseja realizar leitura de dado D Solicitado por uma transação que deseja realizar leitura de dado D 
várias transações podem manter esse bloqueio sobre Dvárias transações podem manter esse bloqueio sobre D
 Bloqueio ExclusivoBloqueio Exclusivo (X) (X)
– Solicitado por uma transação que deseja realizar leitura+atualização Solicitado por uma transação que deseja realizar leitura+atualização 
de um dado D de um dado D uma única transação pode manter esse bloqueio sobre Duma única transação pode manter esse bloqueio sobre D
 Matriz de Compatibilidade de Bloqueios:Matriz de Compatibilidade de Bloqueios:
 Informações de bloqueio são mantidas no DDInformações de bloqueio são mantidas no DD
– <ID-dado,status-bloqueio,ID-transação><ID-dado,status-bloqueio,ID-transação>
SS XX
SS verdadeiroverdadeiro falsofalso
XX falsofalso falsofalso
Bloqueios (Locking)
 Operações de Bloqueio e HistóricoOperações de Bloqueio e Histórico
– O O SchedulerScheduler gerencia bloqueios através da invocação gerencia bloqueios através da invocação 
automática de operações de bloqueio conforme a operação automática de operações de bloqueio conforme a operação 
que a transação deseja realizar em um dado.que a transação deseja realizar em um dado.
 OperaçõesOperações
– ls(D) ou lock-S(D) ou read-lock(D)ls(D) ou lock-S(D) ou read-lock(D): solicitação de bloqueio : solicitação de bloqueio 
compartilhado sobre Dcompartilhado sobre D
– lx(D) ou lock-X(D) ou write-lock(D)lx(D) ou lock-X(D) ou write-lock(D): solicitação de bloqueio : solicitação de bloqueio 
exclusivo sobre Dexclusivo sobre D
– u(D) ou unlock(D)u(D) ou unlock(D): libera o bloqueio sobre D : libera o bloqueio sobre D 
Bloqueios (Locking)
 Exemplo de histórico de bloqueios:Exemplo de histórico de bloqueios:
– Considere a tabela ao lado como duas Considere a tabela ao lado como duas 
transações T1 e T2 emitindo comandos transações T1 e T2 emitindo comandos 
ao scheduler do SGBD ao longo do ao scheduler do SGBD ao longo do 
tempo.tempo.
– O histórico desses comandos pode ser O histórico desses comandos pode ser 
representado por:representado por:
H = ls1(Y) r1(Y) u1(Y) ls2(X) lx2(Y) H = ls1(Y) r1(Y) u1(Y) ls2(X) lx2(Y) 
r2(X) r2(Y) u2(X) w2(Y) u2(Y) c2 r2(X) r2(Y) u2(X) w2(Y) u2(Y) c2 
lx1(X) r1(X) w1(X) u1(X) c1lx1(X) r1(X) w1(X) u1(X) c1
T1T1 T2T2
lock-S(Y)lock-S(Y)
read(Y)read(Y)
unlock(Y)unlock(Y)
lock-S(X)lock-S(X)
lock-X(Y)lock-X(Y)
read(X)read(X)
read(Y)read(Y)
unlock(X)unlock(X)
write(Y)write(Y)
unlock(Y)unlock(Y)
commit( )commit( )
lock-X(X)lock-X(X)
read(X)read(X)
write(X)write(X)
unlock(X)unlock(X)
commit( )commit( )
Bloqueios (Locking)
É permitido a uma transação que já tenha um bloqueio no 
item X converter o bloqueio de um estado para outro.
Upgrade – mudança para um estado mais rígido – exemplo 
: uma transação T pode emitir um read_lock(X) e depois um 
write_lock(X), se T for a única com bloqueio read em X 
poderá executar o upgrade, caso contrário espera.
Downgrade – mudança para um estado menos rígido – 
exemplo : uma transação T que está com bloqueio 
exclusivo write_lock(X) pode emitir um read_lock(X). 
Bloqueios (Locking)
 Problema: o simples uso de bloqueis : o simples uso de bloqueis não garantenão garante escalonamentos escalonamentos 
serializáveis de transaçãoserializáveis de transação
 ExemploExemplo
HN-SR= ls1(Y) r1(Y) u1(Y) ls2(X) r2(X) u2(X) lx2(Y) r2(Y) w2(Y) u2(Y) 
c2 lx1(X) r1(X) w1(X) u1(X) c1
Note que tanto as transações 1 e 2 manipulam os dados X e Y. O dado Y é 
alterado (e “comitado”) por T2 antes de T1 terminar de trabalhar com ele, 
enquanto que o dado X foi lido e atualizado por T2, porém T1 alterou X após 
isso acontecer (o que pode impactar no resultado de T2).
 Necessita-se de uma técnica mais rigorosa de bloqueio para garantir que o Necessita-se de uma técnica mais rigorosa de bloqueio para garantir que o 
escalonamento usado possa ser serial.escalonamento usado possa ser serial.
 A solução mais utilizada é o bloqueio de duas fases (two-phase locking – 2PL)
Bloqueios de Duas FasesBloqueios de Duas Fases
 2PL / Bloqueio de Duas Fases2PL / Bloqueio de Duas Fases
– Premissa:Premissa:
● ““para toda transação Tx, todas as operações de bloqueio de dados para toda transação Tx, todas as operações de bloqueio de dados 
feitas por Tx precedem a primeira operação de desbloqueio feita por Tx”feitas por Tx precedem a primeira operação de desbloqueio feita por Tx”
– Funcionamento do protocolo de duas fases:Funcionamento do protocolo de duas fases:
● Fase de expansão ou crescimentoFase de expansão ou crescimento
– TxTx pode obter bloqueios, mas não pode liberar nenhum bloqueio pode obter bloqueios, mas não pode liberar nenhum bloqueio
● Fase de retrocesso ou encolhimentoFase de retrocesso ou encolhimento
– TxTx pode liberar bloqueios, mas não pode obter nenhum bloqueio pode liberar bloqueios, mas não pode obter nenhum bloqueio 
Bloqueios de Duas FasesBloqueios de Duas Fases
 2PL / Bloqueio de Duas Fases2PL / Bloqueio de Duas Fases
número
bloqueios
Gráfico de bloqueios de Tx
tempostart commit
crescimento encolhimento
Ponto em que os bloqueios param. 
Todos os dados desejados por Tx 
foram obtidos (Pmax(Tx))
execução de operações de Tx
Bloqueios de Duas FasesBloqueios de Duas Fases
 ComparaçãoComparação
 T (sem protocolo) T’ (usando protocolo de duas fases)
 read-lock(y); read-lock(y);
 read-item(y); read-item(y);
 unlock(y); write-lock(x);
 write-lock(x); unlock(y);
 read-item(x); read-item(x);
 x=x+y; x=x+y;
 write-item(x); write-item(x);
 unlock(x); unlock(x);
 Em T’ → Na primeira fase prende todos os recursos necessáriose 
na segunda fase libera os recursos.
Primeira fase
Segunda fase
Bloqueios de Duas FasesBloqueios de Duas Fases
• Importante:Importante:
– Se todas as transações em um escalonamento seguirem o protocolo de Se todas as transações em um escalonamento seguirem o protocolo de 
bloqueio em duas fases, o escalonamento é garantidamente bloqueio em duas fases, o escalonamento é garantidamente 
serializável.serializável.
– O bloqueio em duas fases limita o volume de concorrência, podendo O bloqueio em duas fases limita o volume de concorrência, podendo 
provocar deadlock (impasse) / starvation (espera infinita).provocar deadlock (impasse) / starvation (espera infinita).
Bloqueios de Duas FasesBloqueios de Duas Fases
• Importante:Importante:
– Se todas as transações em um escalonamento seguirem o protocolo de Se todas as transações em um escalonamento seguirem o protocolo de 
bloqueio em duas fases, o escalonamento é bloqueio em duas fases, o escalonamento é garantidamente serializávelgarantidamente serializável..
– O bloqueio em duas fases limita o volume de concorrência.O bloqueio em duas fases limita o volume de concorrência.
• Isso pode provocar deadlock (impasse) / starvation (espera infinita).Isso pode provocar deadlock (impasse) / starvation (espera infinita).
• Mesmo não provocando deadlocks ou starvation, Mesmo não provocando deadlocks ou starvation, um dado pode um dado pode 
permanecer bloqueado por permanecer bloqueado por TxTx muito tempo até que muito tempo até que TxTx adquira bloqueios adquira bloqueios 
em todos os outros dados que deseja, o que pode provocar problemas em todos os outros dados que deseja, o que pode provocar problemas 
de performance.de performance.
Bloqueios de Duas FasesBloqueios de Duas Fases
• Importante:Importante:
– Se todas as transações em um escalonamento seguirem o protocolo de Se todas as transações em um escalonamento seguirem o protocolo de 
bloqueio em duas fases, o escalonamento é bloqueio em duas fases, o escalonamento é garantidamente serializávelgarantidamente serializável..
– O bloqueio em duas fases limita o volume de concorrência.O bloqueio em duas fases limita o volume de concorrência.
• Isso pode provocar Isso pode provocar deadlock (impasse)deadlock (impasse) ou ou starvation (espera infinita)starvation (espera infinita)..
• Mesmo não provocando deadlocks ou starvation, Mesmo não provocando deadlocks ou starvation, um dado pode permanecer um dado pode permanecer 
bloqueado por bloqueado por TxTx muito tempo até que muito tempo até que TxTx adquira bloqueios em todos os outros adquira bloqueios em todos os outros 
dados que deseja, o que pode provocar problemas de performance.dados que deseja, o que pode provocar problemas de performance.
– O 2PL básico2PL básico (técnica apresentada anteriormente)... (técnica apresentada anteriormente)...
• Não garante escalonamentos livres de Não garante escalonamentos livres de deadlockdeadlock
– Tx Tx espera pela liberação de um dado bloqueado porespera pela liberação de um dado bloqueado por Ty Ty de forma de forma 
conflitante e vice-versaconflitante e vice-versa
• Não garante escalonamentos adequados à recuperação pelo Não garante escalonamentos adequados à recuperação pelo recoveryrecovery
Deadlocks (Impasses)Deadlocks (Impasses)
• Um deadlock ocorre quando cada 
transação T1 em um conjunto de duas ou 
mais transações está esperando algum ítem 
que esteja bloqueado por alguma outra 
transação T2 no conjunto.
• Cada transação do conjunto está na fila de 
espera aguardando que o recurso (ítem) 
seja liberado.
Read_lock (Y)
 Read_item (Y)
Write _lock (X)
Read_lock (X)
Read_item (X)
Write _lock (Y)
T1 T2
tempo
Prevenção de DeadlocksPrevenção de Deadlocks
• TimeoutsTimeouts
– Uma transação fica em estado de espera por um determinado tempo Uma transação fica em estado de espera por um determinado tempo 
estabelecido no sistema. Após atingir o tempo ela é desfeita. Método estabelecido no sistema. Após atingir o tempo ela é desfeita. Método 
prático e simples com baixo nível de overhead. prático e simples com baixo nível de overhead. 
– O timeout ocorre quando uma transação não pode continuar sua execução O timeout ocorre quando uma transação não pode continuar sua execução 
durante um intervalo indefinido de tempo, enquanto que outras durante um intervalo indefinido de tempo, enquanto que outras 
transações continuam a ser executadas normalmente. transações continuam a ser executadas normalmente. 
Tratamento de DeadlocksTratamento de Deadlocks
• Protocolos de Prevenção
– Abordagens pessimistas
• Deadlocks ocorrem com frequência!
• Impõem um overhead no processamento de transações
– controles adicionais para evitar deadlock
• tipos de protocolos pessimistas
– técnica de bloqueio 2PL conservador
– técnicas baseadas em timestamp (wait-die / wound-wait)
– técnica de espera-cautelosa (cautious-waiting)
– Uso de timeout
• Se tempo de espera de Tx > timeout então abort(Tx)
Tratamento de DeadlocksTratamento de Deadlocks
• Protocolo 2PL Conservador
– Tx deve bloquear todos os dados que 
deseja antes de iniciar qualquer 
operação
• Caso não seja possível bloquear todos 
os dados, nenhum bloqueio é feito e Tx 
entra em espera para tentar novamente
– Vantagem
• Uma vez adquiridos todos os seus 
bloqueios, Tx não entra em deadlock 
durante a sua execução
– Desvantagem
• Espera pela aquisição de todos os 
bloqueios!
Número
de
bloqueios
tempostart commit
encolhimento
Pmax(Tx)
Tratamento de DeadlocksTratamento de Deadlocks
• Timestamp
– A ideia é associar um rótulo de tempo a cada transação Tx (TS(Tx))
• Técnicas
– Considere que Tx deseja um dado bloqueado por outra transação Ty
– Técnica 1: Esperar-ou-morrer (wait-die)
1) Se TS(Tx) < TS(Ty) 
Então Tx é mais velha que Ty
Neste caso Tx aguarda (wait) para prosseguir bloqueando
2) Se TS(Tx) > TS(Ty)
Então Tx é mais nova que Ty
Tx é cancelada (die) e reiniciada com o mesmo timestamp 
anterior após um período de espera
Tratamento de DeadlocksTratamento de Deadlocks
• Timestamp (continuação)
– Técnica 2: Ferir-ou-esperar (wound-wait)
1) Se TS(Tx) < TS(Ty)
Então Tx é mais velha que Ty
Tx força rollbak em Ty (wound - Tx “fere” Ty) 
Ty é cancelada e reiniciada com o mesmo timestamp anterior 
após um período de espera
2) Se TS(Tx) > TS(Ty)
Então Tx é mais nova que Ty
Neste caso Tx é forçada a esperar (wait) até que o recurso 
disputado esteja disponível.
● Vantagem das duas técnicas: evitam starvation (espera indefinida) de uma 
transação Tx (quanto mais antiga for Tx, maior a sua prioridade)
● Desvantagem das técnicas: muitos abortos podem ser provocados, sem nunca 
ocorrer um deadlock
Tratamento de DeadlocksTratamento de Deadlocks
• Espera Cautelosa
Se Tx deseja D e D está bloqueado por Ty 
 Então Se Ty não está em alguma fila de espera (WAIT)
 então Tx espera D ser liberado
 senão início
 abort(Tx)
 start(Tx)
 fim
•Vantagem
– Se Ty já está em espera, Tx é abortada para evitar um possível ciclo de 
espera
– É livre de Deadlock
•Desvantagem
– A mesma das técnicas baseadas em timestamp
Tratamento de DeadlocksTratamento de Deadlocks
• Validação
– Em técnicas de controle de concorrência de validação (ou técnicas 
otimistas), nenhuma verificação é realizada enquanto a transação está 
sendo executada, diminuindo um custo adicional durante a execução da 
transação.
– Geralmente, as técnicas otimistas de controle de concorrência 
funcionam bem se houver pouca interferência (suposição otimista) 
entre as transações de um escalonamento.
Tratamento de DeadlocksTratamento de Deadlocks
• Validação – Exemplo:
– Uma das técnicas otimistas propõe as seguintes regras:
• Atualizações na transação não são aplicadas diretamente aos itens do 
banco de dados até que a transação atinja seu final.
• Todas as atualizações são aplicadasa cópias locais dos itens de dados.
• Ao final de uma transação, a fase de validação verifica se qualquer uma 
das atualizações da transação viola a serialização.
• Se a serialização não for violada, a transação é confirmada e o banco de 
dados é atualizado a partir das cópias locais; caso contrário, a transação 
é abortada e posteriormente reiniciada.
Tratamento de DeadlocksTratamento de Deadlocks
• Protocolos de detecção
– Abordagens otimistas
• Deadlocks não ocorrem com frequência (são tratados quando 
ocorrem)
• Mantém-se um grafo de espera de transações
• Se há deadlock, seleciona-se uma transação vítima Tx através de um 
ou mais critérios
– Quanto tempo Tx está em processamento
– Quantos itens de dado Tx já leu/escreveu
– Quantos itens de dado Tx ainda precisa ler/escrever
– Quantas outras transações serão afetadas pelo abort(Tx)
Outras Técnicas de 2PLOutras Técnicas de 2PL
•2PL Conservador (ou Estático)
– A transação deve solicitar o bloqueio de TODOS os itens que acessa 
antes de iniciar a execução, ESPERANDO até que todos estejam 
disponíveis.
– Evita deadlock, porém Tx pode esperar muito para executar
– Pouco prático e inviável na maioria dos casos.
•2PL Estrito (muito usado pelos SGBDs)
– Tx só libera seus bloqueios exclusivos após executar commit ou abort
– Assim, nenhuma outra transação pode ler ou escrever item a menos que 
T tenha sido efetivada.
– Vantagem: garante escalonamentos estritos
– Desvantagem: não está livre de deadlocks
Outras Técnicas de 2PLOutras Técnicas de 2PL
•2PL Rigoroso
– Tx só libera TODOS os seus bloqueios (S e X) após executar commit ou 
abort
– Vantagem: 
• Menos overhead para Tx, já que não há esforço para liberar bloqueios 
antes do final.
– Desvantagem: 
• Não está livre de deadlocks
Outras Técnicas de 2PLOutras Técnicas de 2PL
•2PL – Quadro comparativo
T1 SEM ADOTAR 
PROTOCOLO 2PL
T1 COM 2PL 
BÁSICO
T1 COM 2PL 
CONSERVADOR
T1 COM 2PL 
ESTRITO
T1 COM 2PL 
RIGOROSO
READ_LOCK(Y) READ_LOCK(Y) READ_LOCK(Y) READ_LOCK(Y) READ_LOCK(Y)
READ_ITEM(Y) READ_ITEM(Y) WRITE_LOCK(X) READ_ITEM(Y) READ_ITEM(Y)
UNLOCK(Y) WRITE_LOCK(X) READ_ITEM(Y) WRITE_LOCK(X) WRITE_LOCK(X)
WRITE_LOCK(X) UNLOCK(Y) UNLOCK(Y) UNLOCK(Y)
* NÃO DESBLOQUEIA 
O ELEMENTO DE 
BLOQUEIO 
COMPARTILHADO
READ_ITEM(X) READ_ITEM(X) READ_ITEM(X) READ_ITEM(X) READ_ITEM(X)
X=X+Y X=X+Y X=X+Y X=X+Y X=X+Y
WRITE_ITEM(X) WRITE_ITEM(X) WRITE_ITEM(X) WRITE_ITEM(X) WRITE_ITEM(X)
UNLOCK(X) UNLOCK(X) UNLOCK(X)
* NÃO DESBLOQUEIA 
O ELEMENTO DE 
BLOQUEIO 
EXCLUSIVO
* NÃO DESBLOQUEIA 
O ELEMENTO DE 
BLOQUEIO 
EXCLUSIVO
COMMIT COMMIT COMMIT COMMIT COMMIT
Referencias bibliográficas
Sistemas de banco de dados (Elmasri / Navathe)
Capítulo 20
	Slide 1
	Catálogos
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Referencias bibliográficas