Due: Tuesday, April 17th, 2012 9:10am
Start with field.c, which implements a game simulation. Two teams (red and blue) run around a field and try to pass and steal balls. Each team starts with a ball, and the ball is always attached to a player. Players run around randomly, and when they see an adjacent player, then they may try to pass or steal (depending on the teams fo the two players and whether either player has the ball). A pass or steal may randomly fail.
The players are implemented by creating a thread for each player. All of the player threads manipulate the field representation, and players have to inspect and maybe change other players when they try to pass or steal.
The initial implementation compiles, but it tends to crash immediately, because the implementation is full of race conditions.
To compile field.c on some machines, you'll need to use the -pthread flag:
gcc -O2 field.c -pthread
Add mutex locks to avoid race conditions in the implementation. To keep it simple, use one big lock for everything but the random number generator, and use a separate lock for the random-number generator.
Avoid over-synchronization. In particular, it should be possible for one player thread to generate a random number while a different player thread manipulates the field.
Your resulting implementation should run without crashing or other undesireable behavior (such as losing track of a player or making more than 500000 moves). There will still be non-determinism, since the players race against each other, but that's desirable non-determinism in this case.
Random-number generation doesn't need to be shared among processes. Move the random-number state into each player, so that each can generate random numbers without synchronizing.
You might see a slight overall speed-up as a result of this change.
The main thread in the simulation constantly spins, waiting for the epoch counter to increase. That's bad, because it wastes CPU. It's better to send some sort of notification to the main thread when the epoch is increased, and let the main thread otherwise sleep.
Given what you've seen in class, one simple form of waiting and notification is writing and reading from a pipe. Change the program so that when the epoch counter is increased, a byte is wrtten into a pipe. Then the main thread can block by attempting to read from the pipe to wait for the epoch counter to increase.
You might see an overall speed-up as a result of this change.
When a player discovers an adjacent player and tries to pass or steal, then a little contest starts (which can take a while) to determine whether the pass/steal succeeds or fails. Some lock must be held during the contest, so that the other player doesn't move. The field position isn’t going to change, however, so the lock for a contest doesn’t have to be the big lock for the whole field.
For finer-grained locking during a contest, associate a mutex lock with each player. Before a contest, lock the two players, then release the field lock, so that other players can continue to move. You’ll probably also want a separate lock for the pass/steal statistic counters, since they may be updated after a contest.
Keep in mind that when a process acquires multiple locks, it should acquire them in a globally agreed-on order. Otherwise, two processes can deadlock while trying to acquire the same locks in different orders. The original field.c code assigns each player a unique rank, which can be used to order the player locks.
Note: Note that PTHREAD_MUTEX_INITIALIZER works only in a declaration of a mutex. If you need to dynamically initialize a mutex, use pthread_mutex_init with NULL as the second argument.
With parts 2-4 completed, you will very likely see a speed-up relative to part 1.
| Last update: Monday, April 16th, 2012mflatt@cs.utah.edu |