Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Sistemas Operacionais - Aula 4 - Revisado

Deadlocks
by

Douglas Kellermann

on 27 March 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Sistemas Operacionais - Aula 4 - Revisado

Sistemas Operacionais Prof.º Douglas Kellermann Resgatando último conteúdo Conteúdo última aula Gerenciamento de Processos
Escalonamento de processos
Threads Análise e Desenvolvimento de Sistemas Curso Superior de Tecnologia em DEADLOCKS Conteúdo e referências bibliográficas DEADLOCKS / IMPASSES
Recurso
Introdução aos deadlocks
Algoritmo do avestruz
Detecção e recuperação de deadlocks Finalizando Dúvidas?

Próxima semana...

Deadlocks / Gerenciamento de memória Conteúdo Dúvidas conteúdo anterior?
Deadlocks Dúvidas? 1. TANENBAUM, WOODHULL, 2008 Notação do código referência r[A]c[B]p[C]
referência A, número de ordem da referência
capítulo B, identificação do capítulo
página C, número da página Recurso Definições Recurso
Recurso é um objeto/dispositivo que pode ser usado somente por um único processo em um dado instante de tempo.
Recursos preemptíveis
podem ser tomados de processos sem quaisquer efeitos prejudiciais
Recursos não preemptíveis
vão levar o processo à falhar se forem retirados
Então Deadlocks ocorrem quando...
garante-se aos processos exclusividade de acesso aos dispositivos que são normalmente chamados de recursos Exemplos de recursos Que recursos temos.... Exemplos de recursos para o sistema operacional
impressoras
unidades de fita
tabela de alocação de arquivos - FAT

Processos precisam de acesso aos recursos numa ordem racional

Suponha que um processo detenha o recurso A e solicite o recurso B
ao mesmo tempo um outro processo detém B e solicita A
ambos são bloqueados e assim permanecem Ordem racional de acesso Seqüência de eventos Ordem de eventos necessários à utilização de um recurso

1. solicitar o recurso
2. usar o recurso
3. liberar o recurso

Deve esperar se solicitação é negada
processo solicitante pode ser bloqueado
pode falhar resultando em um código de erro Introdução aos deadlocks Definições Um conjunto de processos está em situação de deadlock se todo processo pertencente ao conjunto estiver esperando por um evento que somente um outro processo desse mesmo conjunto poderá fazer acontecer

Normalmente o evento é a liberação de um recurso atualmente retido.

Nenhum dos processos pode...
executar
liberar recursos
ser acordado Condições para Deadlocks São quatro..., segundo Coffman et al. (1971) apud Tanenbaum e Woodhull 1. Condição de exclusão mútua
todo recurso ou está associado a um processo ou disponível
2. Condição de posse e espera
processos que retêm recursos podem solicitar novos recursos
3. Condição de não preempção
recursos concedidos previamente não podem ser forçosamente tomados, o processo detentor deve liberar o recurso
4. Condição de espera circular
deve ser uma cadeia circular de 2 ou mais processos
cada um está à espera de recurso retido pelo membro seguinte dessa cadeia

Todas devem estar presentes para que ocorra um deadlock, ou mais precisamente um impasse de recurso Modelagem de deadlock com grafos dirigidos a) recurso R alocado ao processo A
b) processo B está solicitando/esperando pelo recurso S
c) processos C e D estão em deadlock sobre recursos T e U Como ocorre um deadlock Como pode ser evitado um deadlock Ignorar o problema Estratégias para tratar deadlock 1. Ignorar por completo o problema;
algoritmo do avestruz
2. Detecção e recuperação;
deixar os impasses ocorrerem, detectá-los e executar uma ação
3. Evitação dinâmica;
alocação cuidadosa de recursos
4. Prevenção:
negação de uma das quatro condições necessárias Finge que o problema não existe
Razoável se
deadlocks ocorrem muito raramente
custo da prevenção é alto
UNIX e Windows seguem esta abordagem
É uma ponderação entre
conveniência e correção Detecção e Recuperação de deadlock Detecção Recuperação de deadlock retirar um recurso de algum outro processo
não é aplicável em todos os casos, depende da natureza do recurso
pode precisar de ação externa de apoio, por exemplo, administrar a da saída "misturada" de folhas em impressora com apenas uma bandeja Recuperação de deadlock Recurso preemptivo Memória Memória é um exemplo de recurso preemptivo, pode ser retirado de um processo sem nenhum efeito prejudicial Considere o seguinte exemplo, um sistema com 64MB de memória de usuário, uma impressora e dois processos de 64MB, cada um querendo imprimir algo Seqüencia de operações
Processo A solicita e obtém a impressora;
Processo A começa a calcular os valores a serem impressos
Antes que A tenha terminado o cálculo, ele ultrapassa seu quantum de tempo e é trocado ou paginado
O processo B é executado e tenta sem sucesso adquirir a impressora
Situação de impasse, A tem a impressora, B tem a memória e ambos não podem prosseguir sem o recurso mantido pelo outro. Como a memória é recurso preemptivo, é possível retirar a memória de B (preempção) e alocá-la para A
A pode ser executado e fazer a impressão e depois liberar a impressora
Nenhum impasse ocorre Recurso não-preemptivo Gravador de CD É um exemplo de recurso não-preemptivo, não pode ser retirado do processo corrente sem fazer a computação falhar Considere a seguinte situação: se um processo tiver começado a gravar um CD-ROM, qualquer tentativa repentina de retirar o gravado de CD do processo e passá-lo para outro processo, resultará em um CD corrompido. Após o passo (q), o processo B pode receber S, pois A terminou e C tem tudo que precisa. Mesmo que B deva eventualmente ser bloqueado ao solicitar T, nenhum impasse pode ocorrer. B simplesmente esperará até que C tenha terminado Se em relação ao seqüência original, o sistema soubesse do impasse iminente, poderia suspender B, em vez de conceder S a ele. A seqüência de operações indicada em (d) leva à ocorrência de deadlock Algoritmo do Avestruz Recuperação Observe a posse e solicitações de recursos
Um ciclo (b)pode ser encontrado dentro do grafo, denotando deadlock Com um recurso de cada tipo
Abordagem de detecção para sistemas onde somente estejam disponíveis uma unidade de determinado recurso, por exemplo, uma impressora, um gravador de CD, etc.
Com dois ou mais recursos de cada tipo
Abordagem de detecção para sistemas onde estejam disponíveis dois ou mais recursos de mesmo tipo (não será explorado nesta aula) Por preempção
Por reversão de estado
Por meio de eliminação de processos Detecção com um recurso de cada tipo Segundo esta abordagem de tratamento de deadlock, o sistema operacional não atua preventivamente. Em vez disto, o sistema tenta detectar os deadlocks a medida que ocorrem e age para se recuperar após ocorrido. Sistemas simples, que envolvam apenas um recurso de cada tipo, por exemplo, uma unidade de CD, um plotter e uma unidade de fita, podem adotar um grafo de recursos (a) como base para identificação de ciclos de deadlock Existem várias, mas são pouco interessantes devido peculiaridades associadas à casos específicos Recuperação de deadlock forma mais grosseira mas também mais simples de quebrar um deadlock
elimina um dos processos no ciclo de deadlock; eventualmente pode-se eliminar um processo fora do ciclo, por exemplo, outro processo que esteja utilizando um recurso igual ao que se encontra em disputa no ciclo
procura escolher para eliminação o processo que pode ser reexecutado desde seu início (por exemplo, uma compilação)
os outros processos conseguem seus recursos
se a eliminação não for suficiente, pode-se repetir a ação até que o ciclo seja quebrado Recuperação através da eliminação de processos verifica os processos periodicamente e salva o status completo em um ou mais (histórico) arquivos de checkpoint
se ocorre um deadlock o sistema pode utilizar o estado salvo do processo que detêm o recurso e transferi-lo para o processo bloqueado
reinicia o outro processo no ponto em não havia requisitado o recurso, sendo que agora precisa aguardar que o recurso esteja disponível novamente Recuperação através de reversão de estado Recuperação através de preempção
Full transcript