Ancient CS 61 Content Warning!!!!!1!!!
This is not the current version of the class.
This site was automatically translated from a wiki. The translation may have introduced mistakes (and the content might have been wrong to begin with).

Programming with Pthreads

Learning Objectives

Getting Started

Today's code can be found in the cs61-exercises repository in the l19 directory. Since you should all be familiar with the pingpong problem, we'll begin be examining a pthread-based implementation of the same problem.

Meet Ping and Pong

The file pingpong.c contains an unsynchronized version of the pingpong program. Take a look at the source code and become familiar with the use of the pthread_create and pthread_join APIs. Build and run the program.

You may notice that it appears to be synchronized perfectly! Since the threads use the msgcount to decide whether it's their turn to run, the threads alternate perfectly. However, there is still a race condition.

1. Can you find the race condition? Hint 1 Hint 2 Hint 3

Spend a few minutes trying to find the race condition. If you can't find it, take a look at the hints. If you still can't find it, go ahead to the next part (we're going to show you).

Triggering the race condition

Pingpong2 is still an unsynchronized version of this program, however we've changed two things: First, we've created two ping threads and two pong threads. Second, we've expanded the line

   (*infop->msgcount)++

into multiple lines and inserted a usleep.

Build and run pingpong2 and carefully examine the output.

2. Were you able to trigger the race condition (you should see multiple pings or multiple pongs in a row)?

Takeaway

Even when a program runs perfectly (e.g., pingpong), it may not be properly synchronized. Synchronization bugs often manifest once a system gets exercised under heavy or unexpected load. It's critical to think carefully about concurrent code and develop testing schemes to stress your solutions.

If you want to test solutions to the exercises as you go, you can pipe your pingpong output through check.awk by doing this:

   % ./pingpong2 | awk -f check.awk

If your pings and pongs alternate, you'll get no output; if the check script ever sees two pings (pongs) in a row, you'll get a message.

Race condition, go away!

Now it's time for you to try your hands at synchronization. Fix pingpong2 using a single mutex.

There are two parts to doing this: 1. The mechanics of creating and managing a mutex, and 2. Identifying the critical section and applying the mutex properly.

Mutex Mechanics

Consider the following questions as you set up your mutex.

3. Where should you create and destroy your mutex?

4. Where should you store your mutex so that all the threads access the same mutex?

Identifying and Protecting Critical Sections

5. What is the critical section of your code?

6. How can you place the mutexes to protect the critical section?

When you've gotten pingpong2 to work correctly, move on to the next exercise.

Condition Variables

Although we are using a blocking lock synchronization primitive, this program still exhibits busy-waiting. That is, it is possible for a thread to obtain the mutex and still not have work to do.

7. Describe how the busy-waiting can occur?

We'll start with a single condition variable to get rid of the busy-waiting. Here are the questions to consider as you implement a cv-based solution. (You will want to start with your mutex solution to build the cv-based solution.)

8. What is the condition you'll be checking?

9. What API will you use to wait while the condition is not true?

10. Will you check your condition in an if statement or a while loop?

11. Where will you acquire/release the mutex?

12. Where will you signal or broadcast?

13. Do you need to do a signal or a broadcast?

If you've gotten this far, you're doing great, BUT we still have some unpleasant aspects about our program. In particular, because we have multiple ping and pong threads, we can still end up waking threads needlessly - that is, a ping thread might wake up another ping thread, which is annoying and inefficient. You can address this problem by using multiple condition variables.

The big design questions to ask are:

14. How many condition variables should you use?

15. How many mutexes should you use?

16. How do you use them?

Go for it.

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? 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!

17. What shared state must you maintain?

18. How will you protect that state?

19. 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 #17 to address this)?

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

Wrapping Up

Please take a moment to complete this survey.