Sincronização de Threads

Introdução

• Por enquanto, os threads que vimos são independentes
  • Os threads não requerem acesso a recursos externos ou a chamdas de métodos de outros objetos
  • Os threads não precisam de preocupar com o que está ocorrendo com os outros threads
  •  
• Em outras situação, threads devem compartilhar dados e são obrigados a se preocupar com o que os outros estão fazendo
• Um exemplo disso é a aplicação chamada "Produtor/Consumidor" em que um Produtor produz um fluxo de dados consumidos pelo consumidor
  • Por exemplo, um thread (o produtor) poderia estar gravando dados num arquivo enquanto outro thread (o consumidor) lê dados do mesmo arquivo
  • Outro exemplo: enquanto você digita no teclado, o produtor coloca eventos de mouse numa fila de eventos e o consumidor lê os eventos da mesma fila
  • Em ambos os casos, temos threads que compartilham um recurso comum
  • Com tal compartilhamento, os threads devem se sincronizar para acessar o recurso

O exemplo Produtor/Consumidor

• Um produtor gera um número entre 0 e 9 (a variável i) e o armazena num objeto chamado CubbyHole (um lugarzinho para guardar coisas; um cubículo)
• Para deixar o exemplo mais interessante, o produtor dorme durante um intervalo aleatório entre 0 1 100 ms antes de gerar mais números
  • No programa abaixo, "number" é a identificação do produtor, "i" é o número gerado

public class Producer extends Thread {
    private CubbyHole cubbyhole;
    private int number;

    public Producer(CubbyHole c, int number) {
        cubbyhole = c;
        this.number = number;
    }

    public void run() {
        for (int i = 0; i < 10; i++) {
            cubbyhole.put(number, i);
            try {
                sleep((int)(Math.random() * 100));
            } catch (InterruptedException e) { }
        }
    }
}

• O consumidor consome os inteiros do mesmo CubbyHole asssim que se tornam disponíveis

public class Consumer extends Thread {
    private CubbyHole cubbyhole;
    private int number;

    public Consumer(CubbyHole c, int number) {
        cubbyhole = c;
        this.number = number;
    }

    public void run() {
        int value = 0;
        for (int i = 0; i < 10; i++) {
            value = cubbyhole.get(number);
        }
    }
}

• O produtor e o consumidor compartilham dados através de um objeto comum da classe CubbyHole
  • Embora o consumidor deva receber cada número exatamente uma vez, nem o produtor nem o consumidor tratam de fazer isso acontecer
  • A sincronização entre os dois threads ocorre num nível mais baixo, dentro do CubbyHole
    • Veremos detalhes adiante
• Vamos supor que não houvesse sincronização entre os threads. Que problemas poderiam ocorrer?
• Um problema ocorre quando o produtor é mais rápido do que o consumidor e gera dois números antes de o consumidor ter chance de consumir o primeiro
  • Nessa situação, o consumidor perde um número:

• Um outro problema ocorre quando o consumidor é mais rápido do que o produtor
  • Um número pode ser consumido duas (ou mais)vezes:

• Em ambos os casos, o resultado não é o que se deseja: o consumidor deve receber cada número exatamente uma vez
• Um problema desse tipo se chama uma condição de corrida
  • Uma condição de corrida é uma situação em que 2 ou mais threads ou processos estão compartilhando dados (lendo ou gravando) e o resultado final depende do "timing" do escalonamento dos threads
  • Condições de corrida  levam a resultados imprevisíveis e a bugs sutis, difíceis de achar
  • Um bug é fácil de remover se for reproduzível; quando não o é, o mundo se torna cruel ...
• Uma solução é fazer a sincronização dentro do CubbyHole
  • O CubbyHole só deve permitir o armazenamento de outro número quando o anterior tiver sido consumido
• As atividades do produtor e do consumidor devem ser sincronizados de duas formas diferentes
  • Primeiro, os threads não devem acessar o CubbyHole simultaneamente
    • Um thread pode impedir isso travando o objeto (locking)
    • Quando um objeto está travado, um outro thread que chamar um método sincronizado no mesmo objeto vai bloquear até o obvjeto ser destravado
  • Segundo, os threads devem coordenar seu trabalho
    • O produtor deve ter uma forma de dizer ao consumidor que um novo número está disponível para consumo
    • O consumidor deve ter uma forma de dizer ao produtor que o número foi consumido, liberando a produção de outro número
    • A classe Object provê métodos (wait, notify, notifyAll) para permitir que threads esperem por uma condição e notificar outros threads quando uma condição ocorre

A primeira sincronização: travando um objeto (locking)

• Dentro de um programa, segmentos de código que acessam os mesmos dados usando threads diferentes e concorrentes são chamados de regiões críticas ou seções críticas
• Uma seção crítica pode ser um bloco de statements ou um método inteiro e deve ser identificada com a palavra synchronized
• A JVM fornece um lock para cada objeto e o objeto é travado (o lock é "obtido") ao entrar numa seção crítica
• No exemplo acima, os métodos put e get de CubbyHole.java são as regiões críticas
  • Os dados compartilhados são os atributos de CubbyHole
  • Os threads devem acessar tais dados se forma sequencial
• Eis o código com a indicação da regiões críticas:

public class CubbyHole {
    private int contents;
    private boolean available = false;

    public synchronized int get(int who) {
        ...
    }

    public synchronized void put(int who, int value) {
        ...
    }
}

• Ao entrar num método synchronized, o thread que chamou o método trava o objeto cujo método foi chamado
  • Observe que um thread trava um objeto
  • Se outro thread chamar um método synchronized do mesmo objeto, ele vai esperar até o primeiro liberar o lock
• A aquisição e liberação de um lock é feita de forma atómica pela JVM
  • Time-slicing ou outras formas de escalonar threads não pode causar furos ao esquema
• A palavra synchronized  pode se aplicar a um bloco:

   // ...
   synchronized {
       // qualquer conjunto de statements
   }

• Também é possível adquirir o lock de outro objeto, não só de this:

   // ...
   synchronized(obj) {
       // qualquer conjunto de statements
   }

• syncronized sozinho é equivalente a synchronized(this)

Readquirindo um lock

• O mesmo thread pode obter um lock que ele já possui sem ter que esperar
  • Senão teríamos "deadlock", uma condição de espera permanente
• Veja o exemplo:

public class Reentrant {
    public synchronized void a() {
        b();
        System.out.println("here I am, in a()");
    }
    public synchronized void b() {
        System.out.println("here I am, in b()");
    }
}

• Dizemos que locks são "reentrantes"
• A saída é:

here I am, in b()
here I am, in a()

A segunda sincronização: usando os métodos notifyAll e wait

• Vamos investigar como o código de CubbyHole permite que o produtor e o consumidor sincronizem suas atividades
• O CubbyHole guarda o valor num atributo privado chamado "contents"
• Há um outro atributo privado chamado "available", um booleano que indica se há um valor presente no objeto
  • Isto é, um valor produzido mas ainda não consumido
• Examine essa primeira tentativa de implementação de CubbyHole:

public synchronized int get() {    //won't work!
    if (available == true) {
        available = false;
        return contents;
    }
}
public synchronized void put(int value) {    //won't work!
    if (available == false) {
        available = true;
        contents = value;
    }
}

• Isso não funciona (na realidade, nem compila!)
  • Exemplo de furo: se não houver nada no CubbyHole (available == false), o método get() faz nada
    • O correto seria esperar até ter algo
  • Outro exemplo de furo: se houver algo no CubbyHole (available == true), o método put() faz nada e perde o valor
    • O correto seria esperar até poder guardar o valor
• Temos que dar um jeito de haver espera e de um thread sinalizar o outro quando pode continuar
• Isso é feito com os métodos wait e notifyAll:

public synchronized int get() {
    while (available == false) {
        try {
            //wait for Producer to put value
            wait();
        } catch (InterruptedException e) { }
    }
    available = false;
    //notify Producer that value has been retrieved
    notifyAll();
    return contents;
}

public synchronized void put(int value) {
    while (available == true) {
        try {
            //wait for Consumer to get value
            wait();
        } catch (InterruptedException e) { }
    }
    contents = value;
    available = true;
    //notify Consumer that value has been set
    notifyAll();
}

• O método wait libera o lock e espera notificação para continuar
  • Isso é necessário para que o outro thread possa adquirir o lock, fazer seu trabalho e acordar o outro (com notifyAll)
  • Ao continuar, o lock é obtido novamente
• O método notifyAll "acorda" todos os threads que estão em wait (nesse objeto)
  • Os threads que acordam competem pelo lock
  • Um thread pega o lock, os outros voltam a dormir
• O método notify também existe e acorda apenas um thread (escolhido arbitrariamente)
• Observações importantes:
  • Só se pode usar wait, notify() e notifyAll() quando se está de posse do lock do objeto (dentro de um bloco synchronized)
  • wait() espera uma condição para o objeto corrente e esta condição ocorre com notify() no mesmo objeto
• "Ter posse do lock" também se chama "possuir o monitor do objeto"
  • Detalhes e razões pelo nome Monitor serão dadas na disciplina Sistemas Operacionais
• Há três versões do método wait da classe Object:
  • wait()
    • Espera indefinidamente por uma notificação
  • wait(long timeout)
    • Espera por uma notificação mas, depois de timeout milisegundos, volta mesmo sem notificação
  • wait(long timeout, int nanos)
    • Como antes, mas com mais resolução de tempo
• Esses métodos podem ser usados em vez de sleep, quando se quer ter um controle maior sobre o que está ocorrendo
  • Exemplo: sleep não pode ser interrompido mas com wait/notify, podemos ter melhor controle

Executando o exemplo Produtor/Consumidor

• Eis um exemplo pequeno do produtor/consumidor (ProducerConsumerTest):

public class ProducerConsumerTest {
    public static void main(String[] args) {
        CubbyHole c = new CubbyHole();
        Producer p1 = new Producer(c, 1);
        Consumer c1 = new Consumer(c, 1);

        p1.start();
        c1.start();
    }
}

• Eis a saída:

Producer #1 put: 0
Consumer #1 got: 0
Producer #1 put: 1
Consumer #1 got: 1
Producer #1 put: 2
Consumer #1 got: 2
Producer #1 put: 3
Consumer #1 got: 3
Producer #1 put: 4
Consumer #1 got: 4
Producer #1 put: 5
Consumer #1 got: 5
Producer #1 put: 6
Consumer #1 got: 6
Producer #1 put: 7
Consumer #1 got: 7
Producer #1 put: 8
Consumer #1 got: 8
Producer #1 put: 9
Consumer #1 got: 9

Locks explícitos e variáveis condicionais

• Para proteger regiões críticas (proteger uma seção de código), podemos também usar um lock explícito
  • Um lock explícito é mais flexível do que usar a palavra synchronized
    • Permite proteger alguns statements (sem bloco)
    • permite proteger múltiplos métodos
• Para criar um lock explícito, você instancia uma implementação da interface Lock
  • Normalmente, instancia-se ReentrantLock
• Para obter o lock, usa-se o método lock()
• Para liberar o lock: usa-se unlock()
• Já que o lock não é liberado automaticamente no final de um método, pode ser útil usar try/finally para garantir que o lock seja liberado
• Para esperar por um lock explícito, cria-se uma variável condicional
  • Um objeto que implementa a interface Condition
  • Usar Lock.newCondition() para criar uma condição
• A condição provê métodos:
  • "await" para esperar até a condição ser verdadeira
  • "signal" e "signalAll" para avisar os threads que a condição ocorreu
  • As variantes de "await" aparecem na tabela seguinte

Métodos Condition.await
Método	Descrição
await	Espera uma condição ocorrer
awaitUninterruptibly	Espera uma condição ocorrer. Não pode ser interrompido.
awaitNanos(long timeout)	Espera uma condição ocorrer. Espera no máximo timeout nanossegundos
await(long timeout, TimeUnit unit)	Espera uma condição ocorrer. Espera no máximo timeout TimeUnit
await(Date timeout)	Espera uma condição ocorrer. Espera no máximo até a data especificada

• O exemplo abaixo é CubbyHole reescrito para usar um lock explícito e uma variável condicional
  • Para rodar, execute ProducerConsumerTest2

import java.util.concurrent.locks.*;
public class CubbyHole2 {
    private int contents;
    private boolean available = false;
    private Lock aLock = new ReentrantLock();
    private Condition condVar = aLock.newCondition();

    public int get(int who) {
        aLock.lock();
        try {
            while (available == false) {
                try {
                    condVar.await();
                } catch (InterruptedException e) { }
            }
            available = false;
            System.out.println("Consumer " + who + " got: " +
                                contents);
            condVar.signalAll();
        } finally {
            aLock.unlock();
            return contents;
        }
    }

    public void put(int who, int value) {
                    aLock.lock();
    try {
        while (available == true) {
            try {
                condVar.await();
            } catch (InterruptedException e) { }
        }
        contents = value;
        available = true;
        System.out.println("Producer " + who + " put: " +
                            contents);
        condVar.signalAll();
        } finally {
            aLock.unlock();
        }
    }
}

Estruturas de dados sincronizadas

• Em vez de construir sua própria estrutura de dados sincronizada (como CubbyHole), você pode usar estruturas já prontas, com detalhes de sincronização escondidos
  • O package java.util.concurrent tem tais estruturas
• O exemplo que segue usa BlockingQueue como cubbyhole
  • A fila trata de todos os detalhes (proteção de regiões críticas, sincronização par indicar disponibilidade de dados)
  • Fonte: Producer3.java, Consumer3.java, ProducerConsumerTest3.java

import java.util.concurrent.*;
public class Producer3 extends Thread {
    private BlockingQueue cubbyhole;
    private int number;
                          
    public Producer3(BlockingQueue c, int num) {
        cubbyhole = c;
        number = num;
    }

    public void run() {
        for (int i = 0; i < 10; i++) {
            try {
                cubbyhole.put(i);
                System.out.println("Producer #" + number + 
                                   " put: " + i);
                sleep((int)(Math.random() * 100));
            } catch (InterruptedException e) { }
        }
    }
}

• O consumidor é semelhante
• Para rodar o programa, use ProducerConsumerTest3, que cria um ArrayBlockingQueue (implementação de BlockingQueue):

import java.util.concurrent.*;
public class ProducerConsumerTest3 {
    public static void main(String[] args) {

        BlockingQueue c = new ArrayBlockingQueue(1);
        Producer3 p1 = new Producer3(c, 1);
        Consumer3 c1 = new Consumer3(c, 1);

        p1.start();
        c1.start();
    }
}

Sincronizando coleções

• As coleções de Java (ArrayList, ...) não são sincronizadas
  • Dizemos que o uso dessas coleções não seja "thread-safe"
  • A exceção é Vector que é sincronizada por motivos históricos
• Para criar coleções sincronizadas, você pode criar um decorador da coleção que sincroniza os métodos
• Java já fornece tais decoradores na classe Collections
  • Há várias decoradores porque há várias interfaces para usar coleções
    • Collection
    • List
    • Map
    • Set

• Exemplo: como usar uma lista sincronizada

List list = Collections.synchronizedList(new ArrayList());

• É importante que apenas a nova lista seja utilizada a partir desse ponto
  • A lista original não deve ser tocada diretamente
• Há um problema especial no uso de um iterator
  • Ao usar um iterator, temos que "entrar" e "sair" do iterator usando dois métodos (hasNext e next)
  • Se cada um desses métodos fosse sincronized, ainda não teríamos uma solução, pois o que o next retorna tem que corresponder a o que hasNext falou antes
  • Portanto, temos que fazer uma sincronização atômica com os dois
  • Ver abaixo a forma correta de iterar na lista

      ...
  synchronized(list) {
      Iterator i = list.iterator(); // Must be in synchronized block
      while (i.hasNext())
          foo(i.next());
  }

• Os vários métodos disponíveis para criar esses decoradores são:
  • synchronizedCollection
  • synchronizedList
  • synchronizedMap
  • synchronizedSet
  • synchronizedSortedMap
  • synchronizedSortedSet

Starvation (morte por inanição) e deadlock

• Ao escrever um  programa envolvendo vários threads que competem por recursos, temos que assegurar a equidade
  • Equidade existe quando cada thread recebe recursos suficientes para progredir de forma razoável
  • Um sistema equanime evita duas coisas: starvation e deadlock
• Starvation ocorre quando um ou mais threads não conseguem obter recursos no sistema e não pode progredir
• Deadlock é uma forma especialmente drástica de starvation em que dois ou mais threads estão esperando por uma condição que nunca vai ocorrer
  • Tipicamente, os threads estão esperando por algum lock ou condição que outro thread possui, e há dependência circular
• Vamos exemplificar deadlock com o exemplo do Jantar dos Filósofos (dining philosophers)
  • Cinco filósofos estão sentados numa mesa redonda
  • Na frente de cada filósofo, há uma tijela de arroz
  • Entre cada filósofo há um chopstick (pauzinho chinês)
  • Para poder comer um bocado de arroz, um filósofo deve ter 2 pauzinhos: o à sua esquerda e o à sua direita
  • Os filósofos devem achar uma forma de compartilhar pauzinhos de forma a que todos possam comer
• O applet abaixo implementa o seguinte algoritmo
  1. Um filósofo sempre pega o pauzinho da esquerda primeiro; se o pauzinho estiver aí, o filósofo o pega e levanta sua mão esquerda
  2. O filósofo tenta pegar o pauzinho da direita, se estiver disponível, ele o pega e levanta sua mão direita
  3. Quando o filósofo tem ambos os pauzinhos, ele come o bocado de arroz e fala "Gostoso!"
  4. Ele então larga os dois pauzinhos, deixando que outros filósofos os peguem
  5. O filósofo pausa um pouco e tenta tudo novamente

• O slider no applet controla o tempo de espera (a gula!) dos filósofos
• Quando o slider está em 0, os filósofos não esperam e um deadlock ocorre logo (com a mão esquerda de todos os filósofos para cima)
  • O deadlock ocorre porque cada um está esperando do algo que nunca ocorrerá
• Com um período menor, o deadlock pode demorar um bom tempo até ocorrer
• Criar programas com deadlock é comum e o estudo detalhado de como tratar o assunto será coberto em outra disciplina (sistemas operacionais)
• Por enquanto, basta dizer que uma das técnicas possíveis é escrever o programa de tal forma a impedir a ocorrência do deadlock
• Uma forma de fazer isso é de impor uma ordem na variáveis condicionais
  • No exemplo acima, todos os pauzinhos são iguais e não há ordem imposta
  • Mas podemos numerar os pauzinhos de 1 até 5 e obrigar cada filósofo a pegar o pauzinho de menor número primeiro
  • Isso evita qualquer deadlock
  • Detalhes em outra disciplina ...

programa