15-111

Lab 7 - Web Server Simulation with Heaps

Due: Wednesday, April 1, 2009

Overview

In this assignment, you will implement both a FIFO queue (like the one you did for the Palindrome assignment) and a priority queue (using a Heap), and you will compare how efficient they are when implementing a web server. A web server will often receive several requests at once, and we need to determine in what order we should handle them. One approach would be to simply process the jobs in the order that they arrive. Another approach would be to always process the smallest job, so that a small HTML file does not get stuck behind a large MPEG file.

This assignment asks you to generate a workload, simulate both approaches, and report the simulated average turn-around time for each approach.

For this assignment, we are not providing you with skeletons for any of the classes. You will need to create the *.java files and build the files from scratch. Please keep the following in mind:

There should be exactly one class definition per file, and the name of the file should exactly match the name of the class defined inside.
The methods that are part of the interface for each class that we have specified should be named exactly as we have described. Our test program will assume the methods are named and implemented as we have described here.
Only those methods specified here should be part of the interface. Anything else that you choose to implement should be a private helper method.
Your code should be thoroughly commented, including descriptions of the classes and methods as well as explanations of any non-obvious code or important algorithmic steps.

Part I: The Heap Class

This class will be used to model a priority queue. For this assignment, we will assume that smaller items have a higher priority, so you will be implementing a min-heap.

You must use a Vector to implement your Heap. To be able to use a Vector in the Heap class, the Heap.java file must begin with:

import java.util.Vector;

The methods that you should define for the Heap class are:

public Heap()
This is the constructor for the Heap class. It should initialize an empty Heap.
public boolean isEmpty()
This method should return true if there are no objects stored within the Heap, and false otherwise.
public void insert(Comparable data)
Inserts the specified object into the Heap. It should run in O(log n) time. It is suggested that you implement this method using one or more helper methods.
public Comparable removeMin()
This method should remove the lowest valued element in the Heap. It should run in O(log n) time. It is suggested that you implement this method with one or more helper methods.

Part II: The FifoQueue Class

This class will be used to model a standard First-In-First-Out queue like you designed for the Palindrome assignment.

You must use a LinkedList to implement the FifoQueue. To make life easier for you, you can use Java's LinkedList class if you prefer. To be able to use Java's LinkedList in the FifoQueue class, the FifoQueue.java file must begin with:

import java.util.LinkedList;

If you want to use the LinkedList that we wrote, you should not include this line. The methods that you should define for the FifoQueue class are:

public FifoQueue()
This is the constructor for the FifoQueue class. It should initialize an empty FifoQueue.
public boolean isEmpty()
This method should return true if there are no objects stored within the FifoQueue, and false otherwise.
public void insert(Comparable data)
Inserts the specified object at the end/tail of the FifoQueue.
public Comparable removeMin()
This method should remove the oldest element from the head of the FifoQueue.

Part III: The WebObject Class

This class should create simulated Web objects, like HTML pages, MPEGs, GIFs, &c. For the purpose of our simulation, the only property that a WebObject has is a size in the range of 1024Bytes (1KB) to 1,048,576B (1024KB), measured in whole kilobytes.

The WebObject class must implement the Comparable interface.

The methods you should define for the WebObject class are:

public WebObject()
This is the constructor. It should create a new web object with a random size in the range of 1KB to 1MB (1024 KB).
public int getSize()
This method returns the size of the WebObject
public WebObject copy()
This method should create an exact copy of the WebObject.
public int compareTo(Object compareObj)
This method defines how to compare two objects of the WebObject class. It returns 0 if the sizes of two WebObjects are equal, a negative number if the size of this WebObject is smaller than the size of the object which was passed in, or a positive number if the size of this object is larger than the size of the object which was passed in. This method is required because we are implementing the Comparable interface.

The constructor for the WebObject requires you to generate a random size. To get a random value, you first need to create an object of Java's Random class. Once you have an object, you can call the nextInt() method, which generates a random int value.


	Random r = new Random();
	int num = r.nextInt();

This value will be in the approximate range of -2,000,000,000 to 2,000,000,000. To get this in the range of 1 to 1024, you need to do the following.

Obtain the absolute value of the number, using the Math.abs(int) method.
Use the "%" operator to obtain the remainder when that number is divided by 1024. This gives us numbers in the range of 0 to 1023.
Add 1 to this number, to get a value between 1 and 1024 inclusive.

In order to use the Random class in the WebObject class, the WebObject.java file must begin with the line:

import java.util.Random;

Part IV: The ServerSimulation Class

This class should simulate the activity of two Web servers, one using FIFO scheduling and the other using Shortest Job First (SJF) scheduling (using the Heap). It should simulate the processing of a collection of requests and report the average service time for each of the two simulated servers.

The methods you should write for the ServerSimulation class are:

public ServerSimulation(int numObjects, int kiloByteRate)
The constructor should create numObjects of WebObjects. Each WebObject represents a Web page or other object request by a user. Each of these should be copied. One of them should be enqueued in the Heap, a SJF queue, and the other in the FifoQueue.
The kiloByteRate defines the speed of the Web server’s connection in terms of kilobytes of data per second. It should be stored within a private instance variable.
public int calculateFIFOAverage()
This method should calculate the average service time for a job on the FIFO-based Web server. It should do this by dequeuing each job one at a time. It should then calculate the service time for this job by dividing its size in kilobytes by the kilobyte rate of the connection. A running total should be kept of the service times. Another running total should be kept that is the sum of the service times encountered by each job (the service times of everything before plus the service time for the object itself). At the end, dividing this total service time by the number of jobs will yield the average service time.
The following pseudocode may be useful:

* Initalize delaySoFar to 0
* Initalize sumOfDelays to 0
* Initialize countOfJobs to 0

* While the queue is not empty

- Increment the count of jobs
- Add the current delaySoFar to the sumOfDelays
- Dequeue the next WebObject
- Divide the size of the object by the byteRate and add this amount of time to the delaySoFar

* Return (sumOfDelays / countOfJobs)
public int calculateSJFAverage()
This method should do exactly the same thing as calculateFIFOAverage() above, except that it operates on the Heap, the priority queue based on job size.

Part V: The ServerEvaluation Class

You should implement a class with only one method - main(). This method should be a reasonably good test of the calculateSJFAverage() and calculateFIFOAverage() of the ServerSimulation class. This should show that SJF scheduling by Web servers using priority queues (Heaps) produces a better average service time than traditional queue-based FIFO scheduling.

Generating Random Numbers

If you create a new Random object to generate the size of each WebObject, you will likely get several values in a row that are the same. The reason for this is that when you create a Random object, it uses the current time in milliseconds as the seed (the value from which it generates the "random" sequence of numbers). The computer is fast enough that it is possible for many WebObjects to be created within the same millisecond, in which case all of them will have the same seed and therefore generate the same value.

To get around this, you should create one Random object that all of the WebObjects will use when generating their sizes. In order to do this, you need to declare the Random variable to be part of the class like you would for an instance variable, but you will declare it using the keyword "static".

The "static" keyword indicates that instead of being an instance variable where every object has its own copy, it is a variable that is shared by all objects of the class. So, if you create a static Random object as part of the WebObject class, every WebObject will use the same random number generator, and so you wont have the problem of bunches of WebObjects having the same size (although it is still possible that there will be some duplicates because of the random behavior).

So, in your WebObject class, you should include among the declarations of any instance variables:

private static Random rand = new Random();

where "rand" is whatever name you want to give the Random object.

Also, there is a method in the API for the Random class which automatically generates an int between 0 and some upper bound. Feel free to use this method instead of explicitly calculating the absolute value and then using the % operator to give it the upper bound.