Variáveis de condição (semáforo)

Por esta altura já devem dominar wait conditions. Por isso vou só elaborar rapidamente o que é um semáforo, e mostrar o código.

Um semáforo é uma primitiva de concurrência que protege um determinado número de recursos. As threads podem adquirir e libertar esses recursos. Embora isto pareça semelhante a locks, um semáforo é muito mais liberal (e flexível):

• não existe o conceito de ownership: nem o semáforo nem os seus “recursos” pertencem a qualquer thread. Qualquer thread pode libertar recursos adquiridos por outra thread.
• uma thread pode “consumir” recursos e nunca os libertar, ou então “criar” recursos, libertando-os sem os adquirir.

Em termos de implementação um semáforo é um simples contador inteiro que expões duas operações, cujos nomes tradicionais são p() e v(). Estes nomes são as iniciais de palavras holandesas (a nacionalidade de Edsger Dijkstra, o seu inventor) que significam mais ou menos, decrementar e incrementar. O semáforo bloqueia quando se tenta decrementar (p) e o seu valor é 0. Variando o valor inicial podemos obter diversos comportamentos (uns mais úteis qu outros):

• maior que zero: um certo número de recursos pode ser usado de cada vez
• zero: é necessário criar os recursos antes de serem usados
• menor que zero: é necessário criar alguns recursos que nunca poderão ser adquiridos

Com apenas isto podemos implementar outras primitivas de sincronização, como mutexes e locks. Uma lock pode ser implementada graças a um semáforo que com valor inicial (e máximo) 1, juntando a ideia de propriedade. Uma wait condition é extremamente semelhante a um semáforo com valor inicial 0, sendo p() == wait() e v() == notify().

Uma propriedade engraçada é que, como as locks e as wait conditions podem ser implementadas à custa de semáforos, um semáforo também pode ser implementado à custa de locks e wait conditions. É este o terceiro exercício do terceiro guião. E esta é uma possível solução:

public class Semaphore {
    private int c;    // contador

    public Semaphore(int initial) {
        c = initial;    // valor inicial
    }

    public synchronized void p() throws InterruptedException {
        while(c == 0) wait();    // bloquear se for zero
        --c;    // decrementar
    }

    public synchronized void v() {
        ++c;    // incrementar
        notify();    // acordar uma thread em espera em p()
                    // só se libertou um recurso, só uma thread pode prosseguir
    }
}

Bastante simples, huh?

Bonus points: uma variante ao semáforo clássico permite adquirir e libertar mais que um recurso de cada vez de forma atómica para evitar uma situação que pode levar a deadlocks (conseguem ver como?). Para isso usa-se alteramse as operações p() e v() para receberem um parâmetro que é o número de recursos para manipular: p(int x) e v(int x). A implementação destas duas já não é tão simples…