Project 3 - Threads

Tasks:

1. Implement a user-level thread manager.
2. Add a set of common synchronization primitives to your thread package.
3. Build a thread pool in C
4. Turn a single-threaded server into a multithreaded server

Assignment Goals

• To gain understanding of how thread packages are implemented, including data structures used, the interface provided, and common problems they face.
• To understand some of the problems with user-level threads.
• To make use of common synchronization primitives such as locks and condition variables.
• To gain experience in writing and debugging multithreaded code. In particular, you will be exposed to code that can deadlock or have race conditions.
• To understand the concept of overlapping I/O and computation.
• To practice discussion and analysis of your designs.

Background

One of the challenges in building Internet services is dealing with concurrency. In particular, many independent clients can simultaneously send requests to a given server. A server therefore must be designed to deal with concurrent requests. There are many different strategies for doing this; we will explore two in this project.

A very simple design strategy is to build the server as a single-threaded program. The server's single thread waits until a new request arrives, reads the request, processes the request, and then writes a response back to the originating client. In the meantime, if another request arrives while the server is processing the first, that other request is ignored until the first has been dealt with fully. An example interaction between a server and two clients is illustrated in the following figure.

A more sophisticated strategy would be to build the server as a multithreaded program. When a request arrives at the server, a thread is dispatched to handle it. If multiple tasks arrive concurrently, then multiple server threads will execute concurrently. Each dispatched thread does exactly what the single-threaded server did previously; it reads the request, processes it, then writes a response:

For the purposes of this example, we assume that the server allows a maximum of 2 threads at a time. As the picture above shows, even though request #2 arrives while request #1 is being processed by the first server thread, the second server thread is available to deal with request #2 concurrently. As a result, while the first server thread is processing request #1 (hence using the CPU), the second server thread can read request #2 over the network. Thus, network I/O and computation are overlapped. This has many beneficial effects: the CPU is more effectively utilized, the throughput of the server is increased, and the response time of the server (as seen by the clients) is decreased.

Programmers realized that they could implement multithreading support entirely at the user level, without modifying the kernel at all. The first part of this assignment will require you to implement the thread manager and locking primitives for a user-level thread package.

As we will see, there have been problems with threads implemented entirely at the user level, which motivated kernel developers to include thread support into the kernel. For the second phase of the assignment, you will be using the thread support provided by the kernel, and not using the package that you created. You will be given the source code to a very simple single-threaded networked server. Your goal is to convert this single-threaded server into a multithreaded server, by building a "thread pool" and integrating it into the server. A thread pool is an object that contains a fixed number of threads and supports two operations: dispatch, which causes one thread from the pool to wake up and enter a specified function, and destroy, which kills off all of the threads in the pool and frees up any memory associated with the pool.

Simplethreads

This project, since it does not involve modifying the kernel, does not require VMWare. The simplethreads package should work on any Linux 2.4 machine (it will not work on Linux 2.2 due to missing support for a necessary syscall), and other varieties of UNIX that support pthreads as well. (Please do not use tahiti, fiji, ceylon, or sumatra.)

To begin, copy that file to your work directory (/cse451/LOGIN) and run
tar -xvzf simplethreads-1.02.tar.gz
to expand it (if you are working on a different machine, see scp(1)).

Simplethreads contains a lot of files, but most are safe to ignore. Pay attention to:

Dir/File	Contents
lib/	The simplethreads thread library itself.
lib/sthread_user.c	Your part 1 and part 2 implementations go here.
lib/sthread_ctx.h	Support for creating new stacks and switching between them.
lib/sthread_queue.h	A simple queue that you may find useful.
include/	Contains sthread.h, the public API to the library (the functions available for apps using the library).
test/	Test programs for the library.

Like many UNIX programs, simplethreads uses a configure script to determine parameters of the machine needed for compilation (in fact, you'll find many UNIX packages follow exactly the same steps as simplethreads for compilation). In the simplethreads-1.02 directory, run ./configure to test all these parameters.

Finally, build the package by typing make. You can also build an individual part, such as the library, by running make in a subdirectory. Or, if you just want to compile one file, run make myfile.o (from within the directory containing myfile.c).

Note that, as you make changes, it is only necessary to repeat the last step (make).

One interesting feature of simplethreads is that applications built using it can use either the native, kernel-provided threads or the user-level threads that you'll implement. When running the test programs, use --sthread-pthread to select kernel threads or --sthread-user to select user threads (they default to kernel threads).

In summary, the steps are:

1. Copy the tar.gz source to your directory.
2. tar -xvzf simplethreads-1.02.tar.gz
3. cd simplethreads-1.02
4. ./configure
5. make
6. Run the programs in test/

To Add a Source File

1. Edit the Makefile.am in the directory containing the new file, adding it to the _SOURCES for the library/executable the file is a part of. E.g., to add a new file in the lib/ directory that will become part of the sthread library, add it to the libsthread_la_SOURCES line.
2. From the top-level directory (simplethreads-1.02), run automake.
3. Also from the top-level directory, run ./configure.
4. Your file is now added; run make as usual to build it.

To Add a New Test Program

1. Edit test/Makefile.am. Add your program to the list bin_PROGRAMS. Create new variables prog_SOURCES and prog_LDADD following the examples of the programs already there. For example, if the new program is named test-silly, add:

   test_silly_SOURCES = test-silly.c other sources here
   test_silly_LDADD = $(ldadd)
   

2. Follow steps 2-4 above.

The Assignment

For part 1, we give you:

1. An implementation of a simple queue (sthread_queue.h).
2. A context-switch function that, given a new stack pointer, will switch contexts (sthread_ctx.h).
3. A new-stack function that will create and initialize a new stack such that it is ready to run.
4. Skeleton routines for a user-level thread system (sthread_user.c).

It is your job to complete the thread system, implementing:

1. Data structures to represent threads (struct _sthread in sthread_user.c).
2. A thread creation routine (sthread_user_create()).
3. A thread destruction routine (sthread_user_exit()).
4. A simple non-preemptive thread scheduler.
5. A mechanism for a thread to voluntarily yield, allowing another thread to run (sthread_user_yield()).
6. A routine to initialize your data structures (sthread_user_init()).

The routines in sthread_ctx.h do all of the stack manipulation, PC changing, register storing, etc. Rather than focusing on that, this assignment focuses on managing the thread contexts. Viewed as a layered system, you need to implement the grey box below:

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 that threads be created (after initializing the library), and maybe request yeilds/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, to encapsulate and hide from the applications.

Similarly, your grey box - sthread_user.c - should not need to know how sthread_ctx is implemented, nor should it modify any functionality in that file. Do not attempt to modify the sthread_ctx_t directly; use the routines declared in sthread_ctx.h.

Recommended Procedure

1. Figure out what each function you need to implement does. Look at some of the test programs to see usage examples.
2. Examine the supporting routines we've provided (primarily in sthread_queue.h and sthread_ctx.h).
3. Design your threading algorithm: When are threads put on the ready queue? When are threads removed? Where is sthread_switch called?
4. Figure out how to start a new thread and what to do about the initial thread (the one that calls sthread_user_init).
5. Talk to your fellow students and the TAs about your design.
6. Implement it.
7. Test it. The test programs provided are not adequate; for full confidence in your implementation, you'll need to create some of your own.

Hints

• sthread_create should not immediatly run the new thread.
• Use the routines provided in sthread_ctx.h. You don't need to write any assembly or try to directly manipulate registers for this assignment, nor is an understanding of the exact layout of the stack required (in fact, the routines provided go to great lengths to avoid requiring such knowledge).
• If the routine passed to sthread_create() finishes (returns), you need to make sure the thread's resources are released (i.e. sthread_exit() is called).
• The start routine passed to sthread_new_ctx does not take any arguments (unlike the routine passed to your sthread_user_create). So you can't create a new stack directly with the user-supplied routine; you need to supply a routine that takes no arguments but somehow winds up invoking the user's routine with the user's argument.
• You should free any resources allocated when a thread exits (whether it exits explicitly, by calling sthread_exit(), or implicitly, because the start routine returns). However, you should not attempt to free the stack of a running thread (note: to free a stack, use shread_free_ctx()). This requires a few tricks.
• Dealing with the initial thread is tricky. You need to make sure that an sthread_t struct is created for it at some point, so it can be scheduled like the other threads. However, it wasn't created by your sthread_user_create() function. Remember that, while a thread is running, the state stored in the sthread_t is garbage (though it is probably important that you have a such a struct, so you've got some place to put the state when you want to stop the thread).
• Be very careful using any local variables after calling sthread_switch() as their values are quite likely different from what they were before (you're on a different stack).
• While global variables are bad in general, there will be places in this assignment where they are necessary.
• To debug with gdb(1) or any other debugger, run the configure script with --disable-shared (and then re-run make from the top level). This disables shared-libraries, which cause trouble for the debugger. When you run the project, gdb will stop each time you create a new thread with a message like "Program received signal SIGUSR1, User defined signal 1." This is OK - just type continue.

Part 2: Implement Mutexes and Condition Variables

For 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:

• Design data structures for mutexes (struct _sthread_mutex) and condition variables (struct _sthread_cond).
• Implement the mutex operations (sthread_user_mutex_*()).
• Implement the condition variable operations (sthread_user_cond_*()).

Hints

• Figure out how to block a thread, making it wait on some queue. How do you get the currently running thread? How do you switch out of it? How will you wind up back in it?
• Locks do not immediately switch threads when unlocked.

/cse451/doug/server.tar.gz

tar -xvzf server.tar.gz

As you should see from threadpool.h, your thread pool implementation must support the following three operations:

threadpool_t create_threadpool(int num_threads_in_pool);

void dispatch(threadpool_t pool, dispatch_fn dispatch_to_here, void *arg);

void destroy_threadpool(threadpool_t pool);

The create_threadpool() function should create and return a threadpool. The threadpool must have exactly num_threads_in_pool threads inside of it. If the threadpool can't be created for some reason, this function should return NULL.

The dispatch() function takes a threadpool as an argument, as well as a function pointer and a (void *) argument to pass into the function. If there are available threads in the threadpool, dispatch( ) will cause exactly one thread in the pool to wake up and invoke the supplied function with the supplied argument. (Once the function call returns, the dispatched thread will re-enter the thread pool.) If there are no available threads in the pool, i.e. they have all been dispatched, then dispatch( ) must block until one becomes available by returning from its previous dispatch.

In either case, as soon as a thread has been dispatched, dispatch( ) must return.

The destroy_threadpool function will cause all of the threads in the threadpool to "commit suicide", after which any memory allocated for the threadpool should be freed. (I found this to be the trickiest function to get right.)

man -k pthread | less

In addition to this example code, we've also provided you with some code (threadpool_test.c) that makes use of a thread pool. Type the command make from inside the server/ directory to compile all the code in there, including your threadpool source code and test code. An executable called threadpool_test should be created. When you have a working thread pool implementation, running the test code should result in output that looks like this. Note that just because you get this output while using your thread pool implementation, it doesn't mean that your thread pool works. Your implementation may have subtle race conditions that only show up occasionally. We will be reading your source code to look for such races.

Requirement #1: there should be NO BUSYWAITING in any of your code.

Requirement #2: there should be NO DEADLOCKS and NO RACE CONDITIONS in your code.

Hint #1: pthreads condition variables have the same operations as semaphores (signal and wait), but unlike semaphores, condition variables do not have history. If a thread calls signal, and there is no other thread blocked on wait, then the signal will be lost.

Part 4: Use your thread pool to turn the single-threaded server into a multithreaded server.

In the server.tar.gz archive, we have provided you with a working implementation of a single-threaded network server. The server source code is in the file called server.c. The server implementation makes use of a network library that implements all of the routines needed to read and write data over the Internet. (We've provided you with the source code to this network library in case you're curious. The source code is in the SocketLibrary/ subdirectory. But you shouldn't have to modify an of that code.)

The server is designed to do the following:

1. Create a "listening socket" on a network port specified as a command-line argument to the server. Because the server has created a listening socket, clients can now open connections to the server and send it data. In fact, multiple clients can simultaneously open multiple connections to the server. As explained in the background at the top of this web page, the single-threaded server doesn't handle multiple connections in parallel, but just works on them one at a time.

2. Perpetually loop, doing the following:
   • Accept a new connection from a client. (If there are multiple connections that have arrived, only one will be accepted. The rest will queue up inside the OS, and will be accepted by the server in subsequent iterations through this loop.)

   • Read data from the new connection. (Our server reads 10 bytes.)

   • Process the request. Our server simply does some mindless computation on the 10 bytes. (How much computation it does can be altered by changing the NUM_LOOPS constant in the server source code.)

   • Write a response back to the client. (Our server writes 10 bytes.)

   • Close the connection to the client.

What you must do is change the server to work in the following way:

1. Create a thread pool. (How big the pool is should be specified as a command-line argument to your server.)

2. Create a listening socket.

3. Perpetually loop, doing the following:
   • Accept a new connection from a client.

   • Dispatch the connection to a thread from the thread pool. (Yes, if the thread pool is empty, the server's main thread will block in the dispatch until a thread becomes available.)

• Read data from the dispatched connection.

• Process the request.

• Write a response back to the client.

• Close the connection to the client.

We've also provided you with an implementation of a network client. You should not need to modify or understand the implementation of this client. The client is single-threaded: it loops forever, and in each loop iteration, it opens a connection to the server, writes a request, reads a response, and closes the connection. Therefore, to fully test your multithreaded server, you will need to run multiple clients in parallel.

To launch the single-threaded server, give the following command (on spinlock, coredump, or inside VMware):

./server 4324

To launch a client, give the following command (in another window):

./client servername 4324

./client localhost 4324

To run multiple clients simultaneously, you could issue the following commands:

bash$ ./client localhost 4324 &
bash$ ./client localhost 4324 &
bash$ ./client localhost 4324 &
etc..

Requirement #1: You must implement your multithreaded server by changing the source code to the single-threaded server (server.c).

Requirement #2: You must not create or modify any other source files (besides your threadpool implementation, of course).

Hint #1: You shouldn't need to change or add much code in the existing single-threaded server. We've nicely structured the single-threaded server so that you can reuse most of its functions.

Hint #2: You shouldn't need to understand how network programming works if you don't want to. By heeding hint #1, you will be shielded from all of the details of network programming. Don't be afraid to look under the covers, though!

Hint #3: The code we've provided doesn't ever print anything out. While you're debugging your code, you might want to add some print statements at various places in the client or server to help you figure out what's happening. Make sure you disable the print statements before doing part 5 of the assignment.

Part 5: Measure the performance of your multithreaded server

Now that you have a working multithreaded server, it's time to put it through its paces. You will measure the throughput of your server as a function of the number of threads in the threadpool, and the amount of computation performed in the server. Throughput is simply defined as the number of requests per second that the server can handle.

This means that you need to instrument your server with code that periodically displays the throughput that the server is handling. To do this, just have the main thread (i.e. the code that calls dispatch on the threadpool) increment a counter for every dispatch it issues. Every now and then (i.e., whenever the counter increases by some value, say 50 or 100), take a timestamp using the gettimeofday() system call. Use these timestamps to calculate and print out the server's throughput. (Don't worry about keeping more than 2 timestamps around.)

To change how much computation the server performs, just alter the value of the NUM_LOOPS constant in the server source code. Higher numbers mean more computation. In fact, I suggest you make this another command-line argument to your server.

What you need to do is measure and report the throughput of the server in the following 36 conditions:

• # threads in pool = 1 and NUM_LOOPS=1, 100, 1000, 10000, 100000, 500000
• # threads in pool = 2 and NUM_LOOPS=1, 100, 1000, 10000, 100000, 500000
• # threads in pool = 4 and NUM_LOOPS=1, 100, 1000, 10000, 100000, 500000
• # threads in pool = 8 and NUM_LOOPS=1, 100, 1000, 10000, 100000, 500000
• # threads in pool = 16 and NUM_LOOPS=1, 100, 1000, 10000, 100000, 500000
• # threads in pool = 32 and NUM_LOOPS=1, 100, 1000, 10000, 100000, 500000

(You should run at least as many clients as you have threads in the server's threadpool. For example, for # threads in pool = 4, you should run at least 4 clients. Report the number of clients used in each experiment too.)

To gather this data, run your clients and server inside VMware on a lab workstation. This will guarantee that nobody else is running their server on the same machine as you, thereby disturbing your experiment.

Using your favorite graphing package (such as Microsoft Excel), plot a graph that looks something like:

In other words, your graph should plot the throughput of your server as a function of the number of threads in the thread pool. You should plot a separate line for each different value of the NUM_LOOPS variable. You should play with logarithmic-scale axes (if necessary) in order to get your graph to reveal as much information as possible.

Parts 1 and 2

Your writeup should include the following:

• Design description of your user-level threads and synchronization primitives. Discuss the goals of each, how well your design meets those goals, and the tradeoffs that were made. Each person needs to put this in a readme-username.txt for the part 1 & 2 turnin.

  Note: Each student (including those working together in a group) needs to write their own independent write-up.

If you have added any files, run tar -tzf simplethreads-1.02.tar.gz before you submit and check to make sure your new files are listed.

Your writeup should include the following:

• A verbal description of the structure of your threadpool implementation, including a list of any design decisions you made.

• A list of critical sections inside your threadpool code (and why they are critical sections).

• A description of the synchronization inside your threadpool. What condition variables did you need, where, and why? Under what conditions do threads block, and which thread is responsible for waking up a blocked thread?

• The graph you produced in part 5 (make sure it is in a well known file format), as well as an explanation of what the graph shows and why it is shaped the way it is. Focus your discussion on the interesting features in your graph.

• Discuss conclusions you have reached from this project. What recommendations do you have for designers of thread systems?