Resource hierarchy solution

Write in C language ( will not accept any others than C and will consider ZERO

We discussed both the pthreads library and the dining philosophers problem in class. We also implemented, and discussed, an “arbitrator solution”. You will find with this homework a pthreads implementation of a bad dining philosophers solution that will deadlock. This bad solution is in the file bad_philosophers.c. You will also find with this homework a pthread implementation of a working dining philosophers problem that uses an arbitrator to prevent deadlocks. This solution is in the file good_philosophers1.c. You may modify either of these programs to address any of the questions in this homework. You may also start from scratch if you so choose.

First 1: By yourself, code a version of the “resource hierarchy solution” for dining philosophers. You MAY turn in a fixed/modified version of the bad_philosophers.c code of you can start from scratch. Note that the resource hierarchy solution is discussed in the book and in hundreds of online tutorials. The solution is:

Each philosopher runs in an independent thread and each thread is defined as follows:

While (1) { think for some period of time;

when the fork next to me with the smallest number is available, pick it up; when the fork next to me with the largest number is available, pick it up; eat for some period of time; put one fork down;

put the other fork down; }

Note that the “high” numbered and the “low” numbered fork many NOT always have the same “right fork/left fork” mapping for all the philosopher. The key here is NOT doing left first and then right first or right first and then left first. Rather, it is doing LOWEST NUMBER first and HIGHEST NUMBER second.

Note, there are versions of this program online. It would be best if you do not refer to them and cheat yourself of a chance to figure it out. In any case, you may NOT copy online solutions. Your solution should be your own and it should be THROROUGLY commented to explain exactly what the code is doing. Uncommented code will be scored zero for this question. Your turn in for this question is a C program in a file called good_philosophers2.c. Again, it should be lavishly commented.

Seconds 2: For this question, we’ll define “fair” as meaning that all the philosophers eat about as often as all of the rest of them. How would you determine if a particular algorithm is fair? Using this method, experiment with the arbiter solution and the resource hierarchy solution that you have in good_philosophers1.c and good_philosophers2.c good_philosophers1.c and good_philosophers1.c respectively. Are they both fair? If one is not, provide

your reasoning about WHY it is not fair. Your answer to this question, including any pictures of figures you may want to use, should be in a PDF file called question_2.pdf

3. Third 3: In real programs, it is more likely that any resource could need to grab any resource (chopstick) instead of just some smaller set (chopsticks “close-by”). Consider the program bad_jerk_philosophers.c that implements a new version of the dining philosophers problem. In this case, all the philosophers are jerks and each will, when hungry, make a random choice about which two chopsticks to take from ANYWHERE on the table. The provided code deadlocks fairly quickly. Write two NEW versions of the “jerk dining philosopher problem” that do NOT deadlock. One version should use an arbiter solution and should be called good_jerk_philosophers1.c. The second version should use a resource hierarchy solution and should be called good_jerk_philosophers2.c. As before, both pieces of code should be lavishly commented. Uncommented code will not be graded. Each of the two programs is worth 20 points each.

4. Forth 4: Consider a version of the dining philosophers problem in which any of the N philosophers may grab between 2 and N chopsticks before eating. This means each philosopher may grab ANY number between two and all the chopsticks on the table and those chopsticks need not be anywhere near him (though they could be). Would a resource hierarchy solution for this problem prevent deadlocks? Could such a solution livelock? Could such a solution fail to prevent starvation? Explain your answers for each. You answer, including any diagrams you may wish to include, should be in a single pdf file with the name Four_a.pdf.

5. 5) Fifth 5: Write code that solves the problem in number 4 (A), that prevents both deadlocks and starvation. Call this program Five_b.c You should lavishly comment your code. Explain, in comments, how you designed the program to prevent deadlocks and starvation.

When you are done, create a single zip archive file with ALL your answer files in it. The name of the file should be <your_last_name>_hw2.zip. The zip archive should contain the following files:

good_philosophers2.c - Your resource hierarchy modifications to bad_philosophers.c

question2.pdf - Your answers to problem 2

good_jerk_philosophers1.c - Yourarbitermodificationstobad_jerk_philosophers.c

good_jerk_philosophers2.c - Yourresourcehierarchymodificationstobad_jerk_philosophers.c

Four_a.pdf - written answers for problem 4

Four_b.c - code for problem 5