This assignment is designed to give you experience working with Java threads in a wide variety of scenarios. This project does not involve VMWare. You should do this project in your project teams.
Start early! This project does not require a huge amount of code, but it does require some background reading and a good bit of thinking.
You have all been given accounts on a 4-way multiprocessor, amlia.cs.washington.edu. In addition, most or all lab Linux machines are multi-processors.
To get started, first download the scaffolding files . Use the command 'tar xvf os-project2.tar' to unpack this tar file. There are four sub-directories under src/, corresponding to the four parts of the assignment (the jars directory contains helper functionality; you do not need to look in there). Each sub-directory has a makefile, which supports the "make" target (for building code) and the "make run" target (for running code). Also, 'make clean' deletes .class files and emacs backup files.
Note that any new Java files will be automatically compiled. You should not need to modify the Makefiles.
Note that bugs in concurrent programs are often called Heisenbugs . This is because they have an annoying tendency to disappear or mutate under inspection. This is why it is particularly important to get the program right the first time.
How do you write thread-safe programs? A good start is to follow the two rules we laid down in class: 1) Any shared, mutable state must be properly synchronized; and 2) Compound actions must be protected by a single lock.
Your assignment for part 1 is to implement semaphores using built-in Java functionality (e.g., locks and condition variables). You can use any feature of Java, except java.util.concurrent.Semaphore (or, any other off-the-shelf implementation of Semaphores). However, the Java documentation does provide some useful documentation on Semaphore behavior.
For this part, the scaffolding code in Semaphore.java provides the semaphore interface, which you are required to fill in. In addition, the make run command invokes a simple test routine. Note that the semaphore in this example should behave exactly like a lock (i.e., only one thread in the critical section at a time).
Consider a circle or radius r inscribed in a square:
From basic geometry, we know the areas of the circle and the square (π r^2 and 4 r^2, respectively).
In addition, we can use a large number of random points to estimate the ratio of the circle's area to the square's area, as shown in the following pseudocode:
int pointsInCircle = 0;
for i=0..NUM_SAMPLES {
Point p = chooseRandomPointInSquare();
if (p.insideCircle())
pointsInCircle++;
}
float areaRatio = (float) pointsInCircle / NUM_SAMPLES;
public double calculate(int numSamples, int numThreads) {
return 0.0; // TODO: implement this!
}
We will test your π calculator by invoking 'make test'. The test
functionality is contained in PiCalculatorTest.java. This allows you
to use the 'make run' target for the benchmarking step.
Key point: The number of random samples should be a fixed constant that does not depend on the number of threads. So, with K samples and N threads, each thread does K/N random samples.
In addition, your writeup should provide an explanation of this graph. In particular, you should explain your results in terms of Amdahl's law (what are N and F for this experiment?).
For general web server background, you should look at the following overview . Note that the web server code in scaffolding is derived from this web server.
For this part of the project, we provide you with a single-threaded web server. You are required to convert it into a multi-threaded web server. In addition, you are required to add implement a "statistics" page, which provides visibility into the web server's behavior.
http://hostname:8080/
... where "hostname" is replaced by the name of the host you are running on. If you are running on the same machine as another team, you may encounter a port conflict. In this case, simply change your port number to something else. I would make sure this works before doing anything else.
The web server serves files from the webroot/ subdirectory. You can add files here if you wish. Caveats: the web server is primitive: it only supports text files and html files. Also, any file larger than 64K will be truncated.
Your solution should utilize a static thread pool , which is created at system startup. After the system starts up, you should not create (or destroy) any threads. For benchmarking (described below), the size of the thread pool should be easily adjustable. How you do this is up to you.
For this step, you will add a bit of visibility into the operation of the webserver. The /STATS URL has been coded to return a special "statistics" page (see Response.java). You need to augment this page to return the following information:
You should submit a writeup that includes a graph with threads on the x-axis and throughput (in bytes/sec or req/sec) on the y-axis. For output, you can use the web benchmark output, or you can utilize the statistics information you implemented in step 2. Explain the results! In particular, you should discuss how many threads the web server can utilize, as compared to the pi calculator application.
The WebStone web benchmark tool is installed on forkbomb as /cse451/projects/tools/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 almond.cs.washington.edu, with two simulated clients each fetching the index.html file twice, one would run:
/cse451/projects/tools/bin/webclient -w almond.cs.washington.edu -p 12703 -l 2 -n 2 -u ./urls
Where the file urls would contain the following single line:
/index.html 1
For this part of the project, we provide you with a basic GUI which calculates the first N fibonacci numbers. Your task is to implement the "cancel" button, which stops a long-lived Fibonacci computation in its tracks. This is trickier than it sounds, because it requires digging into the details of how Java's GUI framework (called Swing) manages threads and concurrency.
Your job is to implement the cancel button. Task cancellation should stop the current computation, but should display the results that have been obtained so far. In other words, don't throw away work that has been done; it is OK to display a partial result on the screen.
Added 10/16/06: Your program should only allow one active Fibonacci calculation. A new calculation can start only when the previous calculation has ended (or has been cancelled).
(You might notice that the implementation of Fibonnaci is particularly slow. This was done intentionally to make the system do more work. You shouldn't try to optimize the provided fibonacci algorithm. This is operating systems, not algorithms...)
(BTW, no fair making fun of the GUI. This is operating systems, not HCI...)
In addition, you will need to understand how thread interruption works in Java. Read Sun's documentation, and ask your TAs or instructor if you have questions.
We will test your solutions by invoking 'make run'. So, make sure this does something sensible for each of your solutions. Exception: we will test the pi-calculator by invoking 'make test'.