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
Fim |
Procedure p2: Início
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áforoSe (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á bloqueadoUP (v)Se (v=0) e há processos bloqueados Então WAKEUP // o processo bloqueado termina de executar sua operação DOWN (libera ele) Senão v = v+1; // se não houver processos bloqueados |
5.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) Fim
Procedure consumidor: Início DOWN (cheio) / menos 1 cheio Fim |
No caso acima, 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.
5.2. Algoritmo que representa leitor/escritor usando semáforo
| Init (base, 1)Procedure leitor:
Início |
Procedure escritor:Início DOWN (base) Acessa base UP (base) Fim |
5.3. Algoritmo que representa a alternância estrita usando semáforo
| Init (M1, 1)Procedure p1:
Início |
Init (M2, 0)Procedure p2:
Início |
5.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) fim |
Procedure Carros Esq:Início
DOWN (mutex) Fim |
5.5. Algoritmo que representa infinitos leitores e 1 escritor – Init (mutex, 1)
| Procedure Leitores:Início
DOWN (mutex) fim |
Procedure Escritor:Início
DOWN (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;
5.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 |
5.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)
6.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++ FimProcedure saiuO: Início CarO– Se (CarO=0) SIGNAL (Leste) Fim |
Procedure acessoL: Início Se (CarO>0) WAIT (Leste) CarL++ FimProcedure saiuL: Início CarL– Se (CarL=0) SIGNAL (Oeste) Fim |
END PONTE
6.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.
7.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 |
7.2. Algoritmo que representa o problema do Produtor-Consumidor usando Troca de Mensagens
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.
Inicialização:
para i=1 até i=N faça [ SEND (Produtor, msg) ] // envia N vazios
| 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 |