Project 2 (Threads)



CS 4513 Distributed Computing Systems WPI, D-term 2007

Hugh C. Lauer Project 1 (100 points)

Assigned: Tuesday, March 13, 2007 Due: Friday, March 23, 2007

Introduction & Problem statement

This project is partly a review of concepts from your Operating System course and partly the first step in developing a distributed application.

In this project, you will implement Conway’s Game of Life so that different subsets of the playing board (i.e., sub-grids) are played by different processes or threads. The challenge is to make the processes or threads communicate and synchronize with each other regarding data at the boundaries of their respective subsets.

In this project, the processes or threads will all be on the same computer, but later in the term you will implement a version where they are distributed across physically separate computers.

You may implement this project in Java, C++, or C.

This project is NOT a team project; it is to be done individually.

John Conway’s Game of Life

The Game of Life was invented by John Conway and was originally described in an article in the April 1970 issue of Scientific American, page 120. The Game of Life has since become an interesting object of mathematical study and amusement, and it is the subject of many websites.

The game is played on a rectangular grid of cells, so that each cell has eight neighbors (adjacent cells). Each cell is either occupied by an organism or not. A pattern of occupied and unoccupied cells in the grid is called a generation. The rules for deriving a new generation from the previous generation are these:–

1. Death. If an occupied cell has 0, 1, 4, 5, 6, 7, or 8 occupied neighbors, the organism dies (0 or 1 of loneliness; 4 thru 8 of overcrowding).

2. Survival. If an occupied cell has two or three neighbors, the organism survives to the next generation.

3. Birth. If an unoccupied cell has precisely three occupied neighbors, it becomes occupied by a new organism.

Examples can be found at .

Once started with an initial configuration of organisms (Generation 0), the game continues from one generation to the next until one of three conditions is met for termination:

1. all organisms die, or

2. the pattern of organisms repeats itself from a previous generation, or

3. a predefined number of generations is reached.

To simplify the project, you may ignore repetitions separated by more than one generation. For example, some patterns oscillate, so that generation i+2 is identical to generation i. In more complicate cases, the patterns repeat after 10 or 100 generations.

Concurrent Life

The multi version of the Game of Life follows the same rules as the standard game, but rather than have a single thread or process evaluate all cells for each generation, the work is divided among multiple threads or processes. Each thread or process — called a player — works on a fixed, rectangular subset of the grid. It exchange messages or otherwise communicates with the players of its neighboring subgrids, so that together, they seamlessly implement the rules of the game across an entire grid.

A player may have as many as eight nearest neighbors, four sharing its north, east, south, and west boundaries, respectively, and four sharing its northeast, southeast, southwest, and northwest corners, respectively. If a player has no neighbor in a particular direction, it should act as if cells beyond that boundary are always and forever zero.

After computing a generation, each player informs each of its neighbors about the pattern of occupancy on its side of the corresponding boundaries, and it receives from each of its neighbors the pattern of occupancy of the cells on the neighbor’s side of the boundary. It needs this information from its neighbors so that it can accurately compute the next generation of cells near its own boundaries.

A parent thread or process manages the game. It starts the players with initial values for their respective subgrids, and it receives information at the end of every generation from the players about the state of their subgrids. The parent then displays the entire grid on an output device.

In this project, all subgrids are of fixed size — i.e., 32 ( 32 cells.

Invoking your program

Your program should accept command line arguments with the following syntax

% life X Y gen filename print pause

where

• X and Y are the number of subgrids in the x and y directions, respectively, and where X*Y does not exceed MAXTHREAD = 32.

• gen is the number of generations to play. This value must be greater than zero. The program should halt prior to this number of generations if it determines that the game has reached a steady state.

• filename is the name of a text file containing the initial pattern of occupancy. The format of the file is described below.

• print is an optional argument with value of “y” or “n” on whether each generation (including generation 0) should be printed or displayed before proceeding to the next generation. The default value is “y”.

• pause is an optional argument with value of “y” or “n” on whether keyboard input should be required between generations. The default value is “n”.

As input, Generation 0 should be specified in an ASCII file consisting of a sequence of “x” and “o” characters indicating whether a cell is occupied or vacant, respectively. There must be no spaces between characters, and a newline terminates a row. Your program should place the input in the approximate center of the entire grid, so that subsequent generations have an opportunity to expand in all directions across all threads.

For example, an input file containing the following three lines

oxx

xxo

oxo

represents the starting pattern

[pic]

(Known as the R-pentomino, this is a very interesting pattern that generates a particularly rich structure for about 1100 generations before reaching a steady state.)

The output of your program should have the same format as the input. Each output grid should be preceded by a label indicating the number of the generation. If the print argument is “y”, then your program should print every generation. Otherwise, it should just print the beginning and final generations.

Implementation

Each player will need to maintain two arrays of its subgrid, one for odd-numbered generations and one for even-numbered generations. It computes the next generation from its own grid and the information received from neighboring players. Players may not access each other’s data directly; they must do so via a procedural or communication interface.

When the parent process or thread creates player k, it passes as arguments

• the value k,

• a 32 ( 32 array denoting the initial value of the subgrid for player k, and

• an eight-element array of objects representing the eight nearest neighbors of player k. Note that for a player on the boundary of the grid, some of the objects representing it neighbors will be “null.”

Each player must have a means of communicating with the parent the results of each generation.

It is up to you to define the nature of the objects used to communicate between players. For example, you may use Java synchronized objects, pointers to instances of a C++ class, or pointers to instances of a C struct. You need to synchronize access to these objects so that, for example, one player does not update a boundary value in the object while its neighboring player is reading that value. You may any suitable synchronization mechanism — for example, semaphores or messages.

Deadlocks

There is a very real possibility of deadlocks in this exercise. For example, player i could become blocked while trying to communicate with player j, because player j is waiting for information from player k, which in turn is waiting for information from player i.

You should regard any deadlock as a bug in your program, not an instance of some abstract mathematical theory of deadlocks. If you encounter a deadlock, fix it and then describe in your write-up how you found it and what you did to solve it.

Testing

Testing concurrent programs is always harder than testing sequential programs. You must devise at least three non-trivial test patterns, and you must describe in your write-up whether you believe that these three are comprehensive or not and what else you might try if you had more time.

The term “non-trivial test pattern” means a pattern that produces occupied cells in at least eight sub-grids, that those grids are not all arranged in one dimension, and that the pattern runs but does not repeat for at least 100 generations.

Submission of Project

All code must be clearly commented. All output and printouts must be easy to understand and cleanly formatted. Your name must be on every file. (You would be surprised how many assignments we get without students’ names on them!)

Submit your assignment using the Dropbox of MyWPI at



Submission format

Your submission should include

1. Source code for all programs and header files of this assignment

2. The makefiles for building the executable programs

3. The test files or input that you use

4. Output files showing how your program runs.

5. A write-up describing what you did and how you did it. Brevity is a virtual; details should be documented as comments in your code.

Zip all of your files together into a single zip file named “e-mailID-Project1.zip”, where “e-mailID” is replaced by your WPI e-mail ID. Do not make subfolders in your zip file; everything should be at the top level. If you make a mistake, you may resubmit with the same file name.

It is in your interest to make the TA’s life easy. He/she will download your submission, compile it, run it with your test cases, and run it with our own test cases.

• Do not make us figure out how to do this! We would like to simply unzip the file and then execute a simple make command to build your entire application.

• All student programs should compile without warnings! You may not use the “-Wno_deprecated” switch without prior permission from the instructor or TA.

Grading

Here are the grading guidelines for this project:–

• Successful submission of project via myWPI — 10 %

• Clear, cogent write-up describing your work — 10%

• Successful build (using make) with no errors or warnings on a Fossil Lab machine — 15%

• Definition of at least three non-trivial test patterns — 15%

• Successful operation of your test patterns — 25%

• Successful operation of our test patterns — 25%

Extra credit:–

• Definition and successful execution of a test pattern that aggressively fills all sub-grids of an 8(4 array and aggressively passes values across all boundaries for at least 1000 (non-repeating) generations — 20%

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download