Exercícios

Os exercícios abaixo usam só o que apareceu até aqui: criar threads com pthread_create, esperar com pthread_join, passar dados via struct e devolver resultado convertendo pra void *. Nada de mutex ainda, isso é o próximo capítulo.

Dividir, processar, combinar é um dos formatos que dá pra montar sem sincronização, e boa parte dos exercícios cai nele, mas não é o único. Alguns aqui não têm fase de combinação nenhuma (cada thread termina sozinha, como no download do Exemplo 3), e outros processam fatias sem reduzir a um valor só. O que amarra todos é a mesma condição: enquanto não existe lock, as threads só podem tocar regiões disjuntas da memória. Os exercícios difíceis esbarram de propósito nesse limite, pra você sentir onde ele está, não consertar (ainda).

Salvo indicação, compile com cc main.c -o main -pthread.

Fáceis

5.1 Modifique a soma paralela pra usar 8 threads em vez de 5, sobre um array de 10.000 elementos preenchido com i + 1. Confira que o total continua 50005000.

5.2 No exemplo da soma, o array tem 1000 elementos e são 5 threads, divisão exata. Troque N_ELEMS pra 1003 sem mexer em mais nada e rode. O resultado ainda fica certo? Explique, olhando pra linha que calcula slices[t].len, por que a última fatia é tratada diferente das outras.

5.3 Escreva um programa que cria 4 threads, cada uma recebendo via struct um número inteiro n (1, 2, 3, 4). Cada thread calcula n * n e devolve o resultado. A main coleta os quatro quadrados com pthread_join e imprime a soma deles (esperado: 1 + 4 + 9 + 16 = 30).

5.4 Pegue a busca do máximo e adapte pra encontrar o mínimo de um array de 16 inteiros. O que muda além do nome da função?

5.5 Escreva um programa que dobra cada elemento de um array de 1000 inteiros, em paralelo, escrevendo o resultado no próprio array (v[i] *= 2). Divida em fatias, uma por thread, e note que aqui não existe fase de combinação: cada thread escreve na sua fatia e acabou, o join só garante que tudo terminou antes da main imprimir. Compare com a soma paralela e diga o que sumiu.

Médios

5.6 Generalize a soma paralela pra funcionar com um número de threads que não divide o tamanho do array de forma exata (por exemplo, 1000 elementos e 3 threads). Garanta que nenhum elemento fique de fora nem seja somado duas vezes. Verifique com 1000 elementos e 3, 7 e 11 threads que o total é sempre 500500.

Dica: distribua os elementos que sobram (N_ELEMS % N_THREADS) entre as primeiras fatias, uma a mais em cada, em vez de jogar todos na última.

5.7 Escreva um programa que conta, em paralelo, quantos números primos existem num array de inteiros. Divida o array em fatias, cada thread conta os primos da sua fatia e devolve a contagem parcial, e a main soma as parciais. Teste com o array {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16} (resposta: 6 primos).

5.8 Simule o envio de 6 notificações independentes, cada uma com um tempo de “envio” diferente (use usleep com valores como 300, 120, 250, 80, 400 e 150 ms, um por notificação, passados via struct). Rode primeiro sequencialmente, depois com uma thread por notificação, e meça o tempo de relógio das duas versões com clock_gettime, como no download concorrente. Não há nada pra combinar: cada thread dispara sua notificação e termina. Explique por que o tempo da versão concorrente fica perto da notificação mais lenta (400 ms), e não da soma de todas.

5.9 No download concorrente, a versão concorrente cria uma thread por arquivo. Suponha que você tenha 100 arquivos pra baixar, mas queira usar no máximo 5 threads. Descreva (em prosa ou pseudocódigo, não precisa compilar) como você organizaria o trabalho pra que cada thread processe uma fatia da lista de arquivos, uma depois da outra, respeitando o limite de 5 threads.

Difíceis

5.10 Rode o contador sem sincronização cinco vezes e anote os resultados. Agora reduza o número de incrementos por thread de 100.000 pra 10, mantendo as 10 threads, e rode mais cinco vezes. Com que frequência o resultado dá certo (100) em cada caso? Explique por que diminuir o trabalho dentro do laço muda a probabilidade de você observar o bug, mesmo o bug estando presente nos dois programas.

5.11 Considere este programa, que tenta acumular resultados num array compartilhado em vez de devolver pelo join:

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

#define N 4

int resultados[N];

typedef struct {
    int  id;
    int  valor;
} Tarefa;

void *worker(void *arg) {
    Tarefa *t = arg;
    resultados[t->id] = t->valor * 10;
    return NULL;
}

int main(void) {
    pthread_t tids[N];
    Tarefa tarefas[N];

    for (int i = 0; i < N; i++) {
        tarefas[i].id    = i;
        tarefas[i].valor = i + 1;
        pthread_create(&tids[i], NULL, worker, &tarefas[i]);
    }
    for (int i = 0; i < N; i++)
        pthread_join(tids[i], NULL);

    for (int i = 0; i < N; i++)
        printf("resultados[%d] = %d\n", i, resultados[i]);
}

Este programa não tem o bug do contador, mesmo com 4 threads escrevendo no mesmo array resultados sem sincronização nenhuma, e mesmo o array sendo estado compartilhado. Explique por quê. O que é diferente entre este caso e o counter++? Que propriedade das escritas de cada thread torna a ausência de sincronização segura aqui?

Dica: olhe em qual posição de memória cada thread escreve.

5.12 Agora quebre o programa de propósito. Modifique o worker do exercício anterior pra que todas as threads escrevam na mesma posição resultados[0] += t->valor (em vez de resultados[t->id] = ...). Rode várias vezes. O valor final de resultados[0] deveria ser 1 + 2 + 3 + 4 = 10. Ele é sempre 10? Relacione o que você observa com o bug do contador, e explique por que a mudança de resultados[t->id] pra resultados[0] reintroduziu o problema que o exercício 5.11 não tinha.