Programação concorrente

Duas threads contam linhas de ficheiros diferentes e somam os resultados num contador comum. Cada thread tem a sua execução, mas ambas acedem à memória do processo. Se lerem o mesmo total e escreverem separadamente os novos valores, uma atualização pode perder-se. A coordenação tem de proteger toda a operação que deve ser indivisível.

O que uma thread partilha

Uma thread tem registos, contador de programa e pilha próprios. As threads do processo partilham o espaço de endereçamento, incluindo globais e heap, e os descritores. Uma variável automática pode ser acedida por outra thread se lhe passarmos um apontador válido; estar numa pilha não garante privacidade.

pthread_create inicia uma função com assinatura void *f(void *), e o argumento precisa de continuar vivo enquanto a thread o usa. Para passar um índice e um nome a cada thread, define uma struct com esses campos, guarda um vetor de estruturas vivo até aos joins e passa &tarefa[i] a cada thread.

Passar a todas o endereço da mesma variável de um ciclo permite que leiam o índice errado; se o ciclo a altera enquanto uma thread a lê, há ainda uma data race, com comportamento indefinido em C.

pthread_join espera pela terminação de uma thread e permite recolher o seu retorno, por exemplo um apontador para um bloco obtido com malloc ou para um objeto estático por thread. O retorno não pode apontar para um objeto automático cuja vida acabou com a thread.

Retornar da função inicial da thread equivale a terminar essa thread com pthread_exit. Já exit termina o processo inteiro, incluindo as restantes threads; retornar de main tem esse efeito. Os joins do exemplo conservam o processo vivo até todos os resultados estarem prontos.

O programa seguinte passa uma estrutura distinta a cada thread e recolhe o retorno de cada uma com pthread_join. Guarda-o em fios.c e compila num terminal UNIX com cc -std=c17 -Wall -Wextra -Wpedantic fios.c -pthread -o fios.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct tarefa {
    const char *nome;
    int valor;
};

static void conferir(int erro, const char *op) {
    if (erro == 0)
        return;
    fprintf(stderr, "%s: %s\n", op, strerror(erro));
    exit(1);
}

static void *dobrar(void *arg) {
    struct tarefa *t = arg;
    long *r = malloc(sizeof *r);
    if (r == NULL)
        return NULL;
    *r = 2L * t->valor;
    return r;
}

int main(void) {
    struct tarefa tarefas[] = {
        {"a", 3}, {"b", 7}, {"c", -4},
    };
    const int n = 3;
    pthread_t fios[3];
    for (int i = 0; i < n; i++)
        conferir(pthread_create(&fios[i], NULL, dobrar, &tarefas[i]),
                 "create");
    long total = 0;
    for (int i = 0; i < n; i++) {
        void *ret;
        conferir(pthread_join(fios[i], &ret), "join");
        if (ret == NULL) {
            fputs("sem retorno\n", stderr);
            return 1;
        }
        printf("%s: %d -> %ld\n", tarefas[i].nome, tarefas[i].valor,
               *(long *)ret);
        total += *(long *)ret;
        free(ret);
    }
    printf("total=%ld\n", total);
    return 0;
}

Saída observada:

a: 3 -> 6
b: 7 -> 14
c: -4 -> -8
total=12

Cada thread recebe &tarefas[i], que continua vivo até depois dos joins. O retorno é um bloco reservado pela thread e libertado pelo pai depois de o ler. Com o endereço da mesma variável do ciclo, o valor não é uma cópia estável por thread. Nem o último índice é um resultado garantido quando há leitura e escrita sem sincronização.

Uma atualização perdida

Num modelo de ler, calcular e escrever, o contador começa em 5:

Passo	Thread A, incrementar	Thread B, decrementar	Memória
1	Lê 5		5
2		Lê 5	5
3	Calcula 6		5
4		Calcula 4	5
5	Escreve 6		6
6		Escreve 4	4

A execução serial daria 5. Este entrelaçamento dá 4; inverter as duas escritas daria 6. É um exemplo para explicar a corrida. Em C, acessos concorrentes incompatíveis a um objeto não atómico, sem sincronização, constituem data race e têm comportamento indefinido, por isso não podes afirmar que o programa C real só terá os resultados 4, 5 ou 6. Declarar o contador como volatile não resolve esta corrida, porque impede certas otimizações dos acessos mas não cria uma operação atómica nem uma relação de sincronização entre threads.

Secção crítica e propriedades

A secção crítica é o trecho que usa os dados cujo acesso precisa de coordenação. Uma solução clássica procura:

• Exclusão mútua: no máximo uma tarefa está na secção crítica protegida.
• Progresso: se há tarefas interessadas e ninguém está lá dentro, a escolha de quem entra não pode ser adiada indefinidamente por quem não participa.
• Espera limitada: há um limite ao número de entradas de outras tarefas antes de uma tarefa que pediu acesso poder entrar.

Exclusão mútua não implica as restantes, ou seja um protocolo que nunca deixa ninguém entrar exclui todos e falha o progresso. Um lock sem justiça pode impedir acesso simultâneo sem garantir espera limitada.

Peterson e operações atómicas

Para duas tarefas, a solução de Peterson usa interessado[2] e vez. A tarefa $i$ assinala interesse, cede preferência a $j$ e espera enquanto $j$ está interessado e tem a vez. Ao sair, retira o seu interesse.

interessado[i] = verdadeiro
vez = j
enquanto interessado[j] e vez == j: esperar
secção crítica
interessado[i] = falso

Segue uma entrada com ambos interessados: A escreve vez = B; B escreve depois vez = A. A testa se B está interessado e se vez == B. O segundo teste é falso, por isso A entra. B testa se A está interessado e se vez == A; ambos são verdadeiros, por isso B espera. Quando A sai e retira o interesse, B deixa de esperar. Esta prova assume operações atómicas e uma ordem de memória adequada. Traduzir o pseudocódigo para globais C comuns não cumpre essas hipóteses. Para programar, usa primitivas da biblioteca ou atomics com um modelo de memória escolhido conscientemente.

Test-and-set lê um valor antigo e escreve o novo numa operação atómica. Compare-and-swap só escreve o novo valor se o antigo coincidir com o esperado. Um spinlock pode repetir test-and-set até obter o lock, consumindo CPU enquanto espera. Faz sentido em certos trechos curtos, mas uma espera longa desperdiça CPU. Desativar interrupções numa CPU não impede outra CPU de aceder aos mesmos dados.

Mutex com Pthreads

O mutex protege o contador no programa completo seguinte. Guarda-o como contador.c e compila no terminal UNIX com cc -std=c17 -Wall -Wextra -Wpedantic contador.c -pthread -o contador.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int contador = 0;
static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

static void conferir(int erro) {
    if (erro == 0) return;
    fprintf(stderr, "pthread: %s\n", strerror(erro));
    exit(1);
}

static void *incrementar(void *arg) {
    (void)arg;
    for (int i = 0; i < 10000; i++) {
        conferir(pthread_mutex_lock(&mutex));
        contador++;
        conferir(pthread_mutex_unlock(&mutex));
    }
    return NULL;
}

int main(void) {
    pthread_t a, b;
    conferir(pthread_create(&a, NULL, incrementar, NULL));
    conferir(pthread_create(&b, NULL, incrementar, NULL));
    conferir(pthread_join(a, NULL));
    conferir(pthread_join(b, NULL));
    printf("%d\n", contador);
    conferir(pthread_mutex_destroy(&mutex));
    return 0;
}

A saída é 20000, porque todos os incrementos usam o mesmo mutex; a leitura final acontece depois dos dois joins, quando já não há escritores.

Pthreads devolve o código de erro diretamente em muitas funções, por isso não o interpretes como errno; usa strerror(erro), como no programa.

Obter o mutex uma vez para todo o ciclo também daria o total correto, mas cada thread faria o seu trabalho inteiro sem a outra entrar. Obter por incremento permite entrelaçamento fino e custa mais operações de sincronização. A granularidade deve seguir o que precisa de ser indivisível, não a regra de pôr sempre o menor número de linhas possível.

Semáforos

Um semáforo conta permissões. wait, também chamado P, consome uma se houver disponibilidade; caso contrário espera. post, ou V, acrescenta uma e pode permitir que alguém avance. As operações são atómicas.

Um semáforo iniciado em 3 limita a três utilizadores de um recurso. Iniciado em 0, pode impor uma ordem: B faz wait, A termina a preparação e faz post. Um semáforo binário pode conseguir exclusão mútua, mas não tem necessariamente a noção de dono de um mutex. Não confundas sinalizar disponibilidade com libertar um lock que pertence à thread.

Numa fila limitada a $N$ itens, um protocolo com semáforos começa com vazios=N, cheios=0 e exclusão mútua sobre os índices. O produtor obtém um vazio, obtém o mutex, insere, liberta o mutex e anuncia um cheio. O consumidor obtém um cheio, obtém o mutex, retira, liberta o mutex e anuncia um vazio.

Esperar por uma condição

Uma variável de condição não guarda a verdade da condição nem acumula todos os sinais. A verdade fica nos dados, protegidos pelo mutex. pthread_cond_wait(&cond, &mutex) liberta o mutex e entra em espera atomicamente; quando retorna, voltou a obter o mutex.

Este é o padrão para um consumidor, assumindo quantidade, buffer e índices protegidos por mutex:

pthread_mutex_lock(&mutex);
while (quantidade == 0)
    pthread_cond_wait(&nao_vazio, &mutex);
int valor = buffer[saida];
saida = (saida + 1) % CAPACIDADE;
quantidade--;
pthread_cond_signal(&nao_cheio);
pthread_mutex_unlock(&mutex);

O produtor faz o simétrico: espera enquanto quantidade == CAPACIDADE, insere em buffer[entrada], avança entrada módulo capacidade, aumenta a quantidade e sinaliza nao_vazio. A invariável é $0 \leq quantidade \leq CAPACIDADE$: cada inserção precisa de espaço e cada retirada precisa de um item.

Evento numa fila inicialmente vazia	Quantidade	Posse do mutex
Consumidor testa a fila	0	Consumidor
Consumidor entra em cond_wait	0	Libertado atomicamente ao esperar
Produtor obtém o mutex e insere	1	Produtor
Produtor sinaliza nao_vazio	1	Ainda do produtor
Produtor liberta; consumidor reobtém	1, se ninguém retirou entretanto	Consumidor
Consumidor volta ao teste do while	Confere de novo	Consumidor

Para vários consumidores, define também como termina a produção. Uma flag terminado, sob o mesmo mutex, permite esperar enquanto a fila está vazia e não terminou, e sair quando vazia e terminada. Nesse fim, um broadcast acorda os consumidores que precisam de observar a mudança.

Se uma fila passa de vazia a um item e depois acumula vários itens, sinalizar apenas na transição pode ser suficiente para um único consumidor que continua a retirar. Com vários consumidores, pode deixar outros adormecidos apesar de haver trabalho. Decide entre sinalizar por inserção e acordar vários segundo o número de consumidores e o protocolo, não só segundo o desejo de fazer menos chamadas.

Monitores com retoma imediata e diferida

Um monitor reúne dados partilhados e as operações que os usam sob exclusão mútua, com variáveis de condição para esperar. Em C/Pthreads, o programador constrói essa disciplina com mutex e condição; outras linguagens oferecem parte dela diretamente.

Nos monitores clássicos com retoma imediata, ou semântica de Hoare, um signal entrega o monitor à tarefa que esperava; a tarefa que sinalizou fica suspensa. Se o sinalizador tornou o predicado verdadeiro imediatamente antes do sinal, a tarefa acordada observa esse estado antes de outra operação do monitor o alterar.

Na retoma diferida, associada a Mesa, o sinalizador continua. A tarefa acordada só executa depois de voltar a obter exclusão mútua, e o predicado pode entretanto ter mudado. Pthreads segue esta disciplina de reavaliação e admite ainda despertares espúrios: conserva o while em torno de pthread_cond_wait.

Um exercício que usa if (v == 0) wait(cond) pode assumir retoma imediata num monitor abstrato. Não traduzas essa conclusão para Pthreads sem rever as hipóteses. A disciplina de sinalização e o predicado protegido fazem parte da solução, não apenas a palavra monitor.

Leitores e escritores

Vários leitores podem consultar um objeto sem o alterar, mas um escritor precisa de excluir tanto outros escritores como leitores. A condição de segurança permite vários leitores ou um escritor, nunca ambos ao mesmo tempo.

Num protocolo com preferência pelos leitores, um novo leitor pode juntar-se enquanto já existem leitores ativos. Se chegam leitores continuamente, o conjunto pode nunca ficar vazio e um escritor ficar em inanição, embora os leitores avancem. Bloquear novos leitores quando há um escritor à espera impede esse entrelaçamento; dar preferência estrita a uma fila contínua de escritores pode criar o problema simétrico.

Estado	Novo leitor	Novo escritor
Sem participantes	Pode entrar	Pode entrar sozinho
Leitores ativos, preferência por leitores	Pode juntar-se	Espera todos saírem
Escritor ativo	Espera	Espera

Um mutex exclusivo para todas as consultas garante segurança, mas perde a simultaneidade entre leitores. Um read-write lock permite essa simultaneidade, porém a política de admissão e a justiça dependem do contrato. Não concluas espera limitada só por usar um lock de leitores/escritores. Este problema e a distinção entre políticas de retoma acima são úteis para interpretar fichas e provas históricas; a prática Pthreads atual continua a exigir mutex e predicado reavaliado.

Mutexes evitam corridas, mas um conjunto de locks ainda pode criar impasses. Para avaliar correção, procura tanto acessos concorrentes como ordens de obtenção incompatíveis.