CS 502 Operating Systems WPI,
Spring 2006
Hugh C. Lauer Project
2 (30 points)
Assigned: Monday, February 20, 2006 Due:
Monday, March 6, 2006
The use of threads and synchronization mechanisms such as mutex locks and semaphores allows for easy sharing of resources within a process. In this programming project, you will use these facilities to develop a message passing mechanism that can be used among a set of threads within the same process. You will use the facilities of the pthread and semaphore libraries for thread and synchronization routines.
To exercise these 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” where a single message for that thread can be stored. Because one thread may be trying to store a message in another’s mailbox that already contains a message, you will need to use semaphores in order to control access to each thread’s mailbox. 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 10 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.
For each thread, your program should create a mailbox. For this project, a mailbox is minimally capable of containing a message that is defined by the following C/C++ structure:–
struct msg {
int iFrom; /* who sent message (0 ..
number-of-threads) */
int type; /* its type – part of payload */
int value1; /* first value – part of
payload */
int value2; /* second value – part of
payload */
};
Notice that the identifiers such as iFrom used in
messages are 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(). In the first part of the project, you will
only need to define two message types, namely, RANGE and ALLDONE, as defined below:
#define RANGE 1
#define ALLDONE 2
You should create the mailboxes in a routine called
InitMailboxes(int number_of_mailboxes)
The main thread of your program using the mailbox facilities will call this routine with the argument n+1, where n is the number specified in the command line, not to exceed MAXTHREAD. This will provide one mailbox for each created thread, plus one for the main thread. InitMailboxes() should dynamically allocate an array of mailboxes of this size.
Similarly, InitMailboxes() should create semaphores for each mailbox using the routine sem_init() that is available by linking with the “rt” library in Unix/Linux. It should initialize these semaphores to indicate that the corresponding mailbox is empty.
To handle access to each thread’s mailbox you must write two procedures: SendMsg() and RecvMsg(). These procedures have the following interfaces
SendMsg(int iTo, struct msg *pMsg) // msg as ptr, C/C++
SendMsg(int iTo, struct msg &Msg) //
msg as reference, C++
/* iTo - mailbox to send to */
/* pMsg - message to be sent */
RecvMsg(int iFrom, struct msg *pMsg) // msg as ptr, C/C++
RecvMsg(int iFrom, struct msg &Msg) // msg as reference, C++
/* iFrom - mailbox to receive from */
/* pMsg/Msg - message structure to fill with received message */
The variables, iTo and iFrom, are simply the index of the thread (or mailbox); for example, the index of the parent thread, thread_0, is 0. SendMsg() routine should block if another message is already in the recipient’s mailbox. Similarly, RecvMsg() routine should block if no message is available in the mailbox.
Finally, you should include a routine CleanupMailboxes() that deletes the dynamically allocated mailboxes and all of the created semaphores.
You should organize the mailbox facility as follows:–
· A header file Mailbox.h, that defines the structure msg and that provides the signatures for the functions SendMsg(), RecvMsg(), InitMailboxes(), and CleanupMailboxes(). Mailbox.h should not expose the semaphores or the arrays of mailboxes.
· An “implementation” module Mailbox.c, that provides the code that implements the routines SendMsg(), RecvMsg(), InitMailboxes(), and CleanupMailboxes() and that includes “global” data needed to access the semaphores and the array of mailboxes.
By encapsulating these internal details of the mailbox implementation in Mailbox.c, no part of any program using mailboxes need be aware of the details. Obviously, both Mailbox.c and any program using mailboxes will have to include Mailbox.h.
In summary, the key routines you must write for Mailbox.c are:–
· InitMailbox() – return 0 on success, -1 on failure. Initializes semaphores and mailbox array.
· CleanupMailbox() – return 0 on success, -1 on failure. Cleans up all semaphores and the mailbox array. Should be called whenever the parent thread exits.
· SendMsg(iTo, pMsg) – sends a message to the destination mailbox.
· RecvMsg(iFrom, pMsg) – receives a message from the source mailbox.
Remember that in Mailbox.h, these routines should all be identified as extern so that a client of the mailbox facility can actually link to them.
To test the mailbox facility, you should write a simple program called addem to add the numbers between 1 and an integer limit. This should a sample invocation as follows:–
% addem 10 100
The total for 1 to 100 using 10 threads is 5050.
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 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.
After calling InitMailboxes to set up the mailboxes, the main thread of addem will create the other threads and exercise the mailbox facility. Once a thread is created, it should wait for a message of type RANGE from the parent thread (mailbox id 0) by calling RecvMsg() with its mailbox id as the first argument. When it receives such a message, the child thread should add the numbers between value1 and value2 and return the result to the parent thread with a message of type ALLDONE.
Once the parent thread has received ALLDONE responses from all created threads, it should print the summary total of all response and wait for each created thread to complete. Once each thread has completed, the parent should call CleanupMailboxes() and then terminate.
For the second part of the project, you should save a copy of your part I code and modify it for part II. Part II, which should be called life, will play a distributed version of the Game of Life.
The Game of Life was invented by John Conway. The original article describing the game can be found in the April 1970 issue of Scientific American, page 120. The game is played on a rectangular grid of cells, each of which has eight neighbors (adjacent cells). A cell is either occupied (by an organism) or not. For boundary cases, assume cells outside of the grid are unoccupied. The rules for deriving a 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 exactly three occupied neighbors, it becomes occupied.
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 one generation to the next, or
3. a predefined number of generations is reached.
The straightforward way in which to implement the program is to maintain two separate two-dimensional arrays for even and odd generations. These can be maintained as global variables. For the project you should define a variable MAXGRID as the maximum number of rows or columns in the grid. MAXGRID should be set to 40.
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. This approach could improve performance on a multiprocessor, but introduces added complexity on synchronizing the activities of the threads.
Your program will still need to maintain two global arrays, one for odd-numbered generations and one for even-numbered generations.
You will use thread_0 to coordinate the activities of one or more worker threads, which are actually doing the work of playing the game. Each worker thread computes the new generation of the game for an assigned range of rows as initially specified by thread_0. The number of rows assigned to each thread by thread_0 should be roughly equal. After each generation, each thread reports results back to thread_0 and waits for a GO message from thread_0 before continuing to the next generation. You will need additional message types for new actions. For example, you may want to define the following
#define RANGE 1
//range of rows
#define ALLDONE 2
#define GO 3 //compute next
generation
#define STOP 4
#define ALLZERO 5 //computed rows
contain zeros
#define STATIC 6 //computed rows same
as last generation
#define GENDONE 7 //Generation
calculation is done
Each worker thread should first wait for a RANGE message to indicate what set of rows it is responsible for, and then it should enter an infinite loop waiting for messages telling it what to do.
· If the message is STOP, the thread should exit.
· If the message is GO, the thread should compute its assigned rows of the next generation of the game, using the global array of the previous generation as input. The message should specify whether the odd-numbered or the even-numbered generation is being computed.
When completing a generation, the thread should reply to thread_0 one of the following:–
· ALLZERO, if the results of its computation in this generation produced all zeroes.
· STATIC, if the results of the computation of this generation did not change it rows at all.
· GENDONE, otherwise.
thread_0 must ensure that all threads have completed a generation before proceeding to the next generation. There is no specific order in which worker threads must play. Each thread must only update the cells for its range of rows, but for rows adjacent to those for another thread it is fine for a thread to read the values of cells in rows outside of its range.
It is the responsibility of thread_0 to decide when the game is done using the termination rules previously specified. thread_0 must combine the results for all worker threads to decide if the game is done, in which case it sends a STOP message to all threads. If the game is not done, it sends a GO message to all. Be careful in combining the respective results from each thread because even though one thread may have no or static life, that may not be the case for the regions of all threads.
As input, Generation 0 should be specified in an ASCII file consisting of a sequence of 0’s and 1’s indicating whether a cell is vacant or not. There will be a space between each digit and a newline terminates a row. For example, suppose the file contains
0 1 0 0
0 0 1 1
1 0 0 0
This means that the input consists of three rows and four columns. Your program should ensure that neither the number of rows nor columns exceeds MAXGRID. If so it should print a message and terminate.
Your program should accept 3-5 command line arguments with the following syntax:
% life threads filename generations print input
with the following meaning:
· threads: number of threads with value between 1 and MAXTHREAD.
· filename: file containing generation 0. Note that if the generation contains fewer rows than the given number of threads, you should set the number of threads to the number of rows so each thread has at least one row to work on.
· generations: the maximum number of generations to play. Must be a value greater than zero.
· print: 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: an optional argument with value of “y” or “n” on whether keyboard input should be required before proceeding to the next generation. The default value is “n”.
Regardless of whether intermediate generations are printed, thread_0 should print the total number of generations and final configuration before waiting for all threads to complete and cleaning up semaphores. An example invocation with the previous example used for contents of “gen0” would be:
% life 3 gen0 10 y
Generation 0:
0 1 0 0
0 0 1 1
1 0 0 0
Generation 1:
0 0 1 0
0 1 1 0
0 0 0 0
The game ends after 2 generations with:
0 1 1 0
0 1 1 0
0 0 0 0
Debugging a concurrent program is always tricky. For a simple problem like this one, adding “DebugPrint” statements to the program is a useful technique. These could be activated by extra arguments on the command line. For example,
% life 3 gen0 10 y n y
could indicate that individual threads should print extra output information each time they receive a message or complete a computation. This would help you track what it going one. If you get into a situation where this is not helpful sufficient, you can beef up the debug statements to selectively print by thread.
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.
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 “turning” 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.