quinta-feira, 17 de janeiro de 2008

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?

2 comentários:

Aretha disse...

O mais dificil é ficar sem vc!!

Miguel Galves disse...

São Paulo tem um agravante: os filósofos são fominhas, apressados e metidos a espertinhos. Esperar o sinal abrir ou ficar parado pra não fechar o cruzamento, ou então esperar tranquilamente dentro do seu carro é considerado prova de possuir pinto pequeno.

Gostei da bela análise socio-computacional gerada pelo meu blog :-)

[]s

Miguel