Exercise 3: Outfoxed!§

The game Outfoxed is a cooperative 'whodunit' deduction game for children 5 years or older. Some of you may remember this from preschool! In this exercise, you are asked to write a multi-threaded program that reproduces some elements of this game. Since the game is designed for 5-year-olds, implementing the logic should not be hard - but the multi-threaded aspect will require you to learn about synchronization strategies between threads that may be useful for the second project!

Your program will be in outfoxed.c (which you write from scratch), which will then be linked with outfoxed-driver.c as described below.

When you are done, submit a single file, outfoxed.c, as ex3!

Thus, you must run your outfoxed executable with

loading

A driver script that will be used for grading is available in ~cs3214/bin/checkoutfoxed.py. Run it with:

loading loading

Update: The driver script is designed to perform thorough testing to catch mistakes. It will run your solution on a single CPU in order to test whether your code uses busy-waiting, and flag it if so. In addition, it will vary the number of CPUs on which the code is run to make it more likely for latent race conditions or order violations to manifest themselves.

There is no separate handout for this exercise - all information is contained in the source code of outfoxed.h, which you should read next.

Good luck sleuthing!

FAQ§

Is the driver code thread-safe?§

No! Results will be undefined if, for instance, multiple chicken detectives try to eliminate suspects at the same time. It is your responsibility to prevent this.

Can we change the driver code?§

Only for your own testing debugging, not for grading.

How can I see more information about the events occurring in the game?§

Set the environment variable VERBOSE to 1, i.e., run with

env VERBOSE=1 ./outfoxed  <yourcode>

If my program sometimes works, how will this be graded?§

Errors in multi-threaded code can be intermittent, which is why we run your program multiple times. Each run comprises 50 games. The program will abort() whenever an error occurs. The presence of even a single failed run indicates a serious error. Thus, our grading scale will award full credit for successfully completing all runs, and 60% or less partial credit if some runs fail.

What tools can I use to help me debug?§

Helgrind and DRD are two race-condition checkers installed on the rlogin machines. To use them, run your program with

valgrind --tool=drd ./outfoxed 

or

valgrind --tool=helgrind ./outfoxed 

A third (and faster) tool is Google Thread Sanitizer. To use it, you must compile your program with the clang compiler and the -fsanitize=thread flag.

clang -fsanitize=thread outfoxed-driver.c outfoxed.c -o outfoxed-clang
./outfoxed-clang  <yourcode>

Do we need to use atomics?§

No, the exercise can be solved with just mutexes, semaphores, and condition variables.

How do I test my program on a single CPU?§

Use the taskset command which allows you to restrict the CPUs on which a program's threads are eligible to run.

Do we have to wear detective hats while doing this exercise?§

Wearing detective hats is optional.