A Simple Threading Solution
From Beautifulcode
Contents |
General Overview
Players run in independent threads. Each player tries to make a board as fast as it can. Once a board is finished, the player asks the referee if it is valid.
During computation, a player may ask for a new tile at any time. If a new tile is available because someone shouted 'Go!', it is returned. Otherwise, a special invalid tile is returned that simply means that the requesting player is already holding the maximum number of tiles currently allowed.
It is entirely up to each thread to decide when to check if new tiles are available. Tiles can be drawn concurrently. The more frequently a player checks for new tiles, the more likely the player will have an advantage by obtaining tiles as soon as they become available.
Players can also shout 'Go!' concurrently. A lock is held around the referee's implementation so that it can verify each player's board sequentially. If the board is valid, the global tile count is incremented. The task of shouting 'Go!' is independent from the task of checking for new tiles, which simplifies the reasoning below.
There is an arbitrary time limit that is used to detect when no players are able to make words from their letters. If no player successfully shouts 'Go!' for the duration of the time limit, the game ends in a draw.
The Architecture
The code examples below can be concatenated to produce a working header file for some arbitrary sample implementation (not provided).
Dependencies
#include <vector> #include <string> using std::vector; using std::string;
Declarations
/* These classes are part of the architecture, and are defined below. */ class IPlayScrabble; class SpeedScrabble; /* These undefined classes are referenced, but don't contribute to the architecture. */ class Tile; class ScrabbleBoard; class SpeedScrabbleData;
Class IPlayScrabble
This is an abstract class that all players will derive from.
During play, the player's 'play()' method executes in its own thread. The 'play()' method should manipulate the letters into a valid Scrabble board. Once done, the player may call 'SpeedScrabble::shoutGo()', and if the board is valid, new tiles will be available for everyone.
Other players are playing in concurrent threads. If one of the other players calls 'shoutGo()' and is successful, new tiles will be available for everyone as well.
The only way of deciding whether a new tile is available because of another player's actions is by calling 'SpeedScrabble::drawTile()'. If a tile is available for whatever reason, it will be returned. If not, a special invalid tile is returned, which is distinguishable from any valid tile.
A player class that wishes to obtain new tiles as quickly as possible should make frequent calls to 'SpeedScrabble::drawTile()'. There is no limit to the number or frequency of calls that can be made. If no tiles are available to the player, the invalid tile is simply returned.
There are other fields in this class that are not meant to be used by the implementer of a player. They are used by the SpeedScrabble class itself to keep accounting simple.
class IPlayScrabble
{
public:
/* Called by the referee to begin play. This method will
be executed in its own independent thread. */
virtual void play(SpeedScrabble *referee,
const vector<string> &dictionary,
const vector<Tile> &starting_tiles) = 0;
private:
/* Private data known only to the SpeedScrabble class. */
SpeedScrabbleData *data;
/* This lets the Referee access the private data */
friend class SpeedScrabble;
};
Class SpeedScrabble
This is the referee. Players are registered, and then a Speed Scrabble game is played. Players may only call methods in this class that are specifically documented as being callable from the player threads.
The drawTile() method will either return a new tile, if the calling player is eligible for a new tile, or it will return a unique invalid tile that lets the player know that he is currently holding the maximum number of tiles.
The shoutGo() method checks the player's board. If the board is valid (uses the correct number of tiles, uses the tiles given to the player, and all of the words formed are in the game dictionary) then the global tile limit is increased and 'true' is returned to the player. Otherwise, 'false' is returned to the player.
In the case where the game is won by the player shouting 'Go!', the routine does not return. Instead, the threads are canceled and the game winner is declared.
class SpeedScrabble
{
public:
/* Can be called from any player thread concurrently.
Returns a new tile, or the special invalid tile. */
Tile drawTile(IPlayScrabble *player);
/* Can be called from any player thread concurrently.
Returns 'true' if the board was valid and 'false'
otherwise. */
bool shoutGo(IPlayScrabble *player, ScrabbleBoard *board);
public:
/* The constructor. Creates a game with the given parameters. */
SpeedScrabble(int tile_count_for_starting_hand,
int tile_count_for_win,
int time_limit_in_seconds,
const vector<Tile> &tiles,
const vector<string> &dictionary);
/* Play the game. Start the players, and when the game finishes,
return the winner. Returns NULL if there was a draw (the time
limit was exceeded). */
IPlayScrabble *playGame(const vector<IPlayScrabble *> &players);
private:
/* The dictionary for this game */
const vector<string> &dictionary;
/* A mutex to guard the 'shoutGo' method */
pthread_mutex_t shout_go_mutex;
/* The tile pool and a mutex to guard it */
vector<Tile> tiles;
pthread_mutex_t tile_mutex;
/* The global tile count limit, and a mutex to guard it */
int current_tile_count;
pthread_mutex_t tile_count_mutex;
/* The tile count for winning. The first player to
call 'shoutGo' with a correct board containing
this many tiles is the winner. */
int tile_count_for_win;
};
Deadlock Discussion
There are three mutexes used in this implementation.
The first guards the list of tiles that the referee holds. This is so that players drawing tiles concurrently don't corrupt the vector. This mutex is only taken in a single method, and it is not taken while any other mutexes are held.
The second mutex guards the act of shouting 'Go!'. Players can shout 'Go!' concurrently, and the referee will check them one at a time. This mutex is only taken in a single method, and it is not taken while any other mutexes are held.
The third guards the tile count. The tile count is checked whenever tiles need to be drawn, and it is updated whenever a player shouts 'Go!' successfully. When tiles are drawn, no other mutex is held. When players are shouting 'Go!', the shout_go mutex is held. However, since the shout_go mutex is only obtained in one place, and it is always obtained before the tile_count mutex, a global lock order is established and maintained.
No deadlock can occur. The only instance where more than one mutex is held happens in a single method. Furthermore, the pair of mutexes that are held are taken in the same order every time (because they are in the same method), resulting in a global total ordering on lock acquisitions.
Starvation Discussion
No player action is invoked during any action requiring a mutex to be held, meaning that the player can not deliberately waste the time of any other player. Since players execute in separate threads, other players can act concurrently.
There are two points of thread synchronization that may cause contention. The first is if all players are shouting 'Go!' constantly. This will force threads to serialize, and this relies upon the hosting environment's thread scheduling to avoid starvation. If such a guarantee could not be made, then one possible enhancement could be that the 'shoutGo()' method would penalize a thread that had an incorrect board by forcing its thread to sleep for a very short period of time, which would allow other threads the chance to also shout 'Go!'. This would only negatively affect those players that were behaving in a suspicious manner.
The second point of thread synchronization is when a thread checks for a new tile. If one or more threads are constantly checking for new tiles, the hosting environment's thread scheduler is relied upon for fair scheduling to avoid starvation. If such a guarantee could not be made, then one possible enhancement could be to store the actual tile limit in an atomic way. One could use a small atomic integral type that would not require a mutex when read by the 'drawTile()' method, which avoids this problem all together.
Conclusions
Functionality
This solution works because it is simple. There are only two places where the players interact with the referee, which keeps the complication to a minimum. There is also only one direction of information flow - the players only request information from the referee. Since the referee never forces or interrupts the computation of the player asynchronously, there is no additional complication that must be considered.
Beauty
This solution is beautiful because it is simple. There is only a small amount of information that has to be considered at a time by the developer of the architecture, the developer of a player, or someone reviewing the source code. Someone could implement a player in a very direct manner - most of the code involved would be related to solving the problem of arranging the tiles into a correct board, with only two lines of code devoted to interacting with the referee, and no additional state needed on the player's side. In addition, the player need not be concerned with any locks or mutexes. This leads to solutions that match the problem very closely with very little "bookkeeping" code. This is ideal.
