Homework 5 - Description

Title	Date Posted	Date Due
The Pining K'tahsophers	4 / 24 / 18	5 / 4 / 18 [BUT NO LATE SUBMISSIONS]

For your final rite of passage, it's time for you to solve my homespun variant of a traditional problem in OS synchronization and deadlock avoidance...

What is typically posed as The Dining Philosophers Problem is recast in the LMU spirit as The Pining K'tahsophers.

Reasonably, some of the uninitiated in the audience may not know what a K'tahsopher is; allow me to repair your naivete with a trip down memory lane...

You see, for my CMSI 401 project, our group designed a pioneering in-browser, multiplayer, zombie-survival game by the (inexplicable) name of K'tah; the game has not aged particularly well, but its legend lives on (you can try it below if you please):

Play K'tah!

Problem Details

In the traditional dining philosophers problem, 5 philosophers do nothing but think, get hungry, and then eat from a shared bowl of rice at the center of their table.

However, since K'tah takes place in the land of a post-apocalyptic zombie infestation, we join 5 K'tahsophers, i.e., zombies with an above average intelligence (for zombies) who do nothing but pine (because they have no brains), get hungry, and eat from a shared brain at the center of their table.

What makes them above average intellectually, you ask? Well, they've retained some notion of table manners, and (in part, to ration their meal) eat their brains only with chopsticks, of which they possess only 5 shared between them at their dining table.

In brief, the rules are as follows:

Ktahsophers spend their lives in one of three states: pining, hungry, and eating. Moreover, the only legal transitions between these states are in that order (a Ktahsopher is first pining, then grows hungry, then eats, then returns to pining, etc.). It would NOT be legal for a Ktahsopher to, say, go from the hungry to the pining state.
In order to eat from the brain when hungry, any given Ktahsopher must have both chopsticks at their immediate left and right in-hand.
The Ktahsophers have not exactly mastered communication, so none may explicitly send information of any sort to one another, though it will be obvious when one has obtained a chopstick or not.

From these rules, we have a couple of important questions to answer out of the gates:

Although an amusing pitch (no rebuttals, please), this problem is a classic in OS courses for good reason, as it will expose you to a nontrivial exercise of ensuring synchronization and avoiding deadlock in shared resource settings with many competing processes.

Logistics

Because we are nearing the end of the semester, and far be it from me to saddle you with a bunch of work into finals week, I'll cut you some slack on this assignment:

Consider this a group homework assignment; you may work with your peers to complete this homework and make a group submission (no group more than 5 students) on which you will all receive the same grade.

Specifications

In this assignment, you will simulate the Pining Ktahsophers scenario, allowing each Ktahsopher to pine, get hungry, and eat without any major synchronization or deadlock breakdowns.

To do so, I have provided you with a significant amount of work already done in the following skeleton, with components described next:

Solution Skeleton

Included in this package are the following:

dk-cs.* contain functions specific to handling critical section state transitions of both ktahsophers and their chopsticks.
dk-sync.* contains and initializes the chopstick semaphores and a mutex lock that will be useful for certain critical section handling.
ktahsopher.c contains your implementation of the ktahsopher (more details below).
dk-harness.c contains a test harness to repeatedly simulate the pine-hunger-eat cycle for our ktahsophers.
table.* contains some convenience functions for determining the index of a chopstick on either side of a ktahsopher with the given id, and for selecting the number of ktahsophers at the table.
utility.* contains the randomWait function to simulate some noisy pauses in ktahsopher states.

Intended Behavior

The intended behavior of this package is to facilitate the continuous dining and pining of the ktahsophers without ever entering into an illegal state. It is your (the programmer's) responsibility to use the proper synchronization and deadlock avoidance techniques to accomplish this task.

An illegal state is characterized by:

An improper transition in Ktahsopher state (e.g., going from hungry to pining)
Attempting to use a chopstick that is already being held by another Ktahsopher.
Entering into a deadlock state where each Ktahsopher is holding a chopstick required by another.

Cases 1 and 2 will place a Ktahsopher in the special "out" state, which removes them from the game and constitutes a failure of the system.

Case 3 will cease any sort of progress and the program will lock up.

How do we report this behavior?

Intended Outputs

You are given a statusDisplay function that will detail the state of all chopsticks and ktahsophers, and is printed whenever a Ktahsopher's or Chopstick's state is changed.

The status (borrowed from Dondi, thanks!) will look something like:

  [ _ P | H | E | P | H ]

Above:

Chopstick 0 is currently placed on the table (_), and all other chopsticks are held (|)
Ktahsophers 0 and 3 are pining (P); 1 and 4 are hungry (H); 2 is currently eating (E)

In addition to the statusDisplay (which is given), your solution must indicate when a ktahsopher picks up or puts down a chopstick.

Example Successful Output

Here is what a successfully implemented Pining Ktahsophers output will look like, in perpetuity:

  Starting Ktahsopher test harness...
  Starting ktahsopher 0
  Ktahsopher 0 is pining...
  Starting ktahsopher 1
  Starting ktahsopher 2
  Starting ktahsopher 3
  Ktahsopher 1 is pining...
  Ktahsopher 2 is pining...
  Starting ktahsopher 4
  Ktahsopher 3 is pining...
  Ktahsopher 4 is pining...
  [ _ P _ P _ P _ P _ H ]
  Ktahsopher 4 is hungry.
  [ _ H _ P _ P _ P _ H ]
  Ktahsopher 0 is hungry.
  [ _ H _ H _ P _ P _ H ]
  Ktahsopher 1 is hungry.
  Ktahsopher 4 is picking up chopstick 4...
  [ _ H _ H _ P _ P | H ]
  Ktahsopher 0 is picking up chopstick 1...
  [ _ H | H _ P _ P | H ]
  Ktahsopher 4 is picking up chopstick 0...
  [ | H | H _ P _ P | H ]
  [ | H | H _ P _ P | E ]
  Ktahsopher 4 is eating...
  Ktahsopher 4 is done eating.
  Ktahsopher 4 is putting down chopstick 4...
  [ | H | H _ P _ P _ E ]
  Ktahsopher 4 is putting down chopstick 0...
  [ _ H | H _ P _ P _ E ]
  Ktahsopher 0 is picking up chopstick 0...
  [ | H | H _ P _ P _ E ]
  [ | E | H _ P _ P _ E ]
  Ktahsopher 0 is eating...
  Ktahsopher 0 is done eating.
  [ | E | H _ P _ P _ P ]
  Ktahsopher 4 is pining...
  Ktahsopher 0 is putting down chopstick 0...
  [ _ E | H _ P _ P _ P ]
  Ktahsopher 0 is putting down chopstick 1...
  [ _ E _ H _ P _ P _ P ]
  [ _ P _ H _ P _ P _ P ]
  Ktahsopher 0 is pining...
  Ktahsopher 1 is picking up chopstick 1...
  [ _ P | H _ P _ P _ P ]
  Ktahsopher 1 is picking up chopstick 2...
  [ _ P | H | P _ P _ P ]
  [ _ P | E | P _ P _ P ]
  ...

Note: above, there are some allowable synchronization quirks from the ktahsopher threads running in parallel, but none that violate the rules of valid states as defined above.

So, plainly, we should look at the alternative...

Example Failed Output

Whenever a Ktahsopher violates one of the valid state conditions, they are placed in the "out" state, and represented with an "X" in the statusUpdate.

  Starting Ktahsopher test harness...
  Starting ktahsopher 0
  Starting ktahsopher 1
  Ktahsopher 1 is pining...
  Ktahsopher 0 is pining...
  Starting ktahsopher 3
  Starting ktahsopher 2
  Starting ktahsopher 4
  Ktahsopher 3 is pining...
  Ktahsopher 2 is pining...
  Ktahsopher 4 is pining...
  [ _ H _ P _ P _ P _ P ]
  Ktahsopher 0 is hungry.
  [ _ H _ P _ P _ P _ H ]
  Ktahsopher 4 is hungry.
  [ _ H _ H _ P _ P _ H ]
  Ktahsopher 1 is hungry.
  Ktahsopher 0 is picking up chopstick 1...
  [ _ H | H _ P _ P _ H ]
  Ktahsopher 4 is picking up chopstick 4...
  [ _ H | H _ P _ P | H ]
  Ktahsopher 1 is picking up chopstick 1...
  ***** Chopstick pickup failure!
  [ _ H | X _ P _ P | H ]
  Ending ktahsopher 1
  Ktahsopher 0 is picking up chopstick 0...
  [ | H | X _ P _ P | H ]
  Ktahsopher 4 is picking up chopstick 0...
  ***** Chopstick pickup failure!
  [ | H | X _ P _ P | X ]
  Ending ktahsopher 4
  [ | E | X _ P _ P | X ]
  ...

Above, we see that two Ktahsophers, unprotected by proper synchronization, attempt to pickup chopsticks that are already held by other Ktahsophers, thus entering an illegal state and kicking them from the table for poor manners.

In the provided skeleton, Ktahsophers are in an unordered feeding frenzy and will try to eat at the same time as well.

Your job is to prevent these very scenarios!

Available Tools

You will only need to modify the ktahsopher function in ktahsopher.c to complete the above, but will use tools from the other files given.

Important details:

Ktahsophers are indexed starting at 0, and have a left chopstick indexed equivalently, with the right chopstick equal to their index + 1.
chopSem is an array of semaphores indexed according to the chopstick they represent; a locked chopSem means that a Ktahsopher is holding it.
mutex is a single lock that can be used to ensure synchronization in various critical sections of each ktahsopher's actions.

Here are some useful functions that are available to you:

setKtahsopherState(id, state) sets the state of the ktahsopher with the given id to the given state, an enum with values {pining, hungry, eating}
pickup(id, i) / putdown(id, i) used to pickup or putdown chopstick i from the ktahsopher with the given id. This is used to indicate that a chopstick is being held or not for error checking, and should be used in a critical section once a chopSem has been acquired.
leftChop(id) / rightChop(id) returns the corresponding chopstick (left / right) of the given ktahsopher's id

The rest of the puzzle is up to you!

Simplifications & Restrictions

Just a couple of notes for this assignment:

Although your solution should not incur any issues with synchronization nor deadlock, we will not place any unreasonable restrictions on avoiding starvation (i.e., that a Ktahsopher doesn't get to eat for some time). It is expected, however, that your Ktahsophers will be able to eat at reasonably similar intervals (can compare number of times each Ktahsopher eats within ~30 seconds of running).

Additionally, your solution must support the ability of multiple Ktahsophers to be eating at once! To do otherwise would be wasteful (all those idle chopsticks!).
Your solution *may not* add any global data structures that are not already defined, and *may not* modify anything outside of the clearly indicated segments for you to add code.
You *may* however add any helper functions to ktahsopher.c that aid your solution.

Submission

What

Submit your zipped, completed solution from the skeleton above on Brightspace!

How

We will (unfortunately) be using Brightspace to submit this assignment, though you should always be using version control to organize your assignments (even text)!

To submit your assignment:

Find this assignment listing on Brightspace.
Upload the .zip file containing your submission.
Make sure to click "submit" after the upload is complete!