Transcript ppt
Programming Project #2
CS-502 Operating Systems
Spring 2006
CS502 Spring 2006
Programming project #2
1
Programming Assignment
1. Write a mailbox package for
communicating among threads.
2. Test your package with a simple program
addem that uses multiple threads to add
numbers.
3. Use your package to implement a multithreaded version of the game of Life.
CS502 Spring 2006
Programming project #2
2
Purpose
• To practice writing concurrent programs
that share resources and information
• To practice using the Linux pthread and
semaphore facilities
• To practice structuring a system facility in
terms of its interface and implementation
CS502 Spring 2006
Programming project #2
3
Part 0: Mailboxes
• msg structure:–
struct msg {
int iFrom;
// who sent message (thread #)
int type;
// type (part of payload)
int value1;// 1st value (part of payload)
int value2;// 2nd value (part of payload)
}
• Operations
•
•
•
•
SendMsg(int iTo, struct msg *pMsg)
RecvMsg(int iFrom, struct msg *pMsg)
InitMailboxes(int number_of_mailboxes)
CleanupMailboxes()
• Each mailbox can hold at most one message
CS502 Spring 2006
Programming project #2
4
Operations on Mailboxes
• SendMsg(int iTo, struct msg *pMsg)
• Copies contents of pMsg* into mailbox iTo
• Blocks if mailbox is already full
• RecvMsg(int iFrom, struct msg *pMsg)
• Receives contents from mailbox iFrom, copies to pMsg*
• Blocks if mailbox is empty
• InitMailboxes(int number_of_mailboxes)
• Creates an array of mailboxes, each comprising an instance of
msg and the necessary semaphores
• Initializes the semaphores to indicate mailboxes are empty
• CleanupMailboxes()
• Deletes the array of mailboxes and the semaphores
CS502 Spring 2006
Programming project #2
5
Semaphores
#include <semaphore.h>
• Operations of interest:–
–
–
–
–
sem_init()
sem_wait()
sem_post()
sem_destroy()
– …
CS502 Spring 2006
Programming project #2
6
Implementation of Mailboxes
• Implement as a module or package
– Mailbox.h as interface
• Defines msg and all operations
– Mailbox.c as implementation
• Hides all details from client
• Especially semaphores!
CS502 Spring 2006
Programming project #2
7
Part 1: addem
• Purpose: to test and exercise the Mailbox package
• Command line
– % addem n M
– Uses n threads to add the numbers from 1 to M
• Main thread is thread_0
–
–
–
–
Includes pthread.h, Mailbox.h
Reads and parses command line
Initializes n+1 mailboxes using InitMailboxes()
Creates n worker threads, dispatches part of task to
each thread via SendMsg
– Get results via RecvMsg, combines and prints results.
– Cleans up after itself!
CS502 Spring 2006
Programming project #2
8
Part 2: Game of Life
• John Conway, Scientific American, April 1970.
• Rectangular grid, n m squares
• Each square has eight nearest neighbors
• May be occupied or unoccupied
• Rules for next generation
• An occupied square with 0 or 1 occupied neighbors dies of
loneliness
• An occupied with 4, 5, 6, 7, or 8 neighbors dies of
overcrowding
• An occupied with 2 or 3 occupied neighbors survives
• An unoccupied square with exactly 3 occupied neighbors
becomes occupied
CS502 Spring 2006
Programming project #2
9
Example
• 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
CS502 Spring 2006
Programming project #2
10
Operation
• Command line
– % life n filename g [print [input]]
– Uses n threads to play g generations starting
from the position in file filename
– Optional arguments print and input are to aid in
debugging
CS502 Spring 2006
Programming project #2
11
Operation (continued)
• Main thread is thread_0
– Includes pthread.h, Mailbox.h
– Reads and parses command line
– Creates even and odd generation arrays
• Initializes even array from file
– Initializes n+1 mailboxes using InitMailboxes()
– Creates n worker threads, dispatches range of rows to each thread
via SendMsg
– Loops to compute generations
•
•
•
•
Sends go message to each thread
Get results via RecvMsg
Combines results into new generation array
Determines whether or not it is time to stop
– Cleans up after itself!
CS502 Spring 2006
Programming project #2
12
Project Submission
• Due Monday, March 6 at start of class
• Must run on CS or CCC computers at WPI!
• Submit via turnin
• command = ‘/cs/bin/turnin’ on CCC
machines
• classname = ‘cs502’
• assignment = ‘project2’
• Include
• Code, makefiles, test files or input, test output
• Bring printed copy to class.
CS502 Spring 2006
Programming project #2
13