Assignment Goals

• To gain experience in writing and debugging multithreaded code.
• To make use of common synchronization primitives such as locks and condition variables.
• Learn an important, sophisticated scheduling algorithm: start time fair queuing (STFQ).

Overview of Project

You will construct and evaluate a proportional-share network scheduler.  In particular, you will

• Create a network send and receive scheduler that limits the maximum aggregate rate at which a set of streams can send or receive
• Create a network send scheduler and receive scheduler that divides specified fractions of send and receive bandwidth among different network streams.

• Evaluate the performance of your scheduler.

 

We have provided you with a simple framework  to help you get started. You will not have to write too many lines of new code. Therefore, focus your attention on developing a clean design and learning good concurrent programming techniques.

Background

When sending and receiving data on a network, most of the time the underlying network does a good job at splitting bandwidth fairly across connections. But, in some cases, it is desirable to limit the rate at which a flow or group of flows sends or to split bandwidth proportionally across flows. For example, if you were receiving a large file across a modem using FTP while also trying to surf the web across the modem, you might want to limit the FTP transfers to 1000 bytes/second so that the rest of the bandwidth can be used to give good interactive response time for your web surfing.

In this assignment, you will be given the source code for simple, unscheduled network streams for sending and receiving data. Your goal is to extend these streams to make use of NWScheduler objects you develop in order to schedule network bandwidth across different streams in various ways.

A Quick Introduction to C++

The right way to think of shared sate is as shared objects. We're therefore going to use C++, C's object-oriented descendent, for this project.

Don't worry. For the subset of C++ relevant to this project, the learning curve will be short (especially assuming you already know Java.) Furthermore, I will provide template code to which you will add the details; this should largely insulate you from having to learn much C++ syntax.

Read A Quick Introduction to C++, and you should be good to go. Note that this document was written over a decade ago, so a few of the comments on the state of standards and tools are a bit out of date (for example, the document warns against using C++ templates because debuggers didn't understand them well back then; this warning is much less applicable today.) Nonetheless, it provides a good, quick overview of the key ideas to use (and some issues/pitfalls to avoid.)

Working with threads

Before you begin the assignment, read Coding Standards for Programming with Threads.  You are required to follow these standards for this project. Because it is impossible to determine the correctness of a multithreaded programming via testing, grading on this project will primarily be based on reading your code not by running tests. Your code must be clear and concise. If your code is not easy to understand, then your grade will be poor, even if the program seems to work. In the real world, unclear multi-threaded code is extremely dangerous -- even if it "works" when you write it, how will the programmer who comes after you debug it, maintain it, or add new features? Feel free to sit down with the TA or instructor during office hours for code inspections before you turn in your project (note: to take advantage of this,  start early!)

To simplify your task, we have developed a simple thread package on top of the standard pthread package for your use. The idea is to shield you from the irrelevant detail that inevitably is part of dealing with pthreads. This way, you use the standard package but you also focus on the project at hand.

The files are sthread.h, sthread.cc, and a simple main.cc program that demonstrates their use.

Files to be included in your .cc files: sthread.h
Files to be linked with your .o files: sthread.o (compiled from sthread.cc)
Other required compiler options (when compiling .cc files): -D_POSIX_PTHREAD_SEMANTICS
Other required linking options (when linking .o files):  -lpthread -lrt

The package provides threads, mutex locks, and condition variables as well as some other utility functions that you may need. This package is built on the posix thread library. For more information, see the man pages for the library functions used in the sthread.cc code.

Getting started

Before you begin the assignment, grab the following code: labT.tar

This tar archive contains the source code to the unscheduled InputStream and OutputStream  server that you will modify and/or extend, as well as some other files that we will describe below. To extract the files from the archive, use the following command.

tar -xvf labT.tar

A directory called labT/ will be created, and your files will be extracted into it. You should be able to make the code in that directory on a Linux host. Then, you should be able to run a simple test by running the following commands in two windows (on one or two machines):

machine1.cs.utexas.edu> receiver 5000

machine2.cs.utexas.edu> sender machine1.cs.utexas.edu 5000 5

We have provided a large amount of code to form the backbone of your project. You should have to write relatively few lines of code yourself. But, you must think carefully about the code that you do write because debugging incorrect multi-threaded code is hard.

Become familiar with the code we provided.

• sthread.cc, sthread.h -- simplified thread library
• receiver.cc, sender.cc, InputStream.cc, InputStream.h, OutputStream.cc, OutputStream.h -- simple unscheduled send/receive code
• ScheduledInputStream.cc, ScheduledInputStream.h, ScheduledOutputStream.cc, ScheduledOutputStream.h, NWScheduler.h, NWScheduler.cc, MaxNWScheduler.h, MaxNWScheduler.cc, STFQNWScheduler.h, STFQNWScheduler.cc -- incomplete code for scheduling input/output streams
• Stats.cc -- incomplete code for tracking statistics
• util.cc, util.h, common.c, common.h -- some utilities and other potentially useful code
• unit.cc -- some unit tests
• SocketLibrary/* -- wrappers around lower-level libraries for network communication

Hint: etags

One of the skills a programmer must have is the ability to quickly understand a body of existing code written by others.

Etags is a really useful tool to let you navigate among a group of source files. Type "make etags"; this will create an index of the source files. Now, open one of the files, say receiver.cc in emacs and move your cursor to the name of some interesting function, say saccept(). Where is this function defined? You can use etags to find out. While the cursor is on that function name, type M-. (that's meta-key . normally esc then .); it will ask you the name of the function you want to find (and guess the right one) so hit return; (it may also ask you what TAGS file to use and guess the right one; if so, hit return again). Voila. You are now looking at the code that defines that function.

M-. is about 99% of what you need to know about etags. M-, and M-* are also useful. Here's a cheat sheet.

As an alternative to etags, many IDE (integrated development environments) such as eclipse provide similar (and more sophisticated) ways to navigate through code, find where functions are defined, etc. If you are already using an IDE, then you probably don't need to worry about etags. Of course real programmers use emacs.

Hint

Years ago, my driver education teacher had the exercise of asking the person driving the demo car to find some obscure street in the neighborhood. The point was to put some cognitive load on the driver so s/he could not entirely concentrate on driving and thereby reveal something about how the driver is likely to drive when s/he doesn't have an instructor sitting in the car. This project has something of that flavor -- the semantics of the objects I am asking you to build are designed to make you think a bit about them while you are also trying to write multi-threaded code. Don't let this trick fool you! Once you think about the specifications a bit, I hope you will realize that the structure of the synchronization can be quite simple if you cleanly structure your system. All of the parts of this project are designed to be simple once you have thought carefully about the design. If the design seems complex, don't start writing code---work on simplifying your design (the last comment is good advice for any project.)

You must follow the restrictive coding standards specified. As I described in class, there are specific reasons for these rules: I believe that if you follow these rules, you are very likely to learn to write good multi-threaded code. Conversely, if you violate these rules, I fear that you may not learn this material as well. Code that fails to conform to these rules is incorrect and will receive significant little credit when this lab is graded.

We have provided the skeleton of class Stats. For part 1 of the project, your job is to complete its implementation. 

Update the state member variables, synchronization member variables, constructor, update(), and print() functions to write thread safe code. The basic idea is for update() to keep track of how many bytes each flow (typically a thread) has sent. Then, when toString() is called, the object produces a string of numbers with the ith number showing the number of bytes the ith stream sent since the last call to toString(), and the last column shows the total bandwidth across all flows since the last call to toString().

E.g., if there were four flows, each sending about 1mbyte/s for 10 seconds and we call toString() each second, the sequence of strings returned might look something like this:

1000000 990000 1100000 1000000 4000000
900000 1200000 950000 950000 4000000
1111111 999999 1013321 942222 4066653
...
966787 944921 1233211 1033254   4178173

The source code provides more details.

Run "make plot1.pdf", which runs the demo/test defined in sendAndRecv.cc, redirecting the output to a file called data1; it then uses plot1.gnuplot to plot the output to the file plot1.pdf.  You can view the file with acroread. E.g.,

> make plot1.pdf
> acroread plot1.pdf

Note: If you add any code that prints to stdout, having each line begin with "#" will cause it to be treated as a comment by gnuplot.

Remember to follow the coding standards!

P.S., Did I remind you to follow the coding standards?

Your next task is to design, implement, and test simple ScheduledOutputStream and NWScheduler abstractions. The ScheduledOutputStream classes should extend the InputStream and OutputStream classes we have given you.

ScheduledOutputStream's key method is write(char *buffer, int len) which sends an array of bytes across the network. ScheduledOutputStream's writes interact with a NWScheduler object shared by many ScheduledOutputStreams so that a write call puts its data into the underlying socket and returns only when it is its turn to do so. For this part of the project, you will ensure that there is a maximum total rate of writes across all sockets in your system.

For part 2, the MaxNWScheduler, which extends class NWScheduler, implements a simple policy. A maximum send rate in bytes per second is specified to the MaxNWScheduler in its constructor, and the total rate of sends across all streams sharing a scheduler must never exceed that specified rate. In other words, if a send s0 transmits its data on the underlying socket at time t0 and transmits b0 bytes, and the maximum rate is m, then the next send s1 must not send its data to the underlying socket before time t1 >= t0 + b0/m. Note that this constraint should be met if s0 and s1 are sends by the same thread on the same stream, if s0 and s1 are sends by different threads on the same stream, if s0 and s1 are sends by different threads on different streams, or if s0 and s1 are sends by the same thread on different streams, so the NWScheduler should be shared across all streams in a process so it can coordinate them.

Important note: in class we warned you not to use sleep() except in rare circumstances. For most of the synchronization in this project, you will use wait(), but there is a place where you will have to use sthread_sleep(): after a buffer is sent, no other buffers can be sent until size/bandwidth seconds have passed. Since this time is a specific time interval, you will need to have one of your threads delay for this time interval by sleeping. You are required to structure your program so that there is one and only one thread that ever calls sleep. This alarm thread will coordinate with all of your other threads via a synchronized shared object. When you want to wake a non-alarm-thread up at a specific time, that thread will call a method on the shared object and wait(), and at the specified time the alarm thread will call another method on the shared object that will signal(). (Part 1 of this project is simple enough that you could conceivably structure the program in other ways, but the main goal of part 1 is to prepare you for part 2, which is too complex for other such ad-hoc approaches, so you are required to follow this structure throughout the design.)

In part 2, you should do the following

1. Modify ScheduledOutputStream and MaxNWScheduler to meet the rules listed above. You probably won't have to modify the base NWScheduler or OutputStream classes.
2. Test your system. Once you've implemented this code, make plot2.pdf and make plot2b.pdf should work. Verify that the results of this experiment make sense.

   You must implement and run other tests of your choosing to evaluate this algorithm in general and your implementation in particular. The code you turn in should include these tests, and the final report should include a discussion of these tests and results (possibly including graphs.)

   I would suggest using gnuplot for graphing since you can set up scripts to automatically run your send and receive programs, pipe their output to a file, post-process the file (e.g., using the awk program), and create a plot. Try make plot2.pdf for an example.  But you are welcome do do all of this manually and use a spreadsheet program instead.

The rate limiting scheduler limits the total amount of bandwidth consumed, but it doesn't guarantee anything about what fraction of bandwidth each stream gets. What if you want to guarantee that all streams get equal amounts of bandwidth?  What if you want to give one stream 10x the bandwidth of another one?

One way to do this would be to use separate schedulers for different streams. If you have a total of 10,000 bytes/s of bandwidth and want to evenly divide it across two streams, you could create two NWSchedulers each of which limits its stream to 5,000 bytes/second. There are two problems with this approach: (1) If the number of streams sharing the 10,000 bytes changes over time, we want to change the allocations to each stream accordingly; (2) If one of the threads ends up needing to use less than its full 5,000 bytes/second, we want to let the other one use the spare capacity (that is, we want a work conserving scheduler.)

The Start Time Fair Queuing algorithm (STFQ, invented by researchers at UT Austin) is a work conserving scheduler that partitions bandwidth fairly across multiple streams. In this part of the project, you will subclass NWScheduler into a STFQNWScheduler class. A detailed description of STFQ is here for those who are interested (you do not need to read this paper to do this project.)

A STFQ scheduler maintains a virtual time. Each buffer to be sent has a start tag and a finish tag. Buffers are sent (or received) in the increasing order of their start tags. STFQ defines how start tags, finish tags, and virtual times are assigned.

• When B_fⁱ-- the i'th buffer from stream f -- arrives, it is given a start tag S_fⁱ = max(F_f^i-1, currentVirtualTime) where F_f^i-1 is the finish tag for buffer i-1 of stream f (or 0 if i == 0) and currentVirtualTime is the current virtual time.
• When B_fⁱ arrives, it is given the finish tag F_fⁱ = S_fⁱ + bufferSize_fⁱ/weight_f where bufferSize_fⁱ  is the size of the buffer being sent/received and weight_f  is the weight of stream f.
• The scheduler has a fixed total bandwidth maxBW. When a buffer of size S is sent at real (not virtual) time t0, the network is busy from real time t0 until real time t1 = t0 + S/maxBW
• Buffers are sent in order of their start tags. When the network is busy, no new buffers are sent. When the network is not busy, the packet with the next lowest start tag is sent (or if no buffers are waiting, the next buffer to arrive is sent when it arrives.)
• Initially, the virtual time is 0. If the network is busy the virtual time is defined to be equal to the start tag of the buffer that is currently being sent. If the network is not busy and no buffers are waiting to be sent, then when the next buffer arrives, the virtual time is set to the maximum  finish tag of any buffer that has been sent.

A ScheduledOutputStream->write() call should return when its buffer has been sent.

To get some intuition for how this works, consider the case when there are a bunch of streams using the network. In that case, each buffer from a given stream is given a start time that is  size/weight higher than the previous buffer from that stream. If all streams start at the same virtual time and have the same send sizes and weights, then each one will get a chance to send at the current virtual time, then the virtual time will advance and they will again each get a chance to send... If one stream's weight is twice that of another, it will be allowed to send twice as many bytes as the other stream. If two streams have the same weight and one stream sends a buffer that is twice the size of the other's, it will have to wait twice as long before its next buffer is sent. Also notice how the use of virtual time makes the algorithm work conserving: if 10 streams with the same weight are all actively sending, each gets 1/10 of the bandwidth. But if 8 of them stop, the remaining two each get 1/2 of the bandwidth. The 'max' rule for assigning start tags and the 'not busy' rule for assigning virtual times ensure that the "right thing" happens when a flow or all flows switch between "active" and "idle" modes. For example, if instead of the above rule, we always set S_fⁱ = F_f^i-1 then a flow that was idle for a long time could start transmitting and monopolize the network bandwidth until it "caught up," which would give the other flows bad performance for potentially long periods of time.

In part 3, you should do the following

1. Create  a STFQNWScheduler that extends NWScheduler and imposes the scheduling rules listed above.
2. Run the tests specified in the makefile to generate plot3.pdf and plot3b.pdf. Design, implment, and run some additional tests. Look at the graphs and consider whether they make sense. Comment on your tests and analysis in the report.

Electronically turn in (1) your well commented and elegant source code and (2) a file called report.pdf or report.ps (in postscript or pdf format, not a proprietary and platform-specific format such as .doc).

Your report.[.ps|pdf] file should include four sections:

• Section 1: Administrative: your name, your eid, the number of slip days that you have used so far, the number of slip days you've used on this project, and the number of slip days you have remaining.
• Sections 2, 3, 4: A discussion of parts 1, 2, and 3 of your project. Each section should briefly discuss your high level design and any issues/known bugs in that part of the project. Then it should discuss your testing strategy and evaluation results, including graphs.

If you make report.pdf, you will produce a skeleton report from report.tex (a latex file with text and formatting commands) and plot[1,1b,2,2b,3,3b].pdf. Feel free to update report.tex and add more graphs or to use a different editing program to produce your report. (If you choose to do the latter, you probably want to update the makefile to change or eliminate our rule for producing report.pdf from report.tex.)

The following guidelines should help smooth the process of delivering your project. You can help us a great deal by observing the following:

• After you finish your work, please use the turnin utility to submit your work.

Usage:

turnin --submit impjdi handin-372-labT your_files

The Makefile targets handin.tar and handin automate this.
• Do not include object files in your submission!! (Or core dumps!!!) (e.g., run "make clean" before turnin.)
• You must use a Makefile to compile the program and produce an executable.
• The project will be graded on the public Linux  cluster (run 'cshosts publinux' to get a list) In principle, the libraries you use are Posix compliant, so portability should not be a major issue if you develop on a different platform. (Although we did have some problems getting things to run cleanly on the Suns...). But, if you chose to develop on a different platform, porting and testing on Linux by the deadline is your responsibility. The statement "it worked on my other machine" will not be considered in the grading process in any way.
• Select reasonable names for your files and variables. This way, you make grading easier.

• Your files should never refer to absolute names. For example, to include foo.h, do not write:
   #include "/u/username/projects/proj1/foo.h"  /* poor style */
• You are encouraged to reuse your own code that you might have developed in previous courses to handle things such as queues, sorting, etc.
• You are also encouraged to use code provided by a public library such as the GNU library.
• You will work in two-person teams on this project. You may not look at the written work of any other student. This includes, for example, looking at another student's screen to help them debug, looking at another student's print-out, working with another student to sketch a high-level design on a white-board. See the syllabus for additional details.
• If you find that the problem is under specified, please make reasonable assumptions and document them in the documentation file.
• You are required to adhere to the multi-threaded coding standards/rules discussed in class and described in the hand out.
• Code will be evaluated based on its correctness, clarity, and elegance. Strive for simplicity. Think before you code.

80% Code

The most important factor in grading your code will be code inspection and evaluation of the descriptions in the write-ups. Remember, if your code does not follow the standards, it is wrong. If your code is not clear and easy to understand, it is wrong.
The second most important factor in grading your code will be an evaluation of your testing strategy and the analysis of correctness in the write-ups.
We may also run our own tests.

30% part 1
30% part 2
20% part 3

Hint: One of the most common mistakes we see on projects year after year is using sthread_sleep() when you should be using scond_wait(). The handout discusses this issue in more detail.  This year, I don't want anyone to make this mistake, so be warned: seeing an sthread_sleep in your code in the wrong place is an easy way for a TA to conclude that you don't know how to write multithreaded programs, and the TAs will be instructed to deduct a large number of points from any project that uses sleep() when it should wait() on a condition variable. If you find yourself writing sleep() other than the one place mentioned above, treat that as a red flag that you might be making a mistake.  If you don't know when to use one and when to use the other, come to office hours, but don't start writing code!

Hint: Before writing any code, think of the types of simple generic data structures that we have discussed in class (e.g., bounded buffer, readers/writers, ...). These particular data structures may (or may not) be directly useful for this project, but this flavor of data structure will be extremely useful. 

20% Experiments & Analysis

Graphs and discussions of results and testing strategy.

Start early, we mean it!!!