Imagine a seguinte situação: você está escutando sua música predileta no celular e recebe uma ligação. Quando finalmente a ligação termina, o seu telefone volta a tocar a música normalmente de onde ela havia parado.

Orquestrar essa concorrência por recursos (no exemplo citado, a saída de som disputada por dois aplicativos) é uma das principais tarefas dos sistemas operacionais (Linux, Android, Windows, MacOS, iOS…).

Quando essa disputa envolve aspectos internos nas “entranhas“ destes sistemas como tempo de execução de processadores e espaço de alocação de memória, a terminologia dos envolvidos muda um pouco (saem aplicativos e entram processos, threads e schedules)  e por consequência o nível de complexidade e abstração também aumenta consideravelmente.

Para amenizar tudo isso, alguns Cientistas da Computação desenvolveram ao longo dos anos, modelos mentais e analogias criativas, que simulam de forma lúdica os problemas de sincronização entre os processos internos dos Sistemas Operacionais.

Dentre os vários modelos existentes (Escritores x Leitores, Algoritmo do Bancário, Barbeiro Dorminhoco…) há um que eu considero super fascinante e que foi proposto por Dijkstra em 1965 com o nome de Jantar dos Filósofos.

Irei detalhar esse modelo ao longo deste artigo, utilizando algumas imagens explicativas e espero que consiga dar a você uma ideia do quão interessante ele é.

DeadLocks

A definição básica por trás do problema apresentado pelo lendário programador Norueguês é a seguinte: cinco filósofos estão numa mesa circular, cada um deles possui à sua frente um prato de macarrão e dois garfos, um na esquerda e um na direita.

Pra analogia funcionar é necessário que algumas regras sejam estabelecidas:

1 – Cada Filósofo deve pegar um garfo de cada vez, a ordem não importa (esquerda ou direita).

2 – Só é possível comer o macarrão com os dois garfos.

3 – Quando não estiver comendo, o Filósofo deve ficar pensando.

4 – Se um filósofo pega um garfo ele fica com ele na mão e não solta.

Imagem 1: Mesa circular ocupada por 5 carinhas simpáticas. Cada carinha foi nomeada como F1, F2, F3, F4 e F5, estão sentadas no sentido horário e possuem um prato de macarrão e dois talheres à sua frente, sendo que dividem cada talher com as carinhas do lado.

Em um cenário feliz de colaboração, todos os filósofos irão combinar entre si e comer de forma ordenada e pacífica.

Porém, na Computação Concorrente de Processos (que é onde os problemas dessa analogia se aplicam) existe uma concorrência dos processos por recursos e nenhuma colaboração explícita entre eles.

Num primeiro cenário, todos irão tentar comer de uma vez e por coincidência, todos irão começar pelo garfo da esquerda.

O resultado: todos os Filósofos ficam com um garfo na mão e ninguém come.

Imagem 2: Todas as carinhas deixaram de exibir o sorriso simpático e agora estão tristes. Cada uma está segurando um garfo.

Temos aqui a simulação de um problema conhecido e temido por programadores de Computação Concorrente: o deadlock. Ele acontece quando vários processos disputam por um recurso computacional e de repente todos eles se encontram bloqueados.

Fiz questão de demonstrar nesse exemplo que, a decisão de todos pegarem os garfos da esquerda foi uma mera coincidência. E isso serviu para mostrar como não é trivial prever deadlocks com antecedência.

Starvation

Outro problema da programação concorrente que pode ser simulado através do Jantar dos Filósofos é a inanição de um processo, evento também conhecido como Starvation.

Para montarmos esse cenário, algumas regras precisam ser alteradas:

1 – Um dos filósofos possui uma prioridade menor em relação a todos os outros.

2 – Se um filósofo pega um garfo e o outro está ocupado, ele devolve o primeiro que pegou para a mesa.

3 – Cada filósofo tem um tempo diferente para comer.

Agora vamos ao detalhamento do cenário:

Primeiramente, F1 e F3 estão comendo e F2, F4 e F5  estão pensando. Veja que F2 é o filósofo com menor prioridade entre todos e está sinalizado com uma cor diferente.

Imagem 3: Todas as carinhas estão felizes, exceto por F2 que está sem nenhum garfo e com um sorriso sem graça no rosto. F1 e F3 estão com dois garfos na mão enquanto F5 e F4 estão apenas olhando o tempo passar.

Numa segunda rodada, F1 parou de comer antes de F3. Dando a F5 a possibilidade de capturar os garfos e fazer sua refeição.

Imagem 4: F2 continua sem garfo e sem graça. Enquanto F5 e F3 estão felizes com os dois garfos na mão.

Na próxima rodada, onde finalmente F2 iria ter acesso aos garfos de F3 e F1, o inesperado acontece: F5 termina a sua refeição e F1, que tem maior prioridade em relação a F2, volta a comer.

Imagem 5: F1 está novamente com os dois garfos, F4 consegue finalmente os seus também. F3 e F5 estão ostentando o seu sorriso filosófico sem garfos e F2 se mantém sem garfo, sem graça e com fome.

Não são necessárias muitas rodadas para perceber que F2 irá morrer de fome.

Temos aqui o cenário de inanição de um dos processos. Por conta de uma atribuição de prioridade baixa, ele nunca irá conseguir obter um determinado recurso (tempo no processador ou uma posição na memória) e ficará eternamente bloqueado.

Como solucionar

Existem diversos algoritmos para solucionar esses dois problemas clássicos apresentados. Porém, alguns deles envolvem o conhecimento prévio de aspectos específicos de programação concorrente como semáforos, mutex, exclusão mútua, atomicidade e condições de corrida. Fica muito difícil abordar todas essas soluções neste mesmo artigo.

Mas didaticamente, nós podemos flexibilizar algumas regras, para simular uma possível solução dos 2 impasses apresentados.

No cenário inicial em que acontece um deadlock, uma regra foi imposta: a ordem para capturar os garfos não importa. Ou seja, o programador responsável pelo algoritmo assumiu que um filósofo pegar primeiro o garfo da direita ou esquerda não iria influenciar no resultado final. Vamos alterar isso.

No segundo cenário, onde acontece a starvation do filósofo com menor prioridade, uma regra foi alterada: se o filósofo pega um garfo e não consegue pegar o outro, então ele devolve o primeiro para a mesa. Vamos manter esta regra.

A partir de agora:

1 – Todos os filósofos pegam os garfos da direita para esquerda, exceto o último. Que irá pegar pela ordem inversa.

2 – Os filósofos que não conseguirem pegar o segundo garfo, devolvem o primeiro para a mesa.

Imagem 6: Todas as carinhas agora possuem uma seta indicando qual dos garfos está sendo disputado. Em todas elas, a seta está demonstrando que o garfo da direita irá ser apanhado. Porém, nas carinhas F4 e F5 as duas setas estão apontando o mesmo garfo, pois a seta de F5 aponta para a esquerda.

Veja que nesse cenário, F5 e F4 disputam pelo mesmo garfo, uma vez que F5 tenta pegar o garfo numa ordem inversa. E este pequeno detalhe, dá a chance de que F1 consiga comer numa próxima rodada.

Imagem 7: Apenas F1 está com os dois garfos na mão. F2 e F3 tentam pegar os seus garfos da direita enquanto F4 e F5 disputam pelo mesmo garfo.

Ou seja, temos aqui uma solução para os problemas de Starvation e DeadLock entre nossos intrépidos pensadores, contando que F2 ainda seja o Filósofo com menor prioridade.

Todos os envolvidos irão executar as suas tarefas de dormir e comer no sentido horário.

Conclusão

Obviamente, essa não é a solução perfeita (com a modificação de algumas variáveis ele pode apresentar problemas) e é isso que torna o estudo de sistemas operacionais tão complexo e fascinante.

Por um lado, hoje nós temos computadores e celulares com processadores e memórias poderosas que aliviam um pouco a disputa por recursos. Por outro, a demanda em aproveitar o máximo do desempenho dessas tecnologias também cresce intensamente. (Grandes poderes trazem grande responsabilidades)

Além do mais, a presença de dispositivos inteligentes em nossa vida só tende a aumentar e alguns deles (por questão de economia) não possuem a mesma quantidade de armazenamento e processamento de nossos celulares, computadores e servidores. Ou seja, é difícil dizer que esses problemas Computacionais dos anos 60 venham a se tornar coisa do passado.

A boa notícia é que para Ciência, aprender com o passado nunca será um problema.

Referências:

https://blog.pantuza.com/artigos/o-jantar-dos-filosofos-problema-de-sincronizacao-em-sistemas-operacionais
https://www.youtube.com/watch?v=g9zEqwSZd4o
https://en.wikipedia.org/wiki/Dining_philosophers_problem
https://legacy.cs.indiana.edu/classes/p415-sjoh/hw/project/dining-philosophers/index.htm
https://pages.mtu.edu/~shene/NSF-3/e-Book/MUTEX/TM-example-philos-1.html