Multithreading avançado: thread pools e work stealing

1. Fundamentos de Thread Pools em C

1.1. Conceito de thread pool

Thread pool é um padrão de concorrência onde um conjunto fixo de threads (workers) é pré-criado e reutilizado para executar tarefas submetidas dinamicamente. Em C, implementamos isso com pthreads, gerenciando o ciclo de vida das workers: criação inicial, execução contínua em laço e destruição controlada via shutdown.

1.2. Estruturas de dados para fila de tarefas

A fila de tarefas é o coração do pool. Podemos usar uma fila circular (array com índices head/tail) para desempenho previsível ou lista encadeada para flexibilidade. A fila circular oferece melhor localidade de cache:

typedef struct {
    void (*function)(void*);
    void *arg;
} task_t;

typedef struct {
    task_t *tasks;
    int capacity;
    int head;
    int tail;
    int count;
    pthread_mutex_t mutex;
    pthread_cond_t not_empty;
    pthread_cond_t not_full;
} task_queue_t;

1.3. Sincronização básica

Usamos pthread_mutex_t para exclusão mútua no acesso à fila e pthread_cond_t para notificar workers sobre novas tarefas. O padrão típico:

pthread_mutex_lock(&queue->mutex);
while (queue->count == 0 && !shutdown) {
    pthread_cond_wait(&queue->not_empty, &queue->mutex);
}
// extrair tarefa
pthread_mutex_unlock(&queue->mutex);

2. Implementando um Thread Pool Genérico

2.1. API pública

typedef struct thread_pool thread_pool_t;

thread_pool_t* thread_pool_create(int num_threads, int queue_capacity);
int thread_pool_submit(thread_pool_t *pool, void (*func)(void*), void *arg);
void thread_pool_destroy(thread_pool_t *pool);

thread_pool_create aloca estrutura, inicializa fila e cria N threads workers. thread_pool_submit insere tarefa na fila (bloqueia se cheia). thread_pool_destroy sinaliza shutdown, acorda todas workers e faz join.

2.2. Worker threads: laço infinito

Cada worker executa:

void* worker_loop(void *arg) {
    thread_pool_t *pool = (thread_pool_t*) arg;
    while (1) {
        pthread_mutex_lock(&pool->queue.mutex);
        while (pool->queue.count == 0 && !pool->shutdown) {
            pthread_cond_wait(&pool->queue.not_empty, &pool->queue.mutex);
        }
        if (pool->shutdown && pool->queue.count == 0) {
            pthread_mutex_unlock(&pool->queue.mutex);
            return NULL;
        }
        task_t task = dequeue(&pool->queue);
        pthread_mutex_unlock(&pool->queue.mutex);
        task.function(task.arg);  // executa fora do lock
    }
}

2.3. Tratamento de shutdown

No thread_pool_destroy:

pthread_mutex_lock(&pool->queue.mutex);
pool->shutdown = 1;
pthread_cond_broadcast(&pool->queue.not_empty);
pthread_mutex_unlock(&pool->queue.mutex);

for (int i = 0; i < pool->num_threads; i++) {
    pthread_join(pool->threads[i], NULL);
}

3. Escalonamento e Balanceamento de Carga

3.1. Fila única global vs. filas locais

Fila única global é simples mas sofre contenção no mutex quando muitas threads competem. Filas locais por thread reduzem contenção, cada worker tem sua própria fila e só acessa a própria.

3.2. Estratégias de distribuição

  • Round-robin: distribuir tarefas sequencialmente entre workers
  • Aleatória: escolher worker aleatório para cada tarefa
  • Baseada em afinidade: submeter tarefa ao worker que já tem dados quentes no cache

3.3. Tamanho dinâmico do pool

Monitorar carga (tamanho médio da fila, tempo ocioso das threads) e ajustar número de workers. Implementação complexa, mas útil para cargas variáveis.

4. Work Stealing: Conceitos e Motivação

4.1. Problema do desbalanceamento

Com filas locais, algumas threads podem ficar sobrecarregadas enquanto outras ociosas. Work stealing resolve isso permitindo que threads ociosas "roubem" tarefas de threads ocupadas.

4.2. Princípio do work stealing

Cada thread mantém um deque (double-ended queue) de tarefas. A thread dona insere e retira tarefas do fundo (LIFO). Threads ladras roubam da frente do deque da vítima.

4.3. Vantagens

  • Menos contenção: threads só acessam fila alheia quando ociosas
  • Melhor localidade: thread dona processa tarefas que acabou de criar (dados quentes no cache)
  • Balanceamento natural: trabalho migra para threads ociosas

5. Implementação de Work Stealing em C

5.1. Estrutura de deque lock-free

Implementamos um deque com operações atômicas para evitar locks no caminho crítico:

typedef struct {
    volatile task_t *buffer;
    int volatile top;    // índice da frente (roubo)
    int volatile bottom; // índice do fundo (thread dona)
    int capacity;
} work_stealing_deque_t;

5.2. Algoritmo de roubo

Thread dona faz push_bottom e pop_bottom. Thread ladra faz steal (pop da frente):

task_t steal(work_stealing_deque_t *deque) {
    int t = __atomic_load_n(&deque->top, __ATOMIC_ACQUIRE);
    __atomic_thread_fence(__ATOMIC_SEQ_CST);
    int b = __atomic_load_n(&deque->bottom, __ATOMIC_ACQUIRE);
    if (t < b) {
        task_t task = deque->buffer[t % deque->capacity];
        if (__atomic_compare_exchange_n(&deque->top, &t, t + 1, 
                                        0, __ATOMIC_RELEASE, __ATOMIC_RELAXED)) {
            return task;
        }
    }
    return (task_t){NULL, NULL}; // deque vazio
}

5.3. Sincronização mínima

Usamos atomic_compare_exchange (CAS) para garantir que apenas uma thread rouba com sucesso. Memory ordering __ATOMIC_ACQUIRE/__ATOMIC_RELEASE garante visibilidade correta sem barreiras pesadas.

6. Integração com Thread Pool e Otimizações

6.1. Adaptação do thread pool

Cada worker thread ganha um deque local. O pool mantém array de deques. thread_pool_submit insere no deque da thread atual (ou faz round-robin). Quando o deque local está vazio, a thread tenta roubar de outro deque.

6.2. Políticas de roubo

  • Roubo da frente (top): minimiza conflito com thread dona (que opera no bottom)
  • Roubo do fundo (bottom): pode causar contenção direta com thread dona
  • Vítima aleatória: escolhe worker aleatório para roubar, evita padrões de contenção

6.3. Tratamento de tarefas dependentes

Para tarefas com dependências, usamos contagem de dependências atômica. Tarefa só é executada quando todas as dependências são resolvidas. Garantia de progresso: algoritmo sem locks evita deadlock, e roubo contínuo previne starvation.

7. Comparação de Performance e Casos de Uso

7.1. Benchmarking

Para cargas uniformes (todas tarefas similares), fila global pode ser suficiente. Para cargas irregulares (tarefas de duração variável), work stealing supera significativamente:

// Exemplo: processamento de matriz esparsa
// Fila global: 12.3s (8 threads)
// Work stealing: 7.8s (8 threads) - 37% mais rápido

7.2. Aplicações típicas

  • Servidores web: cada requisição é uma tarefa, duração variável
  • Processamento de imagens: filtros com complexidade diferente por região
  • Simulações físicas: partículas com interações locais, workload irregular
  • Compiladores: análise paralela de módulos com dependências

7.3. Limitações

  • Overhead de roubo: CAS falho custa caro em CPUs com muitos cores
  • False sharing: deques de threads vizinhas no mesmo cache line
  • Tuning: tamanho do deque, número mínimo de tarefas para roubar, política de vítima

Work stealing é implementado em bibliotecas reais como Intel TBB (C++), Java ForkJoinPool e Go scheduler. Em C puro, exige cuidado com memory ordering e atomic operations, mas oferece controle fino sobre desempenho.

Referências