Banco de dados 2 - Deadlock

Prévia do material em texto

UNIVERSIDADE REGIONAL INTEGRADA DO ALTO URUGUAI E DAS MISSÕES DEPARTAMENTO DAS ENGENHARIAS E CIÊNCIA DA COMPUTAÇÃO (URI - ERECHIM)
Bruno Beltrame
Cristian Abranchuck
Jackson Felipe Magnabosco
Teyson Lorenzon
Vinicius Psidonik
DEADLOCKS
BANCO DE DADOS II
Erechim – RS
2018
Resumo
Este artigo aborda alguns métodos de tratamento de deadlocks, os quais são: conceito, dando exemplos de condições para que isto ocorra, a detecção e recuperação, mostrando como detectar e recuperar o sistema quando ocorrer um deadlock, como evitar e prevenir deadlocks, citando algumas técnicas normalmente utilizadas.
Abstract:
This article discusses some methods of handling deadlocks, which are: concept, giving examples of conditions for this to occur, detection and recovery, showing how to detect and recover the system when a deadlock occurs, how to avoid and prevent deadlocks, citing some commonly used techniques.
Sumário
1. INTRODUÇÃO	4
2. ESTRATÉGIAS PARA TRATAR O DEADLOCK	5
3. TÉCNICAS DE RECUPERAÇÃO	7
3.1 Falha de Transação	7
3.2 Queda do Sistema	8
3.3 Falha de Disco	8
4. CONCEITOS DE RECUPERAÇÃO	9
4.1 Controle de Acesso	10
4.2 Controle de Interferência	10
4.3 Controle de Fluxo	10
4.4 Criptografia de Dados	10
4.5 Usuários	10
4.6 Domínio de Segurança	11
4.7 Autoridade	11
4.8 Privilégios	11
4.9 Tipos de privilégios discricionários	11
4.10 Revogação de privilégios	12
4.11 Controle de acesso obrigatório e para segurança multinível	12
4.12 Controle de acesso baseado em papéis.	12
5. Recuperação baseada em atualização postergada	12
5.1 Procedimento para recuperação no momento de uma falha	13
6. Recuperação baseada em atualização imediata	13
6.1 Procedimento para recuperação no momento de uma falha:	13
7. CONCLUSÃO	14
8. REFERÊNCIAS	15
	
1. INTRODUÇÃO
	Existem vários recursos nos sistemas de computadores que somente pode ser usado um processo de cada vez, dando como exemplo impressoras e entradas nas tabelas internas do sistema. Caso dois ou mais processos quiserem escrever simultaneamente na mesma impressora, haverá um impasse. Assim, todos os sistemas operacionais devem ter a capacidade de garantir o acesso exclusivo de um processo a certos recursos, mesmo que temporariamente.
2. ESTRATÉGIAS PARA TRATAR O DEADLOCK
Existem dois métodos de tratamento para casos de deadlock. O protocolo de prevenção de deadlock, que garante que o sistema nunca entrará nessa situação, ou podemos esperar o sistema entrar no estado de deadlock, e depois retirá-lo dessa situação, recuperando-o por meio de técnicas de detecção e recuperação de deadlock.
	São dois métodos principais de prevenção:
· Esperar-morrer(wait-die): É baseado em não-preempção, ou seja, quando uma transação T¹ chama um item de dado mantido por T², T¹ esperará somente se possuir um timestamp menor que T² (T¹ é mais antigo que T²). Caso contrário, será revertida(morta).
· Ferir-esperar(wound-wait): Ao contrário do wait-die, o wound-wait é baseado em preempção, ou seja, quando uma transação T¹ chama um item de dado mantido por T², T¹ esperará somente se possuir um timestamp maior que T²(T¹ é mais recente que T²). Caso contrário, T² será desfeita (T¹ irá ferir T²).
Se o sistema não utilizar um protocolo de prevenção ao deadlock, então é utilizado um método para detecção e recuperação. Uma técnica que verifica o estado do sistema, é recorrido periodicamente para conferir se existe um deadlock, em caso de ocorrência, ele tentará se recuperar. Para isso ele precisará:
· Manter informações sobre a alocação corrente dos itens de dados para transações, assim como qualquer solicitação de itens de dados pendente.
· Proporcionar um algoritmo que use essas informações para definir se o sistema entrou efetivamente em deadlock.
· Se recuperar de um deadlock quando o algoritmo de detecção definir que ele ocorreu.
Os deadlocks podem ser precisamente descritos em termos de um gráfico chamado de gráfico de espera. Há um deadlock no sistema se, e somente se, o gráfico de espera contiver um ciclo. Cada transação envolvida em um ciclo está em deadlock. Para detectar deadlocks, o sistema precisa manter o gráfico de espera e, periodicamente, evocar um algoritmo que verifique a existência de ciclos.
Para ilustrar esses conceitos, considere o gráfico de espera abaixo, que exibe a seguinte situação:
A essa altura, o gráfico contém o ciclo: T (26), T (28), T (27), T (26), implicando que as transações T (26), T (27) e T (28) estão todas em deadlock.
Quando um algoritmo d e detecção determina a existência de um deadlock, o sistema precisa recuperar-se desse deadlock. A solução mais comum é reverter uma ou mais transações para quebrar o deadlock. Devem ser tomadas três ações:
1. Selecionar uma vítima. Dado um conjunto de transações em deadlock,
precisamos determinar quais transações (ou transação) serão desfeitas para
quebra do deadlock. Poderíamos reverter as transações que representam o
menor custo. Infelizmente, o termo mínimo custo não é preciso. 
Muitos fatores podem determinar o custo de um rollback, incluindo:
a. A quanto tempo a transação está em processamento e quanto tempo será ainda necessário para que a tarefa seja completada.
b. Quantos itens de dados a transação usou.
c. Quantos itens ainda a transação usará até que se complete.
d. Quantas transações serão envolvidas no rollback.
2. Rollback. Uma vez decidido que uma transação em particular será revertida, precisamos determinar até que ponto ela deverá ser revertida.
Entretanto, é mais eficaz reverter a transação somente o suficiente para a quebra do deadlock.
Mas esse método exige que o sistema mantenha informações adicionais sobre o estado de todas as transações em execução.
3. Inanição. Em um sistema no qual a seleção de vítimas tem por base fatores de custo, pode acontecer de uma mesma transação ser sempre escolhida vítima.
Assim, essa transação nunca se completa. Essa situação é chamada d e inanição.
Precisamos garantir que uma transação seja escolhida vítima somente um número finito de vezes. A solução mais comum é incluir o número de reversão no fator de custos.
3. TÉCNICAS DE RECUPERAÇÃO
Um computador, assim como qualquer outro equipamento, está sujeito a falhas. Quebra de disco, pane elétrica, erro de software, incêndio ou até mesmo sabotagem… Por isso um sistema de banco de dados deve precaver-se para garantir a integridade e durabilidade das transações, a despeito de tais falhas. Uma parte integrante do sistema de banco de dados é o esquema de recuperação que é responsável pela restauração do banco de dados para um estado consistente que havia antes da ocorrência de falha.
Inúmeros tipos de falhas podem ocorrer com um software, e para cada falha há um tratamento diferente.
3.1 Falha de Transação
Dois tipos de erros podem ocasionar uma falha de transação:
· Erro lógico: A transação não pode mais continuar com sua execução normal devido a alguma condição interna, como uma entrada inadequada, um dado não encontrado, overflow ou limite de recurso excedido.
· Erro de Sistema: O sistema entrou em um estado inadequado (deadlock), com isso, uma transação não pode continuar com sua execução normal. A transação, entretanto, pode ser reexecutada posteriormente.
	3.2 Queda do Sistema
Há algum mau funcionamento de hardware ou um bug no software de banco de dados ou no sistema operacional que causou a perda do conteúdo no armazenamento volátil e fez o processamento da transação parar. O conteúdo de armazenamento não-volátil permanece intacto e não corrompido.
3.3 Falha de Disco
Um bloco de disco perde seu conteúdo em função da quebra do cabeçote ou da falha durante uma operação de transferência de dados. São usadas para recuperação do sistema após a falha, as cópias dos dados em outros discos ou backups de arquivos em meios terciários, como fitas.
Para determinar como o sistema deve recuperar-se das falhas, necessitamos identificar os modos de falha possíveis dos equipamentos usados para armazenar dados. Depois, devemos considerar como esses modos de falha afetam o conteúdo do banco dedados. Então, poderemos desenvolver algoritmos para assegurar a consistência do banco de dados e a atomicidade da transação, a despeito das falhas.
 
4. CONCEITOS DE RECUPERAÇÃO
É importante salientar que os detalhes internos de armazenamento, por exemplo, não são descritos no modelo lógico, pois estas informações fazem parte do modelo físico, que nada mais é que a tradução do modelo 	 lógico para a linguagem do software escolhido para implementar o sistema.
Os bancos de dados são utilizados para armazenar diversos tipos de informações, desde dados sobre uma conta de e-mail até dados importantes da Receita Federal. 
A segurança do banco de dados herda as mesmas dificuldades que a segurança da informação enfrenta, que é garantir a integridade, a disponibilidade e a confidencialidade. Um Sistema gerenciador de banco de dados deve fornecer mecanismos que auxiliem nesta tarefa.
	Os bancos de dados SQL implementam mecanismos que restringem ou permitem acessos aos dados de acordo com papeis ou roles fornecidos pelo administrador. O comando GRANT concede privilégios específicos para um objeto (tabela, visão, sequência, banco de dados, função, linguagem procedural, esquema ou espaço de tabelas) para um ou mais usuários ou grupos de usuários.
	A preocupação com a criação e manutenção de ambientes seguros se tornou a ocupação principal de administradores de redes, de sistemas operacionais e de bancos de dados. Pesquisas mostram que a maioria dos ataques, roubos de informações e acessos não- autorizados são feitos por pessoas que pertencentes à organização alvo.
	Por esse motivo, esses profissionais se esforçam tanto para criar e usar artifícios com a finalidade de eliminar os acessos não-autorizados ou diminuir as chances de sucesso das tentativas de invasão (internas ou externas). Os controles de acesso em sistemas de informação devem certificar que todos os acessos diretos ao sistema ocorram exclusivamente de acordo com as modalidades e as regras pré-estabelecidas, e observadas por políticas de proteção.
	De modo geral, os mecanismos de segurança referem-se às regras impostas pelo subsistema de segurança do SGBD, que verifica todas as solicitações de acesso, comparando-as com as restrições de segurança armazenadas no catálogo do sistema. Entretanto existem brechas no sistema e ameaças externas que podem resultar em um servidor de banco de dados comprometido ou na possibilidade de destruição ou no roubo de dados confidenciais.
	As ameaças aos bancos de dados podem resultar na perda ou degradação de alguns ou de todos os objetivos de segurança aceitos, são eles: integridade, disponibilidade, confidencialidade. A integridade do banco de dados se refere ao requisito de que a informação seja protegida contra modificação imprópria.
	A disponibilidade do banco de dados refere-se a tornar os objetos disponíveis a um usuário ou a um programa ao qual eles têm um direito legitimo. A confidencialidade do banco de dados se refere à proteção dos dados contra a exposição não autorizada. O impacto da exposição não autorizada de informações confidenciais pode resultar em perda de confiança pública, constrangimento ou ação legal contra a organização.
4.1 Controle de Acesso
É todo controle feito quanto ao acesso ao BD, impondo regras de restrição, através das contas dos usuários. O Administrador do BD (DBA) é o responsável superior por declarar as regras dentro do SGBD. Ele é o responsável por conceder ou remover privilégios, criar ou excluir usuários, e atribuição de um nível de segurança aos usuários do sistema, de acordo com a política da empresa.
4.2 Controle de Interferência
É um mecanismo de segurança para banco de dados estatísticos que atua protegendo informações estatísticas de um indivíduo ou de um grupo. Bancos de dados estatísticos são usados principalmente para produzir estatísticas sobre várias populações.
O banco de dados pode conter informações confidenciais sobre indivíduos. Os usuários têm permissão apenas para recuperar informações estatísticas sobre populações e não para recuperar dados individuais, como, por exemplo, a renda de uma pessoa específica.
4.3 Controle de Fluxo
É um mecanismo que previne que as informações fluam por canais secretos e violem a política de segurança ao alcançarem usuários não autorizados. Ele regula a distribuição ou fluxo de informação entre objetos acessíveis. Um fluxo entre o objeto A e o objeto B ocorre quando um programa lê valores de A e escreve valores em B. 
Os controles de fluxo têm a finalidade de verificar se informações contidas em alguns objetos não fluem explícita ou implicitamente para objetos de menor proteção. Dessa maneira, um usuário não pode obter indiretamente em B aquilo que ele ou ela não puder obter diretamente de A.
4.4 Criptografia de Dados
Você pode ler aqui um pouco mais sobre criptografia. É uma medida de controle final, utilizada para proteger dados sigilosos que são transmitidos por meio de algum tipo de rede de comunicação. Ela também pode ser usada para oferecer proteção adicional para que partes confidenciais de um banco de dados não sejam acessadas por usuários não autorizados. Para isso, os dados são codificados através da utilização de algum algoritmo de codificação. Assim, um usuário não autorizado terá dificuldade para decifrá-los, mas os usuários autorizados receberão chaves para decifrar esses dados. A criptografia permite o disfarce da mensagem para que, mesmo com o desvio da transmissão, a mensagem não seja revelada.
4.5 Usuários
	Abrange usuários e esquema do banco de dados onde cada banco de dados Oracle tem uma lista de nomes de usuários. Para acessar um banco de dados, um usuário deve usar um aplicativo desse tipo e tentar uma conexão com um nome de usuário válido. Cada nome tem uma senha associada para evitar o uso sem autorização.
	Devem ser implementados ainda diferentes perfis de usuário para diferentes tarefas no Oracle, tendo em vista que cada aplicação/usuário tem a sua necessidade de acesso. Existe ainda a possibilidade de proteger os perfis com senha, o que é uma excelente medida. Além dessas medidas, o uso de cotas aumenta a restrição de espaço em disco a ser utilizado por usuários/aplicativos.
4.6 Domínio de Segurança
	Onde cada usuário tem um domínio de segurança, um conjunto de propriedades que determinam coisas como ações (privilégios e papéis) disponíveis para o usuário; cota de tablespaces (espaço disponível em disco) do usuário; limites de recursos de sistema do usuário.
As tabelas (tablespaces) do sistema, como a system, devem ser protegidas de acessos de usuários diferentes dos usuários de sistema. A liberação de escrita e alteração de dados em tais tabelas é muito comum em ambientes de teste, onde os programadores e DBAs tomam tal atitude para evitar erros de aplicação por falta de privilégios. Porém, em ambientes de produção, tal medida é totalmente desaconselhável.
4.7 Autoridade
As autoridades fornecem um método de agrupar privilégios e controlar o nível de acesso dos administradores e operadores da base de dados com relação à manutenção e operações permitidas. As especificações da base de dados estão armazenadas em catálogos da própria base de dados. As autoridades do sistema estão associadas a membros de grupos e armazenados no arquivo de configuração administrativa do banco de dados. Este arquivo define as concessões de acesso e o que poderá ser executado de acordo com cada grupo.
4.8 Privilégios
Os privilégios são permissões únicas dadas a cada usuário ou grupo. Eles definem permissões para tipos de autorização. Pelos privilégios é possível autorizar o usuário a modificar ou alcançar determinado recurso do Banco de Dados.
Os privilégios também são armazenados em catálogos do próprio Banco de Dados, visto que os grupos de autoridade por já possuírem grupos predefinidos de privilégio concedem implicitamente privilégios a seus membros.
4.9 Tipos de privilégios discricionários
O SGBD deve oferecer acesso seletivo a cada relação do banco de dados baseando-se em contas específicas. As operações também podemser controladas; assim, possuir uma conta não necessariamente habilita o possuidor a todas as funcionalidades oferecidas pelo SGBD. Informalmente existem dois níveis para a atribuição de privilégios para o uso do sistema de banco de dados:
O nível de conta: Nesse nível, o DBA estabelece os privilégios específicos que cada conta tem, independente das relações no banco de dados.
O nível de relação (ou tabela): Nesse nível, o DBA pode controlar o privilégio para acessar cada relação ou visão individual no banco de dados.
4.10 Revogação de privilégios
Em alguns casos, interessa conceder um privilégio temporário a um usuário. Por exemplo, o proprietário de uma relação pode querer conceder o privilégio SELECT a um usuário para uma tarefa específica e depois revogar aquele privilégio quando a tarefa estiver completada. Por isso, é necessário um mecanismo para a revogação de privilégios. Em SQL, um comando REVOKE é introduzido com o intento de cancelar privilégios.
4.11 Controle de acesso obrigatório e para segurança multinível
Neste método, o usuário não tem um meio termo, ou ele tem ou não tem privilégios, sendo utilizado normalmente em BD que classificam dados de usuários, onde é necessário um nível a mais de segurança. A maioria dos SGBDs não oferecem esse tipo de controle de acesso obrigatório, ficando com os controles discricionários ditos anteriormente. Normalmente são utilizados em sistemas governamentais, militares ou de inteligência, assim como industriais e corporativas.
As classes de segurança típicas são altamente sigilosas (top secret, TS), secreta (secret, S), confidencial (confidencial) (C) e não classificada (unclassified, U), em que TS é o nível mais alto e U é o mais baixo.
De uma forma geral, os mecanismos de controle de acesso obrigatório impõem segurança multinível, pois exigem a classificação de usuários e de valores de dados em classes de segurança e impõem as regras que proíbem o fluxo de informação a partir dos níveis de segurança mais altos para os mais baixos.
4.12 Controle de acesso baseado em papéis.
	É uma abordagem para restringir o acesso a usuários autorizados e uma alternativa aos sistemas de controles de acesso do tipo MAC e DAC. O conceito de controle de acesso baseado em papéis surgiu com os primeiros sistemas computacionais multiusuários interativos. A ideia central do RBAC é que permissões de acesso são associadas a papéis, e estes papéis são associados a usuários. Papéis são criados de acordo com os diferentes cargos em uma organização, e os usuários são associados a papéis de acordo.
5. Recuperação baseada em atualização postergada
A técnica de recuperação baseada na atualização postergada impede qualquer atualização no banco de dados até que a transação complete sua execução com êxito e atinja seu ponto de confirmação.
Durante a execução da transação, as atualizações são registradas somente no log e nos buffers do cache. Se uma transação falha antes de atingir seu ponto de confirmação, não há necessidade de desfazer nenhuma operação, porque a transação não afetou, de modo algum, o banco de dados armazenado em disco.
Depois que a transação atinge seu ponto de confirmação e o log é forçosamente gravado no disco, as atualizações são registradas no banco de dados. Na prática, é inviável devido ao tamanho do cache necessário para manipular grandes transações.
A técnica é conhecida como algoritmo de recuperação NO-UNDO / REDO (não-desfazer / refazer). Não é necessário desfazer porque o banco de dados não é atualizado antes do commit, mas pode ser necessário refazer se o sistema falhar depois do commit, porém antes que todas as suas alterações tenham sido registradas no banco de dados. As operações da transação são refeitas a partir das entradas do log.
5.1 Procedimento para recuperação no momento de uma falha
Todas as operações de escrita das transações confirmadas devem ser refeitas, a partir do log na ordem em que foram gravadas, utilizando o procedimento REDO. As transações que estavam ativas e não chegaram ao commit são efetivamente canceladas e devem ser re-submetidas.
A operação REDO pode se tornar mais eficiente quando um item de dado X for atualizado mais de uma vez por transações confirmadas desde o último checkpoint, mas só é necessário refazer a última atualização de X a partir do log (as outras atualizações seriam subscritas pelo último REDO).
O processo inicia-se a partir do final do log, sempre que um item for refeito, ele é acrescentado a uma lista de itens refeitos e antes de refazer a operação aplicada a um item, a lista é verificada, se o item aparecer na lista, não é novamente refeito, uma vez que seu último valor já foi recuperado.
6. Recuperação baseada em atualização imediata
A técnica de recuperação baseada em atualização imediata faz com que o banco de dados seja ou não "imediatamente" atualizado, quando uma transação emite um comando de atualização, sem ter que esperar que a mesma atinja seu ponto de confirmação. O processo de registro adiado em log deve ser usado para permitir recuperação em caso de falha. 
Existem duas categorias de algoritmos: 
1.	Algoritmo de recuperação UNDO / NO-REDO: Não há necessidade de refazer operações se a técnica de recuperação garantir que todas as atualizações de uma transação sejam registradas no banco de dados em disco antes do commit da transação.
2.	Algoritmo de recuperação UNDO / REDO: Pode ser necessário desfazer e refazer operações se a técnica de recuperação permitir que a transação chegue ao seu ponto de confirmação antes que todas as alterações sejam gravadas no banco de dados.
O sistema deve manter duas listas de transações: uma lista de transações confirmadas desde o último checkpoint (lista de commit) e uma lista de transações ativas (lista ativa).
6.1 Procedimento para recuperação no momento de uma falha:
Todas as operações de escrita das transações ativas devem ser desfeitas, a partir do log na ordem inversa em que foram gravadas, utilizando o procedimento UNDO. Tais transações são efetivamente canceladas e re-submetidas, o processo de desfazer as operações de uma ou mais transações do log deve acontecer na ordem inversa da ordem em que as operações foram gravadas no log.
Todas as operações de escrita das transações confirmadas devem ser refeitas, a partir do log na ordem em que foram gravadas, utilizando o procedimento REDO. Para melhorar eficiência, pode-se partir do final do log.
 
7. CONCLUSÃO
Deadlock é um problema potencial em qualquer sistema e banco de dados. Um estado de deadlock ocorre quando dois ou mais processos estão esperando indefinidamente por um evento que só pode ocorrer por um dos processos em espera. Existem alguns métodos para tratar deadlocks, os quais foram citados neste trabalho: detecção e recuperação, evitar deadlock e prevenção de deadlock.
Uma das estratégias mais simples de tratar deadlock, seria ignorá-lo, porém, é necessária uma análise das necessidades da empresa, para o implemento ou não das estratégias de tratamento do deadlock, assim como, avaliar o custo/benefício que essas implantações podem gerar.
8. REFERÊNCIAS
TAVARES, G. Recuperação de Falhas. Disponível em: <http://www.decom.ufop.br/guilherme/BCC441/geral/bd2_recuperacao-de-falhas.pdf> Acesso em: 14/06/2018.
MACHADO, Francis B.; MAIA, Luiz P.; Arquitetura de Sistemas Operacionais – 3a Edição – Machado/Maia. Disponível em:<http://www.inf.puc-rio.br/~francis/aso3ed/solexerc-v3.2-Jan-2005.pdf>. Acesso em: 25 março 2018.
LOPES, Ever.; Deadlock. Disponível em:<https://www.webartigos.com/artigos/deadlock/3416>. Acesso em: 25 março 2018.
Tanenbaum, Andrew S.. (2003) "Sistemas Operacionais Modernos", Editora Prentice Hall – 2 ed. – São Paulo.
Silberschatz, Abraham; Galin, Peter; Gagne, Grag. (2000). "Sistemas Operacionais: conceitos e aplicações", Editora Elsvier – 8 reimpressões – Rio de Janeiro.
Universidade Federal de Ouro Preto – UFOP; Instituto de Ciências Exatas e Biológicas – ICEB; Departamento de Computação – DECOM <www.decom.ufop.br/guilherme/BCC441/geral/bd2_recuperacao-de-falhas.pdf>KORTH, H.F. e SILBERSCHATZ, A.; Sistemas de Bancos de Dados, Makron Books, 2a. edição revisada, 1994.
 
DATE, C.J.; Int. a Sistemas de Bancos de Dados, tradução da 4ª edição norte-americana, Editora Campus, 1991.
2