Quale compito ha svolto Dijkstra tra i volontari, menzionato nel suo documento "The Humble Programmer"?

65

In il documento di Dijkstra "Humble Programmer" , accenna che ha dato alcuni volontari un problema da risolvere:

“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 è stato il problema che Dijkstra ha dato ai volontari? Quali sono state le soluzioni?

    
posta user712092 11.10.2011 - 22:32
fonte

1 risposta

11

Il "problema dei filosofi del pranzo" è stato il problema presentato.

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).

Questo ha le sue radici nei sistemi concorrenti ed è una tipica domanda universitaria presentata quando si discute di Concurrency.

Credo che siano stati sviluppati 4 o 5 algoritmi "ufficiali" per risolvere il problema, ma una rapida ricerca su google per "Il problema dei filosofi della ristorazione" ti fornirà una serie di risultati.

  • Per dettagli su questo problema da Standford U, visita: link

  • L'articolo di wikipedia si trova in: link

  • Una soluzione di MSDN Magizine si trova in: link

Se leggi la versione originale del documento nelle note a pagina 866 afferma: "Atti del Congresso IFIP 1965, 213-217". Soluzioni di un problema nel controllo simultaneo della programmazione.

Il problema nella concorrenza e nelle risorse condivise è il "Problema dei filosofi in sala". : -)

Spero che aiuti.

    
risposta data 26.10.2011 - 23:41
fonte

Leggi altre domande sui tag