Dining Philosophers Problem

There are nn philosophers numbered 0 through n1n-1, seated around a circle table. Their only problem--besides philosophy--is that the dish served is a very difficult kind of spaghetti, that has to be eaten with two forks. There are two forks next to each plate, so that presents no difficulty: as a consequence, however, no two neighbors may be eating simultaneously. The philosophers' lives consist of an alternation between eating and thinking. The goal is to devise a strategy such that no philosopher is stuck thinking forever and each philosopher may eat at reasonable intervals.

Parameters

  • nn: number of philosophers

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 2 of 2 algorithms

See more
Resource hierarchy solution1965O(2n)O(2^n)O(n)O(n)
Arbitrator solution1965O(2n)O(2^n)O(1)O(1)

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table