CS 3013 & CS 502 Operating Systems WPI, Summer 2006
Hugh C. Lauer Project 2 (20 points)
Assigned: Thursday, June 1, 2006 Due: Thursday, June 15, 2006

Introduction & Problem statement

The use of threads and synchronization mechanisms allows for easy sharing of resources within a process, but using semaphores in their purest form is difficult. In this project, you will develop a message passing mechanism that can be used among a set of threads to provide a more structured form of communication. You will use the facilities of the semaphore library implementing the mailbox mechanism and the pthread library to implement the threads themselves.

To exercise the mailbox routines you will first build a multi-threaded program to add up a range of numbers. Once working, the primary purpose of the project is to build a Game of Life program where work is distributed among a set of threads.

The basic idea of this assignment is to create a number of threads and to associate each thread with a “mailbox” that can receive messages from other threads. The number of threads in your program should be controlled by an argument given on the command line to your program (use atoi() to convert a string to an integer). You should use the constant MAXTHREAD with a value of 20 for the maximum number of threads that can be created.

The parent thread in your program will be known as “thread_0”. The rest of the threads will be known as “thread_1”, “thread_2”, up to “thread_n” (where n is the argument specified on the command line). In creating your threads, your program will need to remember the thread id returned in the first argument of pthread_create() for later use.

Part 1: Mailbox Implementation – 25%

This part of the project is the design and implementation of the mailbox facility itself. All synchronization among threads will take place within this mailbox facility. Your goal is to create an interface and implementation in C or C++ that defines the concept of message and mailbox and provides routines that operate on them.

Messages

A mailbox is an abstract date type capable of containing a number of messages of variable size defined by the following C/C++ structure:–

struct msg {
int iFrom; /* who sent message (0 .. number-of-threads) */
int type; /* its type */
int num; /* number of items in payload (0 .. MAXPAYLOAD) */
long payload[MAXPAYLOAD]; /* payload, an array of long */
};

The actual size of each message varies by the number of elements in the payload.

The field iFrom in a message has values in the range 0 to n (the number of threads specified in the command line). We will call this the “mailbox id” of a thread to distinguish it from the thread id returned by pthread_create(). The field type indicates what kind of message this is; the values of type are defined by the application. The field num specifies the number of elements in the payload array. This may be as small as zero and as large as MAXPAYLOAD. The payload array of each message is the actual content of the message and has num elements in it. You should use a value of 32 for MAXPAYLOAD.

Mailboxes

Each mailbox should be capable of holding a variable number of messages. The actual size of the mailbox depends upon the number of concurrent threads that may be expected to send messages and the average sizes of those messages. On one hand, mailboxes should not be excessively large (because in an OS kernel, mailbox space could easily become a scarce resource); on the other hand, mailboxes have to be large enough to avoid the possibility of deadlocks.

In this project, each mailbox will have one receiving thread and many sending threads. A reasonable approach for implementing a mailbox is as a Producer-Consumer model with many producers and a single consumer per mailbox.

If you are programming in C++, mailbox may be defined as a class with the member functions

SendMsg(msg &Msg) // Msg is reference to message to be sent;
// blocks if mailbox is full
RecvMsg(msg &Msg) // Msg is reference to area to store
// received message; blocks if mailbox
// is empty

Mailbox(int size) // Constructor for mailbox of size bytes
~Mailbox() // Destructor of mailbox

The public member functions of a mailbox are SendMsg and RecvMsg. SendMsg allows a thread to put a new message into the mailbox, but it blocks the thread if the mailbox is too full to accept the message. RecvMsg allows the thread owning the mailbox to retrieve the next message, but it blocks if the mailbox is empty. The other two public member functions are the constructor and the destructor. The constructor allocates the memory needed for each mailbox and creates and initializes all of the semaphores and other internal data needed to implement the mailbox. The destructor deletes the semaphores and frees the memory. You may add other member functions as you feel necessary.

If you are programming in C, the details are more cumbersome but conceptually the same. You would need at least the following functions:–

SendMsg(int iTo, struct msg *pMsg) // msg as ptr
/* iTo - mailbox to send to */
/* pMsg - message to be sent */

RecvMsg(int iFrom, struct msg *pMsg) // msg as ptr
/* iFrom - mailbox from which to get messages */
/* pMsg - message structure to fill with received message */

CreateMailbox(int size) // routine to create and initialize
DestroyMailbox() // routine to deallocate and destroy

You should organize the mailbox facility as follows:–

· A header file Mailbox.h, that defines the structure msg, the class mailbox (if C++), and the functions SendMsg(), RecvMsg(), and the functions to create and destroy mailboxes (if C). The header file Mailbox.h should not expose the semaphores or the internals of any mailbox to the calling program.

· An “implementation” module Mailbox.cpp or Mailbox.c, that provides the code that implements the routines SendMsg(), RecvMsg(), etc.

Implementation notes

The POSIX thread facility defined in <pthread.h> should be used for creating and managing threads. This defines functions such as pthread_create(), pthread_join(), pthread_exit(), and other useful functions. Likewise, the POSIX semaphore facility defined in <semaphore.h> should be used for this project. This defines functions such as sem_init(), sem_wait(), sem_post(), and a number of other useful routines. In order to access the semaphore functions at run time, you will need to link with the “rt” library in Unix/Linux.

Part 2: Testing Mailboxes – 25%

Testing a communication facility for concurrent processes or threads is difficult and is best done with a test tool having some degree of randomness. For this exercise, you should write a simple program called addem to add the numbers between 1 and an integer limit. This should have a sample invocation as follows:–

% addem 10 1000

The total for 1 to 1000 using 10 threads is 500500.

The first argument to addem is the number of threads, and the second argument is the integer limit. addem should, of course, test the arguments for validity and print an error message if necessary.

The main thread of addem should first create a mailbox so that other threads can send messages to it. It should then create n additional “worker” threads to do the actual work of the program, where n is the first argument on the command line. It should pass a pointer to its mailbox as an argument to each thread. After it creates n threads, it should wait for messages from them telling it where to send the messages for the work to be done. Thread_0 then partitions the problem of adding up the numbers into n ranges of random size and allocates each range to one of the threads. It then waits for the results of the work of each thread, adds them together, and prints the total. Finally, it sends done messages to each of its threads and waits for them to terminate before it exits.

Each thread first creates its own mailbox, and sends a pointer to that mailbox to the main thread via a message. It then waits for a message specifying work to be done. When it receives a message requesting work, it does the work, returns the result in a message to the parent thread, and waits for additional work or a done message. When it receives a done message, it deletes its own mailbox and exits.

To add a degree of randomness, a thread should endeavor to sleep or pause for a random number of milliseconds before sending a message back to the parent thread. The intent is for the responses from worker threads to come back in random order, not the order in which they were created.

For this test application, the following message type values are needed.

#define MAILBOX 1
#define DONE 2
#define WORK 3
#define RESULT 4

A message of type MAILBOX will have only one element in its payload, namely a pointer to a mailbox. The array element payload[0] must be typecast to a pointer.

A message of type DONE will have no elements in its payload. Therefore, num will be zero. Messages of type WORK and RESULT should have random numbers of elements in their payloads, but only the first two (in WORK) or the first (in RESULT) will be meaningful. In the case of WORK, payload[0] and payload[1] are the lower and upper bounds, respectively, of the range of numbers to add. In the case of RESULT, the element payload[0] is the sum of the integers from payload[0] and payload[1] (inclusive) of the previous WORK message.

The program addem will include Mailbox.h, giving it access to the mailbox facilities, but it will not be able to see anything inside of Mailbox.c.

Once the parent thread has received RESULT responses from all created threads, it should print the summary total of all responses, send DONE messages, and wait for each created thread to complete. It should not attempt to delete its own mailbox until all threads have exited.

There is little likelihood of deadlock in this test, because all of the commands come from thread_0 and all of the responses go to it.

Part II: John Conway’s Game of Life – 50%

For the second part of the project, you will create a multi-threaded program to play a distributed version of the Game of Life. This “game” 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, each of which has eight neighbors (adjacent cells). Each cell is either occupied by an organism or not. Assume that cells outside of the grid are unoccupied. A grid of occupied and unoccupied cells is called a generation. The rules for deriving a new generation from the previous one 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 http://www.math.com/students/wonders/life/life.html.

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 is unchanged from the previous generation, or

3. a predefined number of generations is reached.

You may ignore other forms of termination. (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.)

Distributed Life

The distributed version of the game follows the same rules as the standard game, but rather than have a single-threaded process evaluate all cells for each generation, a distributed version will use multiple threads to perform the work. Each thread will work on a rectangular subset of the grid. It will exchange messages with its neighboring threads to seamlessly implement the rules of the game across the boundaries.

A thread may have as many as eight nearest neighbors, four sharing the north, east, south, and west boundaries, respectively, and four sharing the northeast, southeast, southwest, and northwest corners, respectively. If a thread has no neighbor in a particular direction, it should assume that it is on the boundary, so that cells in that direction are always zero.

After computing a generation, each thread sends messages about the cells on its own boundaries directly to the neighboring threads sharing those boundaries. Prior to starting the next generation, it should read messages from those same neighbors about the cells on their boundaries. By this means, it can accurately compute the next generation of cells on its own boundary according to the rules.

Your program should accept command line arguments with the following syntax

% life threadX threadY gridX gridY gen filename print input

where

· threadX and threadY are the number of threads in the x and y directions, respectively, and where x*y does not exceed MAXTHREAD.

· gridX and gridY are the sizes of the x and y dimensions of the grid processed by each individual thread. The grid size per thread should not exceed MAXGRID of 32 cells in either dimension.

· gen is the maximum number of generations to play. This value must be greater than zero. The program may halt prior to his number of generations if it determines that it has reached a steady state.

· filename is the name of a text file containing the initial input. 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 before proceeding to the next generation. The default value is “n”.

· input 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 vacant or occupied, 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, the input file that contains the following

oxx
xxo
oxo

represents the grid

(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.

If you have time, it would be useful to trim the lines to delete unoccupied cells at the beginnings and ends of lines and unoccupied lines. Your label should also indicate the row and column number of the first cell.

Implementation

You will use thread_0 to coordinate the activities of one or more worker threads that actually do the work of playing the game. Each worker thread computes the new generation of the game for its assigned subgrid and then sends a message back to thread_0 with the result. Thread_0 collects the subgrids together and prints the output required by the print argument of the command line.

Each thread 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 in messages from neighboring threads.

When thread_0 creates thread_i, it passes as arguments the value i, the values gridX and gridY from the command line, an eight-bit vector indicating what neighbors are present, and a pointer to the thread_0 mailbox. Immediately upon creation, thread_i creates a mailbox of its own and sends a message back to thread_0 with a pointer to that mailbox. Once thread_0 has accumulated pointers to all of the mailboxes of the worker threads, it sends two messages to each one. One message contains the pointers to the mailboxes of the neighboring threads, and the second contains the START command and the initial value of the subgrid (if not all zeros).

Each bit in the eight-bit vector passed to thread_i has a value of 1 if the corresponding neighboring thread will be present and a value of 0 of not (i.e., the thread lies on a boundary). The bits are enumerated in the following order:– north, northeast, east, southeast, south, southwest, west, and northwest. This helps thread_i estimate the size of mailbox needed to receive messages from its neighbors.

The following message type values may be used.

#define MAILBOX 1 // pointer to own mailbox
#define NEIGHBORS 2 // pointers to neighboring mailboxes
#define START 3 // begin computing generations
#define BOUNDARY 4 // value of cells on boundary
#define RESULT 5 // computed subgrid of a generation
#define STATIC 6 // computed rows same as last generation
#define ZERO 7 // computed subgrid is zero
#define STOP 8 // command to terminate thread

The meanings of these messages are as follows:–

· From thread_i to thread_0, MAILBOX contains a payload of one element, namely a pointer to the mailbox.

· From thread_0 to thread_i, NEIGHBORS contains a payload of eight elements, each either a null pointer or a pointer to the mailbox of a neighboring thread. Neighboring threads are listed in the order north, northeast, east, southeast, south, southwest, west, and northwest.

· The START message is from thread_0 to each thread_i, and it contains either an empty payload (num = 0) or a payload specifying a non-empty subgrid for generation 0.

· The BOUNDARY message is from thread_i to thread_j and communicates the values of the cells at the edge of thread_i’s grid (so that thread_j can calculate its next generation). The format of a BOUNDARY message is num=1 and payload [0] contains one bit for a corner cell or up to MAXGRID bits for an edge boundary.

· The RESULT message is sent by thread_i to thread_0. It contains num=gridY of long integers each containing gridX bits, so that the payload array completely describes the subgrid of the thread.

· The STATIC message has num=0 and an empty payload array. This is sent by thread_i to thread_0 meaning that the result of this generation is identical to the result of the previous generation.

· The ZERO message is also sent from thread_i to thread_0 and means that the resulting subgrid is all zeros.

· The STOP message is sent from thread_0 to each thread_i. It contains one payload entry indicating the number of the generation to stop (num=1).

You may need to define other message types or clarify the meanings of these message types. Be sure to explain in your project write-up.

Deadlocks

There is a very real possibility of deadlocks in this exercise. For example, thread_i could be blocked while trying to send a message to thread_j because thread_j’s mailbox is full. But thread_j could be waiting for a message from thread_k, which in turn is waiting for a message from thread_i. This can be avoided by making sure that the mailbox of thread_j is sufficiently large to hold the messages from all of its neighbors.

You are not responsible for mastering the intricacies and mathematics of deadlock avoidance, but you should be aware of the possibility. If it occurs, you should comment in your project description and explain what you did to solve the problem.

Submission of Project

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

Note that while these are application programs, you should assume that you are writing code suitable for inclusion in an operating system. For example, you should not assume that the user always submits correct input or reads the manuals.

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.

For this assignment, please use the turnin program, i.e., the command line tool for turning in assignments on CCC computers. Information about this tool can be found on

http://web.cs.wpi.edu/Help/turnin.html

This class is ‘cs502’, and the assignment is ‘project2’. Therefore, the turnin command would be

/cs/bin/turnin submit cs502 project2 <your files>

Your submission should include

1. The files containing the code for all parts of this assignment

2. The makefiles for building the executable programs

3. The test files or input that you use

4. Files that capture the input and output for building and running and testing the programs.

5. Information about what system(s) on which you maked and ran your programs.

Also, you should bring a printed copy of your work to class on the due date. Make sure that your name is clearly visible on your work.