• Cooperação
• Variáveis compartilhadas
• Operações atômicas
• Exclusão mútua
• Requisitos para exclusão mútua

• Capítulo 4: 4.4
• Capítulo 6: 6.1

• Um computador (ou impressora), muitos usuários

• Resolve o problema mais rápido se dividir o problema entre os processadores.

• Divida o problema em problemas menores, e.g. escalonador, comunicação entre processos.

• Internet

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

• Considere dois processos que compartilham as variáveis A e B:

Qual será o resultado final? Importa a ordem na qual os processos executam?

• Agora considere:

Qual é o resultado final?

• E no seguinte caso?

Operações Atômicas

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

• Não é possível ver as "partes" de uma operação atômica, mas apenas seu efeito final. Ou seja, não é possível ver a operação "em progresso".

• Elas são a base para transações atômicas, que por sua vez formam a base para uma área denominada Processamento de Transações;
• Esta área trata de problemas de coordenação de acessos múltiplos e concorrentes a bancos de dados.
  • Bancos eletrônicos são uma das aplicações importantes da área.

• Se o hardware não fornecer instruções atômicas, como é possível implementá-las em um uniprocessador? E em multiprocessadores?

• Operações atômicas são usadas.

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 ?

• Problema: falta de comunicação! E vocês achavam que isto era papo de psicólogo...

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

• Exclusão Mútua: apenas um processo pode fazer alguma coisa em determinado momento.
  • Exemplo: apenas uma pessoa pode sair para comprar leite em qualquer momento.
• Seção Crítica: uma seção de código na qual apenas um processo pode executar de cada vez.
  • O objetivo é tornar atômico o conjunto de operações.
  • Exemplo: comprar leite.

A maioria envolve trancamento (locking):

• evitar que alguém faça alguma coisa em determinado momento.

  Exemplo, deixar um aviso na porta da geladeira.

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

Processos A e B

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

Computadores & Leite

Processos A e B

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

• Heisenbug!
• Não importa se é raro, na prática vai acontecer nos primeiros 5 minutos. A não ser se você estiver querendo que aconteça, claro.

• A vai comprar se não houver aviso; B vai comprar se houver aviso.

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

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

Computadores & Leite

• Somente A deixa um aviso, e somente se já não existe um aviso;
• Somente B remove um aviso, e somente se houver um aviso;
• Portanto, ou existe um aviso, ou nenhum;
• Se houver um aviso, B compra leite;
• Se não houver aviso, A compra leite;
• Portanto, apenas uma pessoa (processo) vai comprar leite;

Computadores & Leite

• A vai comprar leite uma vez e não poderá comprar mais até que B retorne.
• Portanto essa solução não é boa; em particular ela pode levar a "inanição" (starvation).

Computadores & Leite

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

• Se SemAvisoA B pode comprar porque A ainda não começou.
• Se AvisoA, A está comprando ou esperando até que B desista. B pode desistir.
• Se SemAvisoB A pode comprar.
• Se AvisoB não se sabe:
  • Se B comprar, remove AvisoB, fim.
  • Se B não comprar, remove AvisoB, A pode comprar.

• Muito complicado. Difícil de entender e se convencer de que está correto.
• Código de A é diferente do de B. E se houver mais de dois processos ?
• Enquanto A está esperando, está consumindo CPU (busy waiting).

• Comportamento muito sutil. Difícil de programar e entender.
• Como provar que está correto ?
• Quais os critérios de uma boa solução ?

• Produtor gera items continuamente e os coloca no buffer.
• Consumidor usa items, lendo-os do buffer.
• Buffer é necessário por causa da velocidade relativa de produtor e consumidor.
• Sincronização é necessária no acesso ao buffer:
  • Produtor não pode colocar mais itens em buffer cheio.
  • Consumidor não pode ler itens de buffer vazio.

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--;
  };
}

• Buffer Circular.

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() {
  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;
  };
}

Produtor & Consumidor

• Uma posição de memória não vale o esforço de reescrever o programa!

• Deve permitir apenas um processo dentro de uma seção crítica a cada instante;
• Se várias requisições são feitas ao mesmo tempo, deve permitir que um processo prossiga;
• Processos podem "entrar de férias" somente fora das seções críticas;

• Justiça (fairness): se vários processos estão esperando, dar acesso a todos eventualmente
• Eficiência: não utilizar quantidades substanciais de recursos quando estivar esperando. Em particular, evitar "espera ocupada".
• Simples: deve ser fácil de utilizar.

• Trancar sempre antes de utilizar dado compartilhado
• Destrancar sempre que terminar o uso de dado compartilhado
• Não trancar de novo se já tiver trancado o recurso
• Não destrancar se não foi você que trancou (em geral; pode haver exceções para essa regra)
• Não ficar muito tempo dentro de seções críticas.

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

• Cooperação usando variáveis compartilhadas.
• Necessita operações atômicas por causa de ``race conditions'';
• Implementação através de exclusão mútua:
  • Comportamento difícil de prever;
  • Tem que ser usado com critério;
  • Tem que ser correto, justo, eficiente;