Exercícios

O que você tem em mãos até aqui: o problema da exclusão mútua e as três propriedades de Dijkstra (exclusão mútua, progresso, espera limitada), a ideia de lock, o test_and_set atômico por baixo dele, a escolha entre girar e dormir, e o mutex na prática (pthread_mutex_t em C, synchronized e @Synchronized em Kotlin). Ainda não entramos em deadlock, semáforos ou variáveis de condição, então nenhum exercício aqui precisa disso.

Compile o C com cc main.c -o main -pthread. Pro Kotlin, kotlinc main.kt -include-runtime -d main.jar && java -jar main.jar.

Fáceis

6.1 Pegue o contador com mutex e mude pra 20 threads incrementando 50.000 vezes cada. O resultado esperado é 1000000. Confirme que ele sai igual em toda execução.

6.2 No mesmo contador, comente as chamadas pthread_mutex_lock e pthread_mutex_unlock (deixando só o counter++ dentro do laço) e rode três vezes. Anote os três valores. Agora descomente e rode mais três. Descreva a diferença que você vê entre os dois conjuntos de resultados.

6.3 Explique, com suas palavras, por que a solução “na unha” com uma flag ocupado (a do capítulo do problema da exclusão mútua) viola a exclusão mútua. Aponte exatamente as duas operações que uma segunda thread consegue enfiar no meio.

Médios

6.4 Escreva um programa em C com um mutex protegendo duas variáveis globais, soma e contagem, que várias threads atualizam juntas: cada thread, num laço, faz soma += valor; contagem++. Ao final, a main imprime a média soma / contagem. Garanta que as duas variáveis são atualizadas dentro da mesma seção crítica, e explique o que poderia dar errado se cada uma tivesse o seu próprio mutex.

6.5 O Mutex segura o lock em volta de um único counter++. Escreva uma versão em que cada thread, em vez de travar e destravar 100.000 vezes, calcula a soma parcial numa variável local e trava o mutex uma única vez pra somar sua parcial no counter global. Compare mentalmente quantas vezes o mutex é adquirido nas duas versões, e explique por que a segunda tende a ser bem mais rápida sem deixar de estar correta.

6.6 Traduza o exercício 6.4 pra Kotlin usando synchronized(lock). Depois reescreva encapsulando soma e contagem numa classe com métodos @Synchronized. A versão com a classe protege corretamente a operação “atualizar as duas de uma vez”? Justifique, lembrando da ressalva sobre sequências de chamadas a métodos @Synchronized no final do capítulo do Mutex.

6.7 As três propriedades de Dijkstra são exclusão mútua, progresso e espera limitada. Para cada uma das “soluções” abaixo, diga qual propriedade ela viola:

1. Um protocolo que nunca deixa nenhuma thread entrar na seção crítica.
2. Um lock justo na média, mas em que uma thread específica sempre perde a disputa pras outras e pode esperar indefinidamente.
3. A flag ocupado feita na unha, que deixa duas threads entrarem juntas.

Difíceis

6.8 Considere este trecho, que adquire o mutex e sai da função por um caminho de erro:

pthread_mutex_lock(&lock);
resultado = processa(dado);
if (resultado < 0)
    return resultado;          // sai daqui
counter += resultado;
pthread_mutex_unlock(&lock);

Descreva o que acontece com a próxima thread que chamar pthread_mutex_lock(&lock) quando processa devolve um valor negativo. Depois reescreva o trecho pra que o mutex seja liberado em todos os caminhos de saída, sem mudar a lógica.

6.9 Implemente um lock rudimentar usando a função atômica embutida do GCC/Clang __sync_lock_test_and_set(&flag, 1), que faz o test-and-set descrito no capítulo do lock de forma indivisível (devolve o valor antigo de flag e escreve 1). Seu adquirir deve girar enquanto o valor devolvido for 1, e seu liberar deve zerar a flag com __sync_lock_release(&flag). Proteja o contador com ele e verifique que o resultado dá 1000000.

Dica: while (__sync_lock_test_and_set(&flag, 1)) { } é o laço de espera. Esse é literalmente um spinlock: ele gira em vez de dormir.

6.10 O lock que você escreveu no 6.9 gira (queima CPU) enquanto espera; o pthread_mutex_t dorme (cede o core). Para cada cenário abaixo, diga qual dos dois é a escolha melhor e por quê, usando o trade-off girar-vs-dormir do capítulo do lock:

1. A seção crítica é um counter++, e há mais threads do que cores.
2. A seção crítica é um counter++, cada thread roda no seu próprio core, e a disputa pelo lock é curtíssima.
3. A seção crítica faz uma leitura de disco que leva dezenas de milissegundos.