Sistemas Operacionais

Aula 4: Comunicação/sincronização de processos

Referências

Para que Compartilhar ?

Compartilhamento de recursos:

Multiprocessadores:

Modularidade:

Sistemas distribuídos:

Cooperação: Race Conditions

Processos podem se comunicar através do comparti-lhamento de variáveis.

Quais problemas podem ocorrer quando dois ou mais processos compartilham variáveis?

P1 P2
A = 1 B = 2
Qual será o resultado final? Importa a ordem na qual os processos executam?
P1 P2
A = B + 1 B = 2 * B
Qual é o resultado final?
P1 P2
A = 1 A = 2
Qual é o resultado final? E em um computador com múltiplos processadores ?

Operações Atômicas

A fim de evitar race conditions o conceito de opera-ções atômicas é introduzido.

Operações Atômicas são operações que não podem ser interrompidas.

Operações Atômicas Operações Não-Atômicas
tocar a campainha encher um copo de água
desligar a luz caminhar até a porta

Operações Atômicas

Operações atômicas são relevantes em outras áreas além de Sistemas Operacionais:

Em geral, o hardware provê algumas operações atômicas:

Sincronização

Sincronização é uma maneira para garantir o funcionamento correto de processos cooperantes:

O Problema de Espaço na Geladeira

O Problema de Espaço na Geladeira
Hora Pessoa A Pessoa B
6:00 Olha a geladeira: sem leite -
6:05 Sai para a padaria -
6:10 Chega na padaria Olha a geladeira: sem leite
6:15 Sai da padaria Sai para a padaria
6:20 Chega em casa: guarda o leite Chega na padaria
6:25 - Sai da padaria
6:30 - Chega em casa: Ops!
O que houve de errado ?

Sincronização

O problema anterior foi causado porque uma pessoa não sabia o que a outra estava fazendo.

Uma solução para o problema envolve dois novos conceitos:

Exclusão Mútua

Existem várias maneiras de se obter exclusão mútua.

A maioria envolve trancamento (locking):

Três regras devem ser satisfeitas para o trancamento funcionar:

Regra Exemplo da geladeira
1. Trancar antes de utilizar Deixar aviso
2. Destrancar quando terminar Retirar o aviso
3. Esperar se estiver trancado Não sai para comprar se houver aviso

Computadores & Leite

Primeira tentativa de resolver o Problema de Espaço na Geladeira:

Processos A e B

   if (SemLeite) {
       if (SemAviso) {
           Deixa Aviso;
           Compra Leite;
           Remove Aviso;
       }
   }
Esta "solução" funciona?

Computadores & Leite

NÃO! Por causa de troca de contexto:

Processos A e B

   if (SemLeite) {
       if (SemAviso) {
           Deixa Aviso;
           Compra Leite;
           Remove Aviso;
       }
   }
A Solução piora o problema! Agora falha só de vez em quando, ou seja a depuração fica muito mais difícil:

Computadores & Leite

Segunda tentativa de resolver o Problema de Espaço na Geladeira: mudar o significado do aviso.

Processo A Processo B

  if (SemAviso) {
      if (SemLeite) {
          Compra Leite;
      }
      Deixa Aviso;
  }


  if (Aviso) {
      if (SemLeite) {
          Compra Leite;
      }
      Remove Aviso;
  }

Funciona? Porque?

Computadores & Leite

Que tal o seguinte argumento ?

Certo ?

Computadores & Leite

Suponha que B saia de férias:

(Tá bom, trapaça. Eu nunca disse nada sobre inanição antes. Mas não é importante ?)

Computadores & Leite

Terceira tentativa: Usar dois avisos diferentes.

Processo A Processo B

  Deixa AvisoA;  
  while (AvisoB);  
  if (SemLeite) {  
    Compra Leite;  
  }  
  Remove AvisoA;  


  Deixa AvisoB;
  if (SemAvisoA) {
    if (SemLeite) {
      Compra Leite;  
    }
  }
  Remove AvisoB;
Funciona ?

Computadores & Leite

SIM!

Computadores & Leite

Esta solução funciona, mas não é boa (cara chato!):

Pontos importantes:

Produtor & Consumidor

Produtor & Consumidor

Solução ``ideal'', usa todas as posições do buffer:

Produtor() {
  while (true) {
    while (counter == n);
    buffer[in] = item_produzido;
    in=in+1 mod n;
    counter++;
  };
};

Consumidor() {
  while (true) {
    while (counter == 0);
    item_consumido = buffer[out];
    out=out+1 mod n;
    counter--;
  };
}

Produtor & Consumidor

Produtor() {
  while (true) {
    while (counter == n);
    buffer[in] = item_produzido;
    in=in+1 mod n;
    R1 = [counter];
    inc(R1);
    [counter] = R1;
  };
};

Consumidor() {
  while (true) {
    while (counter == 0);
    item_consumido = buffer[out];
    out=out+1 mod n;
    R1 = [counter];
    dec(R1);
    [counter] = R1;
  };
}

Produtor & Consumidor

Solução não ideal: usa n-1 posições do buffer:

Produtor() {
  while (true) {
    while (in+1 mod n == out);
    buffer[in] = item_produzido;
    in=in+1 mod n;
  };
};

Consumidor() {
  while (true) {
    while (in == out);
    item_consumido = buffer[out];
    out=out+1 mod n;
  };
}
Como escrever uma solução correta que usa n posições do buffer ?

Produtor & Consumidor

Simples, declare um buffer com n+1 posições:

Sincronização: Requisitos

Requisitos para primitivas de exclusão mútua:

Propriedades desejáveis para um mecanismo de exclusão mútua:

Sincronização: Requisitos

Propriedades dos processos utilizando os mecanismos necessárias para manter coerência:

while (!fim) {
  secao_nao_critica;
  lock();
  secao_critica;
  unlock();
}

Resumo