Baixe o app para aproveitar ainda mais
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
Compartilhar