Sistemas de Computação I
Lista de Exercícios - 18/6/98

No início dos anos 70, foram definidas algumas linguagens de programação que ofereciam o conceito de monitor. Um monitor é análogo a um tipo abstrato de dados, encapsulando dados e operações de acesso. No entanto, as operações de acesso oferecem a garantia de exclusão mútua. Vários processos podem compartilhar acesso a um monitor (e a seus dados), mas no máximo um processo pode estar executando o código dentro do monitor a cada instante. Além da exclusão mútua, monitores oferecem, tipicamente, variáveis de condição e primitivas wait e notify.

Java, que define concorrência baseada em threads, oferece um conceito bastante similar ao de monitores. Métodos de um objeto definidos como synchronized garantem execução com exclusão mútua em relação a qualquer outro método também definido dessa forma. Como exemplo, a definição de classe

public class ExpandableArray {
  ... // dados 
  public synchronized int size () { ... }
  public synchronized Object at (int i) {... }
  public synchronized void append (Object o) { ... }
  public synchronized void removeLast () { ... }
}

garante acesso sequencial a qualquer objeto da classe ExpandableArray.

Em contraste com monitores tradicionais, que oferecem variáveis de condição, Java oferece a primitiva de sincronização wait, que faz um processo ficar bloqueado numa fila de espera associada a um objeto, notify, que acorda o primeiro thread nessa fila, e notifyAll, que acorda todos os threads na fila. Não há uma condição específica associada a cada uma dessas primitivas. Observe que, de forma geral, também não há como saber qual thread é o primeiro em uma fila de espera. Por isso, muitas vezes é necessário usar notifyAll, que acorda todos os threads, e fazer com que o bloqueio (wait) seja feito dentro de um loop que testa repetidamente a condição desejada. Como exemplo (bobo) de uso típico, considere a implementação de um buffer limitado:

public class BoundedBufferV implements BoundedBuffer {
  // dados
  ...
  public synchronized void put (Object x) {
    while (usedSlots == array.length) // espera ate' ter lugar
      wait();
    // coloca no array
    if (usedSlots++ == 0) // estava vazio
      notifyAll();
  }
  public synchronized Object take () {
    while (usedSlots == 0) // espera ate' ter algum item
      wait();
    // retira item x do buffer
    if (usedSlots-- == array.length) // estava cheio
      notifyAll();
    return x;
  }
}

Usando os mecanismos descritos (não se preocupe com sintaxe, apenas suponha que existem métodos sincronizados e primitivas wait, notify e notifyAll):

1. Defina uma classe semáforo, com operações P() e V(), que implemente semáforos contadores (semáforos comuns).
2. Resolva novamente os problemas dos canibais, da montanha russa e da busca/inserção/eliminação, utilizando monitores java-like Evite espera ocupada!

   Observe que, com o uso de semáforos, é possível sinalizar condições específicas (por exemplo, pote vazio, no caso dos canibais), e que isso não é mais possível com o uso de notify e notifyAll. Discuta as implicações dessa diferença nas soluções apresentadas.

   Para relembrar os problemas (sendo que agora não é mais para usar semáforos!)...:

   1. Problema do Jantar Comunal. Suponha que um grupo de N canibais come jantares a partir de uma grande travessa que comporta M porções. Quando alguém quer comer, ele(ela) se serve da travessa, a menos que ela esteja vazia. Se a travessa está vazia, o canibal acorda o cozinheiro e espera até que o cozinheiro coloque mais M porções na travessa. Desenvolva código para as ações dos processos canibais e do processo cozinheiro. Use semáforos para sincronização. A solução deve evitar deadlock e deve acordar o cozinheiro apenas quando a travessa estiver vazia. (Suponha um longo jantar, onde cada canibal continuamente se serve e come, sem se preocupar com as demais ações na vida do canibal...)
   2. Problema da Montanha Russa. Suponha que há n processos passageiros e um processo vagão. Os passageiros repetidamente esperam para andar no vagão, que comporta v passageiros, onde v<n. O vagão só pode percorrer a montanha russa quando está cheio.
      1. Usando semáforos, desenvolva código para as ações dos processos.
      2. Generalize sua solução para m processos vagão, onde m>1. Um vagão não pode ultrapassar outro, ou seja, os vagões têm que terminar o percurso na mesma ordem em que o iniciaram. Novamente, um vagão só pode iniciar o percurso quando estiver completo.
   3. Resolva busca/inserção/eliminação. Três tipos de processos compartilham acesso a uma lista encadeada: processos de busca, de inserção e de eliminação. Processos de busca meramente examinam a lista.; assim podem executar concorrentemente entre si. Processos de inserção incluem itens no final da lista; inserções devem ser mutuamente exclusivas para impedir duas inserções de ocorrerem simultaneamente. No entanto, uma inserção pode ocorrer em paralelo com qualquer número de buscas. Finalmente, elimincações podem ocorrer em qualquer ponto da lista. No máximo um processo de eliminação pode ter acesso à lista em qualquer instante, e a eliminação deve ser mutuamente exclusiva com buscas e inserções.

      Este problema é uma extensão dos leitores e escritores. Descreva as ações dos processos de busca, inserção e eliminação usando semáforos. Analise sua solução em relação à possibilidade de starvation para cada um dos tipos de processos.

 
• About this document ...