Problem set 6 EC

This extra credit only problem set gives you a chance to implement some useful synchronization strategies 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 a warp end (one in a pair of warp cells), it falls off the board, warps through time and space, and then reappears after a short delay at the other warp end and continues moving.

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

The pong_celltype enum represents a cell type (empty, sticky, obstacle, or warp).
The pong_cell struct represents the state of a cell, which is a cell type, an optional ball, and an optional warp end.
The pong_warp struct represents the state of a warp end.
The pong_board struct represents the state of a board. Its main component is cells, an array of (width * height) pong_cell objects that represents the state of the board. Cells are stored in row-major order, so the cell at row y and column x is stored in cells[y * width + x].
The pong_ball struct represents the state of a ball, which is a position (x, y) and direction (dx, 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.

Getting started

Merge our 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.

The code for Breakout is in the pset6ec subdirectory. Go there, type make SAN=0, and then try the command ./breakout61. 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. Press Control-C to stop the breakout game.

Goals

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

Main phase: 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:

-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.05s).
-p DELAY: Causes the board to be printed every DELAY seconds (default 0.05s).
-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 and saw the bouncing balls. Now try the command ./breakout61 -d0, without a delay. We get an almost immediate assertion failure! Or try delay and thread sanitization: make SAN=1 breakout61 && ./breakout61 -d0.1 -p0. 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:

There must be no data races. breakout61 should 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.

Notes

The thread sanitizer is incredibly helpful. It will detect errors more quickly without -d.
The board printing thread is inherently thread-unsafe. This would be very painful to fix. It’s best to supply -p0 when the thread sanitizer is on; the board printer will overwrite sanitizer messages.
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.
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].
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.)
The -W argument adds complexity. Test -W4 for race conditions, fine-grained parallelism, and blocking after you get everything else working.
Useful command lines:
- ./breakout61 -d0 -p0 with sanitizers to check for race conditions.
- ./breakout61 -d0 -p0 -W4 with sanitizers to check for race conditions involving warps.
- ./breakout61 -d0.01 -p0.1 and ./breakout61 -d0.01 -p0.1 -W4 without sanitizers to check for deadlock (balls should keep moving around).
- ./breakout61 -b24 -s18 -d0.1 -p0 and ./breakout61 -W4 -d0.1 -p0 (plus top) to check for blocking.
- make check runs automated tests. The grading server also supports some automated tests, and we may add more.

Optional phase: Paddles

In this optional phase, 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 optional phases

For extra credit, add more features to breakout61. Add a “snake” thread! 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.

Problem set 6 EC: Breakout