Capítulo 14. Sincronização

Compartilhar é algumas vezes mais custoso do que dar.

— Mary Catherine Bateson

14.1. Introdução

Os programas concorrentes permitem que várias threads sejam programadas e executadas, mas o programador não tem muito controle sobre quando as threads são executadas. Conforme explicado em [Conceitos: Agendamento de threads], a JVM e o sistema operacional subjacente são responsáveis pelo agendamento de threads nos núcleos do processador.

Ao escrever um programa concorrente, você precisa garantir que o programa funcione corretamente, mesmo que diferentes execuções do mesmo programa provavelmente levarão a diferentes sequências de execução de threads. O problema que apresentaremos a seguir ilustra por que uma sequência de execução de thread pode ser perfeitamente bem, enquanto outra pode levar a um comportamento inesperado e incorreto. (E até mesmo pessoas morrendo de fome!)

14.2. Problema: Jantar dos filósofos

A concorrente nos dá o potencial de tornar nossos programas mais rápidos, mas introduz uma série de outros problemas. A maneira como as threads interagem pode ser imprevisível. Como elas compartilham memória, uma thread pode corromper um valor nas variáveis de outra thread. Apresentamos as ferramentas de sincronização neste capítulo que podem evitar que os threads corrompam os dados, mas essas ferramentas criam novas armadilhas. Para explorar essas armadilhas, apresentamos a você outro problema para resolver.

Imagine vários filósofos sentados em uma mesa redonda com pratos que são periodicamente preenchidos com arroz. Entre os filósofos adjacentes estão pauzinhos individuais, de modo que há exatamente o mesmo número de pauzinhos que o número de filósofos. Esses filósofos só pensam e comem. Para comer, um filósofo deve pegar o pauzinho à esquerdo e o da direita. Figura 14.1 ilustra essa situação.

diners
Figura 14.1 Mesa para cinco filósofos em um jantar.

Seu objetivo é escrever uma classe chamada DiningPhilosopher que estende Thread. Cada thread criada no método main() deve ser um filósofo que pensa por algum tempo aleatório, depois pega os dois pauzinhos necessários e come. Nenhum filósofo deve passar fome. Nenhum dos filósofos deveria ficar preso indefinidamente brigando por pauzinhos.

Embora esse problema pareça simples, a solução não é. Certifique-se de que você entendeu bem os conceitos e a sintaxe Java deste capítulo completamente antes de tentar implementar sua solução. É importante que não haja dois filósofos tentando usar o mesmo pauzinho ao mesmo tempo. Da mesma forma, precisamos evitar uma situação em que cada filósofo esteja esperando que todos os outros filósofos desistam de um pauzinho.

14.3. Conceitos: Interação de thread

Esse problema do jantar dos filósofos destaca algumas dificuldades que estavam surgindo no final do último capítulo. Em Exercício 13.10 dois trechos de código poderiam ser executados concorrentemente e modificar a mesma variável compartilhada, potencialmente produzindo uma saída incorreta. Devido à natureza não determinística do agendamento, temos de presumir que o código executado em duas ou mais threads pode ser intercalados de qualquer maneira possível. Quando o resultado da computação muda dependendo da ordem de execução da thread, ele é chamado de condição de corrida (ou _race condition, em inglês). Abaixo está um exemplo simples de uma condição de corrida em Java.

Programa 14.1 Exemplo simples de uma condição de corrida
public class RaceCondition extends Thread {     
    private static int counter = 0; 
    public static final int THREADS = 4;    
    public static final int COUNT = 1000000;        
    
    public static void main(String[] args) {                              
        RaceCondition[] threads = new RaceCondition[THREADS];           
        for(int i = 0; i < THREADS; i++) {
            threads[i] = new RaceCondition();
            threads[i].start();         
        }           
        try {
            for(int i = 0; i < THREADS; i++)
                threads[i].join();
        }
        catch(InterruptedException e) {
            e.printStackTrace();
        }           
        System.out.println("Counter:\t" + counter);            
    }   
    
    public void run() { 
        for(int i = 0; i < COUNT/THREADS; i++)
            counter++;
    }
}

Essa classe curta (e sem sentido) tenta incrementar a variável counter até que ela atinja 1000000. Para ilustrar a condição de corrida, dividimos o trabalho de incrementar counter igualmente entre vários threads. Se você executar esse programa, o valor final de counter geralmente não será `1000000. Dependendo de qual JVM, sistema operacional e quantos núcleos você tem, talvez nunca obtenha 1000000, e a resposta que você obtiver variar muito. Em todos os sistemas, se você alterar o valor de THREADS para 1, a resposta deverá estar sempre correta.

[raceConditionExercise]
[threadTimeSliceExercise]

Observando o código, o problema pode não ser óbvio. Tudo está centrado na instrução counter++ no loop for dentro método run(). Porém, essa instrução parece ser executada em uma única etapa! Cada thread deve aumentar o valor de counter em um total de COUNT/THREADS vezes, somando até 1000000. O problema é que counter++ não é uma única etapa. Lembre-se de que counter++ é uma abreviação para contador = contador + 1. Para ser ainda mais explícito, poderíamos escrever da seguinte forma.

temp = counter;
counter = temp + 1;

Um thread pode chegar ao ponto de armazenar o counter em um local temporário, mas depois fica sem tempo, permitindo que a próxima thread agendada seja executada. Quando esse for o caso, a próxima thread poderá fazer uma série de incrementos no count que são sobrescritos quando a primeira thread for executada novamente. Como a primeira thread tinha um valor antigo de counter armazenado em temp, adicionar 1 a temp tem o efeito de ignorar os incrementos que ocorreram nesse intervalo. Essa situação pode ocorrer em um único processador com threads alternando entre si, mas é ainda mais perigosa em um sistema com vários núcleos.

A principal lição aqui é que as threads podem alternar entre si a a qualquer momento, com efeitos imprevisíveis. A segunda lição é que o código-fonte é muito grosseiro para mostrar operações atômicas. Uma operação atômica atômica é aquela que não pode ser interrompida por uma troca de contexto para outra thread. O código real que a JVM executa é de nível muito mais baixo do que o código-fonte.

Não é possível forçar facilmente uma operação não atômica a ser atômica, mas existem maneiras de restringir o acesso a determinadas partes do código sob certas condições. O nome que damos a um trecho de código que não deve ser acessado por mais de uma thread ao mesmo tempo é seção crítica. No No exemplo acima, a única linha de código que incrementa o counter é uma seção crítica, e o erro no programa seria removido se apenas uma thread pudesse executar essa linha de código por vez.

A proteção de uma seção crítica é feita com ferramentas de exclusão mútua. Elas são chamadas de ferramentas de exclusão mútua porque impõem o requisito de que uma thread que executa uma seção crítica exclui a possibilidade de outra. Há muitas técnicas, algoritmos e recursos de linguagem na ciência da computação que podem ser usados para criar exclusão mútua. O Java depende muito de uma ferramenta chamada monitor que oculta do usuário alguns dos detalhes da aplicação da exclusão mútua. A exclusão mútua é um tópico profundamente pesquisado com muitas abordagens além além dos monitores. Se planeja escrever programas concorrentes em outra linguagem, talvez seja necessário se atualizar sobre os recursos de exclusão mútua dessa linguagem.

[restaurantSynchronizationExercise]

14.4. Sintaxe: Sincronização de thread

14.4.1. A palavra-chave synchronized

Em Java, o recurso de linguagem que permite que você aplique a exclusão mútua é a palavra-chave synchronized. Há duas maneiras de usar essa palavra-chave: com um método ou com um bloco arbitrário de código. No método você adiciona o modificador synchronized antes do tipo de retorno. Vamos imaginar uma classe com um campo String privado chamado message que é definido como “Will Robinson!” pelo construtor. Agora, definimos o seguinte método.

public synchronized void danger() {
    message = "Danger, " + message;
}

Se danger() for chamada cinco vezes em diferentes threads, message conterá
“Perigo, Perigo, Perigo, Perigo, Perigo, Will Robinson!”. Sem a palavra-chave synchronized, danger() sofreria de uma condição de corrida semelhante à de RaceCondition. Algumas das concatenações de String podem ser sobrescritas por outras chamadas a danger(). Você nunca teria mais de cinco cópias de “Danger,” anexadas ao no início de message, mas você pode ter menos.

[synchronizedKeywordExercise]

Sempre que uma thread entra em um trecho de código protegido pela palavra-chave synchronized ele adquire implicitamente um bloqueio que somente uma única thread pode manter. Se outra thread tentar acessar o código, ela será forçada a esperar até que o bloqueio seja liberado. Esse bloqueio é reentrante. Reentrante significa significa que, quando uma thread mantém um bloqueio e tenta obtê-lo novamente, ela é bem-sucedida. Essa situação ocorre frequentemente com métodos sincronizados que chamam outros métodos sincronizados.

[lockTimingExercise]

Considere o método safety() que faz o “oposto” de danger(), removendo as ocorrências de “Danger,” do início de message.

public synchronized void safety() {
    if(message.startsWith("Danger, "))
        message = message.substring(8);
}

Os métodos danger() e safety() funcionarão bem juntos no mesmo objeto? Em outras palavras, uma thread será impedida de entrar em safety() se outra thread já estiver em danger()? Sim! Os bloqueios em Java estão conectados a objetos. Quando você usa a palavra-chave synchronized em um método o objeto no qual o método está sendo chamado (qualquer que seja o objeto this se refere dentro do método) funciona como o bloqueio. Portanto, somente uma thread pode estar dentro de qualquer um desses métodos em um determinado objeto. Se você tiver 10 métodos sincronizados em um objeto, somente um deles poderá ser executado por vez para esse objeto.

[constructorLeakExercise]
[synchronizedThreadIncrementExercise]

Talvez esse nível de controle seja muito restritivo. Você pode ter seis métodos que entram em conflito entre si e outros quatro que entram em conflito entre si, mas não com os seis primeiros. Usar synchronized em cada declaração de método limitaria desnecessariamente a quantidade de concorrência que seu programa poderia ter.

Embora exija um pouco mais de trabalho, o uso de synchronized em um bloco de código permite um controle mais refinado. A seguinte versão de danger() é equivalente à anterior.

public void danger() {
    synchronized(this) {
        message = "Danger, " + message;
    }
}

O uso de synchronized em um bloco de código nos dá mais flexibilidade de duas maneiras. Primeiro, podemos escolher exatamente a quantidade de código que queremos controlar, em vez de todo o método. Segundo, podemos escolher qual objeto queremos usar para a sincronização. No estilo de bloco, qualquer objeto arbitrário pode ser usado como um bloqueio. Os objetos mantêm uma lista de threads que estão esperando para obter o bloqueio e fazem todos os outros gerenciamentos necessários para que a palavra-chave synchronized funcione.

Se houver duas seções críticas que não estejam relacionadas entre si, você poderá usar o controle refinado que o estilo de bloco oferece. Primeiro, você precisará de alguns objetos para usar como bloqueios, provavelmente declarados de forma que possam ser facilmente compartilhados, talvez como campos estáticos de uma classe.

private static Object lock1 = new Object();
private static Object lock2 = new Object();

Então, sempre que precisar de controle sobre a concorrência, use-os como bloqueios.

synchronized(lock1) {
    // Fazer coisas perigosas 1
}

// Fazer coisas seguras

synchronized(lock2) {
    // Fazer a coisa perigosa 2, não relacionada à coisa perigosa 1
}

Como declarar um método com synchronized é equivalente a ter seu corpo em um bloco que começa com synchronized(this), o que dizer dos métodos métodos static? Eles podem ser sincronizados? Sim, podem. Sempre que uma classe é carregada, o Java cria um objeto do tipo Class que corresponde a essa classe. Esse objeto é o que os métodos estáticos sincronizados dentro da classe usarão como bloqueio. Por exemplo, um método estático sincronizado dentro da classe Eggplant bloqueará o objeto Eggplant.class.

14.4.2. Os métodos wait() e notify()

A proteção de seções críticas com a palavra-chave synchronized é uma técnica poderosa, e muitas outras ferramentas de sincronização podem ser criadas usando apenas essa ferramenta. Entretanto, a eficiência exige mais algumas opções.

Às vezes, uma thread está esperando que outra thread termine uma tarefa para possa processar os resultados. Imagine uma thread coletando votos enquanto outra está esperando para contá-los. Nesse exemplo, a thread de contagem deve esperar que todos os votos sejam lançados antes de começar a contar. Poderíamos usar um bloco sincronizado e um indicador boolean chamado votingComplete para permitir que a thread do coletor sinalize para a thread de contagem.

while(true) {
    synchronized(this) {
        if(votingComplete)
            break;
    }
}
countVotes();

Qual é o problema com esse design? A thread de contagem está está executando o loop while repetidamente, esperando que votingComplete se torne true. Em um único processador, a thread de contagem retardaria o trabalho da thread de coleta que está tentando processar todos os votos. Em um sistema com vários núcleos, a thread de contagem ainda está desperdiçando ciclos de CPU que alguma outra thread poderia usar. Esse fenômeno é conhecido como busy waiting, por motivos óbvios.

Para combater esse problema, o Java fornece o método wait(). Quando uma thread está executando código sincronizado, ele pode chamar wait(). Em vez de ficar ocupada esperando, uma thread que tenha chamado wait() será removida da lista de threads em execução. Ele aguardará em um estado inativo até que alguém apareça e notifique a thread de que sua espera terminou. Se você lembrar do diagrama de estado da thread de Capítulo 13, há um estado Not Runnable no qual as threads entram ao chamar sleep(), chamando wait() ou executando E/S de bloqueio. Usando wait(), podemos reescrever a thread de contagem de votos.

synchronized(this) {
    while(!votingComplete) {
        wait();
    }
}
countVotes();

Observe que o loop while foi movido para dentro do bloco sincronizado. Fazer isso antes poderia ter impedido o término do nosso programa: Enquanto a thread de contagem de votos mantivesse o bloqueio, a thread de coleta de votos não teria permissão para modificar votingComplete. Quando uma thread chama wait(), no entanto, ele abre mão do bloqueio correspondente que está mantendo até que ela acorde e execute novamente. Por que usar o loop while agora? Não há garantia de que a condição que você está esperando é “verdadeira”. Muitas threads podem estar esperando por esse bloqueio específico. Usamos o loop while para verificar que votingComplete é true e esperamos novamente se não for.

Para notificar uma thread em espera, a outra thread chama o método notify(). Assim como o wait(), o notify() deve ser chamado em um bloco ou método sincronizado. Aqui está o código correspondente que a thread de coleta de votos pode usar para notificar a thread de contagem de votos de que a votação foi concluída.

// Finish collecting votes
synchronized(this) {
    votingComplete = true;
    notifyAll();
}

Uma chamada a notify() despertará uma thread que esteja aguardando o objeto de bloqueio. Se houver muitas threads aguardando, o método notifyAll() usado acima pode ser chamado para despertar todas elas. Na prática, geralmente é mais seguro chamar notifyAll(). Se uma determinada condição for alterada e uma única thread em espera for notificada, essa thread talvez precise notificar a próxima thread em espera quando tiver terminado. Se seu código não for muito cuidadosamente projetado, alguma thread pode acabar esperando para sempre e nunca ser notificada se você depender apenas de notify().

[waitNotifyExercise]
[notifyAllExercise]

Exemplo 14.1 Producer/consumer

To illustrate the use of wait() and notify() calls inside of synchronized code, we give a simple solution to the producer/consumer problem below. This problem is a classic example in the concurrent programming world. Often one thread (or a group of threads) is producing data, perhaps from some input operation. At the same time, one thread (or, again, a group of threads) is taking these chunks of data and consuming them by performing some computational or output task.

Every resource inside of a computer is finite. Producer/consumer problems often assume a bounded buffer which stores items from the producer until the consumer can take them away. Our solution does all synchronization on this buffer. Many different threads can share this buffer, but all accesses will be controlled.

Programa 14.2 Example of a synchronized buffer.
public class Buffer {
    public final static int SIZE = 10;
    private Object[] objects = new Object[SIZE];    
    private int count = 0;
    
    public synchronized void addItem(Object object) throws InterruptedException { (1)
        while(count == SIZE) (2)
            wait();     
        objects[count] = object;
        count++;
        notifyAll();         (3)
    }
    
    public synchronized Object removeItem() throws InterruptedException { (4)
        while(count == 0)    (5)
            wait();
        count--;
        Object object = objects[count];     
        notifyAll();         (6)
        return object;
    }
}
1 When adding an item, producers enter the synchronized addItem() method.
2 If count shows that the buffer is full, the producer must wait until the buffer has at least one open space.
3 After adding an item to the buffer, the producer then notifies all waiting threads.
4 The consumer performs mirrored operations in removeItem().
5 A consumer thread can’t consume anything if the buffer is empty and must then wait.
6 After there’s an object to consume, the consumer removes it and notifies all other threads.

Both methods are synchronized, making access to the buffer completely sequential. Although it seems undesirable, sequential behavior is precisely what’s needed for the producer/consumer problem. All synchronized code is a protection against unsafe concurrency. The goal is to minimize the amount of time spent in synchronized code and get threads back to parallel execution as quickly as possible.

[twoLockProducerConsumerExercise]

Exemplo 14.2 Bank account

Although producer/consumer is a good model to keep in mind, there are other ways that reading and writing threads might interact. Consider the following programming problem, similar to one you might find in real life.

As a rising star in a bank’s IT department, you’ve been given the job of creating a new bank account class called SynchronizedAccount. This class must have methods to support the following operations: deposit, withdraw, and check balance. Each method should print a status message to the screen on completion. Also, the method for withdraw should return false and do nothing if there are insufficient funds. Because the latest system is multi-threaded, these methods must be designed so that the bookkeeping is consistent even if many threads are accessing a single account. No money should magically appear or disappear.

There’s an additional challenge. To maximize concurrency, SynchronizedAccount should be synchronized differently for read and write accesses. Any number of threads should be able to check the balance on an account simultaneously, but only one thread can deposit or withdraw at a time.

To solve this problem, our implementation of the class has a balance variable to record the balance, but it also has a readers variable to keep track of the number of threads which are reading from the account at any given time.

public class SynchronizedAccount {
    private double balance = 0.0;   
    private int readers = 0;

Next, the getBalance() method is called by threads which wish to read the balance.

    public double getBalance() throws InterruptedException {
        double amount;      
        synchronized(this) {   (1)
            readers++;
        }       
        amount = balance;      (2)
        synchronized(this) {
            if(--readers == 0) (3)
                notifyAll();   (4)
        }       
        return amount;      
    }
1 Access to the readers variable is synchronized.
2 After passing that first synchronized block, the code which stores the balance is no longer synchronized. In this way, multiple readers can access the data at the same time. For this example, the concurrency controls we have are overkill. The command amount = balance does not take a great deal of time. If it did, however, it would make sense for readers to execute it concurrently as we do.
3 After reading the balance, this method decrements readers.
4 If readers reaches 0, a call to notifyAll() is made, signaling that threads trying to deposit to or withdraw from the account can continue. 
    public void deposit(double amount) throws InterruptedException {
        changeBalance(amount);
        System.out.println("Deposited $" + amount + ".");
    }
    
    public boolean withdraw(double amount)
        throws InterruptedException {
        boolean success = changeBalance(-amount);
        if(success)
            System.out.println("Withdrew $" + amount + ".");
        else
            System.out.println("Failed to withdraw $" +
                amount + ": insufficient funds.");
        return success;
    }

The deposit() and withdraw() methods are wrappers for the changeBalance() method, which has all the interesting concurrency controls.

    protected synchronized boolean changeBalance(double amount) (1)
        throws InterruptedException {
        boolean success;    
        while(readers > 0) (2)
			wait();         
        if(success = (balance + amount > 0)) (3)
            balance += amount;      
        return success; 
    }
}
1 The changeBalance() method is synchronized so that it can have exclusive access to the readers variable. It’s also marked protected because SynchronizedAccount will be used as a parent class in Capítulo 17.
2 As long as readers is greater than 0, this method will wait.
3 Eventually, the readers should finish their job and notify the waiting writer which can finish changing the balance of the account.

14.5. Pitfalls: Synchronization challenges

As you can see from the dining philosophers problem, synchronization tools help us get the right answer but also create other difficulties.

14.5.1. Deadlock

Deadlock is the situation when two or more threads are both waiting for the others to complete, forever. Some combination of locks or other synchronization tools has forced a blocking dependence onto a group of threads which will never be resolved.

In the past, people have described four conditions which must exist for deadlock to happen.

  1. Mutual Exclusion: Only one thread can access the resource (often a lock) at a time.

  2. Hold and Wait: A thread holding a resource can ask for additional resources.

  3. No Preemption: A thread holding a resource cannot be forced to release it by another thread.

  4. Circular Wait: Two or more threads hold resources which make up a circular chain of dependency.

Exemplo 14.3 Deadlock philosophers

We illustrate deadlock with an example of how not to solve the dining philosophers problem. What if all the philosophers decided to pick up the chopstick on her left and then the chopstick on her right? If the timing was just right, each philosopher would be holding one chopstick in her left hand and be waiting forever for her neighbor on the right to give up a chopstick. No philosopher would ever be able to eat. Here’s that scenario illustrated in code.

public class DeadlockPhilosopher extends Thread {
    public static final int SEATS = 5;     (1)
    private static boolean[] chopsticks = new boolean[SEATS]; (2)
    private int seat;
    
    public DeadlockPhilosopher(int seat) { (3)
        this.seat = seat;
    }
1 We define a constant for the number of seats.
2 We create a shared boolean array called chopsticks so that all philosophers can know which chopsticks are in use.
3 The constructor assigns each philosopher a seat number. 
	public static void main(String args[]) {        
        DeadlockPhilosopher[] philosophers = new DeadlockPhilosopher[SEATS];
        for(int i = 0; i < SEATS; i++) {
            philosophers[i] = new DeadlockPhilosopher(i);
            philosophers[i].start();    (1)
        }
        try {
            for(int i = 0; i < SEATS; i++)                        
                philosophers[i].join(); (2)
        }
        catch(InterruptedException e) {
            e.printStackTrace();
        }       
        System.out.println("All philosophers done.");
    }
1 In main(), we create and start a thread for each philosopher.
2 Then, we wait for them to finish which, sadly, will never happen.

After setting up the class and the main() method, things get interesting in the run() method.

    public void run() {         
        try { 
            getChopstick(seat);     			(1)
            Thread.sleep(50);       			(2)
			getChopstick((seat + 1) % SEATS); 	(3)
        }
        catch(InterruptedException e) {
            e.printStackTrace();
        }           
        eat();
    }
1 First a philosopher tries to get her left chopstick.
2 Then she sleeps for 50 milliseconds.
3 Finally, she tries to get her right chopstick. We mod by SEATS so that the last philosopher will try to get the chopstick at the beginning of the array.

Without sleeping, this code would usually run just fine. Every once in a while, the philosophers would become deadlocked, but it would be hard to predict when. By introducing the sleep, we can all but guarantee that the philosophers will deadlock every time.

The remaining two methods are worth examining to see how the synchronization is done, but by getting the two chopsticks separately above, we’ve already gotten ourselves into trouble.

    private void getChopstick(int location) throws InterruptedException {
        if(location < 0)
            location += SEATS;
        synchronized(chopsticks) {
            while(chopsticks[location])
                chopsticks.wait();
            chopsticks[location] = true;
        }       
        System.out.println("Philosopher " + seat +
            " picked up chopstick " + location + ".");
    }
    
    private void eat() {
        // Done eating, put back chopsticks
        synchronized(chopsticks) {
            chopsticks[seat] = false;           
            if(seat == 0)
                chopsticks[SEATS - 1] = false;
            else
                chopsticks[seat - 1] = false;                           
            chopsticks.notifyAll();
        }
    }
}
Exemplo 14.4 Deadlock sum

Here’s another example of deadlock. We emphasize deadlock because it’s one of the most common and problematic issues with using synchronization carelessly.

Consider two threads which both need access to two separate resources. In our example, the two resources are random number generators. The goal of each of these threads is to acquire locks for the two shared random number generators, generate two random numbers each, and sum the numbers generated. (Note that locks are totally unnecessary for this problem since access to Random objects is synchronized.)

import java.util.Random;

public class DeadlockSum extends Thread {
    private static Random random1 = new Random();
    private static Random random2 = new Random();   
    private boolean reverse;
    private int sum;

The class begins by creating shared static Random objects random1 and random2. Then, in the main() method, the main thread spawns two new threads, passing true to one and false to the other.

    public static void main(String[] args) {
        Thread thread1 = new DeadlockSum(true);
        Thread thread2 = new DeadlockSum(false);
        thread1.start();
        thread2.start();
        try {
            thread1.join();
            thread2.join();
        }
        catch(InterruptedException e) {
            e.printStackTrace();
        }                   
    }

Next, the mischief begins to unfold. One of the two threads stores true in its reverse field.

    public DeadlockSum(boolean reverse) {
        this.reverse = reverse;
    }

Finally, we have the run() method where all the action happens. If the two running threads were both to acquire locks for random1 and random2 in the same order, everything would work out fine. However, the reversed thread locks on random2 and then random1, with a sleep() in between. The non-reversed thread tries to lock on random1 and then random2.

    public void run() { 
        if(reverse) {         
            synchronized(random2) {
				System.out.println("Reversed Thread: locked random2");
				try{ Thread.sleep(50); }
				catch(InterruptedException e) {
					e.printStackTrace();
				}
				synchronized(random1) {
					System.out.println("Reversed Thread: locked random1");
					sum = random1.nextInt() + random2.nextInt();                
				}
            }
        }
        else {          
            synchronized(random1) {
				System.out.println("Normal Thread: locked random1");
				try { Thread.sleep(50); }
				catch(InterruptedException e) {
				  e.printStackTrace();
				}
				synchronized(random2) {
					System.out.println("Normal Thread: locked random2");              
					sum = random1.nextInt() + random2.nextInt();                
				}
			}
        }
    }
}

If you run this code, it should invariably deadlock with thread1 locked on random2 and thread2 locked on random1. No sane programmer would intentionally code the threads like this. In fact, the extra work we did to acquire the locks in opposite orders is exactly what causes the deadlock. For more complicated programs, there may be many different kinds of threads and many different resources. If two different threads (perhaps written by different programmers) need both resource A and resource B at the same time but try to acquire them in reverse order, this kind of deadlock can occur without such an obvious cause.

For deadlock of this type, the circular wait condition can be broken by ordering the resources and always locking the resources in ascending order. Of course, this solution only works if there is some universal way of ordering the resources and the ordering is always followed by all threads in the program.

Ignoring the deadlock problems with the example above, it gives a nice example of the way Java intended synchronization to be done: when possible, use the resource you need as its own lock. Many other languages require programmers to create additional locks or semaphores to protect a given resource, but this approach causes problems if the same lock is not consistently used. Using the resource itself as a lock is an elegant solution.

[deadlockExercise]

14.5.2. Starvation and livelock

Starvation is another problem which can occur with careless use of synchronization tools. Starvation is a general term which covers any situation in which some thread never gets access to the resources it needs. Deadlock can be viewed as a special case of starvation since none of the threads which are deadlocking makes progress.

The dining philosophers problem was framed around the idea of eating with humorous intent. If a philosopher is never able to acquire chopsticks, that philosopher will quite literally starve.

Starvation doesn’t necessarily mean deadlock, however. Examine the implementation in Exemplo 14.2 for the bank account. That solution is correct in the sense that it preserves mutual exclusion. No combination of balance checks, deposits, or withdrawals will cause the balance to be incorrect. Money will neither be created nor destroyed. A closer inspection reveals that the solution is not entirely fair. If a single thread is checking the balance, no other thread can make a deposit or a withdrawal. Balance checking threads could be coming and going constantly, incrementing and decrementing the readers variable, but if readers never goes down to zero, threads waiting to make deposits and withdrawals will wait forever.

[concurrentReadExercise]

Another kind of starvation is livelock. In deadlock, two or more threads get stuck and wait forever, doing nothing. Livelock is similar except that the two threads keep executing code and waiting for some condition that never arrives. A classic example of livelock is two polite (but oddly predictable) people speaking with each other: Both happen to start talking at exactly the same moment and then stop to hear what the other has to say. After exactly one second, they both begin again and immediately stop. Lather, rinse, repeat.

Exemplo 14.5 Livelock party preparations

Imagine three friends going to a party. Each of them starts getting ready at different times. They follow the pattern of getting ready for a while, waiting for their friends to get ready, and then calling their friends to see if the other two are ready. If all three are ready, then the friends will leave. Unfortunately, if a friend calls and either of the other two aren’t ready, he’ll become frustrated and stop being ready. Perhaps he’ll realize that he’s got time to take a shower or get involved in some other activity for a while. After finishing that activity, he’ll become ready again and wait for his friends to become ready.

If the timing is just right, the three friends will keep becoming ready, waiting for a while, and then becoming frustrated when they realize that their friends aren’t ready. Here’s a rough simulation of this process in code.

public class Livelock extends Thread {
    private static int totalReady = 0; 		   (1)
    private static Object lock = new Object(); (2)

    public static void main(String[] args) {   (3)
        Livelock friend1 = new Livelock();
        Livelock friend2 = new Livelock();
        Livelock friend3 = new Livelock();
1 First, we create a shared variable called totalReady which tracks the total number of friends ready.
2 To avoid race conditions, a shared Object called lock will be used to control access to totalReady.
3 Then, the main() method creates Livelock objects representing each of the friends. 
        try {       
            friend1.start();
            Thread.sleep(100);
            friend2.start();
            Thread.sleep(100);
            friend3.start();
                        
            friend1.join();
            friend2.join();
            friend3.join();
        }
        catch(InterruptedException e) {
            e.printStackTrace();
        }       
        System.out.println("All ready!");
    }

The rest of the main() method starts each of the threads representing the friends running, with a 100 millisecond delay before the next thread starts . Then, it waits for them all to finish. If successful, it’ll print All ready! to the screen.

    public void run() { 
        boolean done = false;
    
        try {       
            while(!done) { (1)
                Thread.sleep(75); // Prepare for party (2)
                synchronized(lock) {
                    totalReady++;       (3)
                }                   
                Thread.sleep(75); // Wait for friends  (4)
                synchronized(lock) {
                    if(totalReady >= 3) (5)
                        done = true;
                    else
                        totalReady--;   (6)
                }
            }
        }
        catch(InterruptedException e) {
            e.printStackTrace();
        }
    }
}
1 In the run() method, each friend goes through a loop until the done variable is true.
2 In this loop, an initial call to Thread.sleep() for 75 milliseconds represents preparing for the party.
3 After that, totalReady is incremented by one.
4 Then, the friend waits for another 75 milliseconds.
5 Finally, he checks to see if everyone else is ready by testing whether totalReady is 3.
6 If not, he decrements totalReady and repeats the process.

At roughly 75 milliseconds into the simulation, the first friend becomes ready, but he doesn’t check with his friends until 150 milliseconds. Unfortunately, the second friend doesn’t become ready until 175 milliseconds. He then checks with his friends at 225 milliseconds, around which time the first friend is becoming ready a second time. However, the third friend isn’t ready until 275 milliseconds. When he then checks at 350 milliseconds, the first friend isn’t ready anymore. On some systems the timing might drift such that the friends all become ready at the same time, but it could take a long, long while.

In reality, human beings would not put off going to a party indefinitely. Some people would decide that it was too late to go. Others would go alone. Others would go over to their friends' houses and demand to know what was taking so long. Computers are not nearly as sensible and must obey instructions, even if they cause useless repetitive patterns. Realistic examples of livelock are hard to show in a short amount of code, but they do crop up in real systems and can be very difficult to predict.

14.5.3. Sequential execution

When designing a parallel program, you might notice that synchronization tools are necessary to get a correct answer. Then, when you run this parallel version and compare it to the sequential version, it runs no faster or, worse, runs slower than the sequential version. Too much zeal with synchronization tools can produce a program which gives the right answer but doesn’t exploit any parallelism.

For example, we can take the run() method from the parallel implementation of matrix multiply given in Exemplo 13.11 and use the synchronized keyword to lock on the matrix itself.

public void run() {
    synchronized(c) {
        for(int i = lower; i < upper; i++)
            for(int j = 0; j < c[i].length; j++)
                for(int k = 0; k < b.length; k++)
                    c[i][j] += a[i][k] * b[k][j];
    }
}

In this case, only a single thread would have access to the matrix at any given time, and all speedup would be lost.

For the parallel version of matrix multiply we gave earlier, no synchronization is needed. In the case of the producer/consumer problem, synchronization is necessary, and the only way to manage the buffer properly is to enforce sequential execution. Sometimes sequential execution can’t be avoided, but you should always know which pieces of code are truly executing in parallel and which aren’t if you hope to get the maximum amount of speedup. The synchronized keyword should be used whenever it’s needed, but no more.

14.5.4. Priority inversion

In Capítulo 13 we suggest that you rarely use thread priorities. Even good reasons to use priorities can be thwarted by priority inversion. In priority inversion, a lower priority thread holds a lock needed by a higher priority thread, potentially for a long time. Because the high priority thread cannot continue, the lower priority thread gets more CPU time, as if it were a high priority thread.

Worse, if there are some medium priority threads in the system, the low priority thread could hold the lock needed by the high priority thread for even longer because those medium priority threads reduce the amount of CPU time the low priority thread has to finish its task.

[priorityInversionExercise]
[priorityiInversionExperimentExercise]

14.6. Solution: Dining philosophers

Here we give our solution to the dining philosophers problem. Although deadlock was the key pitfall we were trying to avoid, many other issues can crop up in solutions to this problem. A single philosopher might be forced into starvation, or all philosophers might experience livelock through some pattern of picking up and putting down chopsticks which never quite works out. A very simple solution could allow the philosophers to eat, one by one, in order. Then, the philosophers would often and unnecessarily be waiting to eat, and the program would approach sequential execution.

The key element that makes our solution work is that we force a philosopher to pick up two chopsticks atomically. The philosopher will either pick up both chopsticks or neither.

import java.util.Random;

public class DiningPhilosopher extends Thread {
    public static final int SEATS = 5; 
    private static boolean[] chopsticks = new boolean[SEATS];   
    private int seat;
    
    public DiningPhilosopher(int seat) {
        this.seat = seat;       
    }

We begin with a similar setup as the deadlocking version given in Exemplo 14.3.

    public static void main(String args[]) {        
        DiningPhilosopher[] philosophers = new DiningPhilosopher[SEATS];
        for(int i = 0; i < SEATS; i++) {
            philosophers[i] = new DiningPhilosopher(i);
            philosophers[i].start();    (1)
        }
        try {
            for(int i = 0; i < SEATS; i++)                        
                philosophers[i].join(); (2)
        }
        catch(InterruptedException e) {
            e.printStackTrace();
        }       
        System.out.println("All philosophers done.");
    }
1 In main(), we create and start a thread for each philosopher.
2 Then, we wait for them to finish. 
    public void run() {               	(1)
        for(int i = 0; i < 100; i++) {	(2)
            think();				   
            getChopsticks();           
            eat();
        }
    }
    
    private void think() {			  	(3)
        Random random = new Random();
        try {
            sleep(random.nextInt(20) + 10);
        }
        catch(InterruptedException e) {
            e.printStackTrace();
        }
    }
1 This run() method is different from the deadlocking version but not in a way that prevents deadlock.
2 We added the for loop so that you could see the philosophers eat and think many different times without problems.
3 We also added the think() method to randomize the amount of time between eating so that each run of the program is less deterministic. 
    private void getChopsticks() {	  	(1)
        int location1 = seat;
        int location2 = (seat + 1) % SEATS;              
        synchronized(chopsticks) {	  	(2)
            while(chopsticks[location1] || chopsticks[location2]) { (3)
                try {
                    chopsticks.wait();	(4)
                }
                catch(InterruptedException e) {
                    e.printStackTrace();
                }                               
            }           
            chopsticks[location1] = true;
            chopsticks[location2] = true;
        }       
        System.out.println("Philosopher " + seat + " picked up chopsticks " +
			location1 + " and " + location2 + ".");
    }
1 The real place where deadlock is prevented is in the getChopsticks() method. As in Exemplo 14.3, we mod by SEATS so that the last philosopher tries to get the first chopstick in the array.
2 The philosopher acquires the chopsticks lock.
3 Then, she picks up the two chopsticks she needs only if both are available.
4 Otherwise, she waits. 
    private void eat() { 			  	(1)
        // Done eating, put back chopsticks
        synchronized(chopsticks) {	  	(2)
            chopsticks[seat] = false;           
            if(seat == 0)
                chopsticks[SEATS - 1] = false;
            else
                chopsticks[seat - 1] = false;               
            chopsticks.notifyAll();   	(3)
        }
    }
}
1 Finally, in the eat() method, the philosopher eats the rice. We would assume that some other computation would be done here in a realistic problem before entering the synchronized block. The eating itself does not require a lock.
2 After eating’s done, the lock is acquired to give back the chopsticks (hopefully after some cleaning).
3 Then, all waiting philosophers are notified that some chopsticks may have become available.

Our solution prevents deadlock and livelock because some philosopher will get control of two chopsticks eventually, yet there are still issues. Note that each philosopher only eats and thinks 100 times. If, instead of philosophers sharing chopsticks, each thread were a server sharing network storage units, the program could run for an unspecified amount of time: days, weeks, even years. If starvation is happening to a particular philosopher in our program, the other philosophers will finish after 100 rounds, and the starved philosopher can catch up. If there were no limitation on the loop, a starving philosopher might never catch up.

Even if we increase the number of iterations of the loop quite a lot, we probably wouldn’t see starvation of an individual thread because we’re cheating in another way. Some unlucky sequence of chopstick accesses by two neighboring philosophers could starve the philosopher between them. By making the think() method wait a random amount of time, such a sequence will probably be interrupted. If all philosophers thought for exactly the same amount of time each turn, an unlucky pattern could repeat. It’s not unreasonable to believe that the amount of thinking a philosopher (or a server) will do at any given time will vary, but the behavior depends on the system.

It’s very difficult to come up with a perfect answer to some synchronization problems. Such problems have been studied for many years, and research continues to find better solutions.

[fairDiningPhilosophersExercise]

14.7. Exercises

Conceptual Problems

  1. What’s the purpose of the synchronized keyword? How does it work?

  2. The language specification for Java makes it illegal to use the synchronized keyword on constructors. During the creation of an object, it’s possible to leak data to the outside world by adding a reference to the object under construction to some shared data structure. What’s the danger of leaking data in this way?

  3. If you call wait() or notify() on an object, it must be inside of a block synchronized on the same object. If not, the code will compile, but an IllegalMonitorStateException may be thrown at run time. Why is it necessary to own the lock on an object before calling wait() or notify() on it?

  4. Why is it safer to call notifyAll() than notify()? If it’s generally safer to call notifyAll(), are there any scenarios in which there are good reasons to call notify()?

  5. Imagine a simulation of a restaurant with many waiter and chef objects. The waiters must submit orders to the kitchen staff, and the chefs must divide the work among themselves. How would you design this system? How would information and food be passed from waiter to chef and chef to waiter? How would you synchronize the process?

  6. What’s a race condition? Give a real life example of one.

  7. Let’s reexamine the code that increments a variable with several threads from [Concepts: Thread interaction]. We can rewrite the run() method as follows.

    public synchronized void run() {
    for(int i = 0; i < COUNT/THREADS; i++)
        counter++;
}

    Will this change fix the race condition? Why or why not?

  8. Examine our deadlock example from Exemplo 14.4. Explain why this example fulfills all four conditions for deadlock. Be specific about which threads and which resources are needed to show each condition.

  9. What’s priority inversion? Why can a low priority thread holding a lock be particularly problematic?

Programming Practice

  1. In Exemplo 14.1 the Buffer class used to implement a solution to the producer/consumer problem only has a single lock. When the buffer is empty and a producer puts an item in it, both producers and consumers are woken up. A similar situation happens whenever the buffer is full and a consumer removes an item. Re-implement this solution with two locks so that a producer putting an item into an empty buffer only wakes up consumers and a consumer removing an item from a full buffer only wakes up producers.

  2. In Exemplo 14.2 we used the class SynchronizedAccount to solve a bank account problem. As we mention in Seção 14.5.2, depositing and withdrawing threads can be starved out by a steady supply of balance checking threads. Add additional synchronization tools to SynchronizedAccount so that balance checking threads will take turns with depositing and withdrawing threads. If there are no depositing or withdrawing threads, make your implementation continue to allow an unlimited number of balance checking threads to read concurrently.

  3. The solution to the dining philosophers problem given in Seção 14.6 suffers from the problem that a philosopher could be starved by the two philosophers on either side of her, if she happened to get unlucky. Add variables to each philosopher which indicate hunger and the last time a philosopher has eaten. If a given philosopher is hungry and hasn’t eaten for longer than her neighbor, her neighbor shouldn’t pick up the chopstick they share. Add synchronization tools to enforce this principle of fairness. Note that your solution must not cause deadlock. Although one philosopher may be waiting on another who is waiting on another and so on, some philosopher in the circle must have gone hungry the longest, breaking circular wait.

Experiments

  1. Critical sections can slow down your program by preventing parallel computation. However, the locks used to enforce critical sections can add extra delays on top of that. Design a simple experiment which repeatedly acquires a lock and does some simple operation. Test the running time with and without the lock. See if you can estimate the time needed to acquire a lock in Java on your system.

  2. Design a program which experimentally determines how much time a thread is scheduled to spend running on a CPU before switching to the next thread. To do this, first create a tight loop which runs a large number of iterations, perhaps 1,000,000 or more. Determine how much time it takes to run a single run of those iterations. Then, write an outer loop which runs the tight loop several times. Each iteration of the outer loop, test to see how much time has passed. When you encounter a large jump in time, typically at least 10 times the amount of time the tight loop usually takes to run to completion, record that time. If you run these loops in multiple threads and average the unusually long times together for each thread, you should be able to find out about how long each thread waits between runs. Using this information, you can estimate how much time each thread is allotted. Bear in mind that your this average is only an estimation. Some JVMs will change the amount of CPU time allotted to threads for various reasons. If you’re on a multicore machine, it will be more difficult to interpret your data since some threads will be running concurrently.

  3. Create an experiment to investigate priority inversion in the following way.

    1. Create two threads, setting the priority of the first to MIN_PRIORITY and the priority of the second to MAX_PRIORITY. Start the first thread running but wait 100 milliseconds before starting the second thread. The first thread should acquire a shared lock and then perform some lengthy process such as finding the sum of the sines of the first million integers. After it finishes its computation, it should release the lock, and print a message. The second thread should try to acquire the lock, print a message, and then release the lock. Time the process. Because the lock is held by the lower priority thread, the higher priority thread will have to wait until the other thread is done for it to finish.

    2. Once you have a feel for the time it takes for these two threads to finish alone, create 10 more threads that must also perform a lot of computation. However, do not make these threads try to acquire the lock. How much do they delay completion of the task? How does this delay relate to the number of cores in your processor? How much does the delay change if you set the priorities of these new threads to MAX_PRIORITY or MIN_PRIORITY?