| Description |
The goal of this MP is to help you understand (1) how to spawn multiple
processes and threads, and (2) how to use POSIX synchronization primitives.
You will write two separate simple C programs as the first part of MP1. In the
second part, you will be coding a simple C program to get a hands-on experience
on using synchronization primitives. Use any data structures or other system
calls that you need. We suggest that you would start the first part of this MP
early, as the lectures will still cover the second part by next Monday, Feb 6.
Part 1: Process and Thread Management First, get yourself familiar with processes in UNIX. Read chapter 3.3 and 3.4 in R&R (3.1 and 3.2 as well, if necessary). Afterwards, following figure 3.2 in R&R, write a program which creates a process chain, with length N, the argument that main will take in the command line. Following the figure, every process will have a number assigned to it, from 1 to N. Process i shall spawn process i+1 (unless i+1 > N), and then generate a for-loop (for k=1..M, set initially to 100). Note that process N will not spawn children. In each iteration of for-loop, each process will print the following message to stdout, and voluntarily blocks for a certain amount of time. You can do that using sleep or usleep function, defined in unistd.h. (p.314 in R&R) unsigned int sleep(unsigned int seconds); int usleep(unsigned long microseconds); The message that is printed should have the following form: I am process #[mypid], and my child is process #[childpid]: #[k] Finally, each process waits for its child to finish computation, and then return. You will lose points if you do not code your processes to explicitly wait for their children (process N has no children and does not need to wait). Second, write a program which creates N threads (also specified in the command line). To do this, you may find it useful to read chapter 12.1-12.3 in R&R, which discusses POSIX threads. Main will take one argument, N. The function which will be spawned as a thread (name it forLoop) shall take no value as a parameter nor have any return value. Like fork, it takes a for-loop (for k=1..M, set initially to 100). In each iteration, each thread will print the similar message to stdout. Thread #[threadid]: #[k] In both programs, check for errors everywhere, and print messages when errors are received. You will lose points if you ignore errors on pthread_create, etc. Part 2: Thread Synchronization using Semaphores The second part of MP1 is called Challenger-Evaluator problem. Before you start, you may want to read chapter 13, 14 in R&R for better understanding of synchronization of POSIX threads. This problem is similar to the Producer-Consumer problem, so make sure that you understand it. Producer-Consumer problem is introduced in chapter 16 in R&R, although this MP is not as complex. Assume a situation that there is one challenger and multiple evaluators. Challenger's job is to propose the arithmetic expression and expand it from time to time. Evaluators can evaluate only one operation at one time. They will cooperate with one another until the expression is finally simplified to a number. There is only one expression between challenger and evaluators, and both challenger and evaluator can update the expression concurrently. Therefore, the expression should be represented by a shared variable, and thus should be protected by any synchronization primitive. We will use semaphores in MP1. A semaphore is basically an integer variable with two atomic operations: wait and signal. If a semaphore s is bigger than 0, wait tests s and decrements s. If s is equal to 0, it tests s and blocks the caller. On the other hand, if threads are blocked on the semaphore s, which means s is currently equal to 0, then signal unblocks on of these waiting threads. If no threads are blocked on the semaphore, signal increments s. In semaphore.h, there are several functions that implement wait and signal operations. sem_post implements semaphore signaling, and sem_wait implements semaphore wait. There is a slight different version of wait in sem_trywait. All these functions are described in 14.4 in R&R. You may also want to read 14.3 in R&R see how to initialize and uninitialize the semaphores. Declare a global character array (string), which will represent the arithmetic expression. The maximum length will be MAXLEN, set initially to 2000. Assume that there are 4 possible operators: +, -, *, /. Each operator or number will be delimited by <space> character. All expressions are written in pre-order, for example, + * 3 2 - 5 2: should evaluate to 9 * + 2 / 7 2 / 10 2: should evaluate to 25 Write a program (ce.c, ce.h) containing two functions named challenge and evaluate, respectively, which will be spawned as threads. The challenge function shall take in a pre-order arithmetic expression, a string, which will serve as an initial expression to be evaluated. First, copy the initial expression to the global string. Afterwards, it produces a random operator <operator1> and a random single expression such as <operator2> <num1> <num2> (e.g. + 2 3, or * 4 6) and add it to the original expression, as follows: <expression> = <operator1> <expression> <operator2> <num1> <num2> To generate a random number, you may want to look at srand, rand, srandom, random functions. There are slight differences between rand and random, depending on the versions of implementations or systems. For better randomness, you may want to use random and srandom, instead of rand and srand. There is no return value in the challenge function. Whenever the challenge function adds the expression, it should print out the following message: Challenger has added the expression [<new expression>]. Now the expression to be evaluated is [<expression>]. The evaluator function shall take in the thread number, an integer. It will scan through the string to find out which part it should evaluate: the first instance of <operator> <num1> <num2>, as most of you already know. To evaluate any part of the expression, you may want to use atoi function. The number as a result of evaluation will replace the part that it has evaluated. It will be copied back into the global string. (You may find strcpy function useful.) For example, * + 2 / 7 2 / 10 2 will be replaced by * + 2 3 / 10 2 Like the challenge function, it should print out the following message: Evaluator #[threadnum] has evaluated the expression to [<expression>]. If the expression string has been simplified to a single number, exit the program. Finally, write a main program (main.c) that creates 1 challenger thread, and NUMTHREADS evaluator threads (NUMTHREADS set initially to 5). Each evaluator thread shall have its own number from 0 to NUMTHREADS - 1. Pass this thread number when creating each of them. Note that TAs may use another main.c to test your program. Again, check for errors everywhere, and print messages when errors are received. |
| Deliverable |
This assignment is expected to be completed via pair programming. You are
encouraged to form a group of 2, although you may elect to work alone. Newsgroup
communication about general issues is allowed. Please post any questions on the
given code on the newsgroup. You can use the CSIL Linux machines to do the
assignment.
You are strictly required to use C (use stdio.h and printf for output, etc). For the first part, create a fork.c for the multiprocess version, and a thread.c for the multithreaded version. For the second part, create a ce.c for the challenger and evaluator implementations, and a main.c for the main program to test ce.c. To compile you will need to link with the pthread library (-lpthread compiler flag). Finally, create a makefile which builds 3 executables named fork, thread, and main. Create a README file as well, detailing any problems encountered during program design or execution. Include in the README the following information:
|
| Handin |
Use Compass to electronically handin those 6 files (makefile, fork.c,
thread.c, ce.c, ce.h, main.c, README) under the "MP1 Handin" assignment. This
must be done before 4pm on Monday, Feb 13. Every hour late is minus 2% credit.
No submissions accepted after 4pm on Tuesday, Feb 14.
|
| Grading Criteria |
Multiple processes (fork.c) – 20% Multiple threads (thread.c) – 20% Challenger-Evaluator Problem (ce.c, ce.h, main.c) – 50% README – 10% |