Program #4 (Cpt S 223)

Fall 2012 Due: November 16, 2012, 11:59pm on Angel Dropbox

General Guidelines

• All source code must be in C++. You can use Windows or Unix environments at your discretion.

• Each program project should be accompanied by a COVER SHEET (see details below). Assignments without cover page will NOT be graded.

• For this programming assignment, you have the option of either work as a TEAM if you prefer, or as an individual. A TEAM should contain at most 2 students including yourself. Grading will *not* differentiate between the two - i.e., if you are working as a team of two people, then the same grade will be applied to both of you.

• If working as a team, remember to include both your last names in the zip file of your submission.

• If working as a team, submit only one copy of your assignment into the Drop box and indicate in the text box of the drop-box while submission, both names in the project. If you specify only one name then only that person will get the grade and the other will not. So please make sure you fill in both names.

• In the rest of this document, the term “YOU” is used either to refer to you (if you are working individually) or your team (if you work as a team).

• The final material for submission should be entirely written by you. If you decide to consult with others or refer materials online, you MUST give due credits to these sources (people, books, webpages, etc.) by listing them on the cover sheet mentioned below. Note that no points will be deducted for referencing these sources. However, your discussion/consultation should be limited to the initial design level. Sharing or even showing your source code/assignment verbiage to anyone else in the class, or direct reproduction of source code/verbiage from online resources, will all be considered plagiarism, and therefore will be awarded ZERO points and subject to the WSU Academic Dishonesty policy. (Reproducing from the Weiss textbook is an exception to this rule, and such reproduction is encouraged wherever possible.)

• Grading will be based on correctness, design and implementation efficiency, coding style, exception handling, source code documentation, and the written report. Try to also follow the good coding practices discussed in class during the C++ review lecture. See grading rubrics at the end of this document for more specific details.

• Angel DropBox submission: As before, we will use the Angel DropBox for PA4. 1) Once you login to Angel, click on the “Lessons” tab.

2) You will see ”Programming Assignment #4”. Click on that and you will see the submission website. Under Title, just write your first and last name and say PA 3 - e.g., ”Ananth Kalyanaraman, PA4”. If you are submitting as a team, only one of you should submit, and put both your names on the Title: e.g., “Firstname1 Lastname1 & Firstname2 Lastname2, PA4” Leave the message textbox empty, unless you want to add a special comment to us. Then click on the “Attachments” button and attach your ZIP file there. And then press the SUBMIT button EMAIL METHOD (backup only): Only if dropbox doesn’t work for some reason, then you can submit by email to “All course faculty” on Angel. Same time deadlines apply. All assignments with cover sheet should be zipped or tarred into one archive folder (named after your last name).

1 Introduction

You will be primarily using priority queues for this programming assignment. Among priority queues, you are free to pick and choose the most appropriate/efficient heap implementation. Your design can also use any other data structure that we have discussed so far in class, as long as the use of such a data structure could be justified from a design perspective. In fact, go for a simpler data structure wherever possible. An unnecessarily overcomplicated implementation (example: using a heap where actually a simple vector would suffice) will lead to reduction in points. The idea is to let you make the design choice, and identify the most suitable data structure for each component in the system in order to effectively address performance and functional tradeoffs.

Use of any appropriate STL containers is highly encouraged whenever possible (priority queue, set, map, list, vector, etc.). Recall that STL’s “priority queue” implements a binary heap in the form of a MaxHeap. You can easily change it into a MinHeap (as shown in the book, Figure 6.57 @ page 252). You are also free to re-use/reproduce any source code that is provided in the Weiss textbook. Most of its source code are available from the following website: http:

//www.cs.fiu.edu/~weiss/dsaa_c++/Code/.

2 Problem Statement

Your organization has purchased a new parallel computer (or “cluster”) which has p processors. Your task is to design and implement a simple shortest-job-first scheduler that allows multiple users to access the cluster at the same time, as per the specifications in Section 3. Figure 1 is a conceptual illustration of the different components in the system, how they interact, and the necessary data containers you will have to implement. Refer to this figure while reading the rest of this document.

3 Problem Specification

The scheduler performs all required functions at regular timesteps called “ticks”. The tick in other words, is the pulse of the scheduler. During each tick, various events could happen and the scheduler’s responsibility is to address all these events before moving on to the next tick. Because of this, each tick could take variable amount of time to complete, and for design simplicity you can assume that there is sufficient real time within each tick to complete all required tasks. The various events and the respective action that is required to be carried out by the scheduler are outlined below. (Refer Figures 1 & 2 as you read this.)

\underline{Init condition:} When the algorithm starts, the system is initialized with p processors in the free pool. Figure 2 shows the sequence of steps that the scheduler should perform during each tick as a pseudocode.

1. Event: The user inputs at most one job at the start of any tick. Each job arrives to the scheduler in the following format: <job description, n procs, n ticks>. If the job description field is set to “NULL” then that means that the user does not have any job to insert during this clock tick. Action: For each job submission, the system assigns the job a new, unused integer id (referred to as “job id”) and then calls the InsertJob()^{1} function with the following parameters:

1\underline{Note:} The notation InsertJob() does not mean there are no arguments to this function. You need to decide

<job id, job description, n procs, n ticks>, where:

(i) “job description” contains details on what command to execute to run the job (i.e., “<program name> <its arguments>”). It is a string data type. If the job description is set to “NULL” then it means there are no jobs to be inserted in this clock tick;

(ii) “n procs” is the number of processors that this job needs to run on; (iii) “n ticks” is the number of ticks that this job is going to need on each of the n proc

processors. Note that this number is the equivalent of the job’s estimated running time, from start to finish, as the job will be launched on all n procs processors at the same time to run in parallel for n ticks number of ticks.

The InsertJob() function first checks if (0 < n procs ≤ p) and (n ticks> 0). If so, it inserts the job into a “ wait queue”. Otherwise, a job submission error is raised with an appropriate message.

2. Event: The job wait queue is not empty. Action: Among all the jobs in the wait queue, find the job that is expected to take the least time to complete (FindShortest()) – i.e., a job with the minimum value for n ticks. Let J_{i} denote the selected job, and p_{i} denote its n procs. Now, check if there are at least p_{i} processors currently available in the processor “free pool” (CheckAvailability()). If not, then leave the wait queue intact and return. Otherwise:

(a) remove J_{i} from the wait queue (DeleteShortest()), and

(b) remove p_{i} number of arbitrary processors from the free pool and “assign” them to that job (RunJob()), so that they can start executing the job from the next tick^{2}. When a job goes to the running state, along with it a countdown “timer” is started; initialize this to n ticks. If after the first job allocation, there are still more jobs in the wait queue that have sufficient available processors to run on, then iteratively keep removing all the next shortest jobs until no more processors are available for the next shortest job, or the wait queue becomes empty.

what arguments each function signature should have. I have purposefully left that choice to you as part of design.

Same applies to all the other functions.

2Remember, your code does not have to concern itself about running the actual job. You can safely assume that will be internally taken care of by the individual processors that you assigned to run the job. Your responsibility is to make sure that the scheduler is aware of how many processors are now available in the free pool after the allocation and how many processors this new job that got moved to the run queue is using.

3. Housekeeping Event: The running job queue is not empty.

Action: The job timer for ALL running jobs is decremented by one (DecrementTimer()).

4. Housekeeping Event: A job that was in the running state completed during this tick — i.e., its timer has reached a value of zero after decrement. Action: The scheduler should release all the processors attached to this job, back into the free pool so that they become available for other jobs during later ticks (ReleaseProcs()).

4 API and Testing

Follow the below instructions to test your code.

• Write a separate TestDriver.cpp program which first reads an input file, in which a series of job inserts are mentioned, one line per tick. An example input is shown below:

J1 8 10
J2 2 1
J3 12 12
J4 10 2
J5 5 8
J6 4 2
J7 4 6
J8 2 5
J9 4 3
J10 6 2

Your code should iterate through these lines, one tick per each line, and adding any more iterations (i.e., ticks) as necessary until the Wait Queue becomes empty. Within each iteration, the current tick number should be displayed (starting at serial number 1). Then the code should call the Tick() function (as specified in the pseudocode in Figure 2. Define the Tick() function as a member function of your Scheduler class.

• At the end of the Tick() function, print a system-defined Job id number unique to any job submitted during this tick or an error message upon failure to insert. Also print all jobs which got allocated to the running queue in this tick, and also any job or jobs that completed during this tick. Each print message should include the job description, number of processors it needs, and the number of ticks it needed.

• The test program should terminate if the user inputs “exit” for the job descriptor in the standard input.

5 Design Document - (2 page limit)

Along with your source code, also submit a one-page design document (as Word Doc or PDF - no other formats allowed).

In the first part of this document, provide a figure that best describes your design for the scheduler system. It should basically be a modified version of Figure 1, in which you should state what data structures/STL containers you used to implement the three data containers (wait queue, running job queue, free pool) .

In the second part, make a table to simply state the worst-case run-time complexities in your implementation for each of the event functions: InsertJob, FindShortest, DeleteShortest, Check-Availability, RunJob, DecrementTimer, ReleaseProcs. No need for justifications. Just write the answers using the Theta (or Big-Oh if Theta is not possible) notation. You can use n to denote the number of maximum number of jobs (waiting or running) at any given point of time, and p to denote the total number of processors (free or busy).

In the third part, write a short paragraph about what you think are the main shortcomings/bottlenecks of this shortest-job-first strategy, from both a performance and functionality point of view. Support your claims with brief but compelling rationale.

6 FINAL CHECKLIST

Cover sheet (just one per team)

separate folder containing all your sourcecode (including the main function you used for testing)

1-page design document

All the above zipped into another folder archive called Program4¡YourLastName(s)¿.zip

7 GRADING RUBRICS

This assignment is mainly about designing efficient algorithms and implementations for the Schedular class. There is not really an extensive empirical component that involves timing and such but you need to pay attention to design in a manner that is expected to keep the runtimes really low for even large input cases. So for grading this PA, we will primarily look at how well you have designed your algorithm behind the implementation, how well you have implemented the code, and whether your code tests correctly. Therefore the points during grading will be distributed as follows:

The whole assignment is worth a total of 100 points.

7.1 ALGORITHM DESIGN, CODING & TESTING (75 pts)

(30 pts): Is the algorithm design efficient? That is, does the algorithm deploy the appropriate kind of data structures and use them effectively in a way that is expected to deliver the best possible performance both in terms of runtime and memory?

(20 pts): Is the code implemented in an efficient way? i.e., are there parts in the code that appear redundant, or implemented in ways that can be easily improved? Does the code conform to good coding practices of Objected Oriented programming?

(10 pts): Is the code documented well and generally easy to read (with helpful comments and pointers)?

(15 pts): Does the code compile and run successfully on a couple of test cases? Also does the output for the sample test case provided look right?

7.2 REPORT (40 pts)

(30 pts): Is the algorithm described well in the report? Are all important details effectively presented, or does the TA have to dig up some critical information (such as which STL classes were used to implement the Scheduler class or how each of its main methods (both housekeeping and even-driven, see Figure 1) was implementated using different data structures) from the code?

(10 pts): Is the basis of the choice of different data structures well justified/supported with the presentation of the expected time and memory complexities?

Obviously to come up with the above evaluation, the TAs are going to both read and run your code. E

-mail All Course Faculty on Angel, or post a note on OSBLE if you have any questions. Good luck!

Figure 1: Organization of the scheduler system for a parallel cluster that has a total of p processors. 9 Algorithm 1 Pseudocode for the scheduler’ Tick procedure

Tick() 0. \underline{Prompt} user for submitting a new job.

1. \underline{Insert} the job into the wait queue (if the user submitted a valid job);

2. \underline{Decrement} timer for all running jobs in the running queue;

3. \underline{Release} all the processors corresponding to the completed/expired jobs from the running queue to the free pool. A job is said to have “expired” if its timer becomes zero during this tick. Also, any expired job should be automatically removed from the running job queue;

4. \underline{Find} the next shortest job ( < J_{i}, p_{i}, t_{i} >) from the wait queue and check if sufficient number of processors are available in the free pool to run it. If so:

- \underline{Remove} job J_{i} from the wait queue;

- \underline{Insert} job J_{i} into the running queue and assign p_{i} processors (from free pool) to that job; If after this first job allocation, there are still more jobs in the wait queue that have sufficient available processors to run on, then iteratively keep removing all the next shortest jobs until no more processors are available for the next shortest job, or the wait queue becomes empty.

Figure 2: Sequence of steps to be carried out during each Tick() of the scheduler.