Dining Philosophers A common example that require coordinated access to resources is a problem called Dining Philosopher
Posted: Fri Apr 29, 2022 6:34 am
Dining Philosophers
A common example that require coordinated access to resources is
a problem called Dining
Philosophers.
Imagine N philosophers sitting at a round table
(are family members and have been successfully
vaccinated). They alternately thinking and eating from a
shared plate with a big spaghetti plate in the middle of the
table.
There is a total of N forks placed at the
table so that each philosopher has 1 fork between himself and his
neighbor to the right and 1 fork between himself and his neighbor
to the left. A philosopher needs the two chopsticks placed left and
right of her plate to eat.
After finishing eating, he must place the chopsticks back on the
table to give a chance to his left and right neighbors to eat. If a
fork is not available, the philosopher must wait for his neighbor
to release it before he can pick it up1.
After obtaining both chopsticks, a philosopher eats for some
time, then releases both chopstick to think again.
Additional conditions to analyses:
THINKING – When philosopher doesn’t want
to gain access to either fork.
HUNGRY – When philosopher wants to enter
the critical section.
EATING – When philosopher has got both the
forks, i.e., he has entered the section.
The philosopher can enter
on HUNGRY, but not yet star eating, that
gap time is the hungry time.
When the hungry time is big enough, we call this starvation.
In this program the student can use any preferred
language and can modify the templates classes in order to solve the
problem in the best convenient way for the language used to
implement the solution.
Q1. (30 points)…………………………...…………... data
abstraction
Implement a Philosopher class. This class must inherit from
thread or runnable class.
This class has members:
int state;
int id;
String name;
Chopstick left, right //to identify the connection with the set
of Chopstick
This class has at least
a constructor and
a run method.
The constructor must initialize the
name and id to identify the philosopher and the two chopsticks to
represent the sharing behavior with the other philosopher
The run must contain a repetition
process waiting for the exact moment to printing the status of the
philosopher THINKING, EATING, or HUNGRY
repetition process {
// set status and print “philosopher #id is thinking”
// Think for some time
// Try to acquire Chopsticks by Tossing a coin
// set status and print “philosopher #id is eating”
// Eat for some time
// Release the Chopsticks by Tossing a coin
}
Q2. (20
points)……………………….....…………..Synchronization
Implement a Syncro class with the appropriate semaphores to work
with the system synchronization. The Chopstick can be used as a
list of Semaphore.
This class has members:
static Semaphore chopstick[N]
static int state[5];
This class has at least two method Putdownchopstick and
Pickupchopstick.
Putdownchopstick(int i):validate conditions and Put down
chopstick with id i
Pickupchopstick(int i): validate conditions and Pick up
chopstick with id i
Q3. (15
points)……………..………………………………Experiments
Set the values for eating time of 0.5 second, a thinking time of
1 second, and test the program with N = 5,6,7, and an extra one
with N equal to some random number between 10 and 20.
Record how many milliseconds each philosopher
spent eating, thinking,
and starving, run the program for about 20 minutes minimum. With
enough time the program should suffer from either starvation, or
deadlock, or unfairness. Describe with one is the most common in
your experiment and why.
Q4. (25 points)…………………………………………………..…
Deadlock
Change the methodology of tossing a coin to select the chopstick
to some fixed strategy that prevent the deadlock. For
example: 4 philosophers attempting to first acquire the
left fork, and then the right fork, and the fifth philosopher doing
the opposite!
Create your own strategy to solve the
problem and run additional experiment to test if your
solution solves the deadlock problem.
A common example that require coordinated access to resources is
a problem called Dining
Philosophers.
Imagine N philosophers sitting at a round table
(are family members and have been successfully
vaccinated). They alternately thinking and eating from a
shared plate with a big spaghetti plate in the middle of the
table.
There is a total of N forks placed at the
table so that each philosopher has 1 fork between himself and his
neighbor to the right and 1 fork between himself and his neighbor
to the left. A philosopher needs the two chopsticks placed left and
right of her plate to eat.
After finishing eating, he must place the chopsticks back on the
table to give a chance to his left and right neighbors to eat. If a
fork is not available, the philosopher must wait for his neighbor
to release it before he can pick it up1.
After obtaining both chopsticks, a philosopher eats for some
time, then releases both chopstick to think again.
Additional conditions to analyses:
THINKING – When philosopher doesn’t want
to gain access to either fork.
HUNGRY – When philosopher wants to enter
the critical section.
EATING – When philosopher has got both the
forks, i.e., he has entered the section.
The philosopher can enter
on HUNGRY, but not yet star eating, that
gap time is the hungry time.
When the hungry time is big enough, we call this starvation.
In this program the student can use any preferred
language and can modify the templates classes in order to solve the
problem in the best convenient way for the language used to
implement the solution.
Q1. (30 points)…………………………...…………... data
abstraction
Implement a Philosopher class. This class must inherit from
thread or runnable class.
This class has members:
int state;
int id;
String name;
Chopstick left, right //to identify the connection with the set
of Chopstick
This class has at least
a constructor and
a run method.
The constructor must initialize the
name and id to identify the philosopher and the two chopsticks to
represent the sharing behavior with the other philosopher
The run must contain a repetition
process waiting for the exact moment to printing the status of the
philosopher THINKING, EATING, or HUNGRY
repetition process {
// set status and print “philosopher #id is thinking”
// Think for some time
// Try to acquire Chopsticks by Tossing a coin
// set status and print “philosopher #id is eating”
// Eat for some time
// Release the Chopsticks by Tossing a coin
}
Q2. (20
points)……………………….....…………..Synchronization
Implement a Syncro class with the appropriate semaphores to work
with the system synchronization. The Chopstick can be used as a
list of Semaphore.
This class has members:
static Semaphore chopstick[N]
static int state[5];
This class has at least two method Putdownchopstick and
Pickupchopstick.
Putdownchopstick(int i):validate conditions and Put down
chopstick with id i
Pickupchopstick(int i): validate conditions and Pick up
chopstick with id i
Q3. (15
points)……………..………………………………Experiments
Set the values for eating time of 0.5 second, a thinking time of
1 second, and test the program with N = 5,6,7, and an extra one
with N equal to some random number between 10 and 20.
Record how many milliseconds each philosopher
spent eating, thinking,
and starving, run the program for about 20 minutes minimum. With
enough time the program should suffer from either starvation, or
deadlock, or unfairness. Describe with one is the most common in
your experiment and why.
Q4. (25 points)…………………………………………………..…
Deadlock
Change the methodology of tossing a coin to select the chopstick
to some fixed strategy that prevent the deadlock. For
example: 4 philosophers attempting to first acquire the
left fork, and then the right fork, and the fifth philosopher doing
the opposite!
Create your own strategy to solve the
problem and run additional experiment to test if your
solution solves the deadlock problem.