SO_3_ProgramacaoConcorrente

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Sistemas 
Operacionais
Prof. Razer
Prof Razer A N R Montaño 2Sistemas Operacionais
Conteúdo
1. Introdução
2. Multiprogramação
3. Programação Concorrente
4. Gerência do Processador
5. Gerência de Memória
6. Sistema de Arquivos
 
 
Prof Razer A N R Montaño 3Sistemas Operacionais
Programação Concorrente
� Programa sequencial
� Programa executado por só um processo
� Só um fluxo de controle de execução
� Programa concorrente
� É executado por diversos processos simultâneos
� Cooperação, troca de informações, dados, sincronização
� Vários fluxos de execução
� Deve-se possuir cooperação para ser concorrente
� Variáveis compartilhadas, troca de mensagens
� Concorrente: cooperar, ao mesmo tempo
� Um programa executado por vários usuários não é 
concorrente
� Interprocess Comunication (IPC): Comunicação entre 
processos
Prof Razer A N R Montaño 4Sistemas Operacionais
Programação Concorrente
� Mais complexa que a sequencial
� Apresentam todos os tipos de erros comuns, mais os 
específicos
� Depende da velocidade relativa dos processos
� Erros difíceis de identificar
� Existem áreas em que se torna útil
� Máquinas paralelas
� Processos com tempos diferentes
� Tarefas paralelas
� Etc
 
 
Prof Razer A N R Montaño 5Sistemas Operacionais
Programação Concorrente
� Exemplo Sequencial: Ler um arquivo, formatá-lo e 
imprimi-lo
ProcessoArquivo Impressora
� Leitura do arquivo
� Processo bloqueado
� Realiza Formatação
� Envia para Impressora
� Processo bloqueado (buffer de impressora pequeno) 
Prof Razer A N R Montaño 6Sistemas Operacionais
Programação Concorrente
Disco
Processo
Impressora
tempo
Esperando
Executando
Enviando Dados
ProcessoArquivo Impressora
 
 
Prof Razer A N R Montaño 7Sistemas Operacionais
Programação Concorrente
� Processo Leitor
� Lê o arquivo, formata e insere no buffer
� Processo Impressor
� Retira dados do buffer e envia para impressora
Processo
LeitorArquivo
Impressora
Processo
ImpressorBuffer
� Exemplo Concorrente: Ler um arquivo, formatá-lo e 
imprimi-lo
Prof Razer A N R Montaño 8Sistemas Operacionais
Programação Concorrente
Disco
Impressora
Processo
Leitor
tempo
Esperando
Executando
Enviando Dados
Processo
Impressor
� Disco e impressora trabalhando ao mesmo tempo!
Processo
Leitor
Arquivo
Impressora
Processo
ImpressorBuffer
 
 
Prof Razer A N R Montaño 9Sistemas Operacionais
Programação Concorrente
� Grande motivação: Engenharia de Software
� Aplicações inerentemente paralelas
� Protocolos de comunicação
� Supervisão (ex. medicina)
� Controle Industrial
� Sistemas Operacionais
� Onde programas sequenciais são mais ineficientes
� Exemplo: Servidor de Impressão
� Deve Receber e enviar solicitações pela rede
� Deve Enviar para impressora e armazenar em disco
� Etc.
Prof Razer A N R Montaño 10Sistemas Operacionais
Arquitetura Servidor de Impressão
Barramento
Receptor Transmissor
Protocolo
Escritor
Leitor Impressor
Servidor de
Impressão
 
 
Prof Razer A N R Montaño 11Sistemas Operacionais
Especificação do Paralelismo
� Especificação do paralelismo
� Quantos processos
� Que rotinas cada um executará
� Indicação de novo fluxo ou fluxo paralelo
� Dois tipos mais usados:
� Comandos: create_process, exit, wait_process
� Estruturas: Parbegin e Parend
Prof Razer A N R Montaño 12Sistemas Operacionais
Especificação do Paralelismo
� Comandos
� Como funções dentro de um programa
� create_process()
� Criação de um novo fluxo
� Paralelo ao de chamada
� Indica-se a função que irá executar
� exit()
� O fluxo de controle é imediatamente terminado
� Comandos após exit() não são executados
� wait_process()
� Espera outro fluxo terminar
� Indica-se qual fluxo se deseja esperar
 
 
Prof Razer A N R Montaño 13Sistemas Operacionais
Especificação de Paralelismo
main() {
 int f1, f2;
 printf(“Alo do pai\n”);
 f1 = create_process( codigo_do_filho );
 f2 = create_process( codigo_do_filho );
 wait_process(f1);
 printf(“Filho 1 morreu\n”);
 wait_process(f2);
 printf(“Filho 2 morreu\n”);
 exit();
}
codigo_do_filho() {
 printf(“Alo do filho\n”);
 exit();
}
Prof Razer A N R Montaño 14Sistemas Operacionais
Especificação do Paralelismo
� Primeira Saída possível
Alo do pai
Alo do filho
Alo do filho
Filho 1 morreu
Filho 2 morreu
� Segunda Saída possível
Alo do pai
Alo do filho
Filho 1 morreu
Alo do filho
Filho 2 morreu
 
 
Prof Razer A N R Montaño 15Sistemas Operacionais
Especificação do Paralelismo
� Grafo de Dependência
� Nodos são trechos de código
� Arcos são relações de dependência
� Existe um arco de X para Y se Y só é executado depois 
de X
� É um grafo que representa o fluxo de controle
Prof Razer A N R Montaño 16Sistemas Operacionais
Especificação do Paralelismo
Alo do pai
Alo do filho
Alo do filho
create_process
create_process
wait_process f1
wait_process f2
exit
exit
filho 1 morreu
filho 2 morreu exit
 
 
Prof Razer A N R Montaño 17Sistemas Operacionais
Especificação de Paralelismo
main() {
 int f1, f2;
 printf(“Alo do pai\n”);
 f1 = create_process( codigo_do_filho );
 wait_process(f1);
 printf(“Filho 1 morreu\n”);
 // Filho 2 só começa depois que filho 1 termina
 f2 = create_process( codigo_do_filho );
 wait_process(f2);
 printf(“Filho 2 morreu\n”);
 exit();
}
codigo_do_filho() {
 printf(“Alo do filho\n”);
 exit();
}
Prof Razer A N R Montaño 18Sistemas Operacionais
Especificação do Paralelismo
� Forma mais estruturada
� Parbegin: Parallel begin
� Parend: Parallel end
� Parecido com o BEGIN e END do Pascal
� Delimitam todos os comandos que executarão em 
paralelo
� Parbegin : inicia o bloco de comandos em paralelo
� Parend : sincroniza, só continua depois que todos os 
comandos paralelos terminem
� O comando após o Parend só é executado depois que 
todos os comandos entre Parbegin e Parend terminarem
 
 
Prof Razer A N R Montaño 19Sistemas Operacionais
Especificação de Paralelismo
main() {
 int f1, f2;
 printf(“Alo do pai\n”);
 Parbegin
codigo_do_filho();
codigo_do_filho();
 Parend;
 printf(“Filho 1 morreu\n”);
 printf(“Filho 2 morreu\n”);
}
codigo_do_filho() {
 printf(“Alo do filho\n”);
 exit();
}
Os dois 'codigo_do_filho()' são
executados em paralelo
Prof Razer A N R Montaño 20Sistemas Operacionais
Especificação do Paralelismo
� Incorporação na linguagem: create_process, 
wait_process, exit
� Podem ser implementados como funções
� Biblioteca própria
� Incorporação na linguagem: Parbegin, Parend
� Re-estruturação da linguagem
� Biblioteca:
Parbegin( codigo_do_filho, codigo_do_filho)
� Tradução
Inicio();
Parbegin
 Comando1();
 Comando2();
Parend;
Fim();
Inicio();
f1 = create_process(Comando1);
f2 = create_process(Comando2);
wait_process(f1);
wait_process(f2);
Fim();
 
 
Prof Razer A N R Montaño 21Sistemas Operacionais
Especificação do Paralelismo
� Implementação: create_process()
� Cria novo processo
� Gerenciador Processador inicializa estruturas e enfileira
� Espaço de endereçamento deve ser o mesmo
� PC no novo processo é o parâmetro 
� Valor de retorno: PID (process Id)
� Implementação: wait_process(f)
� Bloqueia o processo chamador, se processo esta vivo
� Criar uma fila de processos bloqueados por causa de f
� Lista encadeada ligada a f
� Quando f termina, libera os processos na fila
� Diferenciar e armazenar quando o processo não está rodando: 
ou não está iniciado, ou já morto. 
Prof Razer A N R Montaño
22Sistemas Operacionais
Especificação do Paralelismo
� Implementação: exit()
� Chamada do sistema que destrói o processo chamador
� Verifica se tem algum processo bloqueado, e liberá-los
 
 
Prof Razer A N R Montaño 23Sistemas Operacionais
Seção Crítica
� Exemplo de um Servidor de Impressão
� Processo Escritor: bufferiza um arquivo a ser impresso em disco
� Processo Leitor: lê um arquivo armazenado a ser impresso e 
passa os dados para o Impressor
� Processo Impressor: imprime arquivo
� Processo escritor deve passar o nome do arquivo que 
está sendo escrito para o Leitor
� Processo Leitor pode estar ocupado lendo outro arquivo
� Implementação de uma fila de nomes de arquivos
� Tamanho variável, por isso: lista encadeada para 
implementar a fila
Prof Razer A N R Montaño 24Sistemas Operacionais
Seção Crítica
Estrutura da Fila (lista encadeada de nomes)
struct registro {
 char nome_do_arquivo[64];
 struct registro *prox;
}
struct registro *inicio = NULL; // Primeiro elemento da fila
struct registro *fim = NULL; // Ultimo elemento da fila
 
 
Prof Razer A N R Montaño 25Sistemas Operacionais
Seção Crítica
� Escritor
void escritor(void) {
 struct registro *registro_novo;
 ... // preenche
 registro_nome->prox = NULL;
 if (inicio == NULL) { // fila vazia
 inicio = registro_novo;
 fim = registro_novo;
 }
 else { // fila não vazia
 fim->prox = registro_novo;
 fim = registro_novo;
 }
}
Prof Razer A N R Montaño 26Sistemas Operacionais
Seção Crítica
� Leitor
void leitor(void) {
 struct registro *ler;
 ... 
 // espera até ter um nome na fila
 while (inicio == NULL) 
 ;
 // retira o primeiro nome da fila
 ler = inicio;
 inicio = inicio->prox;
 if (inicio == NULL)
 fim = NULL;
 .. // lê o arquivo cujo nome está em “ler”
 
 
Prof Razer A N R Montaño 27Sistemas Operacionais
Seção Crítica
� Se rodarem em momentos distintos
� OK
� Se rodarem ao mesmo tempo
� Tentarão acessar os mesmos dados ao mesmo tempo
� Fila: inicio e fim
� Não se pode predizer em que instantes eles acessarão os 
dados
� Trabalham com relativa independência
Prof Razer A N R Montaño 28Sistemas Operacionais
Seção Crítica
void escritor(void) {
 struct registro *registro_novo;
 ... // preenche
 registro_nome->prox = NULL;
 if (inicio == NULL) {
 inicio = registro_novo;
 fim = registro_novo;
 }
 else {
 fim->prox = registro_novo;
 fim = registro_novo;
 }
}
void leitor(void) {
 struct registro *ler;
 ... 
 while (inicio == NULL) 
 ;
 ler = inicio;
 inicio = inicio->prox;
 if (inicio == NULL)
 fim = NULL;
 // lê arquivo em “ler”
I
F
abc
1
I
F
abc
2
I
F
novo
3
abc
I
F
novo
4
abc
Suspenso
Só tem um arquivo Leitor vai removê-lo Escritor executa Leitor continua
Leitor
Suspenso
 
 
Prof Razer A N R Montaño 29Sistemas Operacionais
Seção Crítica
� Dois processos acessando mesmos dados ao mesmo 
tempo
� Variáveis compartilhadas podem ser o mecanismo de 
comunicação entre os processos
� SOLUÇÃO: restringir acesso
� Outro exemplo:
int x;
x = 0;
Parbegin
 ++x;
 ++x;
Parend;
� Espera-se que x valha 2, mas não é garantia
Prof Razer A N R Montaño 30Sistemas Operacionais
Seção Crítica
� Em MIPS, ++x ficaria, supondo que está no endereço 
armazenado em $s5:
lw $t0, 0($s5)
addi $t0, $t0, 1
sw $t0, 0($s5) 
� Esse trecho de código executa em paralelo, por dois 
processos separados
 
 
Prof Razer A N R Montaño 31Sistemas Operacionais
Seção Crítica
X: 0 $t0 de P1: ? $t0 de P2: ?
P1: lw $t0, 0($s5)
Processo 1 Processo 2
X: 0
X: 0
X: 0
X: 0
X: 1
X: 1
P1: addi $t0, $t0, 1
P2: lw $t0, 0($s5)
P2: addi $t0, $t0, 1
P2: sw $t0, 0($s5)
P1: sw $t0, 0($s5)
$t0 de P1: 0 $t0 de P2: ?
$t0 de P1: 1 $t0 de P2: ?
$t0 de P1: 1 $t0 de P2: 0
$t0 de P1: 1 $t0 de P2: 1
$t0 de P1: 1 $t0 de P2: 1
$t0 de P1: 1 $t0 de P2: 1
Prof Razer A N R Montaño 32Sistemas Operacionais
Seção Crítica
� Seção crítica: parte do código de um processo que 
acessa dados compartilhados
� Exemplo:
� Servidor de impressão: leitura/escrita da fila
� ++x: código que soma x
� O problema da seção crítica é garantir que se um 
processo está executando sua seção crítica nenhum 
outro processo poderá entrar na sua respectiva seção 
crítica
� Existem várias soluções para o problema
 
 
Prof Razer A N R Montaño 33Sistemas Operacionais
Seção Crítica
� Uma solução estará correta quando:
� Exclusividade mútua entre os processos na execução das 
seções críticas
� Quanto um processo deseja entrar na seção crítica e nenhum 
outro está na sua seção crítica, ele não é impedido de entrar
� Nenhum processo pode ter seu ingresso na seção crítica 
postergado indefinidamente
� A solução não depende das velocidades relativas dos processos
� Soluções erradas apresentam postergação indefinida ou 
deadlocks
� Solução simples: Desabilitar interrupções. 
� Quando entra na seção crítica, desabilita interrupções
� Quando sai, habilita novamente
� Nenhum outro processo ganhará o processador nesse tempo
Prof Razer A N R Montaño 34Sistemas Operacionais
Seção Crítica
� Usado em sistemas dedicados a uma única aplicação 
(sistemas embutidos)
� Fere os princípios de proteção vistos anteriormente
� Não pode ser considerado um método genérico para 
solução do problema da seção crítica
� Diminui a eficiência, visto que periféricos não são 
atendidos
� Não funciona em máquinas paralelas, pois o controle de 
interrupções é feito por processador
 
 
Prof Razer A N R Montaño 35Sistemas Operacionais
Seção Crítica
� Algumas soluções apresentam protocolo de acesso
� Executam algoritmo na entrada e saída da sua 
respectiva seção crítica
� Não usam chamadas ao S.O. nem instruções 
privilegiadas
� São muito complexas
� Apresentam a propriedade busy-waiting
� Quando fica num laço vazio esperando um evento
while (inicio==NULL)
;
Prof Razer A N R Montaño 36Sistemas Operacionais
Seção Crítica
� Pode acontecer deadlock em soluções com busy-waiting 
quando se usa prioridades para escalonar processo
� Deadlock: dois ou mais processos ficam na espera de 
um evento que não vai acontecer
� Algumas possíveis soluções
� Spin-Lock
� Semáforos
 
 
Prof Razer A N R Montaño 37Sistemas Operacionais
Spin-Lock
� Solução para o problema da Seção crítica
� Spin-Lock ou Test-and-Set
� Baseada numa instrução de máquina “Test-and-set”
� Pode ser usada uma instrução do tipo “Swap” ou “Compare on 
Store”
� Instrução SWAP(reg, mem)
� Troca o valor de uma posição de memória com um registrador
aux = Memoria[mem]
Memoria[mem] = reg
reg = aux
� Deve ser atômica
Prof Razer A N R Montaño 38Sistemas Operacionais
Spin-Lock
� Seção crítica: protegida por uma variável que ocupa a 
posição Memoria[mem]: lock
� Valores para lock:
� 0: seção crítica livre
� 1: seção crítica ocupada
� Inicializada em 0
� Inicialização
int lock;
lock = 0;
� Antes de entrar na seção, fecha a porta
do {
 reg = 1;
 swap(reg, lock);
} while (reg == 1);
// Código da seção crítica
 
 
Prof Razer A N R Montaño 39Sistemas Operacionais
Spin-Lock
� Ao sair da seção crítica, abre a porta
lock = 0;
� Vantagens
� Simplicidade
� Não precisa desabilitar interrupções
� A maioria dos processadores têm a instrução necessária
� Desvantagem
� Busy-waiting
� Possível postergação infinita (processo nunca pega o lock)
� Usado quando a seção crítica é pequena, probabilidade
de estar ocupada menor
Prof Razer A N R Montaño 40Sistemas Operacionais
Semáforos
� Mecanismo de sincronização entre processos
� Criado por Dijkstra em 1965
� É um Tipo Abstrato de Dados composto por:
� Valor Inteiro
� Fila de Processos
� Operação P (do holandês proberen, testar)
� Operação V (do holandês verhogen, incrementar)
� Usa o valor inteiro para definir se o processo é 
bloqueado ou não
 
 
Prof Razer A N R Montaño 41Sistemas Operacionais
Semáforos
� Ao executar P sobre um semáforo S
� Valor inteiro é decrementado
� Se o novo valor é negativo
� Processo é bloqueado
� Inserido no fim da fila deste semáforo
P(S):
 S.valor = S.valor – 1;
 Se S.valor < 0
 Bloqueia processo, insere no fim da fila
� Ao executar V sobre um semáforo S
� Valor inteiro é incrementado
� Caso exista algum processo bloqueado na fila
� O primeiro da fila é liberado
V(S):
 S.valor = S.valor + 1;
 Se S.fila não está vazia
 Retira P do início da fila, acorda P
Prof Razer A N R Montaño 42Sistemas Operacionais
Semáforos
� As operações P e V devem ser atômicas
� Simplicidade no uso
� Para cada estrutura de dados compartilhada deve-se
� Criar um semáforo inicializado em 1
� Todo processo, antes de acessar a estrutura deve executar P
� Ao terminar, deve executar V
� O problema dos incrementos ficaria:
int x = 0;
Semaphore S = 1;
Parbegin
 Begin P(S);
 ++x;
 V(S);
 End;
 Begin P(S);
 ++x;
 V(S);
 End;
Parend;
 
 
Prof Razer A N R Montaño 43Sistemas Operacionais
Semáforos
� Podem ser usados para definir relações de precedência
Semaphore S = 0;
Parbegin
 Begin 
 p0funcao1(); // processo p0
 V(S);
 p0funcao2();
 End;
 Begin 
 p1funcao1(); // processo p1
 P(S);
 p1funcao2();
 End;
Parend;
Bloqueia o semáforo
Libera o semáforo Ordem:
 1 – p0funcao1()
 2 – p1funcao2()
Prof Razer A N R Montaño 44Sistemas Operacionais
Semáforos
� Variações
� Não permitir valores negativos
� Ordenar a fila do semáforo conforme alguma prioridade
� Além de P e V, mais uma função que consulta o status
� Mutex ou semáforo binário (0/1, livre/ocupado)
lock(S):
 Se S está livre
 Marca S como ocupado
 Senão
 Insere processo no fim da fila de S
unlock(S):
 Se fila de S está vazia
 Marca S como livre
 Senão
 Retira processo no início da fila de S
 
 
Prof Razer A N R Montaño 45Sistemas Operacionais
Implementação de Semáforos
� As instruções P e V devem ser atômicas
� Maneira mais fácil: 
� Desabilitar interrupções
� Serem chamadas de sistema
� Acrescentar chamadas para criar e destruir semáforos
� Em sistemas com vários processadores
� Tornar a chamada a P e V também seções críticas
� Usar spin-lock
� As seções críticas dos usuários usarão semáforos, sem spin-
lock
Prof Razer A N R Montaño 46Sistemas Operacionais
Problema Produtor-Consumidor
� Dois processos:
� Um produzindo informações
� Outro consumindo informações
� Entre eles existe um buffer
� Dados produzidos são armazenados temporariamente
� Origem dos dados que são consumidos
� Buffer é tipicamente circular
� Bloqueios
� Produtor tenta inserir no buffer cheio
� Consumidor tenta consumir do buffer vazio
 
 
Prof Razer A N R Montaño 47Sistemas Operacionais
Problema Produtor-Consumidor
...
n 1
2
Próxima Inserção
Próxima Remoçãox
y
Prof Razer A N R Montaño 48Sistemas Operacionais
Problema Produtor-Consumidor
struct tipo_dado buffer[N];
int pro_ins = 0;
int prox_rem = 0;
semaphore exclusao_mutua = 1;
semaphore espera_vaga = N;
semaphore espera_dado = 0;
void produtor(void) {
 P(espera_vaga);
 P(exclusao_mutua);
 buffer[prox_ins] = dado_produzido;
 prox_ins = (prox_inx + 1) % N;
 V(exclusao_mutua)
 V(espera_dado);
}
void consumidor(void) {
 P(espera_dado);
 P(exclusao_mutua);
 dado_a_consumir = buffer[prox_rem];
 prox_rem = (prox_rem + 1) % N;
 V(exclusao_mutua);
 V(espera_vaga);
}
 
 
Prof Razer A N R Montaño 49Sistemas Operacionais
Mensagens
� Até agora, programas concorrentes
� Dados compartilhados
� Mecanismo de sincronização
� Agora
� Troca de mensagens
� Sistemas distribuídos
� Troca de mensagens via rede de comunicação
� Usa chamada de sistemas: Send e Receive
Prof Razer A N R Montaño 50Sistemas Operacionais
Mensagens
� Send
� 2 parâmetros: Mensagem e Destinatário
� Endereçamento
� Direto: especifica o processo destinatário
� Indireto: S.O. implementa uma caixa postal, e as mensagens são 
enviadas para estas caixas postais. O S.O. disponibiliza chamadas 
de sistema para manipulação de caixas postais
� Receive
� 1 parâmetro: Endereço de onde deverá ser colocada a 
mensagem lida
� Em alguns sistemas, as mensagens são enfileiradas e Receive 
as desenfileira
� Opcionalmente, pode receber o id do processo do qual quer 
receber mensagens
� Com endereçamento Indireto, passa-se a caixa postal
 
 
Prof Razer A N R Montaño 51Sistemas Operacionais
Mensagens
� Variação: mensagens podem ter prioridades, portanto 
são lidas primeiro as que possuem maior prioridade
� Comportamentos para Receive quando não existe uma 
mensagem disponível:
� Processo fica bloqueado esperando uma mensagem
� Processo retorna imediatamente com indicativo de falha
� Processo fica bloqueado por algum tempo e se não houver 
mensagem, retorna falha (time-out)
� Alguns sistemas provém grupos de processos para 
recebimento da mensagem
� Envio para todo o grupo
� Apenas um processo qualquer do grupo
� Pelo menos um processo do grupo
Prof Razer A N R Montaño 52Sistemas Operacionais
Mensagens
� Se um processo executa o Send mas o destinatário não 
executa o Receive
� Alguns sistemas provém buffers
� O processo que executa Send retorna imediatamente
� A mensagem é guardada pelo S.O.
� A mensagem será entregue quando o destinatário executar o 
Receive
� Armazena-se só uma determinada quantidade de mensagens 
ou por um determinado tempo somente
� Alternativa aos buffers é o Rendezvouz
� O processo que executa Send é bloqueado até que o 
destinatário execute o Receive
� O processo que executa o Receive é bloqueado até que o 
remetente execute o Send
 
 
Prof Razer A N R Montaño 53Sistemas Operacionais
Mensagens
� Bufferização tende a ser mais eficiente, mas aumenta 
complexidade do S.O. e consome mais recursos
� Exemplo de uso de Mensagens:
� RPC: remote procedure call
� Chamada de um método remoto
� Executado através de mensagens
� RPC: Processo chamador
� Executa Send passando o nome do método e os parâmetros
� Logo após executa um Receive para obter o retorno
� RPC: Processo receptor
� Executa um Receive para receber uma requisição
� Logo após o processamento executa um Send para enviar o 
retorno
Prof Razer A N R Montaño 54Sistemas Operacionais
Visão geral e Comparação
� Duas soluções para comunicação entre processos
� Variáveis compartilhadas
� S.O. oferece mecanismos, como semáforos
� Gerência de memória permissiva
� Não há cópia de dados
� Troca de mensagens
� S.O. oferece mecanismos
� Natural em sistemas distribuídos
� Exige um subsistema de comunicação para máquinas diferentes
� Necessita mecanismo de alocação de remoção de memória
� Pesquisar os problemas clássicos:
� Filósofos jantadores
� Leitores e Escritores
� Pesquisar sobre PThreads
 
 
Prof Razer A N R Montaño 55Sistemas Operacionais
Deadlock
� Um dos principais problemas dos programas 
concorrentes
� Podem ocorrer envolvendo arquivos e periféricos
� Definição
� Um conjunto de n processos está em deadlock
quando cada um 
dos n processos está bloqueado à espera de um evento que 
somente pode ser causado por um dos n processos do conjunto
� Só pode ser resolvido com alguma atitude de fora deste 
conjunto de processos
Prof Razer A N R Montaño 56Sistemas Operacionais
Deadlocks
p
r
bloqueado
p
r
alocado
Legenda
p3 p1 p2
p4 p5
r1 r2 r3
 
 
Prof Razer A N R Montaño 57Sistemas Operacionais
Deadlocks
� Quatro condições para uma possível ocorrência de 
deadlock
� Recursos que precisam ser acessados de forma mutuamente 
exclusiva
� Processos poderem manter recursos alocados enquanto 
esperam por recursos adicionais
� Necessidade de os recursos serem liberados pelos próprios 
processos que os utiliza
� Possibilidade de formação de espera circular:
P1 espera R1 alocado por P2 que espera R2 ..... Rn alocado por Pn que 
espera por P1
Prof Razer A N R Montaño 58Sistemas Operacionais
Deadlocks
� Tratamentos
� Eliminar pelo menos uma das 4 condições para cada recurso
� Difícil para certos recursos
� Para cada pedido por recurso, analisar as implicações
� Deixar acontecer, detectar e eliminar (destruir os processos)