Back to Assignments

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:



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:



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:



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:

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.

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:



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.