Modeling a Server Farm

The main purpose of this project is to use our Queue structure to model job division in a multi-server (or processor) setting. Typically, the model has jobs arriving over time and upon arrival must immediately be assigned to a server for processing. Each server maintains its own queue of jobs for processing and operates under the rule that it must process jobs in the order of their arrival.

---

Tasks

Familiarize yourself with the Job class

We have provided you with the Job class you will need for this project. You do not need to change any of the code in the Job class, but you should familiarize yourself with its methods as you will need to use them. The Job class has the following useful methods implemented. You can expect to use all of them by the end of the project.

• public double getArrivalTime(): this returns the time the job arrived at the server farm.
• public double getProcessingTimeNeeded(): this returns the total amount of processing time the job needed to finish when it arrived at the server farm.
• public double getProcesssingTimeRemaining(): this returns the amount of processing time the job still needs to be considered done (this will be less than or equal to getProcessingTimeNeeded(). It will go down as you spend time processing the job).
• public boolean isFinished(): returns true if this job has been processed for long enough to finish (i.e. it's done).
• public double timeInQueue(): returns the amount of time between when the job arrived at the server farm, and when it was finished processing. This will include the total processing time, and potentially some time spent waiting to be processed.
• public void process(double timeToProcessFor, double timeProcessingStarted): spends timeToProcessFor units of time processing the job. If the job finishes, this method updates the values of timeInQueue and isFinished to be accurate. The timeProcessingStarted indicates what time it was on the system clock when process was called. (This just helps compute when the job finished).

The Server class

The first class you will write for this project is a Server class. An individual Server needs to manage a Queue of Jobs, allowing for jobs to be processed in a FIFO (first-in-first-out) manner. Additionally, the Server needs to track system time (i.e. the time on the clock) and some summary statistics about the jobs it is processing that will be needed to analyze the simulation.

You must maintain a Queue of jobs using your LinkedList class that implements the Queue interface. You should also maintain several fields for accounting, including a double named sysTime to track system time and another double field named remainingTime that tracks the remaining amount of processing time needed for all jobs still in the queue, and totalWaitingTime that tracks the total amount of time spent waiting and processing for all jobs processed by the server. All of these fields can start at 0 at the beginning of the simulation.

You can test the overall functionality using the supplied ServerTests that will be used to evaluate your code. You may wish to add additional tests to this file to aid in your debugging.

Implement the following methods for the Server class:

• public Server() this constructor initializes whatever fields the Server will need in order for it to support the other methods. The Server can assume that the system time, number of jobs processed, and total wait time will all start at 0 at its initialization. The Queue of jobs will be empty.
• public void addJob(Job job): adds the specified Job job into the queue. This is a good place to update the remainingTime field if you have one.
• public void processTo(double time): advances the system time of this queue to the specified time time. This method must make sure that the elapsed time was spent processing jobs in the queue. This method is a bit unintuitive to implement and there are some important details to get right. We have included some additional hints for how to go about it here.
• public double remainingWorkInQueue(): returns the total remaining processing time in this Server's queue (make sure you store this as a class field. Otherwise your code will run too slow!).
• public double getTotalWaitingTime(): returns the total waiting time for all of the jobs processed by the server so far (as above, store this as a class field).
• public int size(): returns the number of Jobs in this Server's queue. (As above, make sure you store this as a field. Otherwise your code will be too slow!)
• public void draw(Graphics g, Color c, double loc, int numberOfServers): This is necessary for the GUI we've provided. For this method, you can copy and paste the following method into your Server class. Make sure to import the following in order for it to work: java.awt.Graphics; java.awt.Color; java.awt.Toolkit; java.awt.Font.

  public void draw(Graphics g, Color c, double loc, int numberOfServers){
      double sep = (ServerFarmViz.HEIGHT - 20) / (numberOfServers + 2.0);
      g.setColor(Color.BLACK);
      g.setFont(new Font(g.getFont().getName(), g.getFont().getStyle(), (int) (72.0 * (sep * .5) / Toolkit.getDefaultToolkit().getScreenResolution())));
      g.drawString("Work: " + (remainingWorkInQueue() < 1000 ? remainingWorkInQueue() : ">1000"), 2, (int) (loc + .2 * sep));
      g.drawString("Jobs: " + (size() < 1000 ? size() : ">1000"), 5 , (int) (loc + .55 * sep));
      g.setColor(c); 
      g.fillRect((int) (3 * sep), (int) loc, (int) (.8 * remainingWorkInQueue()), (int) sep);
      g.drawOval(2 * (int) sep, (int) loc, (int) sep, (int) sep);
      if (remainingWorkInQueue() == 0) g.setColor(Color.GREEN.darker());
      else g.setColor(Color.RED.darker());
      g.fillOval(2 * (int) sep, (int) loc, (int) sep, (int) sep);
  }
  		

processTo Method Explanation

The processTo method should start by computing how much time it should spend processing jobs--i.e. the difference between the current system time, and the time passed into processTo. We'll call this timeLeft. Your processTo method should process individual jobs in the Queue, one at a time, in a FIFO order, while timeLeft is greater than 0. Your Server cannot spend more time processing an individual job than the minimum of the job's remaining processing time, and timeLeft. When this method finishes processing a job, it should remove it from the queue, add the job's waiting time (call the job's timeInQueue() method) to the total waiting time for all jobs processed by the server, and incrememnt the number of jobs processed by the server. If there is still timeLeft (i.e. it's greater than 0), the server should continue processing jobs. Remember to update the system time at the end.

Take a look at these slides for a visual of how time is handled in this simulation.

Picking the "Right" Server for the Job

Now we have a Server class that is ready to accept and process jobs for us. The next step in this project is to build a JobDispatcher class that will allow us to create a collection of K Servers and allocate incoming jobs to the most appropriate Server.

With 5, or 10, or 100 different Servers to choose, how should decide where to send jobs when they come in? There are multiple reasonable answers to this question and we will implement and compare several. Specifically, we will implement a RandomDispatcher that chooses a Server at random; a RoundRobinDispatcher that cycles through the Servers in order; a ShortestQueueDispatcher that chooses the Server wth the fewest jobs in its Queue; and a LeastWorkDispatcher that picks the server with the least remaining processing time across the jobs in its Queue.

However all of these types of JobDispatchers share common methods, so instead of rewriting these four times, we will make an abstract class to work as the framework for how each JobDispatcher will function.

Yoy can test the overall functionality of your dispatchers using the supplied DispatcherTests that will be used to evaluate your code. You may wish to add additional tests to this file to aid in your debugging.

An Abstract JobDispatcher class

Make an abstract JobDispatcher class: public abstract class JobDispatcher. A JobDispatcher should manage a collection of Servers (implemented as an ArrayList)..

Other class fields your JobDispatcher should maintain include a double for system time, a ServerFarmViz object to use for visualizing the simulation, and a LinkedList of Jobs to keep track of all the Jobs we've handled so far.

When jobs arrive, your JobDispatcher will advance the system time to their arrival, which requires all Servers to process jobs in their respective queues up to that arrival time. The JobDispatcher will then pick which Server to send the job to, but we'll leave that method abstract for now: public abstract Server pickServer(Job j).

Below are the methods to implement for the JobDispatcher class:

• public JobDispatcher(int k, boolean showViz): constructs a JobDispatcher with k total Servers. Make sure to initialize the fields for time and number of jobs handled to 0. Finally, create a ServerFarmViz object using the following line of code

  new ServerFarmViz(this , showViz );

  and save it in the corresponding class field. (The this keyword is because the ServerFarmViz constructor expects a JobDispatcher object.)
• public double getTime(): returns the system time
• public ArrayList getServerList(): returns the jobDispatcher's collection of Servers
• public void advanceTimeTo(double time): this method updates the system time to the specified time and calls the processTo method for each Server it maintains.
• public void handleJob(Job job): adds the job to the list of jobs we've handled, advances the time to job's arrival time, calls the ServerFarmViz object'srepaint() method, picks the Server appropriate for job (whichever one is returned by the pickServer method), and adds job to the chosen Server, then calls the ServerFarmViz object'srepaint() method again.
• public void finishUp(): advances the time to the earliest point when all jobs will have completed.
• public int getNumJobsHandled(): returns the number of jobs handled in the list we are storing.
• public double getAverageWaitingTime(): sums up all the waiting times of the jobs in the list of jobs we've handled then divides it by the number of jobs.
• public abstract Server pickServer(Job j); as specified above, this method is abstract as we don't know how to implement this method without knowing what particular algorithm we are following for handling our jobs.
• public void draw(Graphics g): This method is necessary for the GUI we've provided. For this method, you can copy and paste the following method into your JobDispatcher class. Make sure to import the following in order for it to work: java.awt.Graphics; java.awt.Color.

  public void draw(Graphics g){
      double sep = (ServerFarmViz.HEIGHT - 20) / (getServerList().size() + 2.0);
      g.drawString("Time: " + getTime(), (int) sep, ServerFarmViz.HEIGHT - 20);
      g.drawString("Jobs handled: " + getNumJobsHandled(), (int) sep, ServerFarmViz.HEIGHT - 10);
      for(int i = 0; i < getServerList().size(); i++){
          getServerList().get( i ).draw(g, (i % 2 == 0) ? Color.GRAY : Color.DARK_GRAY, (i + 1) * sep, getServerList().size());
      }
  }
  		

Implementing Specific Dispatchers

Now that we've built the framework, we're ready to make a few different dispatchers. Each one will extend the JobDispatcher class, which means we'll inherit the methods we've defined so far for free and only need to implement the constructor and the pickServer method. N.B.: when you write the constructors for each class make sure to call the parent's constructor via the super method.

• RandomDispatcher

  For our first dispatcher RandomDispatcher, let's just extend the JobDispatcher class and have the pickServer() method return a random Server.

  Visualize your random dispatcher! At this point, you should be able to run ServerFarmSimulation.java and check that your code is working correctly! You should expect to see jobs being randomly allocated to server, rather than by any pattern. Re-run the simulation after implementing each of the next 3 dispatchers to check that they're behaving as expected!

• RoundRobinDispatcher

  For our next dispatcher RoundRobinDispatcher, we'll pick the Server in a round-robin process (so the first time pickServer() is called, it returns the first, then the next time the second, etc.)

• ShortestQueueDispatcher

  The next dispatcher ShortestQueueDispatcher picks whichever Server has the smallest-sized queue (the server currently assigned the fewest jobs), with ties handled arbitrarily.

• LeastWorkDispatcher

  The final required dispatcher LeastWorkDispatcher picks the Server with the least remaining processing time in its queue, with ties handled arbitrarily.

---

Exploration

Now that we have our dispatchers, we're ready to compare them! We will also look at what happens to wait time as you change the number of servers in the server farm. (Note, make sure to set showViz to false or you'll be waiting forever!).

Modify the ServerFarmSimulation we gave you to run experiments to answer the following questions. We must be able to replicate your results by running this file! That means that your ServerFarmSimulation needs to run all of your experiments, and nicely format the results before printing them so that we can tell what we're looking at!

Required result 1:Make a table comparing the average waiting time of a job for the 4 job dispatchers with 34 servers and 10000000 jobs. Keep meanArrivalTime set to 3 and meanProcessingTime set to 100. Which one(s) works best? Which one(s) worst? Is that what you expected?

Required result 2:Make a graph showing the average waiting time of a job for the shortestQueue dispatcher as you increase the number of servers from 30 to 40. As before, run the simulation for 10000000 jobs. Keep meanArrivalTime set to 3 and meanProcessingTime set to 100. How many servers do you need to not fall too far behind? Does this match your expectations? (For an extension, you can run some follow up experiments and see if you can make a guess at how to answer this questions mathematically.)

---

Extensions

The following are some suggested extensions. You should feel free to pursue your own custom extensions to your project that you find interesting. Please clearly identify your extensions in your report. In your code, make sure the baseline simulations run properly. Making a separate sub-folder for major extensions is recommended.

1. Explore different dispatch methods. Can you beat whichever method you determined to be the 'best' in the exploration section? Make sure to include a thorough set of experimental results (Up to 4 points)
2. Implement one or more different metrics and use them to evaluate the dispatchers. For example, instead of computing average time in the system, instead compute the average ratio of job size to its wait time. Make sure to include a thorough set of experimental results (Up to 3 points)
3. In our project so far, all Servers have been the same. If some of my servers were faster than others, how should I use them? (2-4 points. More points for a detailed explanation with e.g. an equation or specific numerical example)
4. Given a job sequence where on average jobs arrive every x seconds and take y total units of processing time, what seems like a minimal number of Servers necessary to handle those jobs without falling uncontrollably far behind? Does your best dispatcher support this intuition? (2-4 points. More points for a detailed mathematical explanation and a set of simulation results.)

---

Congrats, you're done with everything except for your project report where you will communicate your findings from all that code! The project report is an important part of the work in this project, so don't forget to do it!

---