Project 2 - User-Level Threads
Outline
Out: Thursday, October 17, 2002
Part 1 and 2 Due: Monday, October 28, 2002 11:59 PM
Part 3 Due: Monday, November 4, 2002 11:59 PM
Part 4 Due: Thursday, November 7, 2002 beginning of section
Tasks:
- Implement a user-level thread manager.
- Add a set of common synchronization primitives to your thread package.
- Implement a multithreaded web-server to test your thread package.
- Analyze your design and test results in a report.
Updates:
- 10-18-02: Code updated. Use only version 1.02 available on spinlock/coredump at /cse451/projects/simplethreads-1.02.tar.gz. Version 1.0 was incorrect and should be deleted.
- 10-18-02: Due dates fixed. Parts 1 and 2 by 10/28/02, Part 3 by 11/4/02, and Part 4 by 11/7/02.
- 10-25-02: Turnin is now enabled for part A. Use...
turnin -ccse451=AA -pproject2a my-turnin-directory
- 10-30-02: Turnin is now enabled for part B. Use...
turnin -ccse451=AA -pproject2b my-turnin-directory
- 10-30-02: The WebStone benchmark tool is now available on coredump/spinlock at /cse451/projects/webclient. See below for complete instructions.
- 11-6-02: Turnin is now enabled for part C. Use...
turnin -ccse451=AA -pproject2c my-turnin-directory
Assignment Goals
- To gain understanding of how thread packages are implemented,
including data structures used, the interface provided, and common
problems they face.
- To make use of common synchronization primitives such as
locks and condition variables.
- To understand some of the problems with user-level threads.
- To interact with the instructor and TA.
- To understand the concept of overlapping I/O and computation.
- To practice discussion and analysis of your designs.
Background
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).
Simplethreads
You will be using the simplethreads package for this assignment. It is
available on spinlock/coredump in
/cse451/projects/simplethreads-1.X.tar.gz (Where X is the release
number 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 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.) It will not work with Cygwin. It
has been reported to work with Mac OS X v10.1, but Alex was not able to
reproduce this. Please send mail to the list if you get it working on
Cygwin or Mac OS X.
To begin, copy that 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:
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. |
web/ |
The multithreaded 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 steps as
simplethreads for compilation). In the simplethreads-1.X
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:
- Copy the tar.gz source to your directory.
- tar -xvzf simplethreads-1.X.tar.gz
- cd simplethreads-1.X
- ./configure
- make
- Run the programs in test/
To Add a Source File
If you add a new source file, do the following:
- 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.
- From the top-level directory (simplethreads-1.X), run
automake.
- Also from the top-level directory, run ./configure.
- Your file is now added; run make as usual to build
it.
To Add a New Test Program
- 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)
- Follow steps 2-4 above.
The Assignment
Part 1: Implement Thread Scheduling
|
For part 1, we give you:
- An implementation of a simple queue (sthread_queue.h).
- A context-switch function that, given a new stack pointer, will
switch contexts (sthread_ctx.h).
- A new-stack function that will create and initialize a new stack
such that it is ready to run.
- Skeleton routines for a user-level thread system
(sthread_user.c).
It is your job to complete the thread system, implementing:
- Data structures to represent threads (struct _sthread in
sthread_user.c).
- A thread creation routine (sthread_user_create()).
- A thread destruction routine (sthread_user_exit()).
- A simple non-preemptive thread scheduler.
- A mechanism for a thread to voluntarily yield, allowing another
thread to run (sthread_user_yield()).
- 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:
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 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.
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
- Figure out what each function you need to implement does. Look at
some of the test programs to see usage examples.
- Examine the supporting routines we've provided (primarily in
sthread_queue.h and sthread_ctx.h).
- Design your threading algorithm: When are threads put on the
ready queue? When are threads removed? Where is
sthread_switch called?
- Figure out how to start a new thread and what to do about the
initial thread (the one that calls sthread_user_init).
- Talk to your fellow students and the TAs about your design.
- Implement it.
- 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 provided routines 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 cleaned up
(i.e. sthread_exit() is called).
- The start routine passed to sthread_new_ctx does not take
any arguments (unlike the routine that your
sthread_user_create is passed). 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 globals 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 lots of 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 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:
- 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_*()).
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).
Hints
- Figure out how to block a thread, making it wait on some queue.
How do you get the calling thread? How do you switch out of it?
How will you wind up back in it?
- Locks do not immediately switch threads when unlocked.
Part 3: Implement a Multithreaded Web Server
|
Every web server has the following basic algorithm:
- Web server starts and listens (see listen(2)) for
incoming connections.
- A client (i.e. web browser) opens a connection.
- The server accepts (see accept(2)) the connection.
- The client sends an http request.
- The server services the request by:
- Parsing the request.
- Finding the requested file.
- Reading the file.
- Sending a set of http headers, followed by the contents of the file, to
the client.
- Closing the connection.
- The client displays the file to the user.
The sioux webserver in the web directory impelements
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 eleminate 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.
The webserver should accept the --sthread-pthread and
--sthread-user arguments (see the provided routine
sthread_parse_impl() in sthread.h). This will allow
you to test with both user-level and kernel-level threads and compare.
You should also 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.
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.
Experiment
For your analysis, design an experiment to determine the effectiveness
of user-level threads as compared to kernel-level threads in your
webserver. 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.
Include a presentation of your experimental design, data, analysis,
and conclusions in your report.
Conclusions
Discuss conclusions you have reached from this project. What
recomendations do you have for designers of thread systems?
Using the Web Benchmark
This will be installed by the time you need it. This is now installed.
The WebStone web benchmark tool has been installed on spinlock and
coredump as /cse451/projects/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:
- -n CLIENTS specify the number of parallel clients to
simulate.
- -l LOOPS specify the number of times each client should
fetch the files.
- -w SERVER specify the hostname of the webserver
(when sioux is started, it prints a URL including the hostname).
- -u URLLIST specify a file containin a list of URLs to
fetch, one per line, each followed by a weight (e.g. 1).
All of the above parameters are required. The URLLIST file
should contain one complete URL 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 almond.cs.washington.edu, with
two simulated clients each fetching the index.html file twice, one would
run:
/cse451/projects/webclient -w almond.cs.washington.edu -l 2 -n 2 -u
./urls
Where the file urls would contain the following single line:
http://almond.cs.washington.edu:14038/index.html 1
Parts 1 & 2
In your top-level simplethreads directory, run make
dist. This will produce a file named
simplethreads-X.X.tar.gz. Submit this file using the
turnin(1L) program under project name project2a by
11:59pm on the day it is due. turnin will not work on
coredump/spinlock, so you'll need to use one of the general-purpose
machines (sumatra, fiji, ceylon, or tahiti).
If you have added any files, run tar -tzf
simplethreads-X.X.tar.gz and check to make sure your new files
are listed.
Part 3
Follow the same instructions as for parts 1 & 2; use the project name
project2b.
Part 4
Turnin a final version of your code including any scripts or other files you used in
your experiment by 11:59 PM Wednesday November 6, 2002. It should be submitted under
the project name project 2c.
You have three options for turning in your report:
- Submit a PDF of your report along with your code Wednesday night.
- Email a PDF to your TA by the beginning of section, Thursday November 7, 2002.
- Hand in a paper copy of your report in section, Thursday November 7, 2002.