DBMS Distribuído - Tratamento de Deadlock
Este capítulo apresenta uma visão geral dos mecanismos de tratamento de deadlock em sistemas de banco de dados. Vamos estudar os mecanismos de tratamento de deadlock no sistema de banco de dados centralizado e distribuído.
O que são deadlocks?
Deadlock é um estado de um sistema de banco de dados com duas ou mais transações, quando cada transação está esperando por um item de dados que está sendo bloqueado por alguma outra transação. Um deadlock pode ser indicado por um ciclo no gráfico de espera. Este é um gráfico direcionado no qual os vértices denotam transações e as arestas denotam esperas por itens de dados.
Por exemplo, no gráfico de espera a seguir, a transação T1 está aguardando o item de dados X que está bloqueado por T3. T3 está esperando por Y que está bloqueado por T2 e T2 está esperando por Z que está bloqueado por T1. Conseqüentemente, um ciclo de espera é formado e nenhuma das transações pode continuar em execução.
Tratamento de deadlock em sistemas centralizados
Existem três abordagens clássicas para tratamento de deadlock, a saber -
- Prevenção de deadlock.
- Prevenção de deadlock.
- Detecção e remoção de deadlock.
Todas as três abordagens podem ser incorporadas em um sistema de banco de dados centralizado e distribuído.
Prevenção de deadlock
A abordagem de prevenção de conflito não permite que nenhuma transação adquira bloqueios que levarão a bloqueios. A convenção é que quando mais de uma transação solicita o bloqueio do mesmo item de dados, apenas uma delas recebe o bloqueio.
Um dos métodos de prevenção de deadlock mais populares é a pré-aquisição de todos os bloqueios. Nesse método, uma transação adquire todos os bloqueios antes de começar a executar e retém os bloqueios por toda a duração da transação. Se outra transação precisar de qualquer um dos bloqueios já adquiridos, ela deve esperar até que todos os bloqueios de que precisa estejam disponíveis. Usando essa abordagem, o sistema é impedido de entrar em conflito, já que nenhuma das transações em espera está segurando qualquer bloqueio.
Prevenção de deadlock
A abordagem de prevenção de deadlock trata os deadlocks antes que eles ocorram. Ele analisa as transações e os bloqueios para determinar se a espera leva ou não a um conflito.
O método pode ser resumido da seguinte forma. As transações começam a ser executadas e solicitam itens de dados que precisam ser bloqueados. O gerenciador de bloqueio verifica se o bloqueio está disponível. Se estiver disponível, o gerenciador de bloqueio aloca o item de dados e a transação adquire o bloqueio. No entanto, se o item estiver bloqueado por alguma outra transação em modo incompatível, o gerenciador de bloqueio executa um algoritmo para testar se manter a transação em estado de espera causará um deadlock ou não. Conseqüentemente, o algoritmo decide se a transação pode esperar ou se uma das transações deve ser abortada.
Existem dois algoritmos para este propósito, a saber wait-die e wound-wait. Vamos supor que existam duas transações, T1 e T2, onde T1 tenta bloquear um item de dados que já está bloqueado por T2. Os algoritmos são os seguintes -
Wait-Die- Se T1 for mais antigo que T2, T1 tem permissão para esperar. Caso contrário, se T1 for mais novo que T2, T1 será abortado e reiniciado posteriormente.
Wound-Wait- Se T1 for mais antigo que T2, T2 é abortado e reiniciado posteriormente. Caso contrário, se T1 for mais jovem que T2, T1 terá permissão para esperar.
Detecção e remoção de deadlock
A abordagem de detecção e remoção de deadlock executa um algoritmo de detecção de deadlock periodicamente e remove o deadlock caso haja um. Ele não verifica se há conflito quando uma transação faz uma solicitação de bloqueio. Quando uma transação solicita um bloqueio, o gerenciador de bloqueio verifica se ele está disponível. Se estiver disponível, a transação pode bloquear o item de dados; caso contrário, a transação pode esperar.
Como não há precauções ao conceder solicitações de bloqueio, algumas das transações podem entrar em conflito. Para detectar deadlocks, o gerenciador de bloqueio verifica periodicamente se o wait-forraph tem ciclos. Se o sistema estiver em deadlock, o gerenciador de bloqueio escolhe uma transação vítima de cada ciclo. A vítima é abortada e revertida; e reiniciado mais tarde. Alguns dos métodos usados para a seleção de vítimas são -
- Escolha a transação mais recente.
- Escolha a transação com menos itens de dados.
- Escolha a transação que realizou o menor número de atualizações.
- Escolha a transação com menos sobrecarga de reinicialização.
- Escolha a transação que é comum a dois ou mais ciclos.
Essa abordagem é adequada principalmente para sistemas com poucas transações e onde uma resposta rápida para solicitações de bloqueio é necessária.
Tratamento de deadlock em sistemas distribuídos
O processamento de transações em um sistema de banco de dados distribuído também é distribuído, ou seja, a mesma transação pode ser processada em mais de um site. As duas principais preocupações de tratamento de deadlock em um sistema de banco de dados distribuído que não estão presentes em um sistema centralizado sãotransaction location e transaction control. Uma vez que essas questões são tratadas, os deadlocks são tratados por meio de qualquer prevenção de deadlock, prevenção de deadlock ou detecção e remoção de deadlock.
Localização da transação
As transações em um sistema de banco de dados distribuído são processadas em vários sites e usam itens de dados em vários sites. A quantidade de processamento de dados não é distribuída uniformemente entre esses sites. O período de tempo de processamento também varia. Assim, a mesma transação pode estar ativa em alguns sites e inativa em outros. Quando duas transações conflitantes estão localizadas em um site, pode acontecer que uma delas esteja no estado inativo. Essa condição não ocorre em um sistema centralizado. Essa preocupação é chamada de problema de localização da transação.
Essa preocupação pode ser tratada pelo modelo Daisy Chain. Nesse modelo, uma transação carrega certos detalhes quando se move de um site para outro. Alguns dos detalhes são a lista de tabelas necessárias, a lista de sites necessários, a lista de tabelas e sites visitados, a lista de tabelas e sites que ainda não foram visitados e a lista de bloqueios adquiridos com tipos. Depois que uma transação termina por confirmação ou aborto, as informações devem ser enviadas a todos os sites em questão.
Controle de transação
O controle de transações está relacionado à designação e controle dos locais necessários para o processamento de uma transação em um sistema de banco de dados distribuído. Existem muitas opções quanto à escolha de onde processar a transação e como designar o centro de controle, como -
- Um servidor pode ser selecionado como o centro de controle.
- O centro de controle pode viajar de um servidor para outro.
- A responsabilidade de controlar pode ser compartilhada por vários servidores.
Prevenção de deadlock distribuída
Assim como na prevenção de deadlock centralizada, na abordagem de prevenção de deadlock distribuída, uma transação deve adquirir todos os bloqueios antes de começar a ser executada. Isso evita bloqueios.
O site onde a transação entra é designado como o site de controle. O site de controle envia mensagens aos sites onde os itens de dados estão localizados para bloquear os itens. Em seguida, ele aguarda a confirmação. Quando todos os sites confirmaram que bloquearam os itens de dados, a transação é iniciada. Se algum site ou link de comunicação falhar, a transação terá que esperar até que seja reparada.
Embora a implementação seja simples, essa abordagem tem algumas desvantagens -
A pré-aquisição de bloqueios exige muito tempo para atrasos de comunicação. Isso aumenta o tempo necessário para a transação.
Em caso de falha de site ou link, uma transação deve aguardar muito tempo para que os sites se recuperem. Enquanto isso, nos sites em execução, os itens estão bloqueados. Isso pode impedir a execução de outras transações.
Se o site de controle falhar, ele não poderá se comunicar com os outros sites. Esses sites continuam a manter os itens de dados bloqueados em seu estado bloqueado, resultando em bloqueio.
Prevenção de deadlock distribuído
Como no sistema centralizado, a prevenção de deadlock distribuída lida com o deadlock antes da ocorrência. Além disso, em sistemas distribuídos, os problemas de localização e controle de transações precisam ser resolvidos. Devido à natureza distribuída da transação, os seguintes conflitos podem ocorrer -
- Conflito entre duas transações no mesmo site.
- Conflito entre duas transações em sites diferentes.
Em caso de conflito, uma das transações pode ser abortada ou permitida a aguardar de acordo com algoritmos de wait-die distribuído ou algoritmos de espera-ferida distribuída.
Vamos supor que existam duas transações, T1 e T2. T1 chega ao Site P e tenta bloquear um item de dados que já está bloqueado por T2 naquele site. Portanto, há um conflito no Site P. Os algoritmos são os seguintes -
Distributed Wound-Die
Se T1 for mais antigo que T2, T1 terá permissão para esperar. T1 pode retomar a execução depois que o Site P recebe uma mensagem de que T2 foi confirmado ou abortado com sucesso em todos os sites.
Se T1 for mais jovem que T2, T1 será abortado. O controle de concorrência no Site P envia uma mensagem a todos os sites onde T1 visitou para abortar T1. O site de controle notifica o usuário quando T1 foi abortado com sucesso em todos os sites.
Distributed Wait-Wait
Se T1 for mais antigo que T2, T2 precisa ser abortado. Se T2 estiver ativo no Site P, o Site P aborta e reverte T2 e então transmite esta mensagem para outros sites relevantes. Se T2 saiu do Site P, mas está ativo no Site Q, o Site P transmite que T2 foi abortado; O site L então aborta e reverte T2 e envia esta mensagem a todos os sites.
Se T1 for mais novo que T1, T1 terá permissão para esperar. T1 pode retomar a execução após o Site P receber uma mensagem de que T2 concluiu o processamento.
Detecção de deadlock distribuído
Assim como a abordagem de detecção de deadlock centralizada, os deadlocks podem ocorrer e são removidos se detectados. O sistema não executa nenhuma verificação quando uma transação faz uma solicitação de bloqueio. Para implementação, são criados gráficos de espera globais. A existência de um ciclo no gráfico de espera global indica deadlocks. No entanto, é difícil detectar deadlocks, pois a transação espera por recursos na rede.
Como alternativa, os algoritmos de detecção de deadlock podem usar temporizadores. Cada transação está associada a um cronômetro que é definido para um período de tempo em que a transação deve terminar. Se uma transação não for concluída neste período de tempo, o cronômetro dispara, indicando um possível deadlock.
Outra ferramenta usada para tratamento de deadlock é um detector de deadlock. Em um sistema centralizado, há um detector de deadlock. Em um sistema distribuído, pode haver mais de um detector de deadlock. Um detector de deadlock pode encontrar deadlocks para os sites sob seu controle. Existem três alternativas para detecção de deadlock em um sistema distribuído, a saber.
Centralized Deadlock Detector - Um site é designado como detector de deadlock central.
Hierarchical Deadlock Detector - Vários detectores de deadlock são organizados em hierarquia.
Distributed Deadlock Detector - Todos os sites participam na detecção de deadlocks e removê-los.