\documentclass[11pt]{article}
\renewcommand{\baselinestretch}{1.5}
\input{psfig}
\usepackage{epsfig}
\usepackage{algorithm}
\usepackage{url}
\usepackage{paralist}
\usepackage[leqno]{amsmath}
%\usepackage[german]{babel}
\textwidth=6.5in \textheight=9.0in
%\topmargin=-0.5in
\oddsidemargin=-0.01in
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}[lemma]{Corollary}

% to get nice proofs ...
\newcommand{\qedsymb}{\mbox{ }~\hfill~{\rule{2mm}{2mm}}}
\newenvironment{proof}{\begin{trivlist}
\item[\hspace{\labelsep}{\bf\noindent Proof: }]
}{\qedsymb\end{trivlist}}


\pagestyle{plain}         %  Page numbers in middle bottom of page.
\parskip=0.05in

\begin{document}
\date{}
\title{\vspace*{-1.4in}\Large\bf
       Program \#4 (Cpt S 223)}
\author{\large Fall 2011\\
	Due: November 14, 2011, 11:59pm on Angel
}
\maketitle

\section*{General Guidelines}

\begin{itemize}\itemsep=-0.05ex
\item
All source code must be in C++. You can use Windows or Unix environments at your discretion. 
\item
Each program project should be accompanied by a COVER SHEET (see details below). Assignments without cover page will NOT be graded.
\item
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.
\item
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).
\item
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.)
\item
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.
\item
If working as a team, the same grade will be given to both members of a team.
\item
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.
\item
If working as a team, remember to include both your last names in the zip file of your submission.
\item{\bf Angel DropBox submission:}  
We will use DropBox. 
All assignments with cover sheet should be zipped or tarred into one archive folder (named after your last name). 
Instructions for DropBox submission: I have set up a have set up a new DropBox called ``Program project 4'' inside Angel. The way to submit to the dropbox is as follows:

1) Once you login to Angel, click on the ``Lessons'' tab.

2) You will see ``Program project 4''. 
    Click on that and you will see the submission website. 
    Under Title, just write your first and last name and say Program 4 - e.g., ``Ananth Kalyanaraman, Program 4''. 
    If you are submitting as a team, type in both your names in the textbox. Otherwise leave it empty.  
    Then click on the "Attachments" button and attach your ZIP file there. 
    And then press the SUBMIT button.

      
\end{itemize}


\section{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 ({\it priority\_queue, set, map, list, vector}, etc.).  Recall that STL's ``priority\_queue'' implements a binary heap in the form of a \emph{MaxHeap}. You can easily change it into a \emph{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: \url{http://www.cs.fiu.edu/~weiss/dsaa_c++/Code/}.



\section{Problem Statement}

%\line(1,0){450}

Your organization has purchased a new parallel computer (or ``cluster'') which has $p$ processors. Your task is to design and implement a simple \emph{shortest-job-first scheduler} that allows multiple users to access the cluster at the same time, as per the specifications in Section~\ref{secSpec}. 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.

%\line(1,0){450}


\begin{figure}[p]
%\line(1,0){450}\\
\centerline{\epsfig{figure=figOrganization.eps}}
%\line(1,0){450}
\caption{Organization of the scheduler system for a parallel cluster that has a total of $p$ processors. 
}
\label{figOrganization}
\end{figure}

\begin{figure}[p]
\begin{algorithm}{Pseudocode for the scheduler' Tick procedure}
\textbf{Tick()}
\begin{Block}
	0. \underline{Prompt} user for submitting new jobs, one at a time.\\
  1. \underline{Insert} each of those jobs into the wait queue;\\
  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:
  \begin{Block}
   - \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;
  \end{Block}
\end{Block}

\end{algorithm}
\caption{Sequence of steps to be carried out during each Tick() of the scheduler.}
\label{figTick}
\end{figure}

%\newpage
\section{Problem Specification}
\label{secSpec}


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~\ref{figTick} shows the sequence of steps that the scheduler should perform during each tick as a pseudocode.

\begin{enumerate}

\item
{\bfseries {\em Event: }} The user inputs one or more jobs at the start of any tick. Each job arrives to the scheduler in the following format: 
$< $job\_description, n\_procs, n\_ticks$> $. 

{\bfseries {\em Action:} } 
For each job submission, the system assigns the job a new, unused integer id (referred to as ``job\_id'') and then calls the {\bf InsertJob()}\footnote{\underline{Note:} The notation {\bf InsertJob()} does \emph{not} mean there are no arguments to this function. You need to decide 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.} function with the following parameters:\\
\hspace*{1in}$< $job\_id, job\_description, n\_procs, n\_ticks$> $, where:
\begin{itemize}
\item[(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;
\item[(ii)] ``n\_procs'' is the number of processors that this job needs to run on;
\item[(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.
\end{itemize}

The {\bf InsertJob()} function first checks if ($0 < $ n\_procs $ \leq 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.

\item
{\bfseries {\em Event:}} The job wait queue is \emph{not} empty.\\
{\bfseries {\em  Action:}} Among all the jobs in the wait queue, find the job that is expected to take the least time to complete  ({\bf FindShortest()}) -- i.e., a job with the minimum value for n\_ticks. If there are more than one job to choose from this category, then pick any one of them. 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'' ({\bf CheckAvailability()}). If not, then leave the wait queue intact and return. Otherwise:
\begin{enumerate}\itemsep=-0.05ex
\item remove $J_i$ from the wait queue ({\bf DeleteShortest()}), and 
\item remove $p_i$ number of arbitrary processors from the free pool and ``assign'' them to that job ({\bf RunJob()}), so that they can start executing the job from the next tick\footnote{Remember, your code does \emph{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.}. When a job goes to the running state, along with it a countdown ``timer'' is started; initialize this to n\_ticks.
\end{enumerate}

\item 
{\bfseries {\em Housekeeping Event:}} The running job queue is \emph{not} empty.\\
{\bfseries {\em Action: }} The job timer for \emph{ALL} running jobs is decremented by one ({\bf DecrementTimer()}). 

\item 
{\bfseries {\em 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. \\
{\bfseries {\em  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 ({\bf ReleaseProcs()}). 
\end{enumerate}

%Note that a processor can be in either the busy state or free state (but not both) at any given point of time. 




\section{API and Testing}

Follow the below instructions to test your code. 
\begin{itemize}
\item
Write a separate main.cpp program which runs an indefinite number of iterations. Each iteration corresponds to one tick. In each iteration, the current tick number should be displayed. Then the code should call the Tick() function. Define the Tick() function as a member function of your Scheduler class.
\item 
At the start of each tick, the program should prompt the user to input an arbitrary number of jobs through the standard input, one job at a time. Basically prompt the user for three entries: (i) Job descriptor (a string), (ii) n\_procs (an integer), and (iii) n\_ticks (an integer). After each entry the user will press enter to signal the end of that entry. If the user has no more new jobs to submit, then the user will signal that by entering the string ``null'' for job description. 

%For each job submitted, your code should do the necessary steps to insert the job into the wait queue and display back a system-defined Job\_id number unique to that job upon success or an error message upon failure.
\item 
Then the tick procedure should carry out the remaining steps outlined in the Tick() pseudocode in Figure~\ref{figTick}.
\item
At the end of the Tick() function, display back a system-defined Job\_id number unique to each job submitted during this tick or an error message upon failure to insert. 
\item
If there was any job that completed during this tick, then {\it print} its job\_id along with information on how many processors got released. Also, at the end of the tick, print separately the following items:
\begin{compactenum}[i)]
\item
the contents of the wait queue (just the job ids), 
\item 
list of all currently running jobs (job ids, present timer value, number of processors being used), and 
\item 
the number of processors in the free pool. 
\end{compactenum}
\item
The test program should terminate if the user inputs ``exit'' for the job descriptor in the standard input. 
%But before terminating, the program should report the average number of ticks that each job had to wait in the wait queue before it got moved to running status. 

\end{itemize}

\section{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) . 
%Interactions between modules should be denoted by arrows and appropriate labelled. Be as creative as possible. There is no one ``correct'' way to show this picture. The main ideas behind your design should come across.

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, CheckAvailability, 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.

\section{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

\end{document}



