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. 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 is 0 at its initialization.
• 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. In doing so, this method should process jobs in the queue accordingly: keep in mind that a Server can only process one job at a time, in the order of arrival. Additionally, when a job is completed, make sure to call its setFinishTime method with the appropriate value.
• 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.

Picking the "Right" Server for the Job

Now that we have our Servers ready to accept and process jobs for us, we're ready to start implementing some algorithms on how to dispatch the jobs. However, there are a bunch of different ways to do so: one could imagine dispatching jobs in a round-robin style, or picking the Server with the fewest remaining jobs, or even just picking one at random to make the choice easier. Regardless, all of these different methods will share a lot of code, so instead of rewriting them over each time let's 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 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). When jobs arrive, we'll advance the system time to their arrival (so that all Servers process jobs in their respective queues up to the next arrival), pick the right Server to send them to, then 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): constructs a JobDispatcher with k total Servers. Make sure this initializes all the fields of this class to appropriate values.
• 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 finishUp(): advances the time to the earliest point when all jobs will have completed.
• public void handleJob(Job job): advances the time to job's arrival time, picks the Server appropriate for job (whichever one is returned by the pickServer method), and adds job to the chosen Server.
• 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 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.

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.

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 run some tests and compare them! I've gone ahead and created very lengthy job sequence files with varying parameters for you to test your dispatchers on. Every file is generated in a very similar way that if you are curious about (or if you'd like more test files) I'd be more than happy to discuss with you during office hours, but you'll notice 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.

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

For each of the following questions, develop a hypothesis, test it with your code, and detail your findings in the report.

1. We've implemented a few different dispatchers, but it's somewhat unclear how to 'measure' them. How do we determine what it means to be the 'best' algorithm? As with most things in life, the unfortunate answer is "it depends." One reasonable objective is to minimize the average time jobs wait from the moment of their arrival until their completion time. Under this objective, out of the dispatch methods built which seems to best for this objective?
2. 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?

---

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?

---

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