Problem set 6: Pong

This problem set will teach you some useful strategies for synchronization using a game called pong.

About Pong

Pong, one of the earliest arcade video games, features a ball that moves diagonally on a rectangular playing field.

In CS 61, a pong 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 holes: when a ball hits a hole, it falls off the board and into a ball reserve.

The logic for pong boards and balls is implemented in pongboard.hh.

Getting started

Merge our problem set 6 code into your repository with git pull handout master. 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.

Please use an explicit merge to create your repository. If you copy code by hand, our automated scripts will have trouble analyzing your code, and it’ll be harder for you to incorporate our updates.

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

....................................................................................................
...................._....................................................O......O........O..........
..........O.........................................................................................
................................................................................................._..
..........................................................._........................................
........................................._..........................................................
....................................................................................................
................................_...............................................OO..................
........O..........................................O................................................
......................O.............................................................................
.............................................O......................................................
....................................................................................................
....................................................................................................
....................................................O...............................................
......_.............................................................................................
............................................................................................O.......
................................O...................................................................
....................................................................................................
.............O..................................................................._..................
....................................................................................................
....................................................................................................
..................O.......................................O....................._...................
...................................................................O................................
.................................................O..................................................
...............................................O....................................................
....................................................................................................
.........................................................._.........................................
..O.........O................................................_............._........................
..............................................O..............................O......................
...........O........................................................................................
......................_.............................................................................

The O characters are balls moving around the board. _ characters represent sticky cells and # characters represent holes. You should be able to see the balls bounce off the board edges and even off each other.

Goals

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

We also provide another program, called ./pong61, that supports synchronization in another context, namely networking. This part of the problem set is optional in 2019.

Thread safety: simpong61

The simpong61 program simulates a Pong board with multiple balls, sticky cells, and optional holes. Each ball runs in its own thread.

simpong61 takes the following arguments:

You already tried ./simpong61 -d0.1 -p0.1 and saw the bouncing balls. Now try the command ./simpong61, without a delay. We get an almost immediate assertion failure! Or try delay and thread sanitization: make SAN=1 simpong61 && ./simpong61 -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, -H, -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. Our solution code is in pong_ball::place and pong_ball::move (in pongboard.hh) and ball_thread (in simpong61.cc), with initialization code elsewhere (we added members and/or constructor code to pong_board and/or pong_ball). But you may change anything.

  4. It is possible to avoid all data races with two or three lines of code 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. You may assume that cell types do not change as the board evolves, so there are no data races involving pong_cell::type_.

  7. 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].

  8. Use a command such as ./simpong61 -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 simpong61 thread will appear at the top of the list.)

  9. The -H argument adds some complexity; test for race conditions, fine-grained parallelism, and blocking with -H3 after you get everything else working.

  10. Useful command lines:

    • ./simpong61 with sanitizers to check for race conditions.
    • ./simpong61 -H3 with sanitizers to check for race conditions involving holes.
    • ./simpong61 -p0.1 and ./simpong61 -p0.1 -H3 without sanitizers to check for deadlock (balls should keep moving around).
    • ./simpong61 -b24 -s18 -d0.1 and ./simpong61 -H3 -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.
  11. Our full solutions require much less than 100 lines of code.

Extra credit

For extra credit, add features to simpong61. Implement obstacles on the board, or paddles (moving obstacles, each controlled by their own thread).

Networking

Previous versions of this problem set have included a component called network pong that focuses on networking. You can also work on network pong for fun, but we will not grade your work, even for extra credit.

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.