Deadlocked Diners Edit on Github

The learning objectives for Deadlocked Diners are:

• Synchronization
• Deadlock / Livelock / Starvation
• Coffman Conditions
• Dining Philosophers
• Messing with Interns

We suggest you read the following from the wikibook before starting Deadlocked Diners:

• Deadlock, Part 1: Resource Allocation Graph
• Deadlock, Part 2: Deadlock Conditions
• Deadlock, Part 3: Dining Philosophers

You are creating a start up that allows companies to rent code monkeys interns for a project. They are billed by the number of days it takes to complete the project. The reason why companies want to rent interns is because they realized they do not need dedicated interns, since they do not always have projects at hand (sometimes they are contemplating about life). Basically a company in 1 of 3 states: “trying to rent interns”, “working with interns” or “having a board meeting”. They came to the conclusion that a possible way of handling this dilemma is to simply overwork the interns by having them work for 2 companies, just not at the same time.

This is where you come along….

The scenario is as follows. Each of the companies practices pair programming, so you will need to find a way to schedule the interns so that we can continue to bill each company as often as possible. This means that work on a project can only be completed when the company has TWO interns assigned to it. There are n companies and k interns in this scenario. For some odd reason the ith company likes to work with intern i%k and (i+1)%k… A company might decide to give the interns a break from the project, in which case they are free to be assigned to another company that wants them and won’t be reassigned until said company gives them a break.

Your mentor has written a simulation of this scenario with a synchronization strategy, but it does not work. The mentor left a note that reads:

Dear intern, I have written a simulation of the ‘intern for rent’ program, but sometimes a company grabs one intern, then waits for the second intern, which wont be released until the first intern is given a break…

• Read Resource Allocation Graphs and Deadlock Conditions to have all the knowledge you will need for this assignment.
• We recommend you fill out this Google Form BEFORE you write any code (see the section on testing for details on gathering data). It isn’t graded but should help you wrap your head around the problem conceptually.
• Read simulator.c, bad_company.c, and company.h until you have a good sense of what the code is doing (Nothing will make sense until you do).
• Overwrite good_company.c with your correct solution.

We provided you with a Makefile.

Typing

make

will create the good_company and bad_company executable. For both the good_company and bad_company executable you can execute them with 2 required arguments and 3^rd optional argument as follows:

./bad_company 5 6 100000

will run the bad solution with 5 companies and 6 interns and with a delta of 100000. Delta is approximately how long an operation takes in microseconds (read the source code for more details).

If you see something like this:

Company 0 used our services for 2083 billable days.
Company 1 used our services for 2164 billable days.
Company 2 used our services for 2456 billable days.
Company 3 used our services for 2826 billable days.
Company 4 used our services for 3733 billable days.

Total Billable days : 13262

then the simulation terminated successfully. This does not mean your solution is correct. There may still be race conditions, so it it up to you to test your code thoroughly with all sorts of parameters. If the simulator stops without billing the companies just hit CTRL+Z.

Your grade depends on having a good working solution.

A good solution must have the following:

• No Deadlock
• No Livelock
• Performant
  • Performance will be judged against the reference solution (good_company_reference) and measured by total billable days.
  • You must be within 90% of the reference solution to receive full points.
• Fair (all companies should get a roughly equal number of billable days)
  • You must be within 90% of than the reference solution to receive full points.
  • Fairness is determined by min_billable_days/max_billable_days where higher is better.
• Must adhere to the rules of the scenario
• Run with a single intern should not cause deadlock AND not burn cpu cycles
• A valid solution should not know about the number of interns or or number of companies

Please read details on Academic Integrity fully. These are shared by all assignments in CS 241.

We will be using Subversion as our hand-in system this semester. Our grading system will checkout your most recent (pre-deadline) commit for grading. Therefore, to hand in your code, all you have to do is commit it to your Subversion repository.

To check out the provided code for deadlocked_diners from the class repository, go to your cs241 directory (the one you checked out for "know your tools") and run:

svn up

If you run ls you will now see a deadlocked_diners folder, where you can find this assignment! To commit your changes (send them to us) type:

svn ci -m "deadlocked_diners submission"

Your repository directory can be viewed from a web browser from the following URL: https://subversion.ews.illinois.edu/svn/sp17-cs241/NETID/deadlocked_diners where NETID is your University NetID. It is important to check that the files you expect to be graded are present and up to date in your SVN copy.

We strive to provide the best assignments that we can for this course and would like your feedback on them!

This is the form we will use to evaluate assignments. We appreciate the time you take to give us your honest feedback and we promise to keep iterating on these assignments to make your experience in 241 the best it can be.
https://goo.gl/forms/z06gBY7MocFDrE3S2