2015/semaphores

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

Today's code can be found in the cs61-exercises repository in the l20 directory. We'll start with the Dobby the House Elf problem, since hardly anyone got to that last week. (The code has been copied from l19 to l20).

Help the House Elves

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.

We have provided most of the code to implement Dobby and the elves, but alas, we've forgotten to synchronize them! Can you possibly help us by selecting the right synchronization primitive(s) to solve this problem and adding them to the code in dobby.c? Since this is from last week, limit yourselves to mutexes and condition variables for this part. Next, we'll see whether semaphores work better or not.

At the end of the main function, you'll see a comment "XXX Figure out how to wait on elves and when to print out Dobby's message." That's where a lot of your synchronization code will go, although there will undoubtedly be some initialization code in main as well as some synchronization code in the elf thread function.

Take a principled approach!

1. What shared state must you maintain?

2. How will you protect that state?

3. How will you detect that an elf is finished (this is tricky; the obvious answer won't work and you'll undoubtedly need to update your answer to #1 to address this)?

4. How will you make dobby (main) wait?

Next, let's try this with 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. 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.

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).

Wrapping Up

And as per usual, please complete this survey.