Deadlock
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 basic 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 broken into two parts: Activity Set A – Coding (80 points) You will receive 20 points each for correctly implemented versions of the following programs: • Standard Dining Philosophers Problem with the Waiter/Arbiter Solution • Standard Dining Philosophers Problem with the Resource Hierarchy Solution • Random Dining Philosophers Problem with the Waiter/Arbiter 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 (7.1.3 in 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. random_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_arbiter.c : The program should be a modified version of standard_noprotection.c that adds code to implement the arbiter (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. random_arbiter.c : The program should be a modified version of random_noprotection.c that adds code to implement the arbiter (waiter) solution. random_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 rubric: 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. Correct Implementation (7 points) Your code must indeed implement the algorithms as described in the Wikipedia page. You will receive full credit for a fully correct implementation. Implementations that “work”, but do not match the correct 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 (arbiter 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, roughly, 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 preferred 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 correspond 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 correspond 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 arbiter (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 correspond to a philosopher never being allowed to eat. How might you go about proving that the arbiter 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 arbiter 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_arbiter.c : The program should be a modified version of standard_noprotection.c that adds code to implement the arbiter (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. random_arbiter.c : The program should be a modified version of random_noprotection.c that adds code to implement the arbiter (waiter) solution. random_hr.c : The program should be a modified version of random_noprotection.c that adds code to implement the resource hierarchy solution. answers.pdf : Your answers to the discussion questions shown in green text in the previous section.