Project 2: Thread Scheduling, Synchronization
|...where the disposal of time is surrendered merely to the chance of incidence, chaos will soon reign. -Victor Hugo|
Due: Friday April 1st, Midnight.|
Etc: This project is to be done with your partner in C (not C++).
BackgroundPrograms are commonly parallelized using multiple processes or multiple threads within a process. Processes are more strongly isolated from each other because they do not share an address space, but data sharing is more difficult (also due to the fact that they do not share an address space). A hybrid approach, using multiple processes and multiple threads within a process, is also reasonable; the latest Apache web server uses this approach. Here is a short history of threads. Threads may be implemented entirely at user-level, in the kernel, or a combination of the two. In this assignment you will learn about the tradeoffs between these approaches, and gain some concurrent programming experience.
For this project you will be using simplethreads. Simplethreads is a user-level thread package which borrows a fair amount of code from from the GNU portable threads package. While you will only have to add code in small/well-defined sections, you will have to develop a general idea of how the package works. See these instructions on how to build, modify, and add tests to the Simplethreads package.
CreditsThis assignment and much of the writeup are borrowed from a CSE 451 project at the University of Washington. Rick Cox is the author of Simplethreads.
The AssignmentIf you choose to divy up parts between members make sure that each understands the other's work.
Part 1: Thread SchedulingSimplethreads already contains:
At the top layer, applications will use the sthread package (through the API defined in sthread.h). sthread.c will then call either the routines in sthread_pthread.c or your routines in sthread_user.c (it chooses based on the value passed to sthread_init()). Your sthread_user.c, in turn, builds on the sthread_ctx functions (as described in sthread_ctx.h).
Applications (the top-layer) may not use any routines except those listed in sthread.h. They must not know how the threads are implemented; they simply request threads be created (after initializing the library), and maybe request yields/exits. For example, they have no access to sthread_queue. Nor do they keep lists of running threads around; that is the job of the grey box.
Similarly, your grey box - sthread_user.c - should not need to know how sthread_ctx is implemented. Do not attempt to modify the sthread_ctx_t directly; use the routines declared in sthread_ctx.h.Recommended Procedure:
Part 2: Mutexes and Condition VariablesFor part 2, you'll use the thread system you wrote in part 1, extending it to provide support for mutexs (a.k.a. locks) and condition variables. Skeleton functions are again provided in lib/sthread_user.c. You need to:
Part 3: Synchronization Problem
There are several famous synchronization problems in computer science. For part 3, your job is to implement a "food services" problem, an instance of the better-known multiple-producer, multiple-consumer problem. There are N cooks (each a separate thread) that constantly produce burgers. We'll assume for debugging purposes that each burger has a unique id assigned to it at the time it is created. The cooks place their burgers on a stack. Each time a cook produces a burger, she prints a message containing the id of the burger just cooked. There are M hungry students (each a separate thread) that constantly grab burgers from the stack and eat them. Each time a student eats a burger, she prints a message containing the id of the burger she just ate. Ensure, for health and sanity reasons, that a given burger is consumed at most once by at most one student.
Note that you are implementing an application now. That means the only interface to the thread system that you should use is that described by sthread.h (as distributed in the tar.gz). Do not use functions internal to sthreads directly from your solution to this problem.
Place your solution in a new file called test-burgers.c in the test directory. The program should take 3 command-line arguments: N, M, and the total number of burgers to cook. For examples, test-burgers 5 10 100 should simulate 5 cooks, 10 students, and 100 burgers. The Simplethreads instructions tell you how to add a test program.Hints
Part 4: Multithreaded Web ServerEvery web server has the following basic algorithm:
For part 4 you will make sioux into a multithreaded web server. It must use a thread pool approach; it should not create a new thread for each request. Instead, incoming requests should be distributed to a pool of waiting threads. Make sure your threads are properly and efficiently synchronized. Use the routines you implemented in part 2.
Don't forget that the only interface to the thread system that you should use is that described by sthread.h. Do not use functions internal to sthreads directly from sioux.
You should accept a command-line argument indicating how many threads to use ("sioux 10" should use 10 threads).
Because we have not used asynchronous IO in sioux, it will be very difficult to obtain good performance using the user-level threads. In some cases, it may be difficult to even get correct behavior at all times (e.g., if no new requests are sent, existing requests may not be serviced at all). We recommend using kernel-level (i.e. pthreads) threads for this part.
Testing your webserverTo test the webserver you will need to have multiple clients access it simultaneously. To do this use the wget utility, which downloads a file using its URL. You can use the following shell script test.csh, but change the hostname and port number so that wget requests a file from your webserver. In the file below my server was running on machine royal21 using port 9493. Log onto several different machines (e.g. ssh royal13 in one XTerm and ssh royal27 in another) and run test.csh (simultaneously) from each. You can adjust the number of iterations to make the script run longer or shorter.
#!/s/std/bin/tcsh set i=0 while ( $i < 100 ) wget http://royal21.cs.wisc.edu:9493 -O temp & set i = `expr $i + 1` endType chmod u+x test.csh at the prompt to make test.csh executable. Type ./test.csh to run the script.
In your top-level simplethreads directory, run make dist. This will produce a file named simplethreads-1.10.tar.gz. Run tar tvzf simplethreads-1.10.tar.gz and check to make sure all simplethreads files, and any new files you have added, are listed. Copy the tar.gz file to ~cs537-2/handin/NAME/p2 where NAME is the login name of one member of your team. Hand in one copy per group. After the deadline you will lose permissions to write to your handin directory. Remember that late projects are not accepted. Plan accordingly.
As with the first project, most of your grade will be determined by how well your implementation works. We will run your code on a suite of test cases, some will test correct execution, other error cases. Exercise your program's capabilities thoroughly (read try to break it). Develop on whichever system you like, though make sure your code works on an emperor or royal machine as that is where it will be tested.