Baixe o app para aproveitar ainda mais
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Arquitetura de Sistemas Operacionais Capítulo 7 Sincronização e Comunicação entre Processos Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Sumário Introdução Aplicações concorrentes Especificação de concorrência em programas Problemas de compartilhamento de recursos Exclusão mútua Sincronização condicional Semáforos Monitores Troca de mensagens Deadlock Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Introdução Surgindo os sistemas multiprogramáveis, passou a ser possível uma aplicação ter trechos de códigos sendo executado de forma concorrente – aplicação concorrente; A base é a execução cooperativa de processos ou threads em prol de um objetivo comum; Mesmo em sistemas monoprocessados é possível obter ganhos com aplicações concorrentes; Ao sistema multiprocessados estende as vantagens do uso deste tipo de aplicação; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Introdução É natural o compartilhamento de recursos pelos processos de uma aplicação concorrente; Este compartilhamento pode gerar situações indesejáveis; Para evitar estas situações os processos devem ter a sua execução sincronizadas, a partir de mecanismos oferecidos pelo S.O.; Este capítulo descreve a sincronização e comunicação entre processos. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Aplicações Concorrentes Muitas vezes, os processos concorrentes devem comunicar entre si; Esta comunicação pode ser implementada através de: Memória compartilha; Troca de mensagens. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Aplicações Concorrentes Na próxima figura: Um processo que lê do buffer; Outro processo de grava no buffer; Condições: O processo só lê se o buffer não tiver vazio; O processo só grava se o buffer não tiver cheio; Em ambos os casos, os processos deverão esperar o buffer estar pronto para a operação; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Aplicações Concorrentes Sincronização e comunicação entre processos Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Aplicações Concorrentes Os mecanismos que garantem a comunicação e o acesso aos recursos compartilhados são chamados de mecanismos de sincronização; Nesta abordagem tanto subprocessos como thread tem o mesmo significado que processos, para exemplicação das aplicações; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Especificação de Concorrência em Programas Existem várias notações para especificar a concorrência em programas (partes do programa que devam ser executadas concorrentemente); Conway(1963) e Dennis e Van Horm, criaram a primeira notação: FORK – cria um outro processo; JOIN – sincroniza com outro programa; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Especificação de Concorrência em Programas O programa A começa; Encontra o comando FORK: Começa o programa B em outro processo; O programa A encontra o comando JOIN: O programa A espera o término do programa B; Estes comandos são utilizados no Unix; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Especificação de Concorrência em Programas Dijkstra em 1965 propôs o PARABEGIN e o PARAEND, uma das implementações mais claras; Foram chamadas, posteriormente, de COBEGIN e COEND; O comando PARABEGIN especifica uma seqüência de comandos seja executa de forma concorrente em uma ordem imprevisível, criando um processo para cada comando; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Especificação de Concorrência em Programas O comando PARAEND define um ponto de sincronização, onde o processamento só continua quando todos os processos tiverem terminados; Os comandos podem ser simples, como atribuições ou chamadas a procedimentos; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Especificação de Concorrência em Programas Concorrência em programas Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Especificação de Concorrência em Programas X := SQRT (1024) + (35.4 * 0.23) - (302 / 7) PROGRAM Expressao; VAR X, Temp1, Temp2, Temp3 : REAL; BEGIN PARBEGIN Temp1 := SQRT (1024); Temp2 := 35.4 * 0.23; Temp3 := 302 / 7; PAREND; X := Temp1 + Temp2 - Temp3; WRITELN ('x = ', X); END. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Especificação de Concorrência em Programas O cálculo final de X, só pode ser efetuado após terem terminado o cálculo de Temp1, Temp2 e Temp3; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Problema de Compartilhamento de Recursos Veremos algumas problemas de compartilhamento de recursos: Compartilhamento de um arquivo em disco; Compartilhamento de uma variável na memória principal; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Problema de Compartilhamento de Recursos Arquivo em disco: Atualização de um saldo bancário; Lançamento de um débito/crédito; Em um arquivo são armazenados todos os saldos dos clientes de um banco; O programa (próxima transparência): Lê o saldo de um cliente; Lê o valor da operação; Atualiza o saldo; Grava o saldo. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Problema de Compartilhamento de Recursos PROGRAM Conta_Corrente; . . READ (Arq_Contas, Reg_Cliente); READLN (Valor_Dep_Ret); Reg_Cliente.Saldo := Reg_Cliente.Saldo + Valor_Dep_Ret; WRITE (Arq_Contas, Reg_Cliente); . . END. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Problema de Compartilhamento de Recursos Considerando dois funcionários do banco atualizando o mesmo cliente; Certo 1.100 Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Problema de Compartilhamento de Recursos Variável compartilhada: Dois processos (A e B) executam um comando de atribuição; Processo A soma 1 à X; Processo B diminui 1 de X; Se X, inicialmente, é igual a 2 e de se esperar que o resultado, após a execução dos processos continue igual a 2; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Problema de Compartilhamento de Recursos Linguagem de alto nível Processo A Processo B X := X + 1; X := X - 1; Linguagem de baixo nível Processo A Processo B LOAD x,Ra LOAD x,Rb ADD 1,Ra SUB 1,Rb STORE Ra,x STORE Rb,x Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Problema de Compartilhamento de Recursos Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Problema de Compartilhamento de Recursos Analisando os exemplos conclui-se que em qualquer situação, onde dois ou mais processos compartilham um mesmo recurso, devem existir mecanismos de controle para evitar estes tipos de problemas, conhecidos como race conditions (condições de corrida); Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Solução é impedir que dois ou mais processos acessem o mesmo recurso simultaneamente; Portanto, quando um processo estiver acessando um recurso, os demais processos que queiram acessar este recurso deverão esperar pelo término da utilização deste recurso; Esta idéia é chama de exclusão mútua (mutual exclusion); Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua A exclusão mútua deve afetar apenas os processos concorrentes somente quando um deles tiver fazendo acesso ao recurso compartilhado; A parte do código onde se acessa o recurso compartilhado é chamada de região crítica (critical region); Para evitar os problemas causados pelo compartilhamento basta evitar que dois processos entrem na sua região crítica simultaneamente; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Os mecanismos que implementam a exclusão mútua utilizam protocolos de acesso à região crítica; Quando um processo desejar executar instruções de sua região crítica, deverá executar um protocolo de entrada na região crítica obrigatoriamente; Da mesma forma quando sair da região crítica deverá executar um protocolo de saída; Estes protocolos garantem a exclusão mútua da região crítica; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua BEGIN . . Entra_Regiao_Critica; (* protocolo de entrada *) Regiao_Critica; Sai_Regiao_Critica; (* protocolo de saída) . . END. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Para o programa de Conta_Corrente: Recurso compartilhado Arquivo de contas correntes; Solução Sempre que o Processo A for atualizar o saldo, antes de ler o acesso exclusivo ao arquivo deve ser garantido protocolo de entrada; Se conseguir o acesso, significa que outro processo não esta utilizando o recurso, podendo assim atualizar o saldo Quando gravar o saldo atualizado o Processo A libera o recurso – saída da região crítica – permitindo assim que outro processo utiliza o recurso (arquivo de conta corrente); Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Para garantir a implementação da exclusão mútua os processos envolvidos devem fazer acesso os recursos de forma compartilhada; Existem diversas soluções para este propósito, mas deve-se evitar duas situações: Espera indefinida (starvation starvation); Um processo fora da sua região crítica impede que outros processos utilizem o recurso compartilhado; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Espera indefinida (starvation) Ocorre quando um processo nunca consegue executar a sua região crítica (utilizar o recurso compartilhado); Quando um recurso é liberado o S.O. Possui um critério para selecionar o próximo processo que terá acesso ao recurso; Dependendo do processo de escolha o starvation pode ocorrer; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Espera indefinida (starvation) Escolha aleatória: não está garantindo que em algum momento um processo terá acesso ao recurso pois a escola é aleatória; Por prioridade: a baixa prioridade de um processo em relação aos outros pode impedir o acesso ao recurso; Uma solução simples: criação de filas de pedidos para cada recurso, usando FIFO. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Um processo fora da sua região crítica impede que outros processos utilizem o recurso compartilhado; Neste caso o recurso estaria livre porém alocado a um processo; Assim todos os processos que utilizam este recurso estariam impedidos de entrar nas suas regiões críticas; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Soluções de hardware: Desabilitação de interrupções; Instrução test-and-set. Soluções de software Primeiro algoritmo; Segundo algoritmo; Terceiro algoritmo; Quarto algoritmo; Algoritmo de Dekker; Algoritmo de Peterson; Algoritmo para exclusão mútua entre N processos. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Desabilitação de interrupções Solução mais simples; É desabilitado todas as interrupções antes de entrar na região crítica; É habilitado todas as interrupções após deixar a região crítica; Como a mudança de contexto só pode ser executada através de interrupções, fica garantindo, assim, o acesso exclusivo; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Desabilitação de interrupções BEGIN . Desabilita_Interrupcoes; Regiao_Critica; Habilita_Interrupcoes; . END. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Desabilitação de interrupções Limitações: A multiprogramação pode ficar seriamente comprometida, já a concorrência tem como base o uso de interrupções; Se o processo “esquecer” de habilitar as interrupções, o sistema ficaria seriamente comprometido; Em sistemas multiprocessados esta solução torna-se ineficiente devido ao tempo de propagação de um processador para os outros da desabilitação/abilitação das interrupções; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Desabilitação de interrupções Limitações: Não esquecer que o mecanismo de clock é implementado com o uso de interrupções; A seção crítica pode executar E/S que dependam de interrupções; Apesar das limitações, esta solução pode ser útil quando se deseja que partes do núcleo do S.O. sem interrupções, garantindo que não haverão problemas de inconsistências nas estruturas de dados; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Instrução test-and-set Instrução que: Le uma variável; Armazena o conteúdo em outro local; Atribui um novo valor a mesma variável; É executada sem interrupção, ou seja, é uma instrução indivisível; Desta forma, é garantindo que dois processos não acessem uma variável compartilhada ao mesmo tempo – permite implementar a exclusão mútua; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Instrução test-and-set Test-and-Set (X,Y): O valor lógico de Y é copiado para X; Y recebe o valor lógico verdadeiro. Para coordenar o acesso concorrente, é utilizado uma variável lógica global chamada de bloqueio: Quando bloqueio for falso qualquer processo poderá alterar o seu valor para verdadeiro e ter acesso ao recurso de forma exclusiva; Quando terminar de usar o recurso, o processo retorna o valor falso para o bloqueio, liberando o acesso ao recurso. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Program Test_and_Set var Bloqueio: boolean; Procedure Processo_A; var P_A : boolean; // pode A begin repeat P_A:= true; while (P_A) do Test_and_Set (P_A, Bloqueio); Regiao_Critica_A; Bloqueio:= false; until true; end; Procedure Processo_B; var P_B : boolean; // pode B begin repeat P_B:= true; while (P_B) do Test_and_Set (P_B, Bloqueio); Regiao_Critica_B; Bloqueio:= false; until true; end; begin Bloqueio := false; PARBEGIN Processo_A; Processo_B; PARAEND End. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Instrução test-and-set Esta solução apresenta algumas vantagens: Simplicidade de implementação Uso em arquitetura com múltiplos processadores; Principal desvantagem: Possibilidade de starvation, pois a escolha do processo para acesso ao recurso é aleatória. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Soluções de software Algoritmo 1 Uma solução para dois processos; Onde a alternância na execução das seções críticas; Cada procedimento (A e B) é representado por um loop infinito, onde o recurso é acessado; É formado por protocolo de entrada, seção crítica e um protocolo de saída; A região crítica é representada por uma rotina onde o acesso realmente ocorre; Após a seção crítica as rotinas executam procedimentos individuais. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Algoritmo 1 É utilizada uma variável de bloqueio indicando qual processo poderá acessar a região crítica; Inicialmente possui o valor A indicando que o processo A terá acesso; O processo só terá acesso a região crítica, quando o processo A atribuir a variável de bloqueio o valor ‘B’; Assim fica garantindo a exclusão mútua dos processos. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua program Algoritmo 1; var Vez : char; procedure Proc_A begin repeat while (vez = ‘B’) do ; /nada Regiao_Critica_A; Vez := ‘B’; Processa_A; until false; end; procedure Proc_B begin repeat while (vez = ‘A’) do ; /nada Regiao_Critica_B; Vez := ‘A’; Processa_B; until false; end; begin Vez := ‘A’; PARBEGIN Proc_A; Proc_B; PAREND; end. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Algoritmo 1 Problema 1: O acesso ao recurso só pode ser efetuado por dois processos e sempre de maneira alternada; O processo que utiliza o recurso mais vezes que o outro, permanecerá mais vezes bloqueado; Por exemplo, de Proc_A ficar muito tempo no Processa_A, é possível que Proc_B queria usar o recurso e não o consiga, mesmo Proc_A não necessite do recurso. Caso um processo tenha o loop mais rápido que o outro, a possibilidade de usar o recurso fica limitado ao processo de velocidade menor. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Algoritmo 1 Problema 2: Se houver um problema com um processo de forma que o valor da variável de bloqueio não seja alterado, o outro processo permanecerá indefinidamente bloqueado. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Algoritmo 2 O problema principal do algoritmo 1 é que ambos processos trabalham com a mesma variável global, que indica qual processo terá acesso a região crítica; Para resolver este problema o algoritmo 2 introduz uma variável para cada processo (CA e CB), que indica se o processo está na região crítica; Assim antes de um processo entrar na sua região crítica, testa se o outro processo está usando o recurso; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua program Algoritmo 2; var CA : boolean; CB : boolean; procedure Proc_A begin repeat while (CB) do ; /nada CA := true; Regiao_Critica_A; CA:= false; Processa_A; until false; end; procedure Proc_B begin repeat while (CA) do ; /nada CB := true; Regiao_Critica_B; CB:= false; Processa_B; until false; end; begin CA:= false; CB:= false; PARBEGIN Proc_A; Proc_B; PAREND; end. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Algoritmo 2 Neste caso o uso do recurso não é realizado, necessariamente, alternado; Caso um processo tenha um problema fora da região crítica não bloqueia o outro processo; Mas se um processo tiver um problema na região crítica ou antes de alterar o valor da variável, bloqueará, indefinidamente, o outro processo; Mas, o mais grave é que este algoritmo nem sempre garante a exclusão mútua; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Algoritmo 3 Este algoritmo tenta solucionar o problema do algoritmo 2, colocando a instrução de atribuição de CA e CB antes do loop de teste; Este algoritmo garante a exclusão mútua, mas introduz a possibilidade do bloqueio indefinido de ambos os processos; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua program Algoritmo 3; var CA : boolean; CB : boolean; procedure Proc_A begin repeat CA := true; while (CB) do ; /nada Regiao_Critica_A; CA:= false; Processa_A; until false; end; procedure Proc_B begin repeat CB := true; while (CA) do ; /nada Regiao_Critica_B; CB:= false; Processa_B; until false; end; begin CA:= false; CB:= false; PARBEGIN Proc_A; Proc_B; PAREND; end. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Algoritmo 4 No algoritmo 3, cada processo altera o estado da sua variável desconhecendo o estado do outro processo – este é o problema; Altera o algoritmo 3 de forma que altera o estado o estado da variável antes de entrar a região crítica (como no algoritmo 3), porém existe a possibilidade de reverter esta alteração; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua program Algoritmo 4; var CA : boolean; CB : boolean; procedure Proc_A begin repeat CA := true; while (CB) do begin CA:= false; {pequeno intervalo de tempo aleatório} CA := true; end; Regiao_Critica_A; CA:= false; Processa_A; until false; end; procedure Proc_B begin repeat CB := true; while (CA) do begin CB:= false; {pequeno intervalo de tempo aleatório} CB := true; end; Regiao_Critica_B; CB:= false; Processa_B; until false; end; begin CA:= false; CB:= false; PARBEGIN Proc_A; Proc_B; PAREND; end. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Algoritmo 4 Esta solução garante exclusão mútua e não gera bloqueio simultâneo dos processos; Mas, no caso dos tempos aleatórios serem próximos e a concorrência gerar uma situação onde os processos alterem as variáveis CA e CB para falso antes do término do loop, nenhum dos processos conseguirá executar a sua região crítica, mesmo não sendo permanente, esta situação pode gerar problemas Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Algoritmo de Dekker Primeira solução de software que garantiu a exclusão mútua entre dois processos sem problemas foi proposto por T. Dekker; Este algoritmo possui uma lógica bastante complexa; Ver no livro texto as referencias; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Algoritmo de Peterson Facilmente generalizada para N processos; Similar ao algoritmo 3, além das variáveis de condição (CA e CB), introduz a variável Vez para gerar os conflitos gerados pela concorrência; Antes de acessar a região crítica, o processo sinaliza este desejo (variável de condição), porém o processo cede o uso do recurso (variável Vez); O processo executa o while (protocolo de entrada); Assim além de garantir a exclusão mútua, o bloqueio indefinido nunca ocorrerá, pelo uso da variável Vez; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua program Algoritmo_Peterson; var CA : boolean; CB : boolean; Vez : char; procedure Proc_A begin repeat CA := true; Vez := ‘B’; while (CB and Vez = ‘B’) do ; /nada Regiao_Critica_A; CA:= false; Processa_A; until false; end; procedure Proc_B begin repeat CA := true; Vez := ‘A’; while (CA and Vez = ‘A’) do ; /nada Regiao_Critica_B; CB:= false; Processa_B; until false; end; begin CA:= false; CB:= false; PARBEGIN Proc_A; Proc_B; PAREND; end. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Exclusão Mútua Algoritmo para exclusão mútua para N processos: O algoritmo de Peterson foi generalizado para N processos, Hofri (1990); O algoritmo do Padeiro (bakey Algorithm) proposto por Lamport(1974); Problema espera ocupada (busy wait), este caso, quando um processo não consegue entrar em sua região crítica, este processo permanece em loop testando uma condição, consumino recurso do processador; A solução para este problema foi a introdução de mecanismo de sincronismo que permitem colocar um processo em estado de espera, quando estiver esperando para entrar na região crítica. (semáforos e monitores) Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Sincronização Condicional Sincronização condicional é quando o acesso a um recurso compartilhado exige uma sincronização entre os processos; Exemplo clássico é a comunicação entre dois processos através de operações de gravação e leitura em um buffers; Os processos devem estar sincronizados para que um processo não tente ler um buffer vazio nem gravar em um buffer cheio; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Sincronização Condicional Este problema é conhecido como problema do produtor/consumidor ou do buffer limitado; No algoritmo na próximo slide, o recurso compartilhado é um buffer, definido como tamanho TamBuf, sendo o acesso controlado pela variável Cont; Cont: Igual a zero: significa que o buffer está vazio, e o processo Consumidor deve esperar; Igual a TamBuf: significa que o buffer está cheio, e o processo Produtor deve esperar; O algoritmo resolve a questão da sincronização condicional, mas apresenta o problema da espera ocupada; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Sincronização Condicional PROGRAM Produtor_Consumidor_1; CONST TamBuf = ( *Tamanho *); TYPE Tipo_Dado = (* Tipo *); VAR Buffer : ARRAY [1..TamBuf] OF Tipo_Dado; Dado : Tipo_Dado; Cont : 0..TamBuf; BEGIN Cont := 0; PARBEGIN Produtor; Consumidor; PAREND; END. PROCEDURE Produtor; BEGIN REPEAT Produz_Dado (Dado); WHILE (Cont = TamBuf) DO (*nada*); Grava_Buffer(Dado, Cont); UNTIL False; END; PROCEDURE Consumidor; BEGIN REPEAT WHILE (Cont = 0) DO (*nada*); Le_Buffer (Dado); Consome_Dado(Dado, Cont); UNTIL False; END; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos Proposto por E. W. Dijkstra em 1965; Mecanismo de sincronização que permite implementar a exclusão mútua e a sincronização entre processos de forma simples; Tornou-se um dos principais mecanismos utilizados em projeto de S.O. e aplicações concorrentes; A maioria das linguagens de programação disponibiliza rotinas para utilizá-los; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos Semáforos são: Uma variável inteira não negativa; Manipulados através das seguintes operações indivisíveis: UP (Proberen – teste): incrementa o valor da variável; DOWN (Verhigen – incremento): decrementa o valor da variável; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos Semáforos são: A variável não pode ser negativa, assim um DOWN em um semáforo com valor zero, faz o processo entrar no estado de espera; Normalmente implementada em hardware; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos Os semáforos podem ser: Binários (mutexes): só podem assumir os valores zero e um; Contadores: podem assumir qualquer valor inteiro positivo e zero; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos Exclusão mútua: Pode ser implementada com o uso de semáforos binários associado aos recursos compartilhados; Principal vantagem: não ocorre a espera ocupada; As instruções DOWN e UP funcionam como protocolo de entrada e saída; Quando o valor é um, indica que o recurso está disponível, e se for zero significa que algum processo está utilizando o recurso; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos Exclusão mútua: Quando for entrar na região crítica, o processo executa um DOWN; Se o semáforo for igual a um, este valor é decrementado e o processo entra na região crítica; Se o valor for zero, então o processo impedido de entrar na seção crítica, e seu estado passa a ser de espera, liberando o processador. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos Exclusão mútua: O processo ao sair da região crítica, deve liberar o recurso compartilhado, para tanto, basta executar a instrução UP; Caso existam vários processos esperando a liberação do recurso, o S.O. selecionará um, mudando seu estado de espera para pronto – próximo slide; Não existe a espera ocupada; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos Semáforo binário na exclusão mútua Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos TYPE Semaforo =record Valor : integer; Fila_espera: (*lista dos processos em espera*) end; Procedure DOWN (VAR S: Semaforo); begin if (S = 0) then Coloca_Processo_na_Fila_de_Espera else S = S – 1; End; Procedure UP (VAR S: Semaforo); begin S = S + 1; If (Processo_Esperando) then Retira_da_Fila_de_Espera. End; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos Program Semaforo_1 Var S : Semaforo = 1; Procedure Proc_A; begin repeat DOWN(S); Região_Critica_A; UP (S); until false; end; Procedure Proc_B; begin repeat DOWN(S); Região_Critica_B; UP (S); until false; end; begin PARABEGIN Proc_A; Proc_B; PARAEND; End. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos Sincronização condicional: Pode-se implementar a sincronização condicional; Exemplo: solicitação de E/S, o processo que solicita a E/S executa um DOWN e fica em estado de espera até a operação de E/S ser completada; Quando a operação de E/S finaliza a rotina de tratamento de interrupção excuta um UP, liberando o processo do estado de espera; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos Program Semaforo_2; var Evento: Semaforo := 0; Procedure Solicita_Leitura; begin DOWN(Evento) End; Procedure Le_Dados; Begin UP(Evento) End; Begin PARABEGIN Solicita_leitura; Le_Dados; PARAEND; End; Algoritmo para sincronização condicional: Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos O problema do produtor/consumidor pode ser resolvido com o uso de semáforos; Para tanto: Usa buffer de duas posições; Um semáforo binário para garantir a exclusão mútua; Dois semáforos contadores (Vazio e Cheio) para a sincronização condicional; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos Program Produtor_consumidor_2 Const TB = 2; TYPE TDado = (*qualquer*) VAR Vazio: semaforo := TB; Cheio: semaforo := 0; Mutex: semaforo := 1; Buffer: array[1..TB] of TDado; Dado_1: TDado; Dado_2: TDado; Procedure Produtor begin repeat Produz_Dado (Dado_1); Down (Vazio); Down (Mutex); Grava_Buffer(Dado_1, Buffer); Up(Mutex); Up(Cheio); until false; end; Procedure consumidor; begin repeat Down(Cheio); Down(Mutex); Le_Buffer(Dado_2, buffer); Up(Mutex); Up(Vazio); until false; End; begin parabegin Produtor; Consumidor; paraend; end. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos Semáforos contadores são úteis quando existem processos concorrentes alocando recursos do mesmo tipo (pool de recursos); O semáforo começa com número total de recursos do pool; Quando necessitar de recurso executa um DOWN; Quando liberar o recurso executa um UP; Caso o semáforo contador seja zero, o processo que executar um DOWN ficará em estado de espera. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Semáforos Problemas Problema dos filósofos; Problema do barbeiro; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Monitores Monitores são mecanismos de sincronização de alto nível que tornam mais simples o desenvolvimento de aplicações concorrentes; Proposto por Binch Hansen, 1972 e desenvolvido por C.A.R. Hoare em 1974; Mecanismo de sincronização estruturado, diferente de semáforos, considerados não-estruturados; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Monitores Diferentemente dos semáforos, os monitores são implementados pelo compilador, menos sujeito a erros; Inicialmente implementado em poucas linguagens (Concurrent Pascal, Modula-2, Modula-3) Atualmente, a maioria das linguagens disponibiliza este recurso; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Monitores O monitor é formado por procedimentos e variáveis encapsulado dentro de um módulo; Sua principal característica é a implementação da exclusão mútua entre os procedimentos declarados; Toda vez que é chamado um dos procedimentos, o monitor verifica se outro procedimento esta sendo executado, em caso afirmativo, o procedimento que quer ser executado fica em espera; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Monitores Toda inicialização de variáveis é realizada por um bloco de comandos, sendo executada apenas uma vez, na ativação do programa; Um monitor é definido especificando: Um nome; Declarando: variáveis locais; Procedimentos; Código de inicialização; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Monitores Estrutura do monitor Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Monitores Monitor Exclusao_Mutua; (* variáveis locais *) procedure Regiao_Critica_1; begin : End; Procedure Regiao_Critica_2; Begin : end; Procedure Regiao_Critica_3; begin : end; begin (* código de inicialização *) end. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Monitores Exclusão mútua A implementação mútua utilizando monitores não é realizada diretamente pelo programador; As regiões críticas são definidas como procedimentos no monitor e o compilador garante a exclusão mútua; A comunicação do procedimento e monitor é executada através de chamada a procedimentos e dos parâmetros passados; A seguir, um exemplo, onde processos somam e subtraem um concorrentemente; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Monitores program monitor_1 Monitor Rgião_Critica; var X : integer; procedure Soma; begin X := X + 1; end; Procudure Subtrai; begin X := X – 1; end; begin X:= 0; end; begin PARABEGIN Regiao_Critica.Soma; Regiao_Critica.Susbtrai; PARAEND; end; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Monitores Sincronização condicional: A sincronização condicional pode ser implementada utilizando-se de monitores através de variáveis especiais de condição; É possível associar a execução de um procedimento que faz parte do monitor a uma determinada condição, garantindo a sincronização condicional; Esta variáveis são manipuladas através de duas instruções: WAIT; SIGNAL; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Monitores Sincronização condicional: WAIT coloca o processo no estado de espera, até que outro processo envie um SIGNAL, informado que a condição de espera foi satisfeita; Caso se execute um SIGNAL sem que um processo esteja aguardando, nenhum efeito terá; É possível ter vários processos com sua execução suspensa, assim, o monitor organiza filas associadas as condições de sincronização; O SIGNAL libera apenas um único processo da fila de espera da condição associada; Um processo pode executar um procedimento no monitor, mesmo quando um ou mais processos estão na fila de espera; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Monitores Estrutura do monitor com variáveis de condição Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Monitores Sincronização condicional: Uma solução para o problema do produtor/consumidor usando-se monitor é apresentado no próximo slide; O monitor condicional é estruturado com duas variáveis especiais de condição (cheio e vazio) e dois procedimentos (produz e consome) Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Monitores Monitor Condicional; Var Cheio : (* variável especial de condição *) Vazio : (* variável especial de condição *) procedure Produz; begin if (Cont = TamBuf) then WAIT (cheio); : if (Cont = 1) then SIGNAL (vazio); end; procedure Consume; begin if (Cont = 0) then WAIT (vazio); : if (Cont = Tambuf - 1) then SIGNAL (cheio); end; begin end; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Monitores Sempre que o produtor desejar gravar um dado, deve chamar o procedimento Produz, que testa se existe posições vagas no buffer, se não tiver, deve executar um WAIT em cheio, suspendendo a execução até que um outro processo execute um SIGNAL em cheio; No caso do consumidor, deve executar o procedimento Consume sempre que desejar ler um dado do buffer, caso o buffer esteja vazio deve suspender a sua execução efetuando um WAIT no vazio e esperar um SIGNAL no vazio para continuar; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Monitores No próximo slide uma solução completa para o problema Produtor/Consumidor utilizando-se de monitor condicional; Os procedimentos Produz_Dado e Consome_Dado servem para entrada e saída de dados; Os procedimentos Grava_Dado e Le_Dado são responsáveis pela transferência e recuperação do dado no buffer; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Monitores Program Pro_Con_3; Const TamBuf = (* tamanho do buffer *) Dado : array[1..TamBuf] of (*tipo dado *) Monitor Condicional; Var Cheio : (* variável especial de condição *) Vazio : (* variável especial de condição *) Cont : integer; procedure Produz; begin if (Cont = TamBuf) then WAIT (cheio); Grava_Dado (Dado, buffer); Cont = Cont + 1; if (Cont = 1) then SIGNAL (vazio); end; procedure Consume; begin if (Cont = 0) then WAIT (vazio); Le_Dado (Dado, buffer); Cont = Cont - 1; if (Cont = Tambuf-1) then SIGNAL (cheio); end; begin Cont := 0; end; procedure Produtor begin repeat Produz_Dado (Dado); Condicional.Produz; until false; end; Procedure Consumidor; begin repeat Condicional.Consome; Consome_Dado (Dado); until false; end; begin PARABEGIN Produtor; Consumidor; PARAEND; end. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Troca de Mensagens Troca de mensagens é um mecanismo de comunicação e sincronização entre processos; O S.O. possui um subsistema de troca de mensagens, sem que haja necessidade do uso de variáveis compartilhadas; Para a comunicação entre processos deve existir um canal de comunicação, este podendo ser um buffer ou um linke de comunicação; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Troca de Mensagens Os processos cooperativos trocam mensagens através de duas rotinas: SEND(receptor, mensagem); Envia uma mensagem para um processo receptor; RECEIVE (transmissor, mensagem); Recebe a mensagem enviada por um processo transmissor; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Troca de Mensagens Transmissão de mensagem Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Troca de Mensagens Este mecanismo exige que os processos envolvidos tenham suas execuções sincronizadas; Isto é necessário, já que a mensagem só pode ser tratada após o seu recebimento; Ou que o envio de uma mensagem pode ser condição para a continuação da execução do processo; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Troca de Mensagens a troca de mensagens pode ser implementada de duas formas: Comunicação direta; Comunicação indireta; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Troca de Mensagens Comunicação direta Exige ao enviar ou receber uma mensagem o processo enderece explicitamente o nome do processo receptor ou transmissor; Só permite a troca de mensagens entre dois processos; O principal problema é a necessidade de especificação do nome dos processos envolvidos; Se mudar a identificação dos processos deve-se alterar o código do programa; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Troca de Mensagens Comunicação direta Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Troca de Mensagens Comunicação indireta; Utiliza-se uma área compartilhada, onde as mensagens pode ser escritas e lidas; Esse tipo de buffer é conhecido como mailbox ou port; Suas características (identificação, capacidade, etc.) são definidas no momento a criação; Vários processos podem estar associado a um mailbox, e as rotinas SEND e RECEIVE passam o nome do mailboxes e não mais o nome dos processos; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Troca de Mensagens Comunicação indireta Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Troca de Mensagens Independente do mecanismo de comunicação utilizado, os processos envolvidos devem ter suas execuções sincronizadas em função do fluxo de mensagens; Um processo não pode tratar de uma mensagem que não recebeu; Um processo não pode receber a mesma mensagem mais de uma vez; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Troca de Mensagens Esquemas para implementar o sincronismo: Manter o processo transmissor esperando até a confirmação de leitura; Um processo ao tentar receber uma mensagem ainda não enviada, deve permanecer esperando até que o processo transmissor faça o envio; Este esquema implementa uma comunicação síncrona, conhecida como rendezvous; O problema é que a execução dos processos fica limitado ao tempo de processamento da mensagens; Uma variação mais eficiente de rendezvous, é não bloquear o processo transmissor; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Troca de Mensagens Esquemas para implementar o sincronismo: No terceiro esquema é implementado uma forma assíncrona de comunicação; O processo transmissor e receptor não permanecem esperado o envio e recebimento da mensagem; Além dos buffers para armazenar as mensagens devem haver mecanismos para permitir ao processo identificar se uma mensagem já foi enviada ou recebida; A grande vantagem é aumentar a eficiência de aplicações concorrentes; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Troca de Mensagens Program Prod_Con_4 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; begin PARABEGIN Produtor; Consumidor; PARAEND; End. Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock Deadlock é a situação em que um processo aguarda por um recurso que nunca estará disponível; Normalmente, conseqüência de compartilhamento de recursos em processos concorrentes onde a exclusão mútua é exigida; Torna-se mais freqüente e crítico com a evolução dos S.O. implementado o paralelismo e alocação dinâmica de recursos; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock Próxima figura exemplo de deadlock conhecido como espera circular; Cada processo espera que outro processo libere o recurso alocado; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock Espera circular Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock Condições necessárias Exclusão mútua; cada recurso só pode estar alocado a um único processo; Espera por recurso; Um processo pode estar esperando por outros recursos Não-preempção; Um recurso não pode ser liberado de um processo, só porque outros processos desejam o mesmo recurso; Espera circular; Um processo pode ter de esperar por um recurso alocado a outro processo e vice-versa; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock Deadlock existe em qualquer sistema multiprogramável; As solução implementas devem considerar o tipo do sistema e o impacto em seu desempenho; usina nuclear x folha de pagamento Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock Prevenção Para evitar o deadlock evitar que uma das condições citadas não ocorra; Ausência da primeira condição (exclusão mútua), a falta da exclusão mútua gerará várias inconsistências já mencionadas; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock Ausência da segunda condição (espera por recurso): Processos que já possuam recursos garantidos não devem requisitar novos recursos; Uma forma é pré-alocar todos os recursos necessários a um processo; Esta solução pode gerar um grande desperdício de recursos; É difícil determinar o número de recursos que um processo utiliza; O mais grave é a possibilidade sofrer starvation; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock Ausência da terceira condição (não-preempção): Pode ser evita se permitir que um recurso seja retirado do processo no caso de outro precisar; A liberação de recursos já garantidos pode ocasionar sérios problemas, podendo até impedir a continuidade do processo; Pode ocorre starvation; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock Ausência da quarta condição (espera circular); Forçar que o processo só tenha um recurso por vez; Esta condição restringiria muito o grau de compartilhamento e o processamento de programas; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock A prevenção de Deadlock (evitando uma das quatro condições) é bastante limitada e não é utilizada na prática; É possível evitar o deadlock, mesmo com as quatro condições presentes; A solução mais conhecida é o Algoritmo do Banqueiro (Bank’s Algorithm) proposto por Dijkstra(1965); Basicamente, este algoritmo exige que os processos informem o número máximo de cada tipo de recurso necessário a sua execução; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock Com estas informações, é possível definir o estado de alocação de cada recurso, que é a relação entre o número de recursos alocados e disponíveis e o número máximo de processos que necessitam desses recursos. Com estas informações, o S.O. pode alocar os recursos evitando o deadlock (Tanenbaum 2001); Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock Este algoritmo possui várias limitações, a maior é a necessidade de um número fixo de processos ativos e de recursos disponíveis; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock Detecção do deadlock É necessário mecanismos de detecção de deadlock, onde não existam prevenção de deadlock; Esta detecção identifica a existência de deadlock e quais os recursos e processos envolvidos neste problema; Para tanto é necessário ao S.O. manter estruturas de dados para identificar cada recurso do sistema, o processo que o está alocando e os processos que estão a espera para usar o recurso; Geralmente os algoritmos que verificam a espera circular percorrem esta estrutura sempre que um processo solicita um recurso; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock Detecção do deadlock Dependendo do S.O. o ciclo de busca de deadlock pode variar; Em sistema de tempo compartilhado o tempo de busca pode ser maior, sem comprometer-lo; Sistemas de tempo real devem constantemente verificar, porém a maior segurança leva a um maior overhead; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock Correção Uma solução bastante utilizada é eliminar um ou mais processos envolvidos no deadlock desalocando recursos, quebrando assim a espera circular; A eliminação de processos não é simples, dependendo do tipo de recurso envolvido; Por exemplo: impressão e gravação em disco; Os processos eliminados não tem como ser recuperados, mas os outros processos envolvidos no deadlock continuarão; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock Correção A escolha do processo, normalmente, é feita de forma aleatória, ou com base em algum tipo de prioridade; Este esquema pode consumir tempo considerável do processador, aumentando overhead; Uma solução menos drástica envolve a liberação de alguns recursos até que o ciclo termine; Para esta solução ser eficiente, é necessário que o sistema pode suspender um processo, liberar seus recursos e após a solução, possa retornar ã execução, sem perder o processamento já realizado; Arquitetura de Sistemas Operacionais – Machado/Maia Cap. 7 – Sincronização e Comunicação * Deadlock Correção Este mecanismo é conhecido com rollback: Além do overhead; É muito difícil de ser implementado; É bastante dependente da aplicação;
Compartilhar