Jantar dos Filósofos

Encontrei essa ótima foto com o título 'deadlock' no blog do Miguel, e rapidamente vi passar pela minha mente algumas muitas matérias da graduação, nos saudosos dias de chinelo havaiana e bandejão na Unicamp.

Em inglês, deadlock é uma situação em que progresso algum pode ser feito ou nenhum avanço é possível. Em computação, normalmente se refere a duas ações que estão paradas, uma esperando a outra terminar para poder avançar, e portanto, nenhuma nunca termina, como dois processos que esperam recursos serem liberados um pelo outro.

Mas a parte mais legal disso são as analogias clássicas na literatura e que sempre são citadas em todas as aulas, e que passaram voando pela minha imaginação ao olhar e rir com essa foto. No caso de deadlock, o prelúdio é sempre a explicação de concorrência, que é quase sempre feita com o exemplo do jantar dos filósofos.

Em uma mesa redonda, alguns filósofos estão sentados para pensar e comer, e são servidos de arroz, que deve ser comido com palitinhos, como qualquer iguaria chinesa. Assim como em computação, os recursos são escassos, e há somente um palitinho entre cada dois filósofos. Eles só param de pensar quando têm fome, e para comer, cada filósofo deve ter nas mãos os dois palitinhos aos seus lados, privando seus vizinhos de sua utilização até que ele esteja saciado, quando libera os palitinhos e volta a filosofar. Quando um filósofo tem fome e só tem um palitinho à sua disposição, ele o segura e espera até que o outro esteja disponível. Se um filósofo passa fome por muito tempo, ele morre. Eles só pensam e comem: comunicar-se para resolver o problema da escassez não rola nesta mesa.

A foto acima é um caso real em que cada filósofo tem um palitinho em mãos, e espera indefinidamente até que o colega ao seu lado libere o outro palitinho que vai lhe permitir comer: um deadlock. Em um mundo com poucos recursos, não há palitinhos nem rua para todos.

Uma solução para o problema dos filósofos é adicionar um garçom à mesa, que deve arbitrar o uso dos palitinhos. Em uma mesa com cinco palitinhos e cinco filósofos, como na figura abaixo, se quatro palitinhos já estão sendo usados, o garçom nega o acesso ao último deles. Em computação, o papel do garçom é feito por um pedacinho de código chamado semáforo. Que também existe na foto, mas que aparentemente não foi respeitado.

Nem sempre há arbitração, mas se ela existe, e os filósofos não seguem as regras sobre o uso dos palitinhos, eles merecem mesmo morrer de fome, não? Bem-vindos a São Paulo.

O que é mais difícil, comer arroz de palitinho ou entender essa baboseira toda?