Que tarefa Dijkstra deu aos voluntários, mencionada em seu artigo “The Humble Programmer”?

65

No artigo de Dijkstra "Humble Programmer" , ele menciona que deu algumas voluntários um problema para resolver:

“I have run a little programming experiment with really experienced volunteers, but something quite unintended and quite unexpected turned up. None of my volunteers found the obvious and most elegant solution. Upon closer analysis this turned out to have a common source: their notion of repetition was so tightly connected to the idea of an associated controlled variable to be stepped up, that they were mentally blocked from seeing the obvious. Their solutions were less efficient, needlessly hard to understand, and it took them a very long time to find them.”

Qual foi o problema que Dijkstra deu aos voluntários? Quais foram as soluções?

    
por user712092 11.10.2011 / 22:32
fonte

1 resposta

11

O "problema dos filósofos de jantar" foi o problema apresentado.

Basically there are 5 philosophers that need to eat. (imagine a plate of never ending food in front of each philosopher), between each plate is a fork (5 plates, 5 forks, 5 philosophers).

A philosopher can only eat if he is holding both the fork to the right and the fork to the left. (only two philosophers can eat at any given time).

A fork may be picked up anytime it is available and put down if it is being held. Each fork must be picked up interdependently. (one at a time).

While a philosopher is not eating, they are thinking (the need to alternate states is what drives the problem).

How do you allow each of them to eat and alternate thinking (so the others can eat) without creating a deadlocked system (where one philosopher is holding one fork and waiting for the other, preventing another philosopher from eating).

Isso tem suas raízes em sistemas concorrentes e é uma questão típica da universidade apresentada ao discutir Concorrência.

Eu acredito que 4 ou 5 algoritmos "oficiais" foram desenvolvidos para resolver o problema, mas uma busca rápida no google por "Problema de filósofos de jantar" vai te dar uma variedade de resultados.

  • Para detalhes sobre este problema, por favor visite: link

  • O artigo da wikipedia está localizado em: link

  • Uma solução do MSDN O Magizine está localizado em: link

Se você leia a versão original do documento nas notas de rodapé na página 860 afirma: "Anais do Congresso IFIP 1965, 213-217." Soluções de um problema no controle de programação concorrente. "

O problema em simultaneidade e recursos compartilhados é o "Problema dos Filósofos Jantando". : -)

Espero que ajude.

    
por 26.10.2011 / 23:41
fonte