Baixe o app para aproveitar ainda mais
Prévia do material em texto
Alocação de recursos e deadlocks Apresentação Sabe quando você está no trânsito e está tudo congestionado? Então, essa situação remete justamente ao que é um deadlock, com a diferença de que, logicamente, isso ocorre com recursos computacionais. O deadlock acaba sendo consequência do compartilhamento de recursos entre processos concorrentes. Por isso acontece o congestionamento: os processos necessitam desses recursos quase que simultaneamente. É muita requisição ocorrendo e os sistemas operacionais devem conseguir gerir todo esse caos. Nesta Unidade de Aprendizagem, você verá como acontece a alocação de recursos e, consequentemente, o deadlock. Para isso, irá aprender a reconhecer as técnicas existentes para que ele seja prevenido. Além disso, você também saberá quais são as técnicas para recuperação do deadlock, ainda que ele seja passível de ocorrer a todo momento, uma vez que deve ser levada em consideração a complexidade atrelada cada vez mais aos sistemas operacionais. Bons estudos. Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados: Analisar os princípios de alocação de recursos e deadlock.• Reconhecer técnicas de prevenção ao deadlock.• Identificar técnicas de recuperação do deadlock.• Desafio Os computadores oferecem diversos recursos diferentes e, muitas vezes, vários deles são utilizados ao mesmo tempo. A cada clique ou tecla acionada, existem muitas operações ocorrendo por trás, ou seja, entre o hardware e o software utilizado que, geralmente, é o sistema operacional. Esse sistema é responsável pela comunicação entre os usuários e a máquina. O deadlock ocorre quando diferentes recursos são solicitados por operações computacionais. Por isso, é importante ficar atentos às operações executadas pela máquina quase que simultaneamente, como imprimir algo, realizar uma cópia, dentre outras. Baseado nisso, imagine o seguinte: em seu trabalho, Marcelo precisará realizar alguns procedimentos com o auxílio de um computador. A princípio, ele necessita fazer a cópia de dados de um drive de DVD para um arquivo em disco. Além disso, precisa classificar o arquivo e, por fim, imprimir os resultados. Considerando esse contexto, quais seriam os procedimentos executados pelo sistema operacional para lidar com as diversas requisições de Marcelo? Infográfico O deadlock pode ser visualizado como um certo "bloqueio": ele impede que um recurso seja utilizado por mais de um processo ao mesmo tempo. Dessa forma, os processos geralmente aguardam até que os recursos que desejam sejam liberados para uso. O sistema operacional é responsável pela organização de todos esses procedimentos. A possibilidade de ocorrência de um deadlock leva ao seguinte questionamento: o que poderia ser feito para que isso fosse evitado? Para tentar responder a essa pergunta, no Infográfico a seguir, você verá as quatro condições que, juntas, ocasionam um deadlock. Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar. https://statics-marketplace.plataforma.grupoa.education/sagah/3afe08b6-2c13-485f-a704-3ce3be520743/6c5328ee-c50c-4773-bcd2-f52673dcb8ea.png Conteúdo do livro O deadlock é uma atividade que pode ocorrer quando recursos estão sendo acessados por um ou mais processos. É necessário ter em mente que, apesar de o sistema operacional apresentar controle sobre tudo que é executado na máquina diante das requisições do usuário, em alguns momentos podem ocorrer eventos inesperados, e o deadlock é um deles. No capítulo Alocação de recursos e deadlocks, da obra Sistemas operacionais, você verá conceitos acerca do tema, além de aprender como prevenir e como sair de um deadlock quando ele ocorrer. SISTEMAS OPERACIONAIS Izabelly Soares de Morais Alocação de recursos e deadlocks Objetivos de aprendizagem Ao final deste texto, você deve apresentar os seguintes aprendizados: � Identificar os princípios de alocação de recursos e deadlock. � Reconhecer técnicas de prevenção ao deadlock. � Identificar técnicas de recuperação do deadlock. Introdução Vamos analisar nossas necessidades atuais e verificar quais atividades de seu cotidiano dependem de um recurso computacional? Aposto que quase todas, já que, hoje em dia, mal conseguimos decorar nosso próprio número telefônico. Neste capítulo, você vai lidar com alguns contextos voltados para a alocação de recursos pelos processos que executamos ao utilizarmos as funcionalidades oferecidas pelo sistema operacional que utilizamos. Você vai conhecer também os principais conceitos que tratam de um evento que pode ou não ocorrer — dependendo da demanda de acesso aos recursos — e que pode paralisar um computador: o deadlock. Além dos motivos que podem ocasionar este fator, você vai aprender sobre prevenção e recuperação de um deadlock. Alocação de recursos e deadlock Conforme Silberschatz, Galvin e Gagne (2015), talvez a melhor ilustração de um deadlock possa ser extraída de uma lei outorgada pela legislatura do Kansas, no início do século XX. Ela dizia, em parte: “Quando dois trens se aproximam um do outro em um cruzamento, ambos devem parar completamente e nenhum dos dois deve ser posto em marcha novamente até que o outro tenha partido.” O relato anterior se refere ao momento em que os processos solicitam, quase simultaneamente, acesso ao mais variado tipo de recursos. Complementando a analogia, imagine que você está no trânsito, em horário de pico, num momento em que todos estão tentando se locomover por um único caminho. Aqui, caracteriza-se, claramente, um congestionamento no trânsito. Ainda sob a ótica de Silberschatz, Galvin e Gagne (2015), um processo deve solicitar um recurso antes de usá-lo e deve liberar o recurso após. O processo pode solicitar tantos recursos quantos precisar para executar sua tarefa. É claro que o número de recursos solicitados não pode exceder o número total de recursos disponíveis no sistema. Em outras palavras, um processo não pode solicitar três impressoras, se o sistema tem apenas duas. Sob condições normais de operação, um processo pode utilizar um recurso obedecendo somente à seguinte sequência: 1. Solicitação — o processo solicita o recurso. Se a solicitação não puder ser atendida imediatamente (por exemplo, se o recurso estiver sendo usado por outro processo), o processo solicitante deve esperar até que possa adquirir o recurso. 2. Uso — o processo pode operar sobre o recurso (por exemplo, se o recurso for uma impressora, o processo pode imprimir na impressora). 3. Liberação — o processo libera o recurso. Deadlock é a situação em que um processo aguarda por um recurso que nunca estará disponível ou um evento que não ocorrerá. Essa situação é consequência, na maioria das vezes, do compartilhamento de recursos, como dispositivos, arquivos e registros, entre processos concorrentes em que a exclusão mútua é exigida. O problema do deadlock torna-se cada vez mais frequente e crítico na medida em que os sistemas operacionais evoluem no sentido de implementar o paralelismo de forma intensiva e permitir a alocação dinâmica de um número ainda maior de recursos (MACHADO; MAIA, 2013, p. 119). Na Figura 1, a seguir, o autor retrata bem a situação em que ocorre um deadlock. Alocação de recursos e deadlocks2 Figura 1. Espera circular. Fonte: Machado e Maia (2013, p.119). Ainda conforme Machado e Maia (2013, p. 119), a figura acima, ilustra graficamente o problema do deadlock entre os processos PA e PB, quando utilizam os recursos R1 e R2. Inicialmente, PA obtêm acesso exclusivo de R1, da mesma forma que PB obtêm de R2. Durante o processamento, PA necessita de R2 para poder prosseguir. Como R2 está alocado a PB, PA ficará aguardando que o recurso seja liberado. Em seguida, PB necessita utilizar R1 e, da mesma forma, ficará aguardando até que PA o libere. Como cada processo está esperando que o outro libere o recurso alocado, é estabelecida uma condição conhecida comoespera circular, caracterizando uma situação de deadlock. O exemplo retratado na Figura 1 traz uma demonstração bem simples de uma deadlock. Sabemos, porém, que os sistemas operacionais estão a cada dia mais complexos, disponibilizando mais funcionalidades aos usuários. Dessa forma, é natural que, em ambientes de multiprogramação, diversos processos sejam executados quase que simultaneamente e que suas funcionalidades acabem necessitando, consequentemente, de muito mais recursos. 3Alocação de recursos e deadlocks A situação denominada de deadlock tem início quando um processo ne- cessita de um recurso e realiza sua solicitação. Caso os recursos estejam disponíveis, o processo irá entrar em estado denominado de espera. Nesse estado, geralmente aguarda que ocorra algo como, por exemplo, o recebimento de um sinal, ou a finalização de um evento de entrada e saída. Nem sempre, porém, o processo consegue voltar ao estado anterior, ou seja, ao que ele estava antes de entrar em espera, já que os recursos que ele havia solicitado se encontram reservados para outros processos que também estavam em espera. Para que ocorra a situação de deadlock, quatro condições são necessárias simultaneamente (COFFMAN; ELPHICK; SHOSHANI, 1971 apud MA- CHADO; MAIA, 2013, p. 120), como observa-se a seguir. 1. Exclusão mútua — cada recurso só pode estar alocado a um único processo em um determinado instante. 2. Espera por recurso — um processo, além dos recursos já alocados, pode estar esperando por outros recursos. 3. Não preempção — recursos concedidos previamente a um processo não podem ser tomados à força desse processo, eles devem ser explicitamente liberados pelo processo que os retém. 4. Espera circular — um processo pode ter de esperar por um recurso alocado a outro processo, e vice-versa. Técnicas para prevenção de deadlock Anteriormente, listamos as quatro condições para que o deadlock ocorra. Como prevenção, devemos ter em mente que, caso alguma destas quatro condições não ocorra, também o deadlock não ocorre. Portanto, de acordo com Silbers- chatz, Galvin e Gagne (2015), algumas situações em relação a cada condição citada anteriormente, previnem que haja o deadlock, como listamos abaixo: � Exclusão mútua — a condição de exclusão mútua deve estar presente para que o deadlock aconteça. Isto é, pelo menos um recurso deve ser não compartilhável. Recursos compartilháveis, por outro lado, não requerem acesso mutuamente exclusivo e, portanto, não podem estar envolvidos em um deadlock. Machado e Maia (2013, p. 120) comple- mentam as ideias de Silberschatz, Galvin e Gagne (2015) relatando que a ausência da primeira condição (exclusão mútua) certamente acaba com o problema do deadlock, pois nenhum processo terá que esperar Alocação de recursos e deadlocks4 para ter acesso a um recurso, mesmo que já esteja sendo utilizado por outro processo. � Retenção e espera — para assegurar que a condição de retenção e espera nunca ocorra no sistema, devemos garantir que, sempre que um processo solicitar um recurso, ele não esteja retendo qualquer outro recurso. Um protocolo que podemos usar requer que cada processo solicite e receba todos os seus recursos antes de começar a ser executado. Podemos implementar essa providência requerendo que as chamadas de sistema que solicitem recursos para um processo precedam todas as outras chamadas de sistema. � Inexistência de preempção — se um processo está retendo alguns re- cursos e solicita outro recurso que não possa ser alocado imediatamente a ele (isto é, o processo deve esperar), então todos os recursos que o processo esteja retendo no momento sofrem preempção. � Espera circular — a quarta e última condição para a ocorrência de deadlocks é a condição de espera circular. Uma forma de assegurar que essa condição jamais ocorra é impor uma ordem absoluta a todos os tipos de recursos e requerer que cada processo solicite recursos em uma ordem de enumeração crescente. Um método alternativo para impedir deadlocks é requerer informações adicionais sobre como os recursos devem ser solicitados. Por exemplo, em um sistema com um drive de fita e uma impressora, o sistema pode precisar saber que o processo P solicitará primeiro o drive de fita e depois a impressora, antes de liberar os dois recursos, en- quanto o processo Q solicitará primeiro a impressora e então o drive de fita. Com esse conhecimento da sequência completa de solicitações e liberações de cada processo, o sistema pode decidir, para cada solicitação, se o processo deve ou não esperar para que seja evitado um possível deadlock no futuro. Cada solicitação requer que, ao tomar essa decisão, o sistema considere os recursos correntemente disponíveis, os recursos correntemente alocados a cada processo e as futuras solicitações e liberações de cada processo (SILBERSCHATZ; GALVIN; GAGNE, 2015). Podemos acrescentar que existem algumas situações em que o deadlock pode ser evitado. Claro que nem sempre é possível definir com certeza como os processos e seus respectivos recursos serão administrados pelo sistema 5Alocação de recursos e deadlocks operacional, pois existem contextos em que, embora existam padrões esperados de comportamento, estes nem sempre se cumprem. Um estado é seguro se o sistema pode alocar recursos a cada processo (até o seu máximo) em alguma ordem e continuar evitando um deadlock. Mais formalmente, um sistema está em um estado seguro somente se existe uma sequência segura. Um estado seguro não é um estado de deadlock. Inversa- mente, o estado de deadlock é um estado inseguro. Nem todos os estados inseguros são deadlocks. Um estado inseguro pode levar a um deadlock. Enquanto o estado for seguro, o sistema operacional poderá evitar estados inseguros (e deadlocks). Em um estado inseguro, o sistema operacional não pode impedir que os processos solicitem recursos de tal modo que ocorra um deadlock. O comportamento dos processos controla os estados inseguros (SILBERSCHATZ; GALVIN; GAGNE, 2015). Outra possível alternativa retratada pelos autores se refere à alocação de recursos. Podemos contar com um sistema de alocação de recursos com apenas uma instância de cada tipo de recurso. Dessa forma, a alocação de recursos não estaria apta a gerar um deadlock. Algumas outras possíveis soluções podem ser citadas, como a utilização de algoritmo do grafo de alocação de recursos, e nesse contexto, verificar se estss algoritmos trazem a possibilidade de serem aplicáveis em um sistema de alocação de recursos com diversas instâncias referentes a cada tipo de recurso. O algoritmo do grafo de alocação de recursos não é aplicável a um sistema de alocação de recursos com múltiplas instâncias de cada tipo de recurso. O algoritmo do banqueiro possui este nome porque poderia ser usado em um sistema bancário para assegurar que o banco nunca alocasse seu dinheiro disponível de tal modo que não pudesse mais satisfazer as necessidades de todos os seus clientes. Quando um novo processo entra no sistema, ele deve declarar o número máximo de instâncias de cada tipo de recurso de que ele pode precisar. Esse número não pode exceder o número total de recursos no sistema. Quando um usuário solicita um conjunto de recursos, o sistema deve determinar se a alocação desses recursos o deixará em um estado seguro. Se deixar, os recursos serão alocados. Caso contrário, o processo deve esperar até que algum outro processo libere recursos suficientes (SILBERSCHATZ; GALVIN; GAGNE, 2015). Alocação de recursos e deadlocks6 Técnicas para recuperação de deadlock Após a ocorrência do deadlock, o sistema operacional deve possuir meios para se recuperar. Um dos passos que podem ser executados é quebrar a espera circular, já que ela ocorre devido à espera pela liberação dos recursos por parte dos processos. Conforme Machado e Maia (2013, p. 121), a eliminação dos processos envolvidos no deadlock e, consequentemente, a liberação de seus recursos podem não sersimples, dependendo do tipo do recurso envolvido. Se um processo estiver atualizando um arquivo ou imprimindo uma listagem, o sistema deve garantir que esses recursos sejam liberados sem problemas. Os processos eliminados não têm como ser recuperados, porém outros processos, que antes estavam em deadlock, poderão prosseguir a execução. A escolha do processo a ser eliminado é feita, normalmente, de forma aleatória ou, então, com base em algum tipo de prioridade. Este esquema, porém, pode consumir considerável tempo do processador, ou seja, gerar elevado overhead. Complementando as ideias de Machado e Maia (2013), Silberschatz, Galvin e Gagne (2015) afirmam que, quando um algoritmo de detecção determina que existe um deadlock, várias alternativas estão disponíveis. Uma possi- bilidade é informar ao operador que ocorreu um deadlock e deixá-lo lidar com o problema manualmente. Outra possibilidade é permitir que o sistema se recupere do deadlock automaticamente. Há duas opções para a interrupção de um deadlock. Uma é simplesmente abortar um ou mais processos para romper a espera circular. A outra é provocar a preempção de alguns recursos de um ou mais dos processos em deadlock. Para isso, são listadas algumas particularidades referentes a essas duas possibilidades: � Encerramento de processos — para eliminar deadlocks abortando um processo, usamos um entre dois métodos. Nos dois métodos, o sistema reclama todos os recursos alocados aos processos encerrados. ■ Abortar todos os processos em deadlock — esse método claramente romperá o ciclo do deadlock, mas a um alto custo. Os processos em deadlock podem ter sido executados por muito tempo e os resultados dessas computações parciais devem ser descartados e provavelmente terão que ser refeitos posteriormente. ■ Abortar um processo de cada vez até que o ciclo do deadlock seja eliminado — esse método incorre em overhead considerável, já que após cada processo ser abortado, um algoritmo de detecção 7Alocação de recursos e deadlocks de deadlocks deve ser invocado para determinar se algum outro processo ainda está em deadlock. � Preempção de recursos — para eliminar deadlocks usando a preempção de recursos, provocamos a preempção sucessiva de alguns recursos dos processos e damos esses recursos a outros processos até que o ciclo do deadlock seja rompido. Se a preempção for necessária para lidarmos com os deadlocks, então três questões devem ser abordadas: 1. Seleção de uma vítima — Que recursos e que processos devem sofrer preempção? Como no encerramento de processos, devemos determinar a ordem da preempção para minimizar o custo. Fatores de custo po- dem incluir parâmetros como o número de recursos que um processo em deadlock está retendo e quanto tempo o processo levou para ser executado até o momento. 2. Reversão — Se provocarmos a preempção de um recurso de um pro- cesso, o que deve ser feito com esse processo? É claro que ele não pode continuar a ser executado normalmente, pois algum recurso necessário está faltando. Devemos reverter o processo para algum estado seguro e reiniciá-lo a partir desse estado. Já que, em geral, é difícil determinar o que é um estado seguro, a solução mais simples é uma reversão total: abortar o processo e então reiniciá-lo. Embora seja mais eficaz reverter o processo somente até onde for necessário para interromper o deadlock, esse método requer que o sistema mantenha mais informações sobre o estado de todos os processos em execução. 3. Inanição — Como assegurar que a inanição não ocorrerá? Isto é, como podemos garantir que os recursos interceptados não serão sempre do mesmo processo? Em um sistema em que a seleção da vítima é baseada principalmente em fatores de custo, pode ocorrer que o mesmo processo seja sempre selecionado como vítima. Como resultado, esse processo nunca completará sua tarefa, uma situação de inanição que deve ser resolvida em qualquer sistema. É claro que devemos assegurar que um processo possa ser selecionado como vítima apenas um número finito (pequeno) de vezes. A solução mais comum é incluir o número de reversões no fator de custo. Alocação de recursos e deadlocks8 Sistemas operacionais como Linux, Windows e Mac OS X irão: � Prevenir a ocorrência de deadlocks no interior do próprio SO. � Ignorar sua ocorrência em processos de usuários, e deixar que eles resolvam, manualmente, o problema (muito provavelmente encerrando um dos processos envolvidos). MACHADO, F. B.; MAIA, L. P. Arquitetura de sistemas operacionais. 5. ed. Rio de Janeiro: LTC, 2013. SILBERSCHATZ, A.; GALVIN, P. B.; GAGNE, G. Fundamentos de sistemas operacionais. 9. ed. Rio de Janeiro: LTC, 2015. Leituras recomendadas DELGADO, J.; RIBEIRO, C. Arquitetura de computadores. 5. ed. Rio de Janeiro: LTC, 2017. PAIXÃO, R. R. Arquitetura de computadores – PCs. São Paulo: Érica, 2014. STALLINGS, W. Arquitetura e organização de computadores. 8. ed. São Paulo: Pearson, 2009. TANEMBAUM, A. Organização estruturada de computadores. 6. ed. São Paulo: Pearson, 2013. 9Alocação de recursos e deadlocks Conteúdo: Dica do professor Diversos processos sendo acessados, executados e manipulados quase que simultaneamente podem ocasionar diversas reações no sistema operacional. Apesar de o sistema possuir controle sobre a gerência de processos que realiza, nem sempre tudo sai como o esperado. Na Dica do Professor, você verá mais informações sobre como corrigir um deadlock. Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar. https://fast.player.liquidplatform.com/pApiv2/embed/cee29914fad5b594d8f5918df1e801fd/0802e6b9a1c4b31acf586ab457fa6378 Exercícios 1) O acontecimento do deadlock é algo que não consta nas execuções cotidianas de um sistema operacional, porém é passível de ocorrer caso quatro condições sejam atendidas. Abaixo, assinale a alternativa que traz essas condições. A) Exclusão mútua, pipeline, espera e alocação de recurso. B) Inexistência de preempção, retenção e espera, pipeline e exclusão mútua. C) Preempção, espera circular, pipeline e alocação de recurso. D) Espera circular, retenção e espera, exclusão mútua e inexistência de preempção. E) Retenção, espera circular, preempção e exclusão mútua. 2) Assinale a alternativa que traz a condição que é acionada caso algum dos recursos não esteja disponível para ser compartilhado. A) Exclusão mútua. B) Retenção e espera. C) Deadlock. D) Inexistência de preempção. E) Espera circular. 3) Caso o sistema possua um recurso retido e solicite acesso a algum outro recurso, uma determinada condição é executada. Assinale a alternativa que faz referência aos conceitos que foram citados. A) Espera circular. B) Retenção e espera. C) Exclusão mútua. D) Inexistência e preempção. E) Não preempção. 4) Para que esta condição ocorra, a interceptação dos recursos não pode acontecer. Dessa forma, ele pode ser liberado voluntariamente pelo processo que estiver realizando a interceptação. Assinale a alternativa que condiz com esses conceitos. A) Exclusão mútua. B) Pipeline. C) Espera circular. D) Inexistência de preempção. E) Preempção. 5) Caso não ocorra a imposição de uma ordem absoluta a todos os tipos de recursos e que, nessa ordem, conste a requisição de que cada processo deva solicitar recursos seguindo uma ordem de enumeração crescente, determinada condição é executada. Assinale a alternativa que condiz com esses conceitos. A) Espera circular. B) Retenção e espera. C) Exclusão mútua. D) Não preempção. E) Inexistência e preempção. Na prática Muitas vezes, é difícil ter noção da quantidade de processos e recursos utilizados e, consequentemente, alocados para que sejam realizadas atividades cotidianas com o auxílio de um computador. A seguir, você verá um exemplo prático do que acontece quando mais de um recurso é solicitado por um ou mais processos. Conteúdo interativo disponível na plataforma de ensino! Saiba + Para ampliaro seu conhecimento a respeito desse assunto, veja abaixo as sugestões do professor: Exemplo em que não ocorre deadlock As definições de deadlock podem ser melhor compreendidas por meio de exemplos práticos; nesse vídeo, são apresentados conceitos importantes sobre assuntos que norteiam esse contexto, como uma exemplificação de uma situação em que não ocorre deadlock. Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar. Sistemas Operacionais – Aula 14 – Deadlocks (Introdução) Deadlock é definido muitas vezes como um impasse que ocorre no acesso aos recursos por parte dos processos e execução. Nesse vídeo, veja a parte introdutória sobre esse conteúdo. Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar. Sistemas operacionais: projeto e implementação O livro de Andrew Tanenbaum traz aspectos relacionados à segurança e confiabilidade em sistemas de computação. Com abordagens que equilibram teoria e prática, a obra é uma fonte interessante para quem deseja compreender melhor como os sistemas operacionais funcionam. Conteúdo interativo disponível na plataforma de ensino! https://www.youtube.com/embed/xPygG0oG360 https://www.youtube.com/embed/V8969_UJA8U
Compartilhar