Dining Philosophers

Computer Science Level 2

Five philosophers are sitting around a circular table for a meal of spaghetti. For any philosopher to eat spaghetti, they must have two forks: one in the left hand and one in the right hand. However, they have just five forks total on the table.

To coordinate their meal, the philosophers agree to strictly follow these steps:

  1. Think until the left fork is available, and then pick it up.
  2. Think until the right fork is available, and then pick it up.
  3. Eat for 30 seconds.
  4. Put the right fork down.
  5. Put the left fork down.
  6. Repeat these steps.

Can we guarantee that at least one philosopher is eating every 30 seconds?

Yes No

Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Stephen Mellor
Mar 24, 2018

All philosophers instantly pick up the left fork, and then are all waiting for the right fork to come available, meaning that no-one ever eats spaghetti

19 Helpful 0 Interesting 1 Brilliant 0 Confused

@Agnishom Chattopadhyay I took the problem to be: can one consistently extend this set of a necessary set of rules to ensure that … \ldots Under that formulation one can add the rule

if you are in seat 1 and are only holding 1 fork, drop it one time only.

It’s stupid, I know, but that would set off a chain reaction, and every 30s exactly 1 philosopher eats. Or one could allow for external interference. Prodding 1 philosopher at the start to drop his fork and then leaving (thus breaking the symmetry once) would set this off.

But … yeah, otherwise the solutions are correct: with no other rules and no external interference, the philosophers would be stuck in an infinite cycle of thought whilst holding a fork in their left hands.

R Mathe - 3 years, 1 month ago
Alison King
Mar 27, 2018

They all hold the two forks that are between them, thus each fork is shared. They all begin eating with the fork in their right hands and at a signal switch to eating with the fork in their left hands. Everyone is eating at the same time.

1 Helpful 0 Interesting 0 Brilliant 0 Confused

Your answer is wrong

Michael Wang - 3 years, 2 months ago

Log in to reply

It would be more constructive if you explained why the answer is wrong

Huy Z - 3 years, 2 months ago

Not you. I am talking about Alison King's answer.

Michael Wang - 3 years, 2 months ago

The philosophers cannot eat before they have one fork in each hand. So they cannot "begin eating with the fork in their right hands". Check the part that says: "For any philosopher to eat spaghetti, they must have two forks: one in the left hand and one in the right hand"

Huy Z - 3 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...