View
230
Download
5
Category
Preview:
DESCRIPTION
Slides de autoria do emérito professor Dinailton José da Silva sobre Gerenciamento de Processos, no tema Sistemas Operacionais.
Citation preview
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 1
Sistemas Operacionais Unidade II: Gerenciamento de Processos
Licenciatura em Informtica
Msc Dinailton Jos da Silva
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 2
Multiprogramao
A Tabela apresenta um exemplo de um programa que l registros de um arquivo e executa, em mdia, 100 instrues por registro lido. Neste caso, o processador gasta aproximadamente 93% do tempo esperando o dispositivo de E/S concluir a operao para continuar o processamento.
Outro aspecto a ser considerado a subutilizao da memria principal. Um programa que no ocupe totalmente a memria ocasiona a existncia de reas livres sem utilizao.
Multiprogramao Otimizar o uso do processador e da memria Gerncia de Processos
Leitura de um registro 0,0015s
Execuo de 100 instrues 0,0001s
Total 0,0016s
% utilizao da CPU (0,0001/0,0016) = 0,066 = 6,6%
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 3
Multiprogramao
A multiprogramao tem como objetivo maior maximizar a utilizao da CPU, ou seja, evitar
sempre que possvel que o processador fique ocioso.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 4
Processo
Um processo um programa em execuo, incluindo os valores correntes de todos os registradores do hardware, e das variveis manipuladas por ele no curso de sua execuo
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 5
Mudana de Contexto
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 6
Caractersticas da Estrutura de um Processo
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 7
Bloco de Controle do Processo (PCB)
........
ponteiros
Estado do processo
Registradores
Nome do processo
Prioridade do processo
Limites de memria
Lista de arquivos abertos
Informaes do PCB: Estado do processo Contador de programa Registradores da CPU Informao de escolanamento de CPU Informao de gerncia de memria. Informao contbil. Informao de status E/S.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 8
Mudana de Estado do Processo
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 9
Estados de um Processo
novo(new)
pronto(ready)
Esperando(waiting)
Executando(running)
Terminado(terminated)
interrupoadmitido sada
Despacho do escalonador
Espera por E/S ou eventoTrmino de E/S ou evento
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 10
Criao e eliminao de um processo
A criao de um processo ocorre a partir do momento em que o Sistema Operacional adiciona um novo PCB sua estrutura e aloca um espao de endereamento na memria para uso. No caso da eliminao de um processo, todos os recursos associados ao processo so desalocados e o PCB eliminado pelo Sistema Operacional.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 11
Estrutura de Processos e Subprocessos
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 12
Thread simples e mltipla
cdigo dados arquivos
registradores pilha
thread
cdigo dados arquivos
thread
registradores
pilha
thread
registradores
pilha
thread
registradores
pilha
Thread simples Thread mltipla
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 13
PROCESSOS FOREGROUND E BACKGROUND (primeiro e segundo plano)
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 14
PROCESSOS LIMITADOS POR CPU (CPU-BOUND) E POR E/S (I/O-BOUND)
(a) CPU-boundtempo tempo
E/ S E/ S
UCP UCP
(b) I/ O-bound
limitado por CPU: passa a maior parte do tempo no estado de execuo, ou seja, utilizando o processador. limitado por E/S: passa a maior parte do tempo no estado bloqueado, pois realiza um elevado nmero de operaes de E/S.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 15
ESCALONADORES
Um escalonador um programa responsvel pelo trabalho de escolher processos e de escalar processos para execuo. O escalonador de processos escolhe processos guardados em disco e os carrega na memria para execuo.
O escalonador de CPU escolhe dentre os processos prontos aquele que ser executado, alocando a CPU a ele.
*Algoritmos de enfileiramento sero apresentados ao longo do curso.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 16
Exerccios
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 17
Sincronizao
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 18
PROGRAMAO CONCORRENTE
Um programa concorrente executado simultaneamente por diversos processos que cooperam entre si.
necessria a existncia de interao entre os processos para que o programa seja considerado concorrente.
A concorrncia deve utilizar mecanismos rpidos para interao entre processos: variveis compartilhadas e trocas de mensagens
O compartilhamento de recursos entre processos pode ocasionar situaes indesejveis, capazes at de comprometer a execuo das aplicaes. Para evitar esse tipo de problema os processos concorrentes devem ter suas execues sincronizadas.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 19
SINCRONIZAO
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 20
CONCORRNCIA EM PROGRAMAS
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 21
CONCORRNCIA EM PROGRAMAS
Onde dois ou mais processos compartilham um mesmo recurso, devem existir mecanismos de controle para evitar problemas de concorrncia. Situaes onde dois ou mais processos esto acessando dados compartilhados, e o resultado final do processamento depende de quem roda quando, so chamadas de condies de corrida.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 22
EXCLUSO MTUA
Como evitar a ocorrncia de condies de corrida? A questo chave para evitar qualquer problema em compartilhamento de recursos encontrar formas de proibir que mais de um processo acesse o dado compartilhado ao mesmo tempo. Excluso mtua: forma de se ter certeza de que se um processo estiver usando uma varivel ou arquivo compartilhados, os demais sero impedidos de fazer a mesma coisa.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 23
EXCLUSO MTUA
Regies crticas As partes do programa que pode levar ocorrncia de condies de corrida
Evitando que dois processos estejam processando suas sees crticas ao mesmo tempo, evitaria a ocorrncia de condies de corrida.
Embora essa soluo impea as condies de corrida, isso no suficiente para que processos paralelos que usam dados compartilhados executem corretamente. Precisa-se evitar tambm outras situaes indesejadas: 1 . Nenhum processo que esteja fora de sua regio crtica pode bloquear a execuo de outro processo. 2. Nenhum processo pode esperar indefinidamente para entrar em sua regio crtica (starvation - espera indefinida)
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 24
EXCLUSO MTUA Soluo de hardware
DESABILITAO DAS INTERRUPES: Ao adentrar na sua regio crtica, o processo desabilita as interrupes da mquina.
Isto garante que outro processo no ser escalonado para rodar.
Esta uma soluo funcional, porm ela compromete o nvel de segurana do sistema computacional, pois se um processo desabilitar as interrupes e, por um motivo qualquer, no habilit-las novamente, todo o sistema estar comprometido. BEGIN
. Desabilita_Interrupcoes; Regiao_Critica; Habilita_Interrupcoes; . END.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 25
EXCLUSO MTUA - Soluo de hardware
PROGRAM Test_And_Set;
VAR Bloqueio : Boolean;
BEGIN
Bloqueio := false;
PARBEGIN
Processo_A;
Processo_B;
PAREND;
END.
PROCEDURE Processo_A;
VAR Pode_A : Boolean;
BEGIN
REPEAT
Pode_A := true;
WHILE (Pode_A) DO
Test_And_Set (Pode_A, Bloqueio);
Regiao_Critica_A;
Bloqueio := false;
UNTIL false;
END;
PROCEDURE Processo_B;
VAR Pode_B : Boolean;
BEGIN
REPEAT
Pode_B := true;
WHILE (Pode_B) DO
Test_And_Set (Pode_B, Bloqueio);
Regiao_Critica_B;
Bloqueio := false;
UNTIL false;
END;
Programa Test_And_SET TSL
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 26
EXCLUSO MTUA - Soluo de software PRIMEIRO ALGORITMO: ESTRITA ALTERNNCIA
PROGRAM Algoritmo1; VAR Vez : CHAR; BEGIN Vez := A; PARBEGIN Processo_A; Processo_B; PAREND; END. PROCEDURE Processo_A; BEGIN REPEAT WHILE (Vez = B) DO; (*No faz nada*) Regiao_Critica_A; Vez := B; Processamento_A; UNTIL false; END;
PROCEDURE Processo_B; BEGIN REPEAT WHILE (Vez = A) DO; (*No faz nada *) Regiao_Critica_B; Vez := A; Processamento_B; UNTIL false; END;
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 27
EXCLUSO MTUA - Soluo de software SEGUNDO ALGORITMO
PROGRAM Algoritmo2; VAR CA, CB: BOOLEAN; BEGIN CA := false; CB := false; PARBEGIN Processo_A; Processo_B; PAREND; END. PROCEDURE Processo_A; BEGIN REPEAT WHILE (CB) DO; (*No faz nada*) CA := true; Regiao_Critica_A; CA := false; Processamento_A; UNTIL false; END;
PROCEDURE Processo_B; BEGIN REPEAT WHILE (CA) DO; (*No faz nada*) CB := true; Regiao_Critica_B; CB := false; Processamento_B; UNTIL false; END;
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 28
EXCLUSO MTUA - Soluo de software TERCEIRO ALGORITMO
PROGRAM Algoritmo3; VAR CA, CB: BOOLEAN; BEGIN CA := false; CB := false; PARBEGIN Processo_A; Processo_B; PAREND; END. PROCEDURE Processo_A; BEGIN REPEAT CA := true; WHILE (CB) DO; (*No faz nada*) CA := true; Regiao_Critica_A; CA := false; Processamento_A; UNTIL false; END;
PROCEDURE Processo_B; BEGIN REPEAT CB := true; WHILE (CA) DO; (*No faz nada*) CB := true; Regiao_Critica_B; CB := false; Processamento_B; UNTIL false; END;
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 29
EXCLUSO MTUA - Soluo de software QUARTO ALGORITMO
PROGRAM Algoritmo4; VAR CA, CB: BOOLEAN; BEGIN CA := false; CB := false; PARBEGIN Processo_A; Processo_B; PAREND; END. PROCEDURE Processo_A; BEGIN REPEAT CA := true; WHILE (CB) DO BEGIN CA := false; {pequeno intervalo de tempo aleatrio} CA := true; END; Regiao_Critica_A; CA := false; UNTIL false; END;
PROCEDURE Processo_B; BEGIN REPEAT CB := true; WHILE (CA) DO BEGIN CB := false; {pequeno intervalo de tempo aleatrio} CB := true; END; Regiao_Critica_B; CB := false; UNTIL false; END;
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 30
EXCLUSO MTUA - Soluo de software ALGORITMO DE PETERSON
PROGRAM Algoritmo_Peterson; VAR CA, CB: BOOLEAN Vez : CHAR; BEGIN CA := false; CB := false; PARBEGIN Processo_A; Processo_B; PAREND; END. PROCEDURE Processo_A; BEGIN REPEAT CA := true; WHILE (CB and Vez = B) DO; (*faz nada*) Regiao_Critica_A; CA := false; Processamento_A; UNTIL false; END;
PROCEDURE Processo_B; BEGIN REPEAT CB := true; WHILE (CA and Vez = A) DO;(*faz nada*) Regiao_Critica_B; CB := false; Processamento_B; UNTIL false; END;
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 31
EXCLUSO MTUA - Soluo de software
Apesar de todas solues de algoritmos apresentadas implementarem a excluso mtua, todas possuam uma deficincia conhecida como espera ocupada (busy waiting):
Perda de tempo de processamento: todas as solues utilizam-se de um lao de espera ocupada para impedir que dois processos entrem ao mesmo tempo em suas regies crticas e tais laos consomem, desnecessariamente, o tempo do processador; Prioridade invertida: este problema ocorre quando existem dois processos executando, um A de alta prioridade, e outro B de baixa prioridade e o Gerente de Processos est programado para colocar para rodar qualquer processo de alta prioridade que esteja no estado de pronto.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 32
EXCLUSO MTUA Sincronizao condicional
O problema do produtor-consumidor, ou sincronizao condicional, consiste em dois processos que compartilham um buffer de tamanho fixo. Um dos processos, o produtor, coloca informao no buffer, e o outro, o consumidor, as retira.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 33
EXCLUSO MTUA - Sincronizao condicional ALGORITMO PRODUTOR/CONSUMIDOR
PROGRAM Produtor_Consumidor_1;
CONST TamBuf = (* Tamanho qualquer *);
TYPE Tipo_Dado = (* Tipo qualquer *);
VAR Buffer : ARRAY [1..TamBuf] OF Tipo_Dado;
Dado1 : Tipo_Dado;
Dado2 : Tipo_Dado;
Cont : 0..TamBuf;
BEGIN
Cont := 0;
PARBEGIN
Produtor;
Consumidor;
PAREND;
END. PROCEDURE Produtor; BEGIN REPEAT Produz_Dado (Dado1); WHILE (Cont = TamBuf) DO; (*faz nada*) Grava_Buffer (Dado1, Buffer); Cont := Cont + 1; UNTIL false; END;
PROCEDURE Consumidor; BEGIN REPEAT WHILE (Cont = 0) DO; (*faz nada*) Le_Buffer (Dado2, Buffer); Consome_Dado (Dado2); Cont := Cont - 1; UNTIL false; END;
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 34
EXCLUSO MTUA - SEMFOROS ALGORITMO SEMFORO
PROGRAM Semaforo_1; VAR S : Semaforo := 1; BEGIN PARBEGIN Processo_A; Processo_B; PAREND; END. PROCEDURE Processo_A; BEGIN DOWN (S); Regiao_Critica_A; UP (S); Processamento_A; END;
PROCEDURE Processo_B; BEGIN DOWN (S); Regiao_Critica_B; UP (S); Processamento_B; END;
TYPE Semaforo = RECORD Valor : INTEGER; Fila_Espera : (*Lista de processos pendentes*); END; PROCEDURE DOWN (Var S : Semaforo); BEGIN IF (S = 0) THEN Coloca_Proc_Fila ELSE S := S - 1; END;
PROCEDURE UP (Var S : Semaforo); BEGIN S := S + 1; IF(Tem_Proc_Espera) THEN Tira_Proc; END;
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 35
EXCLUSO MTUA - SEMFOROS ALGORITMO SEMFORO Produtor/Consumidor
PROGRAM Produtor_Consumidor_2; CONST TamBuf = 2; TYPE Tipo_Dado = (* tipo qualquer *); VAR Vazio : Semaforo := TamBuf; Cheio ; Semaforo := 0; Mutex : Semaforo := 1; Buffer : ARRAY [1..TamBuf] OF Tipo_Dado; Dado1 : Tipo_Dado; Dado2 : Tipo_Dado; BEGIN PARBEGIN Produtor; Consumidor; PAREND; END.
PROCEDURE Produtor; BEGIN REPEAT Produz_Dado (Dado1); DOWN (Vazio); DOWN (Mutex); Grava_Buffer (Dado1, Buffer); UP (Mutex); UP (Cheio); UNTIL false; END;
PROCEDURE Consumidor; BEGIN REPEAT DOWN (Cheio); DOWN (Mutex); Le_Buffer (Dado2, Buffer); UP (Mutex); UP (Vazio); Consome_Dado (Dado2); UNTIL false; END;
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 36
EXCLUSO MTUA Troca de Mensagens ALGORITMO Troca de Mensagens Produtor/Consumidor
PROGRAM Produtor_Consumidor_4; BEGIN PARBEGIN Produtor; Consumidor; PAREND; END. PROCEDURE Produtor; VAR Msg : Tipo_Msg; BEGIN REPEAT Produz_Mensagem (Msg); SEND (Msg); UNTIL false; END;
PROCEDURE Consumidor; VAR Msg : Tipo_Msg; BEGIN REPEAT RECEIVE (Msg); Consome_Mensagem (Msg); UNTIL false; END;
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 37
Problemas Clssicos de Sincronizao Problema dos filsofos: um exemplo clssico de sincronizao de processos. Considera a existncia de cinco filsofos sentados em torno de uma mesa redonda. Cada filsofo tem sua frente um prato de macarro. Um filsofo que deseje comer precisa contar com o auxlio de 2 garfos e entre cada prato existe um garfo.
A vida de um filsofo consiste em perodos nos quais ele alternadamente come e pensa. Quando um filsofo sente fome, ele tenta tomar posse dos garfos sua direita e sua esquerda, um por vez, em qualquer ordem. Se ele tiver sucesso nesta empreitada, come um pouco do macarro, libera os garfos e continua a pensar. A questo a ser respondida : como escrever um programa para simular a ao de cada filsofo que nunca leve a situaes de bloqueio?
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 38
Problemas Clssicos de Sincronizao PROBLEMA DO BARBEIRO SONOLENTO Neste problema, considera-se uma barbearia onde existe um barbeiro, uma cadeira de barbeiros e diversos lugares onde os clientes que estiverem esperando, podero sentar.
Se no houver nenhum cliente presente, o barbeiro simplesmente senta em sua cadeira e cai no sono. Quando chegarem fregueses, enquanto o barbeiro estiver cortando o cabelo de outro, estes devem sentar, se houver cadeira vazia, ou ir embora, se no houver nenhuma cadeira disponvel
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 39
Deadlock
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 40
DEADLOCK
Deadlock a situao em que um processo aguarda por um recurso que nunca estar disponvel ou um evento que no ocorrer. Essa situao consequncia, na maioria das vezes, do compartilhamento de recursos, como dispositivos, arquivos e registros, entre outros processos concorrentes em que a excluso mtua exigida.
Muitos deadlock ocorrem em sistemas de computao devido natureza de recursos dedicados (isto , os recursos somente podem ser usados por um usurio por vez).
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 41
DEADLOCK ESPERA CIRCULAR
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 42
DEADLOCK
Exemplo Deadlock: Lei aprovada pela assemblia norte-americana no incio deste sculo: "Quando dois trens se aproximarem um do outro em um cruzamento, ambos devero parar completamente e nenhum dos dois dever ser acionado at que o outro tenha partido."
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 43
DEADLOCK
Exemplo Deadlock: DEADLOCK DE TRFEGO Um certo nmero de automveis est tentando atravessar uma parte da cidade bastante movimentada, mas o trfego ficou completamente paralisado. O trfego chegou numa situao onde somente a polcia pode resolver a questo, fazendo com que alguns carros recuem na rea congestionada. Eventualmente o trfego volta a fluir normalmente, mas a essa altura os motoristas j se aborreceram e perderam tempo considervel.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 44
DEADLOCK
Em uma situao de operao normal, um processo pode utilizar um recurso somente se: Requisitar: se a requisio no pode ser atendida imediatamente (por exemplo, o recurso est em uso por outro processo), ento o processo requisitante deve esperar at obter o recurso;
Usar: O processo pode operar sobre o recurso (por exemplo, se o recurso uma impressora, ele pode imprimir) e;
Liberar: O processo libera o recurso.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 45
DEADLOCK
Existe quatro condies necessrias para que ocorra um deadlock: Condio de excluso mtua: cada recurso s pode estar alocado a nico processo em um determinado instante. Condio de posse e de espera: processos que estejam de posse de recursos obtidos anteriormente podem solicitar novos recursos. Condio de no-preempo: recursos j alocados a processos no podem ser tomados fora. Eles precisam ser liberados explicitamente pelo processo que o detm. Condio de espera circular: deve existir uma cadeia circular de dois ou mais processos, cada um dos quais esperando por um recurso que est com o prximo membro da cadeia.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 46
DEADLOCK (Ocorrncia e Evitando)
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 47
DEADLOCK Mtodos para lidar com deadlock:
Evitar dinamicamente o deadlock, pela cuidadosa alocao dos recursos aos processos. Isto requer que sejam fornecidas ao sistema operacional informaes adicionais sobre quais recursos um processo ir requisitar e usar durante sua execuo.
Prevenir o deadlock por meio de um conjunto de mtodos para garantir que pelo menos uma das condies necessrias (slide anterior) no poder ser satisfeita.
Detectar e recuperar uma situao de deadlock.
Ignorar completamente o problema. Se um sistema que nem previne, evita ou recupera situaes de deadlock, se um ocorrer, no haver maneira de saber o que aconteceu exatamente. Neste caso, o deadlock no detectado causar a degredao do desempenho do sistema, porque recursos esto detidos por processos que no podem continuar, e porque mais e mais processos, conforme requisitam recursos, entram em deadlock.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 48
DEADLOCK Algoritmo do Avestruz:
a abordagem mais simples: "enterre a cabea na areia e finja que no h nenhum problema acontecendo" (Tanenbaum, 2008).
A estratgia do UNIX: simplesmente ignorar o problema. Maioria dos usurios preferi a ocorrncia de deadlocks ocasionais. Custo alto para eliminao (restries inconvenientes ao uso dos recursos) Deciso: convenincia ou correo.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 49
DEADLOCK Deteco (1 recurso para cada tipo) Um recurso para cada tipo:
1. O processo A possui o recurso R e requisita o recurso S. 2. O processo B nada possui, mas requisita o recurso T. 3. O processo C nada possui, mas requisita o recurso S. 4. O processo D possui o recurso U e requisita os recursos S e T. 5. O processo E possui o recurso T e requisita o recurso V. 6. O processo F possui o recurso W e requisita o recurso S. 7. O processo G possui o recurso V e requisita o recurso U.
D, E e G situao de deadlock
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 50
DEADLOCK Deteco (1 recurso para cada tipo) Se detectar um ciclo o algoritmo termina:
1. Para cada nodo N no grafo execute os cinco passos seguintes, em que N o nodo inicial.
2. Inicialize L com uma lista vazia e assinale todos os arcos como desmarcados (L=[]).
3. Insira o nodo atual da lista L (L=[R,A]) e verifique se o nodo agora aparece em L duas vezes. Em caso afirmativo, o grafo contm um ciclo e o algoritmo termina.
4. A partir do referido nodo, verifique se existe algum arco de sada desmarcado. Em caso de afirmativo v para o passo 5; do contrrio, v para o passo 6.
5. Escolha aleatoriamente um arco de sada desmarcado e marque-o. Ento, siga esse arco para obter o novo novo atual e v para o passo 3.
6. O final foi alcanado. Remova-o e volte para o nodo anterior , marque-o como atual e v para o passo 3. Se esse nodo for o inicial, o grafo no conter ciclo algum e o algoritmo terminar.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 51
DEADLOCK Deteco (vrios recursos para cada tipo)
E Recursos existentes A Recursos disponveis C Matriz de alocao atual (linha = processo, coluna = recurso utilizado) D Matriz de requisies (linha = processo, coluna = requisio de recurso)
)1234(=E )0012(=A
=
021010020100
C
=
001201011002
R
Recursos existentes Recursos disponveis
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 52
DEADLOCK RECUPERAO Por meio de preempo:
>>Tomar temporariamente um recurso de seu atual dono e entreg-lo a outro processo.
Por meio de reverso de estado (volta ao passado): >>Um processo que possui um dos recursos necessrios revertido apara um estado em um instante anterior ao momento em que adquiriu algum outro recurso. >>Se o processo que sofreu reverso de estado tentar adquirir o recurso novamente, ele ter de esperar at o recurso estar disponvel.
Por meio de eliminao de processos: >> a maneira mais rude, mas tambm a mais simples de se eliminar a situao de deadlock matar o processo >>Sempre que possvel, melhor matar o processo que seja capaz de ser executado desde o seu incio para evitar efeitos colaterais.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 53
DEADLOCK EVITANDO
EVITANDO O DEADLOCK Se o sistema for capaz de decidir se a alocao de determinado recurso ou no segura, e s fazer a alocao quando ela for segura, teremos como evitar deadlocks.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 54
DEADLOCK EVITANDO
Estado Seguro >>existe uma sequencia de alocaes que permitem que todos os processos venham a terminar seus processamentos.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 55
DEADLOCK EVITANDO
Estado Inseguro >>No h garantia de que o processo ser concludo no seu ciclo de processamento.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 56
DEADLOCK EVITANDO
Algoritmo do Banqueiro >>se requisio de processo for maior que a capacitada ofertada, a mesma no ser atendida.
Dinailton Jose da Silva Licenciatura em Informtica Sistemas Operacionais 9 de maro de 2015 57
Exerccios
Sistemas OperacionaisUnidade II: Gerenciamento de ProcessosNmero do slide 2Nmero do slide 3Nmero do slide 4Nmero do slide 5Nmero do slide 6Nmero do slide 7Nmero do slide 8Nmero do slide 9Nmero do slide 10Nmero do slide 11Nmero do slide 12Nmero do slide 13Nmero do slide 14Nmero do slide 15Nmero do slide 16Nmero do slide 17Nmero do slide 18Nmero do slide 19Nmero do slide 20Nmero do slide 21Nmero do slide 22Nmero do slide 23Nmero do slide 24Nmero do slide 25Nmero do slide 26Nmero do slide 27Nmero do slide 28Nmero do slide 29Nmero do slide 30Nmero do slide 31Nmero do slide 32Nmero do slide 33Nmero do slide 34Nmero do slide 35Nmero do slide 36Nmero do slide 37Nmero do slide 38Nmero do slide 39Nmero do slide 40Nmero do slide 41Nmero do slide 42Nmero do slide 43Nmero do slide 44Nmero do slide 45Nmero do slide 46Nmero do slide 47Nmero do slide 48Nmero do slide 49Nmero do slide 50Nmero do slide 51Nmero do slide 52Nmero do slide 53Nmero do slide 54Nmero do slide 55Nmero do slide 56Nmero do slide 57
Recommended