This problem set will teach you some useful strategies for synchronization using a simulator for a breakout-like game.
- Due: Mon 12/6 at 11:59pm for college students (1 day later for DCE).
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
pong_celltypeenum represents a cell type (empty, sticky, obstacle, or warp).
pong_cellstruct represents the state of a cell, which is a cell type, an optional ball, and an optional warp end.
pong_warpstruct represents the state of a warp end.
pong_boardstruct represents the state of a board. Its main component is
cells, an array of
(width * height)
pong_cellobjects that represents the state of the board. Cells are stored in row-major order.
pong_ballstruct represents the state of a ball, which is a position (
y) and direction (
dy). Its member function
move()implements the logic for ball movement, including collisions, sticky cells, and some aspects of warps.
move()returns 1 if the ball moved and -1 if the ball fell off the board.
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
make, and then try the command
./breakout61 -d0.05 -p0.05. Your terminal
should fill up with board pictures like this:
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.
Your goal for this problem set is to support thread safety with
efficient synchronization. The
./breakout61 program tests this goal.
Part 1: Thread safety
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:
-b N: Sets the number of balls (default 24).
-s N: Sets the number of sticky cells (default 12).
-W N: Sets the number of warp ends (default 0). Must be even.
-d DELAY: Sets the delay in seconds between moves for each ball (default 0).
-p DELAY: Causes the board to be printed every
-w WIDTH: Sets the width of the board (default 100).
-h HEIGHT: Sets the height of the board (default 31).
-1: Runs all balls in a single thread for testing purposes.
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
-h arguments (but not
There must be no data races.
breakout61should run indefinitely, without reporting errors or deadlocking, with or without the thread sanitizer.
There must be fine-grained parallelism. It must be possible for more than one ball to move at a time, provided the balls are in different regions of the board. (You can define “region” however you like, so long as larger boards have more regions.)
Your code must block. Specifically, in the handout code, if a ball hits a sticky cell, the thread managing that ball spins (runs without blocking) until the ball is dislodged; and threads handling warp tunnels cause frequent spinning. In your code, a thread managing a stuck or warped ball should block until the ball is dislodged, and a thread managing a warp tunnel should block until a ball arrives.
The signal handler that supports
-pis inherently thread-unsafe. This would be very painful to fix. Just don’t use
-pwhen the thread sanitizer is on.
The thread sanitizer is incredibly helpful. It will detect errors more quickly without
You may change any code and add structure members.
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.
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.
std::mutexand friends have some restrictions that may surprise you. For example, you cannot have a
std::vectorof mutex objects; instead, you must create a plain old dynamically-allocated array using
Use a command such as
./breakout61 -b24 -s18 -d0.1to test for blocking. If your laptop fan starts running, your code is polling rather than blocking. (Or use Linux
topor Mac OS X
top -o cpuin a terminal window; a polling
breakout61thread will appear at the top of the list.)
-Wargument adds complexity. Test
-W4for race conditions, fine-grained parallelism, and blocking after you get everything else working.
Useful command lines:
./breakout61with sanitizers to check for race conditions.
./breakout61 -W4with sanitizers to check for race conditions involving warps.
./breakout61 -p0.1 -W4without sanitizers to check for deadlock (balls should keep moving around).
./breakout61 -b24 -s18 -d0.1and
./breakout61 -W4 -d0.1to check for blocking.
make SAN=1 checkruns 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
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
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
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?
Remember to fill out
This pset was created for CS61.