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

Testing

As you proceed through this project, maintain testing files to exercise the functionality of your code that you have written. Use previous testing files provided to you as templates for the structure.

Wrapping up the Job class

Let's complete the Job class:

• public double getArrivalTime(): this returns the arrival time of this job.
• public double getTotalProcessingTime(): this returns the total necessary processing time of the job.
• public double getTimeProcessed(): this returns the time spent working on this job so far.
• public double getTimeRemaining(): this method returns the necessary time remaining to spend working on this job.
• public boolean isFinished(): returns true if this job has been run to completion.
• public void setFinishTime(double time): this sets the time when the job completed.
• public double getFinishTime(): this method returns the time when the job was completed.
• public double timeInQueue(): returns the difference in time between the arrival and finish times of this job.
• public void process(double time): processes this job for the specified time units of time. Make sure that all necessary fields of the class are updated.

What fields seem necessary in order to implement these methods? One annoyance is that the Job class doesn't have a way of telling itself what time it finishes, so we'll have to make a mental note of that and return to that when we are writing the Server class.

The Server class

Now that we have our Job class finished, we want to create a Server class. An individual Server needs to manage a Queue of Jobs, allowing for jobs to be offered into the system in a FIFO setting. Additionally, it needs to give some functionality for processing those jobs in that order for a set amount of time. A Server will also track the system time (stored as a double), which the Server can assume is 0 at its instantiation. Finally, we will also have our server class track some summary statistics of the jobs it has processed that we will use to analyze our different server methods--the total number of jobs processed (an int) and the total waiting time for each job processed (a float). Both of these can be assumed to start at zero. Specifically, for this class we will implement the following methods:

• 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.
• public void processTo(double time): advances the system time of this queue to the specified time time. We'll use this method to process work in the Queue until the next event--in this case, a new job arriving, happens. When doing this, we must also spend that time processing the current job or jobs that the server is working on. We must keep in mind that a Server can only process one job at a time, but that once a job is finished, it will immediately move onto the next job in the Queue. Using a Queue for this ensures that the Server processes the jobs in the order of arrival. Practically, what processing a job means is that we call the current Job's process method with the amount of time we want to spend processing it. When the time passed into the processTo method is less than the remaining processing time for the current Job, we simply call the current Job's process method with the amount of time passed in. Otherwise, we need to process the current Job to completion, then spend the remaining time processing the next Job(s). (Note that this method should be able to handle processing multiple Jobs to completion one after another). When a job has completed, we must track 2 things: 1) we must make sure to call the Job's setFinishTime method with the appropriate value, and 2) we must update the Server's counter for the number of jobs processed, and the Server's field tracking the total waiting time for Jobs in its Queue.
• public double remainingWorkInQueue(): returns the total remaining processing time in this Server's queue.
• public int size(): returns the number of Jobs in this Server's queue.
• 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);
  }
  		

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. But with K different Servers to choose from when a job comes, how should decide where to send it? There are multiple reasonable answers to this question and we will be implementing and comparing several of them. 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.

The JobDispatcher class

Since we have many different algorithms in mind for the task of dispensing jobs, let's make this class abstract: public abstract class JobDispatcher. A JobDispatcher should manage a collection of Servers--implemented as an ArrayList and track the system time. In order to let the Server collection be accessed by the subclasses of our abstract JobDispatcher class, it should probably be set to public (or better yet, protected). Your jobDispatcher class should have a boolean for whether or not to show the visualization we have provided. You'll want to run it for debugging, but not when processing the large files we give you for your experiments. Your JobDispatcher class should have a class field for a ServerFarmViz object and initialize it in the constructor if the show visualization boolean is true (otherwise set it to null). The constructor for ServerFarmViz requires you to pass in an instance of a JobDispatcher (consider using the this keyword). When jobs arrive, we'll advance the system time to their arrival, which requires all Servers process jobs in their respective queues up to the next arrival--use the Server.processTo method. Then, we pick the right Server to send them to and send them to that Server. However, the method of picking the right Server for the Job is not something that we know how to write without knowing which algorithm in particular we're talking about, so we'll leave that as abstract for now: public abstract Server pickServer(Job j). Below are all the required methods for the JobDispatcher class:

• public JobDispatcher(int k, boolean showViz): constructs a JobDispatcher with k total Servers. Make sure this initializes all the fields of this class to appropriate values.
• public float getTime(): returns the time
• public ArrayList getServerList(): returns the jobDispatcher's collection of Servers
• public void advanceTimeTo(double time): this method updates the current time to the specified time and calls the processTo method for each Server it maintains.
• public void handleJob(Job job): advances the time to job's arrival time, if showViz is true, it 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, if showViz is true, it calls the ServerFarmViz object'srepaint() method again.
• public void finishUp(): advances the time to the earliest point when all jobs will have completed.
• public void handleJobs(Queue<Job> jobs): polls each Job from the specified queue of Jobs and calls handleJob on them. After all the Jobs have been handled, calls finishUp()
• public int getNumJobsHandled(): gets the total number of jobs handled across all Servers.
• public double getAverageWaitingTime(): gets the total waiting time for each Server, adds them together, and divides it by the number of jobs handled across all Servers.
• 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. Please download the main file for the GUI here: ServerFarmViz.java. 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());
      }
  }
  		

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! Once you've implemented your RandomDispatcher, you should download jobs.txt, a small collection of jobs to run your jobDispatcher with. Make sure you have also downloaded ServerFarmViz.java. You can then download and run the provided ServerFarmTester.java file we've provided. This will show a visualization of how the random dispatcher handles the queue of jobs. There shouldn't be any particular pattern in how it decides to send a job to a particular Server (each row is a server, and shows the number of jobs in the queue and the remaining processing time for all the jobs in its queue). Modify this tester file to visualize how each of the following dispatchers work after you have implemented them. Your program should take in a single string command line argument determining which of the 4 dispatchers should be used in the visualization (random, round, shortest or queue). These follow specific rules, so you can use this visualization to check if it's working correctly!

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.)

Add code to the ServerFarmTester file to visualize your RoundRobinDispatcher on the same set of jobs. The tester file should now visualize whichever of the two dispatchers based on a string command line parameter.

ShortestQueueDispatcher

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

Add code to the ServerFarmTester file to visualize your ShortestQueueDispatcher.

LeastWorkDispatcher

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

Add code to the ServerFarmTester file to visualize your LeastWorkDispatcher on the same set of jobs.

Required program: Modify ServerFarmTester to take in a string command line argument with valid options: random, round, shortest and least. Your program should run the corresponding dispatcher to the string passed in and visualize the output. We will use this program to check that your dispatchers are working as expected! Make sure to include a usage statement explaining your command line parameter to the user!

---

Exploration

Now that we have our dispatchers, we're ready to compare them! You will write a ServerFarmSimulation class that processes the same sequence of jobs using the 4 different dispatchers and compares them. While determining the 'best' dispatcher is situation dependent, we will start by comparing the average waiting time for the sequence of jobs across the 4 types of dispatchers.

To run these simulations, we have given you lengthy job sequence files with varying parameters for you to experiment with your dispatchers on. Every file is generated programatcially, and every filename looks like JobSequence_x_y: the number x refers to the average arrival rate of Jobs and y refers to the average processing time of each job. In particular, the filename JobSequence_x_y denotes a job sequence where, on average, a job is arriving every x time units and requires y total units of processing time.

You will use the following 3 files in your experiments:

• JobSequence_7_30_short.txt
• JobSequence_10_100_short.txt
• JobSequence_3_100_short.txt

These are the previous longer versions:

• JobSequence_7_30.txt
• JobSequence_10_100.txt
• JobSequence_3_100.txt

Your ServerFarmSimulation class should have a main method that takes in 2 command line parameters: the number of servers and the filename of the job sequence file. It should use each of the 4 types of dispatchers to process all of the jobs in the file, and print the average waiting time for each dispatcher type, making it clear in the print statements which dispatcher type each waiting time belongs to.

Required result: In your report, you should include a nicely formatted table with a row for each job dispatcher type, and a column for each of the 3 job sequence files we have given you (JobSequence_7_30.txt, JobSequence_10_100.txt and JobSequence_3_100.txt). The table should include the average waiting time computed for each pairing of dispatcher type and job sequence when run with 30 servers.

This table should include a title and caption. You should also interpret these results in the text of your results section. For example, which of the four dispatch methods seems best for this objective?

---

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?
2. Explore different objectives. For example, instead of minimizing average time in the system, instead minimize the average ratio of job size to its wait time.
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?
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?
5. Optimize your code so that they work with the original long test files and describe what choices you made to get it to run within a reasonable amount of time (a few minutes).

---

Report

Your intended audience for your report are your peers not in the class, but who have taken a CS course. Your report should explain the core CS concept used, present the results of your program, and discuss the meaning of the results: what did you discover and does it make sense?

Your project report should contain the following elements. Please include a header for each section.

• Abstract

  A brief summary of the project, in your own words. This should be no more than a few sentences. Give the reader context and identify the key purpose of the assignment. Each assignment will have both a core CS purpose--usually a new data structure--and an application such as a simulation or analysis.

  Writing an effective abstract is an important skill. Consider the following questions while writing it.

  • Does it describe the specific project application?
  • Does it describe the results of your simulation or analysis?
  • Is it concise?
  • Are all of the terms well-defined?
  • Does it read logically and in the proper order?
• Results

  Present your results. Include text output, images, tables, graphs, or qualitative descriptions, as appropriate. Include a discussion as to whether the results make sense and what they mean. For this week, make sure to include your results from the Exploration section.

• Extensions

  Describe any extensions you undertook, including text output, graphs, tables, or images demonstrating those extensions. If you added any modules, functions, or other design components, note their structure and the algorithms you used.

• Reflection

  • What are the runtimes of the Queue methods within your LinkedList? Specifically, what are the runtimes of the peek, poll, and offer methods?

  • Some of the required dispatch methods pick the Server asymptotically faster in the worst case than others: specifically, two of the methods take constant time, and two of them take longer. How do the contant time methods compare to those that take longer?

• References/Acknowledgements

  A list of people you worked with, including TAs and instructors. Include in that list anyone whose code you may have seen, such as those of friends who have taken the course in a previous semester.

Handin

Here's a checklist of everything you should do when you are finished with a project and are ready to turn it in.

+ Create a report and export to pdf

+ Organize your project folder

+ Submit your project on Google Drive