Problem set 6 – CS 61 2019

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

Extended deadline: Fri 12/13 at 11:59pm for college students (1 day later for extension).
- NO CLASSWORK WILL BE ACCEPTED AFTER THE EXTENDED DEADLINE REGARDLESS OF LATE HOURS. That is, you cannot use late hours to delay the extended deadline.

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.

The pong_celltype enum represents a cell type (empty, sticky, obstacle, or hole).
The pong_cell struct represents the state of a cell, which is a cell type and an optional ball.
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.
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, holes, and sticky cells. move() returns 1 if the ball moved and -1 if the ball fell into a hole.

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:

-b N: Sets the number of balls (default 24).
-s N: Sets the number of sticky cells (default 12).
-H N: Sets the number of holes (default 0).
-d DELAY: Sets the delay in seconds between moves for each ball (default 0).
-p DELAY: Causes the board to be printed every DELAY seconds.
-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 ./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):

There must be no data races. simpong61 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 if the board has holes, the main thread frequently spins without blocking. In your code, the thread managing a stuck ball should block until the ball is dislodged, and the main thread should block until a ball falls into a hole.

Notes

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.
The thread sanitizer is incredibly helpful. It will detect errors more quickly without -d.
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.
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.
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.
You may assume that cell types do not change as the board evolves, so there are no data races involving pong_cell::type_.
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 ./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.)
The -H argument adds some complexity; test for race conditions, fine-grained parallelism, and blocking with -H3 after you get everything else working.
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.
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.

Problem set 6: Pong