Problem set 6: Breakout

This problem set will teach you some useful strategies for synchronization using a simulator for a breakout-like game.

About Breakout

Breakout, one of the earliest arcade video games, features a ball that moves diagonally on a rectangular playing field and breaks through colored bricks.

In CS 61, a breakout board is a rectangular grid of cells with one or more diagonally-moving balls. Each cell can contain at most one ball. Balls bounce off the edges of the playing field and off each other. Board cells can be sticky; when a ball hits a sticky cell, it stops moving until dislodged by another ball. Board cells can also be warps. Warp cells are paired: when a ball hits one warp, it falls off the board for a while into a warp tunnel, then reappears at the paired warp end and continues moving.

The logic for pong boards and balls is implemented in board.cc and breakout61.cc.

Getting started

Merge our problem set 6 code into your repository with git pull handout main. This will merge our code with your previous work. If you have any “conflicts” from problem set 5, resolve them before continuing further. Run git push to save your work.

Type make, and then try the command ./breakout61 -d0.05 -p0.05. Your terminal should fill up with board pictures like this:

Breakout page

The O characters are balls moving around the board. _ characters represent sticky cells and the colored numbers represent the bricks in the process of being broken. You should be able to see the balls bounce off the board edges and bricks and even off each other.

Goals

Your goal for this problem set is to support thread safety with efficient synchronization. The ./breakout61 program tests this goal.

Part 1: Thread safety

The breakout61 program simulates a Breakout board with multiple balls, sticky cells, and warp tunnels. Each ball runs in its own thread.

breakout61 takes the following arguments:

You already tried ./breakout61 -d0.05 -p0.05 and saw the bouncing balls. Now try the command ./breakout61, without a delay. We get an almost immediate assertion failure! Or try delay and thread sanitization: make SAN=1 breakout61 && ./breakout61 -d0.1. The thread sanitizer is very unhappy and reports many “data races.”

The handout code is not thread-safe; you must make it thread-safe. Given any combination of -d, -W, -s, -b, -w, and -h arguments (but not including -p):

Notes

  1. The signal handler that supports -p is inherently thread-unsafe. This would be very painful to fix. Just don’t use -p when the thread sanitizer is on.

  2. The thread sanitizer is incredibly helpful. It will detect errors more quickly without -d.

  3. You may change any code and add structure members.

  4. It is not too difficult to avoid all data races using a coarse-grained locking strategy. Do that first. Fine-grained parallelism and blocking require more work.

  5. Think carefully about your fine-grained parallelism strategy. If you’re not careful, your code will deadlock. Consider reducing the amount of parallelism you support in favor of ease of programming. It is OK if your fine-grained parallelism strategy causes balls to cluster together as a side effect.

  6. The C++ std::mutex and friends have some restrictions that may surprise you. For example, you cannot have a std::vector of mutex objects; instead, you must create a plain old dynamically-allocated array using new std::mutex[SIZE].

  7. Use a command such as ./breakout61 -b24 -s18 -d0.1 to test for blocking. If your laptop fan starts running, your code is polling rather than blocking. (Or use Linux top or Mac OS X top -o cpu in a terminal window; a polling breakout61 thread will appear at the top of the list.)

  8. The -W argument adds complexity. Test -W4 for race conditions, fine-grained parallelism, and blocking after you get everything else working.

  9. Useful command lines:

    • ./breakout61 with sanitizers to check for race conditions.
    • ./breakout61 -W4 with sanitizers to check for race conditions involving warps.
    • ./breakout61 -p0.1 and ./breakout61 -p0.1 -W4 without sanitizers to check for deadlock (balls should keep moving around).
    • ./breakout61 -b24 -s18 -d0.1 and ./breakout61 -W4 -d0.1 to check for blocking.
    • make SAN=1 check runs automated tests. The grading server also supports some automated tests, and we may add more.

Extra credit part 2: Paddles

This part is extra credit!

In part 2, you’ll add a paddle thread to ./breakout61. This thread should move the paddle that appears when you run the game as ./breakout61 -P.

In the Breakout arcade game, players moved a small paddle back and forth, aiming to keep the ball from falling off the screen. In your ./breakout61 game, you should modify paddle_thread to do the same thing. Your paddle_thread should examine the board to determine how best to move the paddle, based on nearby ball positions. However, you it do so without data races, which will require a synchronization strategy (such as locking the board before examining ball positions, or modifying the ball threads to keep safely-accessible statistics). The paddle should pause for at least delay / 2 microseconds between moves, and it should move by no more than 2 columns per move.

This part is intentionally open-ended, and it’s got limited systems content, but maybe you’ll have fun anyway!

More extra credit

For extra credit, add more features to breakout61. Add a “snake” thread, say. Can you use networking system calls make it so that breakout61’s paddles can be controlled over the Internet, or readline so that its paddles can be controlled using the keyboard?

Turnin

You will turn in your code by pushing your git repository and informing the grading server. Inform us ASAP if you have changed partner or repository from pset 5.

Remember to fill out README.md and AUTHORS.md.


This pset was created for CS61.