Exclusão Mútua

No último post encontrámos um problema que surge numa situação tão simples como incrementar um contador, simplesmente porque introduzimos paralelismo sem termos controlo sobre esse paralelismo.

Para resolver este problema temos de garantir que enquanto uma thread está a incrementar o contador, nenhuma das outras threads faz o mesmo. Por outras palavras (mais que mil?), queremos que as threads sejam agendadas sempre desta forma:

A sequência das operações 1, 2 e 3 é aquilo que se costuma chamar de região crítica. Uma região crítica é uma porção de código que deve executar de forma atómica, i.e., como uma única operação.

Numa região crítica deve existir uma garantia de exclusão mútua. Isto significa que apenas uma thread pode estar a executar a região crítica em cada instante.

Em Java existe um mecanismo de exclusão mútua intrínseco em cada objecto. Todos os objectos têm uma lock. Esta lock é acedida através de uma sintaxe especial: blocos synchronized. Um bloco synchronized garante exclusão mútua nesse bloco. Podemos definir métodos inteiros como synchronized colocando simplesmente a palavra synchronized no cabeçalho desse método:

synchronized void mutuallyExclusiveMethod(...) {
    // Região crítica
}

Também podemos definir apenas certas partes de um método como synchronized desta forma:

void methodWithMutuallyExclusiveParts(...) {
    // Região não crítica
    synchronized(obj) {
        // Região crítica
    }
    // Região não crítica
}

Aqui obj é o objecto usado para garantir a exclusão mútua. Quando usamos métodos synchronized o objecto usado implicitamente é this. No fundo a primeira forma descrita acima é equivalente a isto:

void mutuallyExclusiveMethod(...) {
    synchronized(this) {
        // Região crítica
    }
}

Isto significa que, se tivermos duas instâncias de uma classe, o acesso em paralelo a um método synchronized de cada uma dessas instâncias não corre em exclusão mútua. No entanto, se chamarmos métodos synchronized do mesmo objecto em paralelo, eles correrão em exclusão mútua. Já vamos ver isto melhor nos exercícios.

Um bloco synchronized garante que a lock intrínseca a cada objecto seja adquirida no início e libertada no fim, independentemente da forma como se sai do bloco:

• a última instrução do bloco foi executada;
• foi executado um return dentro do bloco;
• foi lançada uma excepção dentro do bloco;

Agora vamos aos exercícios.

Exercício 1

Para que o segundo exercício do guião anterior execute de forma correcta temos de garantir exclusão mútua aquando do incremento. Podemos fazê-lo de forma muito simples, alterando a classe Counter assim:

synchronized void increment() {
    ++counter;
}

Se correrem o programa agora, o resultado será 10 milhões conforme experado, mas será muito mais lento. Isto porque, entre outras coisas, usar sincronização “remove” algum paralelismo. Isto é facil de verificar olhando para a imagem acima que mostra a forma como as threads são agendadas de forma sequencial. Se tivermos mais que um processador/core este efeito será muito mais visível porque não podemos ter uma thread a incrementar em cada core, por causa da exclusão mútua na região crítica.

Mas porque é que não há problema neste incremento?

for(int i = 0; i < 1000000; i++/*<--este*/) {

Simplesmente porque a variável i não é partilhada. Existe uma para cada thread, e cada thread manipula apenas a sua cópia. Não há nenhuma race condition. Esta parte do ciclo pode executar em paralelo com outras threads sem problemas.

Será possível manter o programa correcto sem introduzir sincronização (para não perder performance)?

Neste caso é. Como vimos acima, o problema é o estado partilhado. Porque a execução de cada uma das threads é independente, i.e., não dependem do resultado das outras, podemos eliminar o estado partilhado. Basta fazer com que cada thread incremente o seu próprio contador:

public class Incrementer extends Thread {
    private int counter = 0;
    
    public int getCount() {
        return counter;
    }
    
    @Override
    public void run() {
        for(int i = 0; i < 1000000; i++) {
            ++counter;
        }
    }
}

E no final, a thread principal “junta” todos os dez resultados, assim:

int total = 0;
for(int i = 0; i < 10; i++) {
    threads[i].join();
    total += threads[i].getCount();
}
System.out.println(total);

Assim temos um programa correcto e eficiente, que tira vantagem de paralelismo, sem sincronização. Este caso era bastante simples mas geralmente é muito díficil (ou impossível) de eliminar a sincronização.

Exercício 2

public class Bank {
    private final int[] accounts;

    public Bank(int nAccounts) {
        accounts = new int[nAccounts];
    }

    public int size() {
        return accounts.length;
    }

    public int total() {
        int sum = 0;
        for (int i = 0; i < accounts.length; i++) {
            sum += consult(i);
        }
        return sum;
    }

    public int consult(int number) {
        return accounts[number];
    }

    public void credit(int number, int amount) {
        accounts[number] += amount;
    }

    public void debit(int number, int amount) {
        accounts[number] -= amount;
    }
}

(Nota: não faço qualquer verificação para evitar saldos negativos porque isso é parte do terceiro guião.)

Esta implementação não tem qualquer forma de sincronização. Vamos escrever um programa para testar esta classe numa situação onde temos várias threads:

public class BankWorker extends Thread {
    private final Random rng = new Random();
    private final Bank bank;
    private int movement = 0;

    public BankWorker(Bank bank) {
        this.bank = bank;
    }

    public int total() {
        return movement;
    }

    @Override
    public void run() {
        for (int i = 0; i < 10000; i++) {
            int account = rng.nextInt(bank.size());
            int op = rng.nextInt(3);
            int delta = rng.nextInt(1000);
            if (op == 0) {
                bank.credit(account, delta);
                movement += delta;
            } else if (op == 1) {
                bank.debit(account, delta);
                movement -= delta;
            } else {
                int other = rng.nextInt(bank.size());
                bank.transfer(account, other, delta);
            }
        }
    }
}

public final class BankTest {
    public static void main(String[] args) throws InterruptedException {
        Bank bank = new Bank(10);

        BankWorker[] workers = new BankWorker[16];
        for (int i = 0; i < workers.length; i++) {
            workers[i] = new BankWorker(bank);
        }

        for (int i = 0; i < workers.length; i++) {
            workers[i].start();
        }

        int sum = 0;
        for (int i = 0; i < workers.length; i++) {
            workers[i].join();
            sum += workers[i].total();
        }

        System.out.printf("Expected total:\t%d\n", sum);
        System.out.printf("Actual total:\t%d\n", bank.total());
    }
}

Não deve haver problemas em perceber este código. Se o corrermos podemos facilmente ver que o nosso banco não funciona bem com várias transacções em simultâneo, porque temos race conditions nos movimentos.

Vamos então implementar exclusão mútua ao nível do banco, recorrendo a synchronized:

public synchronized void credit(int number, int amount) {
    accounts[number] += amount;
}

public synchronized void debit(int number, int amount) {
    accounts[number] -= amount;
}

Correndo agora o nosso teste podemos ver que o banco já funciona correctamente.

Mas porque é que bastou sincronizar estes dois métodos?

O método consult apenas lê o valor que está na conta. Ler um inteiro é uma operação atómica, por isso não há problemas. Mas, se os saldos fossem, por exemplo, long, poderíamos ter problemas, porque ler um long não é uma operação atómica numa máquina de 32-bits, logo devíamos usar exclusão mútua neste também.

O método total é chamado apenas depois de todas as outras threads pararem, por isso não há problema nenhum. Mas num banco não podemos parar os movimentos. Se quisermos saber o total existente no banco, em paralelo com vários movimentos, devemos usar sincronização neste método também. Porém tornarmos simplesmente o método synchronized não é muito boa ideia. Imaginem que o banco tem um milhão de clientes. Ao correr total impedimos todos os movimentos de prosseguir enquanto a soma estiver a ser calculada (o que pode levar algum tempo). Mais tarde veremos uma forma melhor para sincronizar este método.

O que interessa reter é que na dúvida a jogada segura é sincronizar, porque é melhor que o banco seja lento do que perdermos as nossas poupanças…

Exercício 3

Agora temos de adicionar um método para efectuar transferências, como composição das outras duas operações. Simples:

public synchronized void transfer(int from, int to, int amount) {
    debit(from, amount);
    credit(to, amount);
}

E vamos alterar ligeiramente a classe BankWorker para fazer também transferências:

public void run() {
    for (int i = 0; i < 10000; i++) {
        int account = rng.nextInt(bank.size());
        int op = rng.nextInt(3);
        int delta = rng.nextInt(1000);
        if (op == 0) {
            bank.credit(account, delta);
            movement += delta;
        } else if (op == 1) {
            bank.debit(account, delta);
            movement -= delta;
        } else {
            int other = rng.nextInt(bank.size());
            bank.transfer(account, other, delta);
        }
    }
}

Correndo novamente o teste podemos confirmar que o banco ainda é de confiança.

total()

Vamos agora provar que o método total() não funciona sem sincronização. Para isto temos de alterar ligeiramente a classe BankWorker. O que vamos fazer é inicializar todas as contas com o mesmo saldo, e efectuar apenas transferências. Assim o total deve ser sempre o mesmo em qualquer instante, visto que nunca se adiciona nem retira dinheiro do banco, apenas se troca de conta. Eis essas alterações:

public void run() {
    for (int i = 0; i < 10000; i++) {
        int account = rng.nextInt(bank.size());
        int other = rng.nextInt(bank.size());
        int delta = rng.nextInt(1000);
        bank.transfer(account, other, delta);
    }
}

public static void main(String[] args) throws Exception {
    Bank bank = new Bank(1000);
    for(int i = 0; i < bank.size(); i++) {
        bank.credit(i, 1000);
    }

    BankWorker[] workers = new BankWorker[16];
    for (int i = 0; i < workers.length; i++) {
        workers[i] = new BankWorker(bank);
    }

    for (int i = 0; i < workers.length; i++) {
        workers[i].start();
    }

    System.out.println(bank.total());

    for (int i = 0; i < workers.length; i++) {
        workers[i].join();
    }

    System.out.println(bank.total());
}

(Convém manter as classes que serviam para testar anteriormente e efectuar estas alterações em cópias ou subclasses para podermos testar os dois cenários. Esta é uma situação em que dá mesmo jeito uma framework de unit testing, mas para já vamos manter o foco no controlo de concorrência)

Reparem que adicionei um chamada ao método total() enquanto as threads estão a correr para expôr race conditions.

Reparem também que aumentei o número de contas. Isto é para aumentar a probabilidade de os erros aparecerem.

Agora corram o teste…

998657
1000000

E outra vez…

1000857
1000000

No primeiro temos um erro inferior a 0.2%, e no segundo inferior a 0.1%. Como podem ver o erro ainda é bastante pequeno. Se tivessemos um número de contas menor podia nem se notar.

Embora a diferença seja pequena, o dinheiro não pode “aparecer” ou “desaparecer” assim. Há casos em que podemos tolerar pequenas diferenças esporádicas, se no final o resultado for correcto. Mas num banco, a tolerância deve ser zero, por isso temos de corrigir isto.

A solução é deveras simples:

public synchronized int total() {
    // ...
}

Embora esta solução não seja a melhor em termos de performance (o banco tem de parar completamente enquanto alguém conta o dinheiro, o que pode levar muito tempo), é a mais simples e não requer conhecimentos adicionais.

O exercício 4 fica para outro post, porque é necessário explicar um conceito novo: deadlocks.