OS_HW_05_F2020
Assignment Five: Deadlock Prevention
EECE 4029: Operating Systems and Systems Programming
ELTN 4022: Operating Systems
Department of Electrical Engineering and Computer Science
University of Cincinnati, Cincinnati OH
Revision Date: Oct 24, 2020
Purpose
In this assignment, you will implement two different deadlock avoidance methods in two different
versions of the dining philosophers problem. Once you have implemented them, you will run some
asic fairness tests, report your results, and provide an explanation for any “unfairness” you may
have seen.
Activity Summary
This assignment is worth 100 points and is
oken into two parts:
Activity Set A – Coding (80 points)
You will receive 20 points each for co
ectly implemented versions of the following programs:
• Standard Dining Philosophers Problem with the Waite
A
iter Solution
• Standard Dining Philosophers Problem with the Resource Hierarchy Solution
• Random Dining Philosophers Problem with the Waite
A
iter Solution
• Random Dining Philosophers Problem with the Resource Hierarchy Solution
You will be provided with implementation of both the “standard” and “random” dining
philosopher problem. These reference implementations have NO deadlock prevention and
absolutely will deadlock when you run them. You are to modify each of these as needed to
create the four programs above.
Activity Set B – Analysis (20 points)
You will run your four programs with a setting of 10 philosophers and 10 million meals
available. You will be asked to collect statistics on how many times each philosopher is allowed
to eat and produce a histogram of the frequencies that each philosopher was allowed to eat.
You will likely determine that ONE of the four programs above is not fair in the sense that not
all philosophers are accorded the same opportunities. You will asked a series of discussion
questions about this situation and will develop an understanding of the source of the observed
unfairness and an understanding that one should profile and/or think about any interactions
that might occur between specific thread code and avoidance algorithms and how that might
affect metrics of performance like speed and fairness.
Background Reading
Before beginning this assignment, be sure to read the textbook section on the Dining Philosopher
Problem XXXXXXXXXXin the Operating Systems Concepts 10th edition). Also review the Wikipedia page on
the topic at https:
en.wikipedia.org/wiki/Dining_philosophers_problem. The rest of this
assignment writeup assumes you are familiar with the concepts introduced in both sources.
Activity Set A: Programming Exercises (80 points total for Activity A)
You are provided with two commented programs:
standard_noprotection.c: This program implements the standard dining philosophers problem
as described in the book and in the Wikipedia article. Specifically, in THIS version, a hungry
philosopher will attempt to get the chopsticks immediately to the left and right of the seating
position. Each philosopher is implemented as a separate pthread. This version also has a “finite
number of meals”. All threads will end when that number of meals have been consumed. In the
default version of the code I’m giving you, there are 10 philosophers and 10 million meals available.
As there is no deadlock protection. This code will DEFINITELY deadlock before all 10 million meals
are consumed.
andom_noprotection.c: This program implements a modified dining philosophers problem in
which each philosopher can choose to use ANY two chopsticks (forks) on the table. As before, each
philosopher is implemented as a separate pthread. This version also has a “finite number of meals”.
All threads will end when that number of meals have been consumed. In the default version of the
code I’m giving you, there are 10 philosophers and 10 million meals available. As there is no
deadlock protection. This code will DEFINITELY deadlock before all 10 million meals are consumed.
You should write FOUR programs, using the above two as a starting points, as follows:
standard_a
iter.c : The program should be a modified version of
standard_noprotection.c that adds code to implement the a
iter (waiter) solution.
standard_rh.c : The program should be a modified version of standard_noprotection.c that
adds code to implement the resource hierarchy solution.
andom_a
iter.c : The program should be a modified version of random_noprotection.c
that adds code to implement the a
iter (waiter) solution.
andom_hr.c : The program should be a modified version of random_noprotection.c that adds
code to implement the resource hierarchy solution.
You should turn in FOUR program files with the above names that contain the required code. Each
will be separately graded using the following ru
ic:
Comments (8 points) You must include meaningful comments that explain what you did and why you did it.
ANY code you add to the templates MUST be commented, no matter how trivial. Explain why everything you
added is there and explain how what you did matches the algorithms as described in the Wikipedia article.
Co
ect Implementation (7 points) Your code must indeed implement the algorithms as described in the
Wikipedia page. You will receive full credit for a fully co
ect implementation. Implementations that “work”,
ut do not match the co
ect algorithm, will lose points proportional to the number of deviations from the
standard.
Lack of Deadlocks (5 points) Your code MUST not deadlock for a least the 10 million “meals” served to the
philosophers. If you don’t deadlock, you’ll get these points even if you lost points on the previous two
sections.
Note, you MUST put your code in files with names as indicated.
Activity Set B: Analysis (20 points total for Activity B)
When I ran my solutions to the four problems, and kept track of how many of the 10 million meals
each philosopher got to eat for them, I got the following data:
The x-axis is the “philosopher number” – each philosopher gets one set of four bars. The y-axis is
the number of meals (out of 10 million) each philosopher got to eat, the four colored bars are the
number of meals that philosopher got to eat for each of the four different combinations of
protection method (a
iter or resource hierarchy) and problem type (standard or random). You may
note that three of the four seem… rather fair…. As all of the ten philosophers got to each eat,
oughly, 1 million meals. Of course, there IS that one that’s a little weird. For some reason,
philosophers (for one of the protection methods) are prefe
ed if they have smaller identification
numbers. Although all four solutions prevent deadlocks, and no philosopher starves (I.E. is put in a
situation where eating is NEVER permitted), clearly they are not – under one set of rules – being
treated fairly. In a PDF to be turned in, answer the following questions:
1) Create your own histogram of how often each philosopher gets to eat with respect to each
algorithm. In your histogram, CLEARLY indicate which bars co
espond to each of the four
programs you wrote. Include your histogram in the PDF. Clearly indicate the meanings of
the x and y axes and indicate which bars co
espond to each of the four algorithm/problem
pairs you coded. (5 points)
2) Do you think that it is possible to prove that none of these solutions deadlock with the
experimental data you collected? Why or why not? If you think you can, why do you think
the data is sufficient. If you think you cannot, then what COULD you do to offer such a
proof? (5 points)
3) What would you need to do to establish that the a
iter (waiter) solution to this problem is
FREE of starvation? Starvation occurs when one or more threads never get to run in their
critical sections. In the example problem, it would co
espond to a philosopher never being
allowed to eat. How might you go about proving that the a
iter solution is STARVATION
FREE. You don’t need to provide a formal proof, but do provide a discussion of what facts
you would need to establish to prove prevention of starvation. Hint: This might consider
thinking about how the mutex operators themselves are implemented along with the
mechanics of the a
iter solution (5 points)
4) Once you’ve identified which of your four programs was unfair, examine the code and
speculate on how it is interacting with the allocation of resources (chopsticks) to create the
unfairness. In other words, explain why philosophers with lower ID numbers seem to get
preferential treatment. Again, a formal proof is not necessary, but you should at the very
least show, by discussion, a few examples of how the unfairness arises (5 points).
Deliverables
Turn in, on canvas, the following files:
standard_a
iter.c : The program should be a modified version of standard_noprotection.c that adds code to
implement the a
iter (waiter) solution.
standard_rh.c : The program should be a modified version of standard_noprotection.c that adds code to implement
the resource hierarchy solution.
andom_a
iter.c : The program should be a modified version of random_noprotection.c that adds code to
implement the a
iter (waiter) solution.
andom_hr.c : The program should be a modified version of random_noprotection.c that adds code to implement the
esource hierarchy solution.
answers.pdf : Your answers to the discussion questions shown in green text in the previous section.