<aside> 🧵 Filosofia. Lanches. Dança das cadeiras. E muito mais enquanto exploro os desafios do paralelismo em programas com multi-threads. Mini-guia para atacar o problema do Jantar de Filósofes da 42sp!
</aside>
palavras-chave: paralelismo, multithreading, semáforo, mutex, concorrência, deadlock.
Primeiramente, você está chegando aqui depois de vencer a maratona do minixéu. Parabéns 🎉🍰 Existe uma justaposição interessante entre o que aprendemos sobre forks e processos no minigel, e o que teremos que aprender sobre threads e paralelismo para este projeto.
O Philosophers é a versão 42 de um problema famoso no mundo da ciência da computação, proposto por Edsger Dijkstra, programador/cientista da computação/professor holandês, chamado de “Jantar dos Filósofos” (e das filósofas também 💜), cujo objetivo é ilustrar problemas de sincronização, e pensar sobre as técnicas para resolver estes problemas. Assim, alegoricamente Dijkstra monta um cenário fictício de um jantar em que as pessoas ao redor da mesa precisam compartilhar seus garfos para jantar, e o desafio é pensar como instruir essas pessoas a executarem uma sequência de ações que seja sustentável, ou seja, que permita que todo mundo se alimente e que ninguém morra de fome.
O que eu achei difícil nesse projeto foi a parte de modelar o problema. Entender a descrição do problema no pdf é fácil, agora descrever esse cenário fictício por meio de linhas de código foi uma tarefa que me desafiou muito. Como representar um filósofo? Como representar um garfo? Como representar o ato de comer?
Foi estudando sobre o conceito de threads e as funções permitidas no projeto que deu pra começar a responder essas perguntas, e conforme fui me familiarizando com o mundo das threads e os desafios do paralelismo — concorrência de dados (data racing), engarrafamento de threads (deadlocks) —, fui entendendo melhor os contornos do problema, o papel de cada coisa no modelamento do jantar, e assim a coisa foi tomando forma e fazendo mais sentido.
Esse foi o primeiro projeto que eu tive que recalcular a rota muitas e muitas vezes, até o último momento (literalmente tivemos q reescrever o projeto de um outro jeito no dia em q achávamos que o projeto acabaria). Talvez tenha dado sorte nos anteriores, mas a sensação é de que antes, eu sempre conseguia traçar um fio de raciocínio para resolver o problema, que era seguido de início ao fim, era como se eu “acertasse” de primeira. No Philosophers, tive que pensar e repensar em diversos pontos do projeto como eu estava manipulando as threads e a memória acessada por elas, desde o momento 0 (em que achava que um philosopher era um struct e um garfo tinha que ser uma variável, ⚠️ spoiler: não necessariamente), até o momento de sincronizar todas as threads (achava que cada thread seria responsável por uma etapa do ciclos de comer/dormir/pensar, até descobrir que ⚠️ spoiler: não é bem por aí). Então um conselho q eu daria para eu no início desse projeto seria: desapega nível HARD das ideias iniciais, e vai recalculando a rota o mais rápido possível. Boa sorte 🍀
<aside> 🏳️⚧️ Disclaimer sobre o gênero da palavra “filósofo” neste acelera: Eu pessoalmente me incomodo com o fato de que na gramática normativa do português, falar “os filósofos” se refere a qualquer pessoa que estude/pense/produza filosofia, enquanto que falar “as filósofas” se refere a pessoas do gênero feminino. Até porque quando escuto “os filósofos estavam jantando espaguete”, eu preciso fazer uma acrobacia mental enorme para não imediatamente imaginar vários homens brancos barbudos, cisgêneros, cissexuais e heteropassáveis, sem deficiências e não-gordos, discutindo ao redor de uma mesa, balançando garfos no ar com suas barbas sujas de molho de tomate. O que subconscientemente contribui para a cristalização da ideia de que as pessoas que fazem filosofia devem ser somente homens brancos barbudos, cisgêneros, cissexuais e heteropassáveis, sem deficiências e não-gordos. Infelizmente. Em inglês é mais neutro falar “the philosophers” (apesar de ser igualmente provável incorrer no erro de pensar que “the philosophers” são homens brancos barbudos etc. you know the drill). Por causa disso, tentarei ao máximo usar linguagem neutra neste texto, e das vezes em escapar um “filósofo”, te convido a fazer a ginástica mental da descolonização junto comigo ✨🤸
</aside>
Como sempre, gosto de começar explicando o significado da palavra em inglês. Thread significa linha (de costurar 🪡), ou fio (de lã 🐏). É uma palavra que evoca a ramificação de algo grande em pedaços menores, longos e finos. Por exemplo, “perder o fio da meada” em inglês pode ser “to lose the thread” - “I lost the thread of what I was saying” pode-se traduzir como “eu esqueci o que ia dizendo”. No sentido de que aquela ideia que seria dita é uma parte menor, um fio, de algo maior — todas as coisas que se passam na cabeça de alguém. (obs: join significa unir. Então não estranhe quando estudar que existe uma função de encerramento chamada pthread_join: o nome evoca a ideia de que todos os fios em que a thread principal main foi desfiada uma hora precisam ser re-unidos novamente - daí o join).
É muito importante sair desse projeto com a clareza da diferença entre o que é uma thread e um fork. As duas ferramentas, forks e threads, servem ao propósito de dividir a carga de processamento de um programa em “subprogramas” que rodam independente e paralelamente. Diferente dos forks que são processos novos que copiam o espaço de memória do processo principal e trabalham cada um com a sua cópia — ou seja, alterações na memória dentro de processos filhos não alteram a memória do processo pai —; as threads não são processos novos (não têm um PID), são como que fragmentos da thread principal (a main), e, surpreendentemente, compartilham o mesmo espaço de memória entre si, o que traz suas vantagens e seus desafios para que tudo funcione certinho. Ou seja, as alterações que as threads fazem reverberam na thread principal, e entre todas as threads que compartilham o mesmo espaço de memória. Por esse motivo também, threads são chamadas de “lightweight processes” (processos ultra-leves), porque compartilham o mesmo espaço de memória que o processo pai, ou seja, quase sempre criar threads novas vai consumir menos memória do que criar novos processo.
Threads e processos são parecidos porque o seu resultado final é o mesmo: colocam o computador para executar instruções paralelamente de um programa. No minishell, as instruções paralelas eram os diferentes comandos da pipeline. No Philosophers, o que acontece é que cada philosopher vive o mesmo ciclo de vida (comer→dormir→pensar→repeat) ao mesmo tempo. E uma vez que threads compartilham o mesmo espaço de memória, e as pessoas filósofas do problema proposto compartilham seus garfos para jantar, faz sentido que threads sirvam para modelar este problema, certo?
Isso é apenas uma introdução e eu não vou me demorar muito mais — recomendo que você faça suas buscas, leia o manual sobre as threads, enfim, turn yourself around :) Mas uma última coisinha: lembra quando vc estava estudando sobre forks e descobriu que, a menos que vc force a execução sequencial em uma determinada ordem usando waitpid, o output de um mesmo programa pode aparecer em ordem diferente de uma execução para a outra? Pois as threads têm essa mesma brisa:
Os prints bagunçados são igual ao que acontecia usando a
fork(). Isto é, a primeira thread criada é a primeira a executar, mas não necessariamente os comandos dessa thread virão primeiro que os das próximas threads. Dá pra ver isso no output da primeira execução (print à direita), que oprintfda thread de índice 1 foi printado antes do da thread 0. E esse comportamento não é garantido de ser repetido em execuções subsequentes.
Isso acontece porque a ordem de execução dos comandos de um processo dependem do algoritmo de agendamento que o sistema operacional tem implementado dentro de si. E do ponto de vista de quem programa (eu e vc), é impossível prever em qual ordem os comandos serão executados.