Sync (MetroREC)

Implementei o mecanismo de sincronização do embarque de passageiros na estação de metrô da METROREC, um trabalho de Sistemas Operacionais. Cada passageiro é uma thread, cada vagão é outra, e o problema é garantir duas coisas ao mesmo tempo: ninguém embarca sem assento e o vagão não parte com passageiro liberado ainda em pé.

O enunciado restringia as ferramentas: só pthread_mutex_* e pthread_cond_*, um único lock por estação, sem semáforo e sem espera ativa. A premissa é um vagão por vez, com no máximo um carro na estação.

O contrato das quatro funções

O runner (teste fornecido) chama a estação em quatro pontos. station_init prepara a estrutura. station_load_car(station, count) é chamada pela thread do vagão com o número de assentos e só retorna quando todos os passageiros que ela liberou confirmaram o embarque ou quando os assentos acabam. station_wait_for_car bloqueia o passageiro até existir vagão com assento livre. station_on_board é a confirmação de que ele sentou.

Reserva não é confirmação

Essa foi a parte que exigiu pensar antes de escrever código. Entre reservar um assento e avisar que sentou, o passageiro ainda precisa se mover; vários passageiros podem reservar antes de qualquer um deles chamar station_on_board. Se o vagão contasse reservas, ele partiria com gente ainda em pé no corredor.

Resolvi tratando boarding como contador de confirmações pendentes: sobe quando o passageiro reserva o assento e desce quando ele confirma. O vagão espera enquanto o contador for maior que zero, ou seja, enquanto existir alguém que ele liberou e que ainda não avisou que sentou.

O estado da estação

struct station guarda tudo o que as duas pontas precisam saber uma da outra:

• mutex — o único lock da estação, protege todos os campos;
• car_arrived — variável de condição onde os passageiros dormem esperando assento;
• passenger_boarded — variável de condição onde o vagão dorme esperando confirmações;
• car_present — vale 1 enquanto existe vagão na estação;
• free_seats — assentos que este vagão ainda pode reservar;
• waiting — passageiros que entraram em station_wait_for_car e ainda não reservaram;
• boarding — confirmações pendentes deste vagão.

O struct fica completo no header, e não opaco, porque o runner aloca a estação na pilha da main e precisa do tipo completo para isso.

A reserva

O passageiro se registra em waiting antes de dormir, porque o vagão precisa saber quantas pessoas já estão esperando no instante em que chega. Depois fica no laço até existir vagão e assento livre.

void station_wait_for_car(struct station *station) {
    pthread_mutex_lock(&station->mutex);

    station->waiting++;

    while (!station->car_present || station->free_seats == 0) {
        pthread_cond_wait(&station->car_arrived, &station->mutex);
    }

    station->waiting--;
    station->free_seats--;
    station->boarding++;

    pthread_mutex_unlock(&station->mutex);
}

A saída do laço é a reserva, e ela acontece dentro do lock: decrementar waiting, decrementar free_seats e incrementar boarding são uma operação só do ponto de vista dos outros passageiros. Sem isso, dois passageiros poderiam ver o mesmo último assento livre e reservar duas vezes.

Duas variáveis de condição

São dois predicados diferentes: passageiro espera “vagão presente e assento livre”, vagão espera “nenhuma confirmação pendente”. Com uma condvar só, um signal poderia acordar a thread que não estava esperando aquela condição e a notificação se perderia.

Com duas, cada grupo é acordado pelo seu canal. O vagão usa broadcast em car_arrived, porque vários passageiros podem embarcar no mesmo carro; e usa signal em passenger_boarded, porque ele é o único que dorme nessa condição.

O fechamento do vagão

while (station->boarding > 0 || (station->free_seats > 0 && station->waiting > 0)) {
    pthread_cond_wait(&station->passenger_boarded, &station->mutex);
}

station->car_present = 0;
station->free_seats = 0;

pthread_mutex_unlock(&station->mutex);

A condição de espera tem dois termos. O primeiro é a obrigação do contrato: não partir com confirmação pendente. O segundo absorve quem chegou logo depois da abertura das portas, em vez de o vagão partir com assento vazio e passageiro esperando.

Zerar car_present e free_seats antes do unlock é o que impede um passageiro atrasado de reservar assento num vagão que já partiu. O encerramento acontece com o lock na mão, então ninguém observa o estado no meio do caminho; o próximo vagão começa com a estação limpa.

Capacidade não positiva é tratada como zero. O contrato não define esse caso, e a escolha foi não oferecer assento nenhum, de modo que o vagão sai vazio.

Validação

O build é -std=gnu11 -Wall -Wextra -Werror -pthread, então a implementação compila sem aviso nenhum. O runner fornecido cria 100 threads de passageiro, faz vários vagões passarem com número de assentos sorteado entre 0 e 49 e verifica três situações: vagão vazio sem ninguém esperando, vagão sem assento com muita gente esperando e vagão com mais assentos do que passageiros. A saída termina em Looks good! quando não há divergência.

Para procurar falha intermitente rodei o teste 60 vezes seguidas, depois mais 30 com o processo fixado em um núcleo (taskset -c 0) e uma vez sob o helgrind. O helgrind apontou quatro contextos de corrida, todos em load_car_returned, um indicador de controle do próprio runner: ele é volatile, mas as leituras e escritas não são atômicas. Nenhum contexto foi apontado em sync_car.c.

No ambiente local também acrescentei ao runner um caso inválido: station_load_car com capacidade negativa deve retornar de imediato sem deixar ninguém embarcar. Ele passa, e o resto do runner ficou intacto.

Limitações

• Um vagão por vez é premissa do enunciado. car_present e free_seats descrevem o vagão corrente; dois carros simultâneos exigiriam um estado por carro e outra regra de fechamento.
• Os avisos do helgrind são do runner, não da estação. Isso precisa ser dito toda vez que o resultado é citado, senão parece que a implementação tem corrida.

Pontos de melhoria

• Rodar o helgrind desde a primeira versão. Deixei para o fim e passei a maior parte do tempo desconfiando do código quando o resultado apontava um problema que não era meu.
• Criar mais casos de limite no runner, além do de capacidade negativa: capacidade 1 com dois passageiros esperando, vagão com zero assentos e um único passageiro, sequência de vagões vazios.