From CS61
Jump to: navigation, search

Learning Objectives

  • Increase comfort level using pthreads
  • Start solving more complex synchronization problems
  • Become familiar with using semaphores for synchronization

Getting Started

Since many people found the lock and CV implementation of Dobby challenging, I went through a solution to it in the video for class today. If you did not get a chance to watch the video, raise your hand and have a staff member help you through the (first) Dobby problem. The structure of this problem is similar to many we find in real systems: waiting for a collection of things to happen, when you need to account for each thing independently. (This is what processes do when they exit! They have to clean up state from their children.) Once you are comfortable with the lock + CV implementation of Dobby, move on to the next part of the exercise.

Today's code can be found in the cs61-exercises repository in the l21 directory. (As before, we copied a bunch of code from the l20 directory.

Help the House Elves

By now you should be familiar with Dobby's life, but in case you've forgotten, it's here (again)!

Dobby has been put in charge of all the kitchen House Elves at Hogwarts. Each elf must complete some the following series of tasks before it can leave for the day:

1. Prepare sumptious feast. 2. Clean up after messy Hogwarts students. 3. Say, "Harry Potter is the greatest Wizard Ever." Whenever an elf completes one of its tasks, it announces what it just did. When an elf has completed all of its tasks, the supervisor dismisses the elf by saying "Thanks for your work, Elf N!" where N corresponds to the elf's ID number.

At the beginning of the day, Dobby (the main program) opens the kitchen and lets the elves inside (starts their threads). At any given moment, Dobby and possibly multiple other elves are working. Dobby is not allowed to dismiss an elf until that elf has finished working, but Dobby must dismiss an elf soon after the elf completed his/her work; he can't wait until all the elfs are done with their work.

You've now solved this problem once using mutexes and condition variables, so now we're going to solve it a couple of different times using semaphores.

You'll find the pt61_sem implementation in the directory too (two files: semaphore.c and pt61_sem.h.

The file dobby-sem.c is identical to the file you started with in the previous exercise, but this time you should try to solve it using semaphores.

Part One

Let's start with an easier problem: Dobby doesn't need to identify each elf; he just needs to say, "Thank you Elf!" See if you can get that to work with semaphores.

Part Two

Now, once you've got that working, go for the big win: figure out a way to identify which elf is exiting and print out the compete message "Thanks for your work, Elf N!" (you're only allowed to modify the elf thread).

The Dining Philosopher's Problem

If you don't get to this one, that's OK, but this is a classic Computer Science Synchronization problem and we wouldn't be doing our job if we didn't introduce you to it! There is always a good story line having to do with forks and pasta, but our rendition is as follows:

Five silent philosophers are sitting around a (round) table. There is one chopstick placed between each pair of philosophers. A philosopher's life is spent alternating between thinking and eating. Obviously, eating requires that a philosopher obtains two chopsticks (philosophers are quite polite and only ever take the chopsticks on either side of them; reaching across the table to grab a chopstick would be the height of bad manners). Equally obviously, each chopstick can only be used by a single philosopher at a time. (We are ignoring the health issues surrounding the fact that philosophers do end up sharing chopsticks.) When a philosopher has finished eating s/he places the chopsticks back down on either side of him/her.

A correct solution should:

  • Ensure that no philosopher starves (quite literally). This means that the algorithm can theoretically run forever with each philosopher simply alternating between thinking and eating.
  • Be deadlock free (else you would fail the above condition).
  • No two philosophers can be using the same chopstick.
  • No chopstick can be in use by more than one philosopher at any point in time.
  • Achieve as much parallelism as possible (i.e., you can't simply use one big lock).

We've set up the code for you again. You'll find philosopher.c containing an unsynchronized philosopher function and a main loop that creates the philosopher threads and then does a timed wait on one of them for 10 seconds at which point the main routine kills all the philosophers.

You may use whatever state and synchronization primitives you wish, as long as you do something better than "one big lock." That is, you may have mutexes to protect state, but you can't solve the problem by just acquiring one big lock and assigning two philosophers to eat. This problem is pretty tricky, so don't get discouraged if it isn't obvious how to solve it. Have fun with it -- talk through different approaches with your tablemates and see if you can come up with something that works.

If you solve this and have more time, try solving it with a different set of primitives!

Wrapping Up

And as per usual, please complete this survey.