Project 2 Part 2, Synchronization primitives
and multi-threaded web server
Dates
Out: Sunday, February, 17, 2003
Due: Friday, February 28, 2003 Monday, March 3, 2003
Tasks:
- Finish your sthreads package by implementing the synchronization
primitives
- Extend your original sthreads test suite to include testing of the
mutices and condition variables.
- Implement a multi-threaded web server using the sthreads package.
Note: There is no reason to do the synchronization primitives before the web
server. Pick whatever order you find easier for you. One student suggsted that
implementing the webserver first may give you a better idea as to how the
synchronization primitives (and the rest of sthreads) are supposed to work.
Updates/Announcements:
- Feb 26: Simplethreads is at version 1.05. Be sure to update
as there are some large changes to the sioux web server as well as the
addition of a skeleton for a threadpool. This release also fixes a few
more race conditions in the supplied code.
- Feb 26: Webstone benchmark client installed
- Feb 17: Simplethreads is at version 1.04. Be sure to update
as there are critical additions
The Assignment
Implement Mutices, and Condition Variables
|
We give you
- Code for atomic operations including test_and_set.
You'll use the thread system you wrote in part 1,
extending it to provide support for mutices (a.k.a. locks) and
condition variables. Skeleton functions are again provided in
lib/sthread_user.c.
You need to:
- Design data structures for mutices (struct _sthread_mutex)
and condition variables (struct _sthread_cond).
- Implement the mutex operations (sthread_user_mutex_*()).
- Implement the condition variable operations (sthread_user_cond_*()).
Remember that you code is preemptive. That means that you cannot assume that
ANY operation executes atomically except for the ones provided in
atomic.h. We will be grading according to this assumption! No
leniency will be given for not using atomic operations where required
(the whole correctness of your implementation hinges on proper use of atomic
operations!).
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.
- We are not requiring an early design doc turnin this time, but we
recommend you write one and run it by us first before implementing. If
nothing else, it will be good practice for industry or grad school.
- Coding is a draft/revision process (like writing an essay). You
are welcome to run drafts by us.
Implement a Multithreaded Web Server
|
For your convenience, we give you
- Code for atomic operations including test_and_set.
- The code for a multi-threaded web server, minus a threadpool for
dispatching requests
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 implements
the server side of the above algorithm.
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.
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.
To test your web server, we have provided a tool that hammers your web server
with requests. The information for how to use this tool is down in the
last section titled Benchmarking your web server.
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.
Hints
- Develop your application using --sthread-pthread.
In your writeup, make sure you include the following:
- A list of all modified and added files as well as where they are in your
directory hierarchy.
- A finalized design doc explaining how your complete user level
thread system works (scheduler, locks, etc)
- Explain any difficulties or problems that you might have in your code
including things you decided not to fix or issues that you could not resolve.
- A list of all the extra credit you did as well as any pertinent information
regarding your extra credit projects
Answer the following questions:
- Is join a useful command? Does it make sense to have a thread
require joining after exit to avoid memory leaks?
- Was the preemptive nature of the thread package useful for the
multithreaded server?
- When would you not want a preemptive scheduler? Describe an application
who's needs would be better met with a non-preemptive scheduler?.
- Why do operating systems use preemptive scheduling? Is this smart?
Is there a reason they would use a non-preemptive system?
Also please answer the following feedback questions (your answers here will not
affect your grade):
- What was the hardest part of this assignment?
- What was the easiest part?
- What technical issues detracted from the learning in this project?
Do you have suggestions for avoiding these issues?
- What was the learning to work ratio? Do you think you learned and was it
worth it?
- What could have been done to improve the whole project?
- Which operating systems concepts do you think this project covered?
- Was too much time spent on this project? If so, what kind of project
would you rather have had in place? (would have rather have spent 2 weeks
on filesystems? vm? etc)
- What insults would you like to throw at the TAs for assigning this thing?
(In other words, please give us any feedback, suggestions, or comments on
the project)
You may do any of the extra credit from the previous portion of the project.
Here is a list of more extra credit projects that you may choose from. As
always, you can propose your own project to the TAs for extra credit.
- Fix your scheduler. Respond to all the errors pointed out in your code
from part 1.
- Benchmark your web server
and report the results. The requirements
for this are spelled out at the end of the benchmarking section. This is one of
the easiest extra credit projects to do. However, you may need to leave
your simulation running for a large number of hours, so start early.
For the following extra credit projects, make sure you run your basic
design across a TA before implementing it. That way, we can catch anything
fundamentally wrong with your approach early on.
- Implement a semaphore.
- Implement a monitor system (using conventions to ensure calling of
monitor enter and exit)
Hardcopy Turnin
The hardcopy is due in class the day after the electronic turnin. Make sure
you have the following in your hard copy:
- Your previous turnin with the corrections
- All the changed code and anything else relevant
- A copy of your writeup
To print out your code in unix, you will want to do something like the
following:
enscript -DDuplex:true -DTumble:true -2r -Ec -G -C -H5 -j
-P<printer name> <files>
Yes, use that exact line as it will save you lots of paper. It will
print out your code in 2 columns, duplex, with syntax highlighting, and line
numbers. Check "man enscript" for more options. It's a great program, if a
bit difficult to use.
Electronic Turnin
Turnin an electronic copy (see below) of your writeup and a final version of
your code including any axillary scripts or things that are relevant (you'll
probably only have these if you do some of the extra credit) by 11:59 PM on the
day it is due. It should be submitted under the project name project2-2.
Follow the same instructions for packaging up the code in part 1.
You have two options for the electronic format of your writeup:
DO NOT GIVE US A MS-WORD DOCUMENT
Neither of your TAs has windows installed anywhere that they normally work. We
can't open word files easily (and no, we don't want to use Open Office or
anything). This is really important, so I'll write it again with an annoying
blink and marquee tag.
Benchmarking your web server.
|
This will be installed by the time you need
it.
It is now installed (2/26/2003).
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 containing 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 1 -n 1 -u
./urls
Where the file urls would contain the following single line:
http://almond.cs.washington.edu:14038/index.html 1
Extra Credit: Experiment
This was originally part of the main assignment, but in interests of time,
we decided to move it to extra credit. The main objective is to show the
performance difference between kernel and user threads as well as
the performance of systems under low, medium, and high levels of
multiprogramming.
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. You will probably see a performance
difference in at least 2 dimensions: your threads versus linux threads,
and low number of threads versus high number of threads.
Include a presentation of your experimental design, data, analysis,
and conclusions in your report.