Project 2 - User-Level Threads



Part 1 and 2 Due:
Part 3 and 4 Due:

For this project, you will be working in groups of 3. Please use the online tool to register your groups.


  1. Implement a user-level thread manager.
  2. Add a set of common synchronization primitives to your thread package.
  3. Implement a multithreaded web-server to test your thread package.
  4. Analyze your design and test results in a report.

Assignment Goals


In the beginning (well, the relative beginning), there was UNIX. UNIX supported multiprogramming; that is, there could be multiple independent processes each running with a single thread of control.

As new applications were developed, programmers increasingly desired multiple threads of control within a single process so they could all access common data. For example, databases might be able to process several queries at the same time, all using the same data. Sometimes, they used multiple processes to get this effect, but it was difficult to share data between processes (which is typically viewed as advantage, since it provides isolation, but here it was a problem).

What they wanted was multithreading support: the ability to run several threads of control within a single address space, all able to access the same memory (because they all have the same mapping function). The programmers realized that they could implement this entirely in the user-level, without modifying the kernel at all, if they were clever.

As you'll discover in the last part of this assignment, there were some problems with this approach, which motivated kernel developers to include thread support in the kernel itself (and motivated researchers to do it better; see Scheduler Activations).


You will be using the simplethreads package for this assignment. It is available on spinlock/coredump in /cse451/projects/simplethreads-1.X.tar.gz or .tar.gz">for download. (Where X is the release number, which may be updated. Use the latest version. Please watch for updates as the project progresses.)

This project, since it does not involve modifying the kernel, does not require VMWare. The simplethreads package has been tested on:

Please do not use attu.

To begin, copy the tar.gz file to your work directory (/cse451/LOGIN) and run

tar -xvzf simplethreads-1.X.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:

lib/ The simplethreads thread library itself.
lib/sthread_user.c Your part 1 and part 2 implementations go here.
lib/sthread_ctx.{c,h} Support for creating new stacks and switching between them.
lib/sthread_switch_{powerpc,i386}.h Assembly functions for saving registers and switching stacks.
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.
web/ The webserver for part 3.

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 build steps as simplethreads). In the simplethreads-1.X directory, run ./configure to generate an appropriately configured Makefile.

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. Because both provide the same interface (once you've completed parts 1 and 2, anyway), the applications don't even know which version is running. The configure script will accept a --with-pthreads argument to select the version in use (the default is user threads). To switch back and forth, re-run configure and then run make clean.

In summary, the steps are:

  1. Copy the tar.gz source to your directory.
  2. tar -xvzf simplethreads-1.X.tar.gz
  3. cd simplethreads-1.X
  4. ./configure [--with-pthreads]
  5. make
  6. make check (Run the programs in test/)

To Add a Source File

If you add a new source file, do the following:

  1. Edit the 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. The edited has to be processed by the automake tool before it can be used by make. From within the top-level directory:
  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/ 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.

To Add a New Arbitrary File

  1. Edit the in the directory containing your file. Add your file to the list EXTRA_DIST (see top-level for an example).
  2. Follow steps 2-4 above.

The Assignment

Part 1: Implement Thread Scheduling

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, and nasty stuff like that. 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:

Simplethread Layers

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

  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.


Part 2: Implement Mutexs 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:

The non-preemptive nature of this assignment aids you greatly in your tasks (since it gives you atomic critical sections). However, you should think about what you would need to do if your threads were preemptive; add comments to the routines indicating precisely where the critical sections are and what appropriate protection might be applicable (e.g. how you would use a spinlock or other atomic operation).


Part 3: Implement a Multithreaded Web Server

Every web server has the following basic algorithm:

  1. Web server starts and listens (see listen(2)) for incoming connections.
  2. A client (i.e. web browser) opens a connection.
  3. The server accepts (see accept(2)) the connection.
  4. The client sends an http request.
  5. The server services the request by:
    1. Parsing the request.
    2. Finding the requested file.
    3. Reading the file.
    4. Sending a set of http headers, followed by the contents of the file, to the client.
    5. Closing the connection.
  6. The client displays the file to the user.

The sioux webserver in the web directory implements the server side of the above algorithm.

For part 3 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 (this is to eliminate thread creation costs from your experimental data). Make sure your threads are properly and efficiently synchronized. Use the routines you implemented in part 2.

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 sioux.

You should accept a command-line flag indicating how many threads to use.

In testing, you may encounter "Address already in use" errors. TCP connections require a delay before a given port can be reused, so simply waiting a minute or two should be sufficient.

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 threads for this part.

Part 4: Analysis and Report

Design Discussion

Your report should include a section on the design of your user-level threads, synchronization primitives, and webserver. Discuss the goals of each, how well your design meets those goals, and the tradeoffs that were made. Justify your design decisions as compared with other possible designs. Goals for some aspects (e.g. synchronization) are discussed in the text; for others, you need to determine what appropriate goals are. Some goals you may wish to consider for all systems code are speed, complexity, and usefulness.


For your analysis, design an experiment to either:

This experiment should be conducted in the standard scientific method. It should explore the performance of the server under a variety of different conditions chosen to confirm or deny various aspects of your hypothesis. You may want to go over your experimental design with a TA.

There are several variables to examine in either option. While you will probably need to vary at least a few parameters to gain a good understanding of the behavior of your system, keep in mind that a good experiment only varies one parameter at a time. You should also make sure to repeat each trial several times, to increase the confidence in your data.

Include a presentation of your experimental design, data, analysis, and conclusions in your report.


Discuss conclusions you have reached from this project. What recommendations do you have for designers of thread systems? Can you recommend user threads or kernel threads? Why? What other features might be useful?

Timing on the Pentium 4

To help you conduct microbenchmarks, we have provided an example using the Pentium time stamp counter to obtain cycle-accurate timing information. The clock speed, in MHz, of a Linux machine can be found by examining the file /proc/cpuinfo. The sample code can be found on coredump/spinlock in /cse451/projects/timer.tar.gz or here. (Unfortunately, we do not have sample code for PowerPC timing.)

Using the Web Benchmark

The WebStone web benchmark tool has been installed on spinlock and coredump as /cse451/projects/tools/bin/webclient. It measures the throughput and latency of a webserver under varying loads. It simulates a number of active clients, all sending requests in parallel (it does this by forking several times). Each client requests a set of files, possibly looping through that set multiple times. When the test is complete, each client outputs the connection delay, response time, bytes transfered, and throughput it observed (depending on the server, the clients may all observe very similar results, or the data may vary widely). The tool takes the following arguments:

All of the above parameters are required. The URLLIST file should contain one relative URL (just the file name) per line followed by a space and then a number (the number is the weight representing how often to request the file relative to other files in the list - most likely, 1 is the value you want).

For example, to test a webserver on, with two simulated clients each fetching the index.html file twice, one would run:

/cse451/projects/tools/bin/webclient -w -p 12703 -l 2 -n 2 -u ./urls

Where the file urls would contain the following single line:

/index.html 1

Please turnin one copy of the project per group. It would help us if you select one group member to execute all turnins (only the last submission will be graded).

Parts 1 and 2

In your top-level simplethreads directory, run make dist. This will produce a file named simplethreads-1.X.tar.gz. Make a new directory called username where username is your CSE login and move simplethreads-1.X.tar.gz into that directory. Submit this directory using the turnin(1L) program under project name project2a by . Turnin will not work on coredump/spinlock, so you'll need to use attu.

Run tar -tzf simplethreads-1.X.tar.gz and check to make sure all simplethreads files, and any new files you have added, are listed. (For parts 3 and 4, make sure any files from your experiment are included.)

All submitted files should be in text format. Word documents should not be submitted (by turnin or email).

Parts 3 and 4

Follow the same instructions as for parts 1 and 2. Turnin a final version of your code including any scripts or other files you used in your experiment by . It should be submitted under the project name project2b.

You should turn in your report on paper in lecture by