Lab 12

Lecture 12: 22.10.2018

Programming for shared memory with processes. (Mastermind)

Develop a client/server application for playing the Mastermind game. The clients (players) communicate with the server trying to guess a code sequence of 4 letters, while the server is responsible for generating the code sequences to be guessed by each player, and for providing feedback about the players' attempts at guessing their code sequences. In more detail:

Each game is played by a server and a client. There can be a maximum of N_PLAYERS clients playing simultaneously.
Every time that a new client enters the game, the server generates a new code sequence composed of 4 letters. By default, the range of letters (N_LETTERS) is 6, i.e., from 'A' to 'F'.
Whenever a client submits a new attempt, the server responds with 'xByW' where 'x' is the number of letters that are in the correct position and 'y' is the number of letters that exist in the code but are in a different position. For example, for the code sequence 'AAFB' and attempt 'ABAA', the response is '1B2W'.
Whenever a client guesses its code sequence, a message indicating the number of attempts used to guess the code is presented, and a new game with a new code sequence is started.

The communication between the server and the clients should be done through a shared memory segment. The segment must hold a vector, indexed by client, with all the information required for a client and server to communicate. Consider the following structure to represent that information:

  typedef struct {
  char state;          // PLAYER_OUT: no player; PLAYER_IN: player in the game
  char who;            // SERVER_MOVE: server has responded; PLAYER_MOVE: player has made new attempt
  char move[N_BOARD];  // last attempt of player or last response of server
  int attempts;        // number of attempts
  } struct_player;

Synchronization between server and clients should be done with semaphores. When a client sends an attempt to the server, it should go into sleep mode until the server responds. On the other hand, the server should also sleep when there are no more attempts to answer to. To ensure a fair response time, the server should use a round-robin strategy to answer to the clients.

The server and the clients should be initialized with different executables. As a suggestion, consider the following starting code for the server and for the clients.

Programming for shared memory with processes. (NQueens)

Develop an application to solve in parallel the problem of placing N-queens in a chess board. The problem consists in finding all possible arrangements of N queens in a chess board of dimension N, such that no two queens attack each other. Two queens attack each other if they are in the same line, column or diagonal. The figure shows the positions that are attacked by a queen placed in board of dimension 7x7 and, on the side, it shows a possible solution for such board.

Given that the number of queens is equal to the board dimensions, it is mandatory to have one queen per board line. Thus, we can represent the position of the queens in the board by a vector of N rows that associates to each row the column in which the queen is placed.

A procedure to place the N queens in the board is to start by the first row and consider the N available column positions available. Then, for each position in the first row, consider the positions in the second row that will not attack the first queen. Apply this idea to the other rows, to obtain all possible solutions. As we progress with the rows, it is necessary to save valid intermediate combinations. This can be done with a queue of tasks where we save these combinations.

Starting from the following code structure, implement a sequential version of the queue of tasks. Then make a first parallel version in which the different workers synchronize in the two operations that access the queue of tasks.

Last, extend the parallel version to support multiple task queues associated with groups of workers. Each group of workers only consumes tasks from its task queue, but distributes its intermediate combinations by all queues in a round-robin fashion.