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:

  1. Finish your sthreads package by implementing the synchronization primitives
  2. Extend your original sthreads test suite to include testing of the mutices and condition variables.
  3. 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:

The Assignment

Implement Mutices, and Condition Variables

We give you

  1. 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:

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

Implement a Multithreaded Web Server

For your convenience, we give you

  1. Code for atomic operations including test_and_set.
  2. The code for a multi-threaded web server, minus a threadpool for dispatching requests
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.

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

Analysis and Writeup

In your writeup, make sure you include the following:

  1. A list of all modified and added files as well as where they are in your directory hierarchy.
  2. A finalized design doc explaining how your complete user level thread system works (scheduler, locks, etc)
  3. 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.
  4. A list of all the extra credit you did as well as any pertinent information regarding your extra credit projects
Answer the following questions:

  1. Is join a useful command? Does it make sense to have a thread require joining after exit to avoid memory leaks?
  2. Was the preemptive nature of the thread package useful for the multithreaded server?
  3. When would you not want a preemptive scheduler? Describe an application who's needs would be better met with a non-preemptive scheduler?.
  4. 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):

  1. What was the hardest part of this assignment?
  2. What was the easiest part?
  3. What technical issues detracted from the learning in this project? Do you have suggestions for avoiding these issues?
  4. What was the learning to work ratio? Do you think you learned and was it worth it?
  5. What could have been done to improve the whole project?
  6. Which operating systems concepts do you think this project covered?
  7. 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)
  8. 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)
Extra Credit
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.
  1. Fix your scheduler. Respond to all the errors pointed out in your code from part 1.
  2. 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.
  1. Implement a semaphore.
  2. Implement a monitor system (using conventions to ensure calling of monitor enter and exit)
Turnin

Hardcopy Turnin

The hardcopy is due in class the day after the electronic turnin. Make sure you have the following in your hard copy: 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.

- DO NOT GIVE US A MS-WORD DOCUMENT -

Benchmarking your web server.

Using the Web Benchmark

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:

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.