COEN 346 – Operating Systems
Assignment 02
Dining Philosophers

Team Member:
Shulang Tan ID: 40020482
Ruowei Lin ID: 40051150




Department Name: Electrical and Computer
Engineering University Name: Concordia University
Country: Canada
Date: 7/11/2021





Introduction
In this assignment, we want to solve the dining philosopher problem. The key to solve
this problem is to make sure the action of picking up chopsticks is atomic, so we use
synchronized functions. A philosopher can eat when both chopsticks are available,
which can ensure deadlock-freedom. We also use a queue to decide the order in which
philosophers eat to prevent starvation. The philosophers are free to leave in the middle,
but no new philosophers can join the table.

Classes
• Philosopher
• Monitor
• DiningPhilosophers
• BaseThread

Philosopher
Implements the actions of philosophers. Each iteration, philosophers will take
following actions in sequence: eating (and using pepper shaker), thinking, talking (we
set the chance to 50%), leaving(we set the chance to 10%). Philosophers must send a
request to the monitor before they can take any action (except thinking).

Monitor
The monitor class is used to monitor all philosopher’s actions. I use several variables
to indicate the availability of resources, such as chopsticks[]. An eatingQueue is used
to decide the order in which philosophers eat. The philosopher who wants to eat (tries
to pick up chopsticks) will be put on the end of the eatingQueue. A philosopher can eat
iff the following requirements are met: his left- and right-hand side chopsticks are both
available; he is on the head of the eatingQueue. This strategy is used to ensure
starvation-freedom.

DiningPhilosophers
The main function. Let user decides the number of philosophers and begin their dining.

BaseThread
Base thread inherited from thread class. Never changed.

Program Flow
1. Let user decides the number of philosophers, spawn the philosophers.
2. Each thread (philosopher) takes actions in sequence described above; they are
free to leave in the middle.
3. The monitor will decide whether they can take the action, if not, they will be
forced to wait. When any philosopher finish eating, using pepper shaker or
talking, all philosophers who is waiting will be notified.
4. After everyone finish their dining iterations (or leave), the program terminates.

Compile results
Let there be ten philosophers. Since the output has too many lines, I will only show the
beginning and the end of the output.
Begin:

We can see that at the beginning of the first iteration of dining, only philosopher 1 and
philosopher 3 are eating, even if there are many pairs of chopsticks available. At this
moment, the philosopher 2 is on the head of the eating Queue, the evidence is that when
the philosopher 1 and philosopher 3 finish eating, the philosopher 2 begins eating.
Because of the eatingQueue, in the first iteration, the order in which philosophers eat
depends on the order in which their threads start. However, this phenomenon disappears
as the second iteration begins, because philosophers take different time to think and eat,
and they also randomly decide whether to talk or not.
End:


We can see that, at the end of dinner, there is no philosopher who have many iterations
that need to be finished, which means using eatingQueue can achieve starvation-
freedom.

Conclusion
The key to achieve deadlock-freedom is letting philosophers eat if they can pick up two
chopsticks simultaneously. The key to achieve starvation-freedom is using an
eatingQueue and follow the FIFO rule, because when a philosopher wants to eat, he
will be put into the queue and have a chance to eat. The philosophers are allowed to
leave in the middle, and the rest of philosophers can still finish their dinner as normal.
However, no more philosophers can join in the dinner because wherever they sit, he
and a philosopher next to him will starve, because there is no chopstick in between
them, they can never pick up two chopsticks.


欢迎咨询51作业君