3. COMUNICAÇÃO ENTRE PROCESSOS
Condições de disputa: ocorre quando dois processos acessam “simultaneamente” os dados compartilhados entre eles. Ex: spooler de impressora (programa que permite que vários usuários utilizem a mesma impressora, imprimindo na ordem solicitada), quando um pedido de impressão desaparece por ter ocorrido uma interrupção de um processo, gerando a perde de informações no spooler. Então o processo que o requisitou não será servido.
Seções Críticas: S.O. devem ser construídos de maneira a evitar a disputa entre processos. Podemos evitar essa disputa, proibindo que mais de um processo leia e escreva simultaneamente em uma área de dados compartilhada, isto é o que se chama de exclusão mútua. Os trechos de programa em que os processos estão executando computações sobre dados compartilhados com outros processos são chamados de seções críticas. Para evitar disputas: não pode haver dois processos simultaneamente em suas seções críticas, nenhum processo parado fora de sua região crítica pode bloquear outros processos, nenhum processo deve esperar um tempo longo para entrar em sua região crítica.
Exclusão Mútua com Espera Ocupada
Soluções que visam garantir a exclusão mútua:
1. Desabilitando interrupções: A forma mais simples de garantir a exclusão mútua, é fazer com que cada processo, ao entrar na região crítica, desabilite interrupções, e as reabilite antes de sair, impedindo que a UCP seja chaveada para outro processo. Problemas: os usuários têm direito de desabilitar interrupções e se esquecer de reabilitar o S.O. não pode mais executar e usuário mal intencionados podem desabilitar interrupções a fim de que seu programa seja o único a ser executado no processador.
2. Variáveis de comporta: Utilizamos uma variável auxiliar que quando em 0 indica que a seção crítica está livre e quando em 1 indica que está ocupada. Problemas: a disputa apenas se transferiu da região crítica para a variável de comporta. Vantagens: facilidade na programação (não exige linguagem de programação concorrente)
3. Alternância Estrita: Solução que obriga que a região crítica seja dada a um dos processos por vez, em uma alternância estrita. O teste contínuo de uma variável na espera de um certo valor é chamado de espera ocupada, e representa um grande desperdício de UCP. Problemas: requer precisão na alternância entre dois processos e o número de acessos de cada processo deve ser igual ao do outro.
Algoritmo que representa uma alternância estrita: |
Procedure p1:
Início
Seção normal
Enquanto (vez!=1) faça nada
Seção critica
Vez <- 2
Seção normal
Fim |
Procedure p2:
Início
Seção normal
Enquanto (vez!=2) faça nada
Seção critica
Vez <- 1
Seção normal
Fim |
4. SLEEP e WAKEUP: Temos os chamados deadlocks, que acontece quando nenhum processo pode prosseguir, pois está aguardando alguma condição que somente pode ser atingida pela execução do outro – há um bloqueio nos dois processos – (ex: no caso da prioridade, um processo não pode executar até que o com alta prioridade termine). As rotinas Sleep (muda o estado do processo em execução para bloqueado) e Wakeup (pega um processo bloqueado e transfere para o estado pronto), realizam a espera através do bloqueamento do processo, ao invés de desperdício do tempo de UCP. Problemas: ocorre um deadlock por causa da variável compartilhada (cont, que representa quantos itens estão dentro do buffer), pois o buffer apresenta uma capacidade finita de reter dados, então quando o produtor deseja colocar dados em um buffer cheio e quando o consumidor tenta tirar dados de um buffer vazio, o processo não pode acessar o buffer. Por ex: se um processo for interrompido, o contador fica com o valor anterior. Vamos exemplificar o algoritmo através do exemplo produtor (coloca dados no buffer) e consumidor (retira dados de um buffer) e onde N é o tamanho do buffer.
Algoritmo que representa uma tentativa para resolver o problema produtor-consumidor: |
Procedure produtor:
Início
Produz item (I)
Se (cont=N) então SLEEP
insere no buffer (I)
cont++
Se (cont=1)
então WAKEUP (consumidor)
Fim |
Procedure consumidor:
Início
Se (cont=0) então SLEEP
Remove do buffer (I)
cont––
Consome item (I)
Se (cont=N-1)
então WAKEUP (produtor)
Fim |
5. SEMÁFOROS: resolve o problema do sleep e wakeup, não funciona para máquinas distintas. O processamento das ações de DOWN e UP (devem ser implementados pelo S.O., por exemplo, desabilitando interrupções) é realizado sem interrupções. Há os semáforos binários (ex: mutex, inicializado com 1 e quando mutex=1 -> livre e quando mutex=0 -> ocupado). DOWN e UP são operações atômicas, ou seja, garantem que quando uma operação no semáforo está sendo executada, nenhum processo pode acessar o semáforo até que a operação seja finalizada ou bloqueada. Problema do semáforo: temos que ter muito cuidado com a programação, pois se houver uma inversão de DOWN, pode ocorrer deadlocks.
DOWN (v) // v é o nome do semáforo
Se (v>0) // se o valor do semáforo for menor que zero, decrementa
Então v = v-1
Senão SLEEP; // senão o processo será bloqueado
UP (v)
Se (v=0) e há processos bloqueados
Então WAKEUP
// o processo bloqueado termina de executar sua operação DOWN (libera ele)
// volta para o DOWN onde parou (finalizando-o) e indo para a linha seguinte do procedimento
Senão v = v+1; // se não houver processos bloqueados
1. Algoritmo que representa o problema produtor-consumidor: (buffer é finito tam = N)
Init (vazio, N) // N é o tamanho do buffer
Init (cheio, 0) // não tem nada no buffer
Init (mutex, 1) // primeiro o produtor |
|
Procedure produtor:
Início
Produz item (I)
DOWN (vazio) / menos 1 vazio
DOWN (mutex) / testa exc mútua
insere no buffer (I)
UP (mutex) / sai da exc mútua
UP (cheio) / um cheio a mais
Fim
|
Procedure consumidor:
Início
DOWN (cheio) / menos 1 cheio
DOWN (mutex) / testa exc mútua
retira do buffer (I)
UP (mutex) / sai da exc mútua
UP (vazio) / um vazio a mais
Consome item (I)
Fim |
No caso: o mutex é utilizado apenas para garantir a exclusão mútua, para executar a seção crítica. O consumidor bloqueia quando o número de cheios=0, e o produtor quando o número de vazios=0. |
2. Algoritmo que representa leitor/escritor usando semáforo |
Init (base, 1)
Procedure leitor:
Início
DOWN (base)
Acessa base
UP (base)
Fim |
Procedure escritor:
Início
DOWN (base)
Acessa base
UP (base)
Fim |
3. Algoritmo que representa a alternância estrita usando semáforo |
Init (M1, 1)
Procedure p1:
Início
DOWN (m1)
Seção crítica
UP (m2)
Fim |
Init (M2, 0)
Procedure p2:
Início
DOWN (m2)
Seção crítica
UP (m1)
Fim |
4. Algoritmo que representa o problema dos carros
Temos uma ponte e dois lados Direito e Esquerdo com vários carros, mas apenas 1 pode passar por vez na ponte. (temos um número infinito de carros por isso temos que ter os contadores de carros da direita e esquerda) init (mutex,1) |
Procedure Carros Dir:
Início
DOWN (mutex)
Car D ++
Se car D = 1
Então DOWN (ponte)
UP (mutex)
Acessa ponte
DOWN (mutex)
Car D –
Se car D = 0
Então UP (ponte)
UP (mutex)
fim
|
Procedure Carros Esq:
Início
DOWN (mutex)
Car E ++
Se car E = 1
Então DOWN (ponte)
UP (mutex)
Acessa ponte
DOWN (mutex)
Car E –
Se car E = 0
Então UP (ponte)
UP (mutex)
Fim |
5. Algoritmo que representa infinitos leitores e 1 escritor – Init (mutex, 1) |
Procedure Leitores:
Início
DOWN (mutex)
cont ++
Se cont = 1
Então DOWN (base)
UP (mutex)
Acessa base
DOWN (mutex)
cont –
Se cont = 0
Então UP (base)
fim |
Procedure Escritor:
Início
DOWN (base)
Acessa base
UP (base)
Fim |
DOWN (v) // v é o nome do semáforo
Se (v>0) // se o valor do semáforo for menor que zero, decrementa
Então v = v-1
Senão SLEEP; // senão o processo será bloqueado
UP (v)
Se (v=0) e há processos bloqueados
Então WAKEUP
// o processo bloqueado termina de executar sua operação DOWN (libera ele)
// volta para o DOWN onde parou (finalizando-o) e indo para a linha seguinte do procedimento
Senão v = v+1;
6. Fila de impressão utilizando semáforo
temos 3 semáforos:
Init (vazio, N) // N é o tamanho do buffer
Init (cheio, 0) // não tem nada no buffer
Init (mutex, 1) |
Procedure Solicita Impressão:
Início
Gera requisição (doc)
DOWN (vazio) / menos 1 vazio
DOWN (mutex) / testa exc mútua
insere documento (doc)
UP (mutex) / sai da exc mútua
UP (cheio) / um cheio a mais
Fim |
Procedure Envia Impressão:
Início
DOWN (cheio) / menos 1 cheio
DOWN (mutex) / testa exc mútua
remove documemento (doc)
UP (mutex) / sai da exc mútua
UP (vazio) / um vazio a mais
Imprime documento (doc)
Fim |
7. Fila de impressão utilizando semáforo (sem limite, fila infinita)
temos 2 semáforos:
Init (cheio, 0) // não tem nada no buffer
Init (mutex, 1) |
Procedure Solicita Impressão:
Início
Gera requisição (doc)
DOWN (mutex) / testa exc mútua
insere documento (doc)
UP (mutex) / sai da exc mútua
UP (cheio) / um cheio a mais
Fim |
Procedure Envia Impressão:
Início
DOWN (cheio) / menos 1 cheio
DOWN (mutex) / testa exc mútua
remove documemento (doc)
UP (mutex) / sai da exc mútua
Imprime documento (doc)
Fim |
6. MONITORES: criado para evitar as dificuldades da programação de semáforos que deve ser muito cuidadosa. Quando uma rotina de monitor não pode continuar executa um WAIT (bloqueio) e SIGNAL para continuar (libera o processo bloqueado). O monitor controla para que cada função dentro do monitor seja executada sem interrupção e internamente utiliza semáforo. Somente um processo pode executar instruções dentro do Monitor. Problema: são inaplicáveis para sistemas distribuídos (onde cada processador conta com sua própria memória)
1. Algoritmo que representa o problema Carros Oeste e Carros Leste usando Monitor:
Init (ContO, 0) Init (ContL, 0) |
Procedure Oeste:
Início
Ponte.acessoO
acessa_ponte
Ponte.saiuO
Fim |
Procedure Leste:
Início
Ponte.acessoL
acessa_ponte
Ponte.saiuL
Fim
|
Monitor PONTE
Procedure acessoO:
Início
Se (CarL>0) WAIT (Oeste)
CarO++
Fim
Procedure saiuO:
Início
CarO–
Se (CarO=0) SIGNAL (Leste)
Fim
|
Procedure acessoL:
Início
Se (CarO>0) WAIT (Leste)
CarL++
Fim
Procedure saiuL:
Início
CarL–
Se (CarL=0) SIGNAL (Oeste)
Fim |
END PONTE |
2. Algoritmo que representa o problema Produtor-Consumidor usando Monitor |
Procedure produtor:
Início
Produz item (I)
PRODCONS.insere (I)
Fim |
Procedure consumidor:
Início
PRODCONS.retira(I)
Consome Item (I)
Fim
|
Monitor PRODCONS
Procedure produtor:
Início
Se (cont=N) WAIT (cheio)
insere no buffer (I)
cont++
Se (cont=1)
então SIGNAL (vazio)
Fim |
Procedure consumidor:
Início
Se (cont=0) então WAIT (vazio)
Remove do buffer (I)
Cont –
Se (cont=N-1)
então SIGNAL (cheio)
Fim |
END PRODCONS
OBS: é semelhante ao Sleep / Wake up, mudando que, o produz item e consome item ficam fora do monitor e o monitor tem as operações Signal e Wait ao invés de Sleep e Wake Up. O Monitor garante que uma procedure não será liberada para ser executada antes de finalizar a procedure corrente. (a não ser que um proced. Se torne bloqueado, daí sim os outros poderão ser executados).
|
7. TROCA DE MENSAGENS: Possibilita o trabalho com sistemas distribuídos e também a sistemas de memória compartilhada. Existem duas primitivas:
SEND (destino,&mensagem)
RECEIVE (origem,&mensagem)
Se nenhuma mensagem estiver disponível no momento de executar RECEIVE, o receptor pode bloquear até que uma chegue.
SEND (destino,&mensagem)
RECEIVE (origem,&mensagem)
Se nenhuma mensagem estiver disponível no momento de executar RECEIVE, o receptor pode bloquear até que uma chegue.
1. Algoritmo que representa alternância estrita usando Troca de Mensagens
Inicialização: SEND (P1,msg) |
Procedure P1:
Início
Seção Normal
RECEIVE(P2,msg)
Seção Crítica
SEND(P2,msg)
Seção Normal
Fim |
Procedure P2:
Início
Seção Normal
RECEIVE(P1,msg)
Seção Crítica
SEND(P1,msg)
Seção Normal
Fim |
2. Algoritmo que representa o problema do Produtor-Consumidor usando Troca de Mensagens
Inicialização: para i=1 até i=N faça [ SEND (Produtor, msg) ] // envia N vazios
No Início, são enviados N vazios para permitir ao produtor encher todo o buffer antes de bloquear. Caso o buffer esteja cheio, o produtor bloqueia no RECEIVE e aguarda a chegada de uma nova mensagem vazia |
Procedure Produtor:
Início
Produz.item(I)
RECEIVE(Consumidor, msg)
// aguarda mensagem vazia
Constrói_msg (I, msg)
SEND (Consumidor, msg) // envia item ao consumidor
Fim |
Procedure Consumidor:
Início
RECEIVE(Produtor, msg) // pega mensagem
Extrai_msg (msg, I) // pega Item da mensagem
Consome.item(I)
SEND (Produtor, msg) // envia resposta vazia
Fim |
O material acima está dividido em oito partes, foi escrito por Alex De Francischi Coletta em 2003 e adaptado para a WEB.
Bibliografia: FREITAS,
Ricador Luis de “Apostila de Sistemas Operacionais” utilizado no curso de graduação em Engenharia de Computação da Pontifícia Universidade Católica de Campinas na disciplina de Sistemas Operacionais I.
