Exclusão Mútua (deadlocks)

Agora é-nos pedido para reimplementar o banco com exclusão mútua ao nível das contas individuais.

O que significa isto?

Até agora no nosso banco ocorre apenas uma transacção de cada vez porque temos todos os métodos críticos marcados com synchronized. Isto significa que enquanto alguém está a efectuar uma transacção, ninguém pode mexer em nenhuma conta.

No entanto não existe problema nenhum se todas estas transacções ocorrerem em simultâneo:

• O cliente 42 deposita 1000 €;
• O cliente 23 levanta 1000 €;
• O cliente 17 transfere 1000 € para o cliente 29;

Isto significa que o banco pode tornar-se mais eficiente fortalecendo a condição que garante a que o banco funciona correctamente. Em lugar de “ocorre apenas uma transacção de cada vez” podemos ter “ocorre apenas uma transacção envolvendo uma determinada conta de cada vez”. Por outras palavras, não pode estar duas threads a mexer na mesma conta. E como implementamos isto?

Necessitamos de exclusão mútua em cada conta. Como já vimos, em Java todos os objectos têm um mecanismo de exclusão mútua intrínseco. Como as nossas contas são simples números inteiros e em Java os números inteiros são tipos primitivos (i.e. não são objectos), as contas não têm esse mecanismo. Para isso temos de usar objectos em vez de números inteiros para representar as contas. Está então na hora de criar uma classe para representar uma conta, e mudar a regiões exclusão mútua para as contas:

public class Account {
    private int balance = 0;

    public synchronized int consult() {
        return balance;
    }

    public synchronized void credit(int amount) {
        balance += amount;
    }

    public synchronized void debit(int amount) {
        balance -= amount;
    }
}

Agora o banco sofre estas alterações:

private final Account[] accounts;

public Bank(int nAccounts) {
    accounts = new Account[nAccounts];
    for (int i = 0; i < nAccounts; i++) {
        accounts[i] = new Account();
    }
}

// ...

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

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

public void debit(int number, int amount) {
    return accounts[number].debit(amount);
}

Tudo muito simples. Os métodos para contar o total do banco e para transferências vamos deixar como estão para já.

Podemos confirmar se funciona tudo como anteriormente correndo os dois testes que elaboramos anteriormente. Em princípio apenas o primeiro teste funciona (o dinheiro não aparece nem desaparece espontâneamente). Se ambos apresentaram os resultados esperados, corram novamente. Significa que tiveram sorte e as threads foram escalonadas de uma forma correcta por coincidência. O segundo teste deve falhar porque não estamos a usar o mesmo objecto para exclusão mútua no método total (o banco) e nos movimentos (as contas).

Vamos agora tratar das transferências. Uma possível implementação seria esta:

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

O problema desta implementação é que é possível encontrar o banco num estado inválido. Basta que alguém consulte os saldos das duas contas entre a operação de débito e a operação de crédito. Essa pessoa verá que a primeira conta já foi debitada mas o dinheiro não existe na segunda conta. Isto não é nada desejável. Temos de garantir que ninguém pode mexer, ou mesmo consultar nenhuma das duas contas enquanto efectuamos toda a operação. Por outras palavras, a transferência tem de ser uma operação atómica, como já o era anteriormente com exclusão mútua ao nível do banco.

Para isso temos de usar ambas as contas para exclusão mútua:

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

Mas… os métodos debit e credit também necessitam de exclusão mútua nas suas respectivas contas. Como é que podemos chamar esses métodos se já o método transfer também corre com exclusão mútua?

Podemos porque o mecanismo de exclusão mútua intrínseco é reentrante. Isto significa que podemos fazer algo deste género:

synchronized(obj) {
    synchronized(obj) {
        // ...
    }
}

Isto porque, como a thread já tem garantia de exclusão mútua em obj após o primeiro synchronized, não existe nenhum problema em pedir novamente exclusão mútua nesse objecto para a mesma thread.

Podemos então usar métodos synchronized dentro de blocos synchronized que usam o mesmo objecto.

Se corrermos agora o teste que verifica se no final o banco tem o dinheiro que seria esperado… O mais provável é que leve montes de tempo. Literalmente, uma eternidade. Não vale a pena esperar porque o que aconteceu foi um deadlock.

Imaginem a situação clássica de dois (ou mais) piratas que possuem uma parte do mapa do tesouro cada um. O primeiro pirata só revela a sua parte depois de o outro revelar a dele. Do outro lado a mesma coisa. A menos que um deles “ceda”, nunca encontrarão o tesouro.

Aqui aconteceu o mesmo. Duas threads tentaram efectuar transferências em sentidos opostos:

• transfer(a, b, 1000);
• transfer(b, a, 1000);

A primeira thread adquiriu a lock da conta a e a sua fatia de processador terminou, dando lugar à segunda thread. Esta adquiriu a lock da conta b e tentou adquirir a da conta a. Como a primeira thread possui a lock da conta a, a segunda bloqueia à espera que esta seja libertada. A primeira thread volta a ter o processador para si e tenta adquirir a lock da conta b. Mas essa está na posse da segunda thread por isso a primeira bloqueia que esta seja libertada. Estão ambas à espera que a outra “largue o osso”. Ao contrário dos piratas, nenhuma das threads irá ceder nesta situação. As duas threads nunca irão fazer progresso e mais ninguém poderá mexer nas contas a e b.

Esta situação pode envolver mais threads mas é sempre o mesmo problema com a mesma solução:

• transfer(a, b, 1000);
• transfer(b, c, 1000);
• transfer(c, a, 1000);
• transfer(d, c, 1000);
• transfer(e, d, 1000);
• …

E qual é a solução? Se estivessemos a usar locks explicitamente e não com recurso a synchronized podíamos definir timeouts. Isto faria com que ao fim de algum tempo sem ter successo uma das threads acabaria por “largar o osso”, deixando as outras prosseguir. Depois de estas deixarem a região crítica a thread desistente poderia então prosseguir também.

Mas podemos resolver isto só com synchronized, sem usar timeouts. Se o problema é as threads “marcarem” as contas pela ordem oposta a solução é… usar sempre a mesma ordem! Podemos ordenar as contas (pelo seu número) e dispor os blocos synchronized por essa ordem:

public void transfer(int from, int to, int amount) {
    int hi, lo;
    if (from < to) {
        lo = from;
        hi = to;
    } else {
        lo = to;
        hi = from;
    }
    synchronized (accounts[lo]) {
        synchronized (accounts[hi]) {
            debit(from, amount)
            credit(to, amount);
        }
    }
}

Agora as operações transfer(1, 2, 1000) e transfer(2, 1, 1000) já podem ser efectuadas em segurança, porque os blocos synchronized irão usar sempre as contas pela mesma ordem (1, 2).

Se corrermos o primeiro teste novamente, podemos ver que agora não bloqueia. (Convém correr este teste mais que uma vez, para minimizar a possibilidade de obter um falso positivo por “sorte”.)

Quanto ao método total… Vamos ignorá-lo até falarmos de locks explícitas, porque não é nada fácil de corrigí-lo usando synchronized e não faz parte do que era pedido, foi adicionado apenas para podermos testar. Se alguém se quiser tentar, a ideia é ir marcando cada conta antes de a somar e libertando todas apenas no final.