What task did Dijkstra give volunteers, which was mentioned in his paper “The Humble Programmer”

algorithmshistory

In Dijkstra's paper "Humble Programmer", he mentions that he gave some volunteers a problem to solve:

“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.”

What was the problem Dijkstra gave to the volunteers? What were the solutions?

Best Answer

The "Dining philosophers problem" was the problem presented.

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

This has its roots in concurrent systems and is a typical university question presented when discussing Concurrency.

I believe that 4 or 5 "official" algorithms have been developed to solve the problem but a quick search on google for "Dining philosophers problem" will get you a vareity of results.

If you read the original version of the paper in the footnotes on page 866 it states: "Proceedings of the IFIP Congress 1965, 213-217. " Solutions of a problem in concurrent programming control."

The problem in concurrency and shared resources is the "Dining Philosophers Problem". :-)

Hope that helps.

Related Topic