/**
* @author Jane Programmer
* @cwid 123 45 678
* @class COSC 2336, Spring 2019
* @ide Visual Studio Community 2017
* @date March 12, 2019
* @assg Assignment 11
*
* @description Assignment 11 Priority queues and scheduling
* simulation of jobs with priorities.
*/
#include “Queue.hpp”
#ifndef JOBSIMULATOR_HPP
#define JOBSIMULATOR_HPP
/** Job class
* Class for job scheduling simulation. A Job enters a system
* at random intervals (determined by the JobSchedulerSimulator on
* a random Poisson basis). A job has a priority level and a serviceTime
* which is the amount of system time it needs in order to complete
* it task. The main property to keep track of for jobs in a
* simulation is how long they have to wait before they are selected
* to be processed/run by the system. Jobs keep track of their cost,
* which can be used to measure a particular system’s performance
* (lower costs mean the system performed well, higher costs mean the
* system performed more poorly). For systems with priority based jobs,
* the measure of the cost is determined of the function a job spent
* waiting, and how high of a priority the job had. We use the
* simple calculation of cost = priority * waitTime to calculate
* the cost for a job once it completes.
*
* @var nextListId A static int variable, used to assign unique ids
* when processes are created, for identification purposes.
* @var id The actual unique id assigned to a job object.
* @var priority This jobs priority level. Higher numbers mean higher
* priority jobs in this simulation.
* @var serviceTime The amount of system time this job needs in order to
* complete its task.
* @var startTime The time when the job was created. Also the time
* when the job began waiting in a queue to be selected to run.
* @var endTime The time when the job finished waiting (when it was
* finally selected by the system to begin execution). The difference
* between endTime – startTime determines the total waitTime for this
* process (calculated by getWaitTime() accessor method).
*/
class Job
{
private:
static int nextListId;
int id;
int priority;
int serviceTime;
int startTime;
int endTime;
public:
Job();
Job(int priority, int serviceTime, int startTime);
void setEndTime(int endTime);
int getId() const;
int getServiceTime() const;
int getPriority() const;
int getWaitTime() const;
int getCost() const;
bool operator==(const Job& rhs) const;
bool operator<(const Job& rhs) const;
bool operator>(const Job& rhs) const;
bool operator<=(const Job& rhs) const;
friend ostream& operator<<(ostream& out, const Job& aJob);
};
/** JobSchedulerSimulator
* This class organizes and executes simulations of job scheduling, using
* different scheduling methods. The simulations are goverend by a number
* of system parameters, that are specified when a simulation is created.
* When a simulation is run, various data is gathered that describes the
* results of the simulation. In general, the job scheduling being
* simulated is simple. The system runs for discrete time steps (total
* number of which is goverened by simulationTime parameter). At each step
* we check for and simulate new job arrivals. When jobs arrive, they
* are placed on a single job queue. We then check if the processor/executor
* is busy or not, and if not and if the job queue has some jobs on it, we
* simulate dispatching a job. Differences in how jobs are organized on
* a queue, and their effects on system performance (as a function of
* total or average cost) can be explored with this simulator.
*
* These are parameters of the simulation, they govern properties of
* job arrivals and characteristics when a simulation is run:
*
* @var simulatTime The total number of time steps a simulation will
* run. Time steps will run from 1..simulationTime number of
* discrete steps.
* @var jobArrivalProbability The Poisson probability that a job will
* arrive any any given discrete time interval. This governs how
* often new jobs arrive and are created in the simulation.
* @var [minPriority, maxPriority] The range of Job priority levels
* for jobs that arrive. This simulation generates priorities for
* the jobs randomly with uniform probability within this range, and
* assigns them to new jobs that arrive.
* @var [minServiceTime, maxServiceTime] The range of Job serviceTimes
* for jobs that arrive in the system simulation. Service times are how
* long a job needs to execute, once it is selected to be processed.
* Service times are generated with uniform probability in this
* given range when new jobs arrive.
*
* These are resulting statistics of a simultion. While a simulation is
* being run, data is gathered about various performance characteristics, like
* wait times and costs. At the end of a simulation, these statistical results
* are available for analysis of the system preformance.
*
* @var description A description of the dispatching/queueing method used.
* @var numJobsStarted The new number of jobs that entered and were
* started during the most recent simulation run.
* @var numJobsCompleted The number of jobs that were successfully run during
* a simulation.
* @var numJobsUnfinished The number of jobs left in the waiting queues when
* a simulation finished.
* @var totalWaitTime The total amount of time spent waiting by jobs
* that completed in the simulation. Mainly useful for calculating
* the averageWaitTime.
* @var totalCost The total cost of all jobs that completed in the simulation.
* Also mainly useful for calculating averageCost statistic.
* @var averageWaitTime The average waiting time for completed jobs of the
* most recent simulation.
* @var averageCost The average system cost for completed jobs of the most
* recent simulation.
*/
struct JobSchedulerSimulator
{
private:
// simulation parameters
int simulationTime;
double jobArrivalProbability;
int minPriority;
int maxPriority;
int minServiceTime;
int maxServiceTime;
// simulation results
string description;
int numJobsStarted;
int numJobsCompleted;
int numJobsUnfinished;
int totalWaitTime;
int totalCost;
double averageWaitTime;
double averageCost;
// private functions to support runSimulation(), mostly
// for generating random times, priorities and poisson arrivals
double randomUniform();
int randomRange(int minValue, int maxValue);
bool jobArrived();
int generateRandomPriority();
int generateRandomServiceTime();
public:
JobSchedulerSimulator(int simulationTime = 10000,
double jobArrivalProbability = 0.1,
int minPriority = 1,
int maxPriority = 10,
int minServiceTime = 5,
int maxServiceTime = 15);
string summaryResultString();
string csvResultString();
// Assignment 11
// You need to add a new method to the class definition of the
// JobSchedulerSimulator named runSimulation() here.
friend ostream& operator<<(ostream& out, JobSchedulerSimulator& sim);
};
#endif
/**
* @author Derek Harter
* @cwid 123 45 678
* @class COSC 2336, Spring 2019
* @ide Visual Studio Community 2017
* @date March 1, 2019
* @assg C++ Queues videos
*
* @description A Queue ADT with two concrete impelementation
* examples: an array based queue implementaiton (AQueue), and
* a linked list based implementation (LQueue).
*/
#include
#include
#include
using namespace std;
#ifndef QUEUE_HPP
#define QUEUE_HPP
//————————————————————————-
/** queue (base class)
* The basic definition of the Queue Abstract Data Type (ADT)
* and queue operations. All declared functions here are
* virtual, they must be implemented by concrete derived
* classes.
*/
template
class Queue
{
public:
/** clear
* Method to clear out or empty any items on queue,
* put queue back to empty state.
* Postcondition: Queue is empty.
*/
virtual void clear() = 0;
/** isEmpty
* Function to determine whether the queue is empty. Needed
* because it is to remove from empty queue. This
* function will not change the state of the queue (const).
*
* @returns bool true if queue is empty, false otherwise.
*/
virtual bool isEmpty() const = 0;
/** enqueue
* Add a new item onto back of queue.
*
* @param newItem The item of template type T to add on back of
* the current queue.
*/
virtual void enqueue(const T& newItem) = 0;
/** front
* Return the front item from the queue. Note in this ADT, peeking
* at the front item does not remove the front item. Some ADT combine
* front() and dequeue() as one operation. It is to try and
* peek at the front item of an empty queue. Derived classes should
* throw an exception if this is attempted.
*
* @returns T Returns the front item from queue.
*/
virtual T front() const = 0;
/** dequeue
* Remove the item from the front of the queue. It is what
* it means to try and dequeue from an empty queue. Derived classes should
* throw an exception if dequeue() from empty is attempted.
*/
virtual void dequeue() = 0;
/** length
* Return the current length or number of item son the queue.
*
* @returns int The current length of this queue.
*/
virtual int length() const = 0;
/** tostring
* Represent queue as a string
*/
virtual string tostring() const = 0;
// overload operators, mostly to support boolean comparison betwen
// two queues for testing
bool operator==(const Queue
virtual const T& operator[](int index) const = 0;
// overload output stream operator for all queues using tostring()
template
friend ostream& operator<<(ostream& out, const Queue& aQueue);
};
//————————————————————————-
/** Empty queue exception
* Class for empty queue exceptions
*/
class EmptyQueueException
{
private:
string message;
public:
EmptyQueueException()
{
message = “Error: operation on empty queue”;
}
EmptyQueueException(string str)
{
message = “Error: ” + str + ” attempted on emtpy queue”;
}
string what()
{
return message;
}
};
/** InvalidIndex queue exception
* Class to be thrown when an invalid index is asked for when indexing
* into a queue object.
*/
class InvalidIndexQueueException
{
private:
string message;
public:
InvalidIndexQueueException()
{
message = “Error: invalid index request for queue”;
}
InvalidIndexQueueException(string str)
{
message = “Error: ” + str + ” invalid index request for queue”;
}
string what()
{
return message;
}
};
//————————————————————————-
/** queue (array implementation)
* Implementation of the queue ADT as a fixed array. This
* implementation combines a circular buffer implementation, to make
* sure that both enqueue() and dequeue() operations are O(1) constant
* time. However, it also uses dynamic memory allocation, and
* demonstrates doubling the size of the allocated space as needed to
* grow queue if/when the queue becomes full.
*
* @var allocSize The amount of memory currently allocated for this queue.
* @var numitems The current length or number of items on the queue.
* @var front A pointer to the index of the front item on the queue.
* @var back A pointer to the back or last item on the queu.
* @var items The items on the queue. This is a dynamically allocated array that
* can grow if needed when queue exceeds current allocation.
*/
template
class AQueue : public Queue
{
private:
int allocSize; // amount of memory allocated
int numitems; // The current length of the queue
int frontIndex; // index of the front item of the queue
int backIndex; // index of the last or rear item of the queue
T* items;
public:
AQueue(int initialAlloc = 100); // constructor
AQueue(int initItems[], int numitems);
~AQueue(); // destructor
void clear();
bool isEmpty() const;
bool isFull() const;
void enqueue(const T& newItem);
T front() const;
void dequeue();
int length() const;
string tostring() const;
const T& operator[](int index) const;
};
//————————————————————————-
/** Node
* A basic node contaning an item and a link to the next node in
* the linked list.
*/
template
struct Node
{
T item;
Node
};
//————————————————————————-
/** queue (linked list implementation)
* Implementation of the queue ADT as a dynamic linked list. This implementation
* uses link nodes and grows (and shrinks) the nodes as items enqueued and dequeued
* onto queue.
*
* @var queueFront a pointer to the node holding the front item of the queue.
* @var queueBack a pointer to the node holding the back item of the queue.
* @var numitems The length or number of items currently on the queue.
*/
template
class LQueue : public Queue
{
protected:
Node
Node
int numitems; // the queue length
public:
LQueue(); // default constructor
~LQueue(); // destructor
void clear();
bool isEmpty() const;
void enqueue(const T& newItem);
T front() const;
void dequeue();
int length() const;
string tostring() const;
const T& operator[](int index) const;
};
//————————————————————————-
// Assignment 11
// You should add your PriorityQueue definition here. You class should
// be derived from the LQueue
// You only need to override and implement 1 method in your PriorityQueue
// class, the enqueue() method, which should insert new items into the
// linked list ordered by priority, rather than inserting at the end
// of the queue as is done by the basic enqueue()
// include the implementaiton of the class templates
#include “Queue.cpp”
#endif
/**
* @author Derek Harter
* @cwid 123 45 678
* @class COSC 2336, Spring 2019
* @ide Visual Studio Community 2017
* @date March 1, 2019
* @assg C++ Queues videos
*
* @description A Queue ADT with two concrete impelementation
* examples: an array based queue implementaiton (AQueue), and
* a linked list based implementation (LQueue).
*/
//————————————————————————-
/** Queue equivalence
* Compare two given queues to determine if they are equal or not.
* stacks are equal if they are both of the same size, and each
* corresponding item on each stack is equal at the same position on the
* stack. This function relies on overloaded operator[] to access
* items on stack by index for the comparison.
*
* @param rhs The stack on the right hand side of the boolean comparison
* expression to compare this stack against to check for equivalence.
*
* @returns bool Returns true if the stacks are equal, and false otherwise.
*/
template
bool Queue
{
// if number of items on the stacks don’t match, then they can’t
// be equivalent
if (this->length() != rhs.length())
{
return false;
}
// otherwise need to check each item individually
for (int index = 0; index < this->length(); index++)
{
if ((*this)[index] != rhs[index])
{
return false;
}
}
// if we get to this point, all itmes checked were equivalent, so
// we are done and the answer is yes the stacks are equal
return true;
}
/** Queue output stream operator
* Friend function for Queue ADT, overload output stream operator to allow
* easy output of queue representation to an output stream.
*/
template
ostream& operator<<(ostream& out, const Queue& aQueue)
{
out << aQueue.tostring();
return out;
}
//-------------------------------------------------------------------------
/** queue (array) constructor
* Constructor for queue. Default to enough room for 100 items
* NOTE: the front pointer points directly to the index of the front item, but
* the backIndex pointer points to the index-1 of the item where next insertion
* will happen.
* NOTE: we treat the items array as a circular buffer, so all increments of
* indexes must be modulo current allocSize, to wrap backIndex around to beginning.
*
* @param initialAlloc Initial space to allocate for queue, defaults to
* 100.
*/
template
AQueue
{
allocSize = initialAlloc;
numitems = 0;
frontIndex = 0;
backIndex = allocSize – 1; // back points to (x-1) % allocSize index
items = new T[allocSize];
}
/** queue (array) constructor
* Constructor for queue using an array initializer.
* NOTE: the front pointer points directly to the index of the front item, but
* the backIndex pointer points to the index-1 of the item where next insertion
* will happen.
* NOTE: we treat the items array as a circular buffer, so all increments of
* indexes must be modulo current allocSize, to wrap backIndex around to beginning.
*
* @param initialAlloc Initial space to allocate for queue, defaults to
* 100.
*/
template
AQueue
{
this->allocSize = numitems;
this->numitems = numitems;
frontIndex = 0;
items = new T[allocSize];
// copy the initialize items into this queue
for (int index = 0; index < numitems; index++)
{
items[index] = initItems[index];
}
// set up the back index
backIndex = numitems - 1;
}
/** queue (array) destructor
*/
template
AQueue
{
// free up currently allocated memory
delete [] items;
}
/** queue (array) clear
* Function to initialize the queue back to an empty state.
* Postcondition: frontIndex = 0; backIndex = allocSize-1; numitems=0; isEmpty() == true
*/
template
void AQueue
{
frontIndex = 0;
backIndex = allocSize – 1;
numitems = 0;
}
/** queue (array) isEmpty
* Determine whether queue is currently empty or not.
*
* @returns returns true if the queue is empty, otherwise
* returns false.
*/
template
bool AQueue
{
return numitems == 0;
}
/** queue (array) isFull
* Determine whether queue is currently full or not.
*
* @returns returns true if the queue is full, otherwise
* returns false.
*/
template
bool AQueue
{
return numitems == allocSize;
}
/** queue (array) enqueue
* Add newItem to the back of the queue.
* Preconditon: The queue exists
* Postcondition: The queue is changed and newItem is added to the back
* of the queue.
* @param newItem The new item to add to the frontIndex of this queue.
*/
template
void AQueue
{
// if queue is full, grow it
if (isFull())
{
// double the current size
int newAllocSize = 2 * allocSize;
// alloc the new space
T* newItems = new T[newAllocSize];
// and copy the queue to the new storage space
// since we are copying anyway, we shift the items from the old
// frontIndex back to index 0
int oldIndex = frontIndex;
for (int index = 0; index < numitems; index++)
{
newItems[index] = items[oldIndex];
oldIndex = (oldIndex + 1) % allocSize;
}
frontIndex = 0;
backIndex = numitems-1;
// free up the old space, start using the new space
delete [] items;
items = newItems;
allocSize = newAllocSize;
}
// add the item, and increment our top
backIndex = (backIndex + 1) % allocSize;
numitems++;
items[backIndex] = newItem;
}
/** queue (array) front
* Peek at and return the front element of the queue.
* Preconditon: The queue exists and is not empty
* Postcondition: If the queue is empty, we throw QueueEmpty
* exception; otherwise, the front element of the queue is
* returned
* @returns T The item of type T currently on the front of this
* queue.
*/
template
T AQueue
{
//assert(topIndex != 0);
if (isEmpty())
{
throw EmptyQueueException(“AQueue
}
else
{
return items[frontIndex];
}
}
/** queue (array) dequeue
* Remove the front element from the queue. Some ADT combine dequeue
* and front. We have two separate operations in this ADT.
* Preconditon: The queue exists and is not empty.
* Postcondition: If the queue is empty, we throw QueueEmpty
* exception; otherwise the front element of the queue is removed
* from the queue.
*/
template
void AQueue
{
// assert(topIndex != 0);
if (isEmpty())
{
throw EmptyQueueException(“Aqueue
}
else
{
numitems–;
frontIndex = (frontIndex + 1) % allocSize;
}
}
/** queue (array) length
* Getter method to access the current queue length.
*
* @returns length Returns the current queue length.
*/
template
int AQueue
{
return numitems;
}
/** queue (array) tostring
* Represent this queue as a string.
*
* @returns string Returns the contents of queue as a string.
*/
template
string AQueue
{
ostringstream out;
out << "Front: ";
int index = frontIndex;
while (index != (backIndex + 1) % allocSize)
{
out << items[index] << " ";
index++;
}
out << ":Back" << endl;
return out.str();
}
/** Queue (array) indexing operator
* Access internel elements of queue using indexing operator[].
* This is not a normal queue operation, we use mainly for testing
* so that we can compare if two queues are equal at each internal
* element of the queue. For this reason, this operator should
* probably be private to the Queue class.
*
* @param index The index of the item on the queue we want to access
* and return, where index 0 represents the front of the queue and
* index == numitems-1 is the back.
*
* @returns T Returns the item at "index" on the queue.
*/
template
const T& AQueue
{
// bounds checking, we will throw our stack exception if fails
if (index < 0 || index >= numitems)
{
throw InvalidIndexQueueException(“AQueue
}
// otherwise we can directly access the asked for item from our items array
// our memory buffer is being treated as a circular buffer, so we
// have to calculated the indicated index by hand
else
{
return items[(frontIndex + index) % allocSize];
}
}
//————————————————————————-
/** queue (list) constructor
* Constructor for linked list version of queue.
* An empty queue is indicated by both front and back
* pointers pointing to null.
*/
template
LQueue
{
queueFront = NULL;
queueBack = NULL;
numitems = 0;
}
/** queue (list) destructor
* Destructor for linked list version of queue.
*/
template
LQueue
{
clear();
}
/** queue (list) clear
* This will empty out the queue. This method frees up all of the
* dynamically allocated memory being used by the queue linked list
* nodes.
*/
template
void LQueue
{
Node
// iterate through Nodes in queue, freeing them up
// as we visit them
while (queueFront != NULL)
{
temp = queueFront;
queueFront = queueFront->link;
// dellocate this Node memory
delete temp;
}
// make sure all private members are cleard correctly
queueBack = NULL;
numitems = 0;
}
/** queue (list) isEmpty
* Check if queue is empty or not.
*
* @returns true if the queue is currently empty, or
* false otherwise.
*/
template
bool LQueue
{
return queueFront == NULL;
// return numitems == 0;
}
/** queue (list) enqueue
* Add the indicated item onto the back of the queue.
*
* @param newItem The new item we will add to the back of
* this queue.
*/
template
void LQueue
{
// dynamically allocate space for the new Node to hold
// this newItem
Node
// initialize the node
newNode->item = newItem;
newNode->link = NULL;
// if the queue is empty, then this new node is the
// front and back node
if (queueFront == NULL)
{
queueFront = newNode;
}
// otherwise, it gets added onto the back
else
{
queueBack->link = newNode;
}
// the new node added is now the new back of the queue
queueBack = newNode;
numitems++;
}
/** queue (list) front
* Return the front item from the queue.
*
* @returns T Returns the item currently at the front of
* this queue.
*/
template
T LQueue
{
//assert(queueFront != NULL)
if (isEmpty())
{
throw EmptyQueueException(“LQueue
}
else
{
return queueFront->item;
}
}
/** queue (list) dequeue
* This function actually removes the item at the front of the queue from
* the queue. It is what happens if you try and dequeue() from
* an empty queue. This method throws an exception if dequeue is attempted
* from an empty queue.
*/
template
void LQueue
{
//assert(queueTop != NULL)
if (isEmpty())
{
throw EmptyQueueException(“LQueue
}
else
{
// keep track of the current front, so we can deallocate
Node
temp = queueFront;
// remove the front item from the queue
// if queue becomes empty, make sure both front and back
// are NULL
queueFront = queueFront->link;
if (queueFront == NULL)
{
queueBack = NULL;
}
numitems–;
// deallocate the old top now
delete temp;
}
}
/** queue (array) length
* Accessor method to return the current length of this queue.
*
* @returns int The current queue length
*/
template
int LQueue
{
return numitems;
}
/** queue (array) tostring
* Represent this queue as a string.
*
* @returns string Returns the contents of queue as a string.
*/
template
string LQueue
{
ostringstream out;
Node
out << "Front: ";
while (temp != NULL)
{
out << temp->item << " ";
temp = temp->link;
}
out << ":Back" << endl;
return out.str();
}
/** Queue (list) indexing operator
* Access internel elements of queue using indexing operator[].
* This is not a normal queue operation, we use mainly for testing
* so that we can compare if two queues are equal at each internal
* element of the queue. For this reason, this operator should
* probably be private to the Queue class.
*
* @param index The index of the item on the queue we want to access
* and return, where index 0 represents the front of the queue and
* index == length-1 is the back.
*
* @returns T Returns the item at "index" on the queue.
*/
template
const T& LQueue
{
// bounds checking, we will throw our stack exception if fails
if (index < 0 || index >= numitems)
{
throw InvalidIndexQueueException(“LQueue
}
// otherwise we will have to search our list for the desired item
// we will search from the queue front, which is considered
// index 0
else
{
int currentIndex = 0;
Node
while (currentIndex != index)
{
currentIndex++;
currentNode = currentNode->link;
}
return currentNode->item;
}
}
//————————————————————————-
// Assignment 11
// You should add the implemenation of your PriorityQueue
// enqueue() method here.
/**
* @author Jane Programmer
* @cwid 123 45 678
* @class COSC 2336, Spring 2019
* @ide Visual Studio Community 2017
* @date March 12, 2019
* @assg Assignment 11
*
* @description Assignment 11 Priority queues and scheduling
* simulation of jobs with priorities.
*/
#include
#include
#include
#include
#include
#include
#include “JobSimulator.hpp”
#include “Queue.hpp”
using namespace std;
//————————————————————————-
/**
* A constant for the Job class, used to keep track of
* and assign unique id’s for each job created.
*/
int Job::nextListId = 1;
/** Job default constructor
* Default constructor for Job, needed because some Queue types
* create an empty array of Job objects, so they need to get filled
* with empty jobs. We simply initialize everything to 0, as
* Job objects created this way, without a priority or service time,
* can’t be used as real jobs in a simulation.
*/
Job::Job()
{
this->id = 0;
this->priority = 0;
this->serviceTime = 0;
this->startTime = 0;
this->endTime = 0;
}
/** Job constructor
* The actual constructor that needs to be used for Jobs in a simulation.
* The job is assigned a priority, serviceTime and we record the startTime
* when the job arrived and began waiting on the system queue for processing.
*
* @param priority Each job in our simulations has a priority level. In this
* Job object and simulation, the higher the number, the higher the priority
* of the Job.
* @param serviceTime This is the time that the job needs to run, once it is
* selected/scheduled by the system dispatcher to be executed. This represents
* the time the system is busy processing this Job once it starts running.
* @param startTime The system time at which this jobs was created. Also will be
* the system time this job was added to a job queue in the system and began
* waiting to be executed.
*/
Job::Job(int priority, int serviceTime, int startTime)
{
this->id = nextListId++;
this->priority = priority;
this->serviceTime = serviceTime;
this->startTime = startTime;
this->endTime = startTime;
}
/** endTime setter
* Setter method to set the endTime of this Job. This is actually the endTime
* of when the job stoped waiting and began executing (not the time when the job
* was finished). The endTime – startTime gives the total waitTime this job
* spent waiting.
*
* @param endTime The time when job stoped waiting on a queue and began executing.
*/
void Job::setEndTime(int endTime)
{
this->endTime = endTime;
}
/** id getter
* Getter method to return this Job’s id. Used for display purposes.
*
* @returns int The unique id of this Job is returned.
*/
int Job::getId() const
{
return id;
}
/** service time getter
* Getter method to return this Job’s service time. Service time
* is the amount of time this job needs from the system to complete
* its task.
*
* @returns int The serviceTime for this Job is returned.
*/
int Job::getServiceTime() const
{
return serviceTime;
}
/** priority getter
* Getter method to return this Job’s priority level. Priority
* is a measure of the job importance. In this simulation, higher
* priority means higher importance.
*
* @returns int The priority level for this Job is returned.
*/
int Job::getPriority() const
{
return priority;
}
/** waitTime getter
* Getter method to return this Job’s waitTime. Wait time is
* the difference from the endTime when the job stoped waiting
* (and began executing) and startTime when the job was created
* and began waiting to get access to the system for execution.
*
* @returns int The wait time for this Job is returned. Wait time
* is not valid until after the job as exited the wait queue, and
* its endTime has been set.
*/
int Job::getWaitTime() const
{
return endTime – startTime;
}
/** cost getter
* Getter method to return this Job’s cost. Cost is a measure of
* used to evaluate how well a particular system performs in
* processing jobs. In this simulation, we want to minimize time
* high priority jobs spend waiting, and maximize high priority
* job throughput. Thus cost is a combination of priority and how
* long the job spent waiting to be processed. Since higher numbers
* are used to mean higher priorities, multiplying the wait time
* times the priority scales the cost so that high priority jobs
* that have to wait for long periods have high costs. In the
* system, we want to minimize cost as a measure of performance.
*
* @returns int The cost for this Job is returned. Cost is a measure
* of performance with regards to this parcitular jobs. Cost is
* measured in this system as the job priority times the time the
* job was forced to wait before it could start executing.
*/
int Job::getCost() const
{
return priority * getWaitTime();
}
/** overload boolean equal comparison
* Overload boolean comparison between jobs. The main purpose of
* providing boolean comparisons between jobs in this simulation is
* so that priority based schedulers can order the jobs based on
* priority level, from lowest priority to highest priority. Thus
* for a Job, jobs are equal when they have equal priorities.
*
* @param rhs The Job object on the right hand side of the boolean
* comparison.
*
* @returns bool True if the two jobs have equal priority, false
* otherwise.
*/
bool Job::operator==(const Job& rhs) const
{
return this->priority == rhs.priority;
}
/** overload boolean less than
* Overload boolean less than comparison between jobs. The main
* purpose of providing boolean comparisons between jobs in this
* simulation is so that priority based schedulers can order the jobs
* based on priority level, from lowest priority to highest priority.
* Thus for a Job, a job is less than another job if its priority
* is smaller.
*
* @param rhs The Job object on the right hand side of the boolean
* comparison.
*
* @returns bool True if this job has lower priority than the rhs
* job, false otherwise.
*/
bool Job::operator<(const Job& rhs) const
{
return this->priority < rhs.priority;
}
/** overload boolean greater than
* Overload boolean greater than comparison between jobs. The main
* purpose of providing boolean comparisons between jobs in this
* simulation is so that priority based schedulers can order the jobs
* based on priority level, from lowest priority to highest priority.
* Thus for a Job, a job is greater than another job if its priority
* is bigger.
*
* @param rhs The Job object on the right hand side of the boolean
* comparison.
*
* @returns bool True if this job has higher priority than the rhs
* job, false otherwise.
*/
bool Job::operator>(const Job& rhs) const
{
return this->priority > rhs.priority;
}
/** overload boolean <=
* Overload boolean less than or equal comparison between jobs. The
* main purpose of providing boolean comparisons between jobs in this
* simulation is so that priority based schedulers can order the jobs
* based on priority level, from lowest priority to highest priority.
* Thus for a Job, a job is less than or equal another job if its
* priority is smaller or the same.
*
* @param rhs The Job object on the right hand side of the boolean
* comparison.
*
* @returns bool True if this job has lower or equal priority than the
* rhs job, false otherwise.
*/
bool Job::operator<=(const Job& rhs) const
{
return this->priority <= rhs.priority;
}
/** overload output stream operator
* Overload the output stream operator to provide a representation
* of this Job suitable for display. Mainly useful for displaying
* queue contents and for debugging purposes.
*/
ostream& operator<<(ostream& out, const Job& aJob)
{
// out << "[id: " << aJob.id
// << " priority: " << aJob.priority
// << " serviceTime: " << aJob.serviceTime
// << " startTime: " << aJob.startTime
// << " endTime: " << aJob.endTime
// << " waitTime: " << aJob.getWaitTime()
// << "]";
out << "[id: " << aJob.id
<< " priority: " << aJob.priority
<< "]";
return out;
}
//-------------------------------------------------------------------------
/** random uniform
* Return a random floating point value in the range of [0.0, 1.0] with
* uniform probability of any value in the range being returned.
* The algorithm is that rand() returns an int in range [0, RAND_MAX]
* and doing floating point division on the random integer by
* RAND_MAX recasts the result into a floating point number in range
* [0.0, 1.0].
*
* @returns double Returns a randomly generated double valued number
* with uniform probability in the range [0.0, 1.0]
*/
double JobSchedulerSimulator::randomUniform()
{
double randValue = double(rand()) / double(RAND_MAX);
return randValue;
}
/** random range
* Generate a random ingeger number in the given range from [minValue to
* maxValue]. We are given minValue and maxValue, a random integer is
* generated (with uniform probability) that is between minValue and
* maxValue (inclusive, so minValue or maxValue are valid results
* that can be returned, or any integer in between).
*
* @param minValue The minimum value of the range of integers to generate.
* @param maxValue The maximum of the range of integers to generate.
*
* @returns int Returns a random integer value in range [minValue,
* maxValue] inclusive of the end points.
*/
int JobSchedulerSimulator::randomRange(int minValue, int maxValue)
{
// the range is difference between desired max and min. We need
// this magnitude in order to correctly generate a random value in
// the given range
int range = maxValue - minValue + 1;
// generate a random value in range 0 to range (inclusive)
int randValue = rand() % range;
// shift the value so it is in range [minValue, maxValue]
randValue += minValue;
return randValue;
}
/** job arrived
* Test if a job arrived. We use a poisson distribution to generate
* a boolean result of true, a new job arrived in this time period,
* or false, a new job did not arrive. A Poisson distribution is often
* a good model of discrete arrivals of jobs or customers in a system.
* See Malik Ch. 18, pg. 1233 for description of the poisson arrival
* calculation here.
*
* @param none, but we use the class simulation parameter
* jobArrivalProbability to determine if a new job arrived
* using a Poisson distribution. The jobArrivalProbability
* is the probability of an arrival during a time period (lambda).
*
* @returns bool True if a new job arrived according to random check,
* false otherwise.
*/
bool JobSchedulerSimulator::jobArrived()
{
// if a random uniform value in range [0.0, 1.0] is greater than
// e^(-arrivalProbability), then a job has arrived according to
// the poisson distribution
return randomUniform() > exp(-jobArrivalProbability);
}
/** generate priority
* Generate a random priority within the given range of the
* simulation parameters [minPriority, maxPriority] inclusive.
*
* @param none, but minPriority and maxPriority simulation
* parameters are used in this function to randomly select
* a priority for a Job in the given range.
*
* @returns int A random priority in the range [minPriority, maxPriority]
* using the current settings of the simulation parameters.
*/
int JobSchedulerSimulator::generateRandomPriority()
{
return randomRange(minPriority, maxPriority);
}
/** generate service time
* Generate a random job service time within the given range of the
* simulation parameters [minServiceTime, maxServiceTime] inclusive.
*
* @param none, but minServiceTime and maxServiceTime simulation
* parameters are used in this function to randomly select a
* service time for a Job in the given range.
*
* @returns int A random serviceTime in the range [minServiceTime,
* maxServiceTime] using the current settings of the simulation
* parameters.
*/
int JobSchedulerSimulator::generateRandomServiceTime()
{
return randomRange(minServiceTime, maxServiceTime);
}
/** simulator constructor
* Mostly just a constructor to allow all of the simulation parameters
* to be set to initial values when a simulation is created. All of these
* simulation parameters have default values specified for a standard
* job simulation. All simulation result member values are initialized
* to 0 or null values in preparation for a simulation run.
*/
JobSchedulerSimulator::JobSchedulerSimulator(int simulationTime,
double jobArrivalProbability,
int minPriority,
int maxPriority,
int minServiceTime,
int maxServiceTime)
{
// initialize/remember the simulation parameters
this->simulationTime = simulationTime;
this->jobArrivalProbability = jobArrivalProbability;
this->minPriority = minPriority;
this->maxPriority = maxPriority;
this->minServiceTime = minServiceTime;
this->maxServiceTime= maxServiceTime;
// initialize simulation results to 0, ready to be calculated
this->description = “”;
this->numJobsStarted = 0;
this->numJobsCompleted = 0;
this->numJobsUnfinished = 0;
this->totalWaitTime = 0;
this->totalCost = 0;
this->averageWaitTime = 0.0;
this->averageCost = 0.0;
}
/** summary results
* Convenience methods for creating a string for display listing
* all of the simulation parameters, and all of the simulation
* results. Mostly useful after a simulation has just completed,
* to get a summary of the simulation results for the given
* simulation parameters.
*
* @returns string This method constructs and returns a string
* with a summary of the current simulation parameter settings
* and a summary of the simulation results.
*/
string JobSchedulerSimulator::summaryResultString()
{
ostringstream out;
out << "Job Scheduler Simulation Results" << endl
<< "--------------------------------" << endl
<< "Simulation Parameters" << endl
<< "--------------------------" << endl
<< "Description : " << description << endl
<< "Simulation Time : " << simulationTime << endl
<< "Job Arrival Probability : " << jobArrivalProbability << endl
<< "Priority (min,max) : (" << minPriority << ", " << maxPriority << ")" << endl
<< "Service Time (min,max) : (" << minServiceTime << ", " << maxServiceTime << ")" << endl << endl
<< "Simulation Results" << endl
<< "--------------------------" << endl
<< "Number of jobs started : " << numJobsStarted << endl
<< "Number of jobs completed : " << numJobsCompleted << endl
<< "Number of jobs unfinished: " << numJobsUnfinished << endl
<< "Total Wait Time : " << totalWaitTime << endl
<< "Total Cost : " << totalCost << endl
<< "Average Wait Time : " << setprecision(4) << fixed << averageWaitTime << endl
<< "Average Cost : " << setprecision(4) << fixed << averageCost << endl
<< endl << endl;
return out.str();
}
/** csv results
* A method for outputing the simulation results as a string of
* comma separated values (csv). This method is useful for generating
* data about large numbers of simulations for later analysis.
*
* @returns string This method constructs and returns a string
* of comma separated values (csv) of current simulation results,
* suitable for constructing a x.csv file for data analysis.
*/
string JobSchedulerSimulator::csvResultString()
{
ostringstream out;
out << numJobsStarted << ","
<< numJobsCompleted << ","
<< numJobsUnfinished << ","
<< totalWaitTime << ","
<< totalCost << ","
<< setprecision(4) << fixed << averageWaitTime << ","
<< setprecision(4) << fixed << averageCost << endl;
return out.str();
}
/** overload output stream operator
* Overload the output stream operator for convenience so we can
* output a simulation object directly to an output stream.
*
* @param out A reference to the output stream we are sending our
* output to.
* @param sim The JobSchedulerSimulator object we are outputing
* the values of. This is a friend funciton of the class, so
* the object is given as second parameter of this binary operator.
*
* @returns ostream Returns the given output stream object, but after
* we have inserted the output representation of the sim into it.
*/
ostream& operator<<(ostream& out, JobSchedulerSimulator& sim)
{
out << sim.summaryResultString();
return out;
}
// Assignment 11
// You need to add the implementation of your runSimulation()
// method, as described in the assignment, here.
/**
* @author Jane Programmer
* @cwid 123 45 678
* @class COSC 2336, Spring 2019
* @ide Visual Studio Community 2017
* @date March 12, 2019
* @assg Assignment 11
*
* @description Assignment 11 Priority queues and scheduling
* simulation of jobs with priorities.
*/
#include
#include
#include “Queue.hpp”
#include “JobSimulator.hpp”
using namespace std;
/** main
* The main entry point for this program. Execution of this program
* will begin with this main function.
*
* @param argc The command line argument count which is the number of
* command line arguments provided by user when they started
* the program.
* @param argv The command line arguments, an array of character
* arrays.
*
* @returns An int value indicating program exit status. Usually 0
* is returned to indicate normal exit and a non-zero value
* is returned to indicate an error condition.
*/
int main(int argc, char** argv)
{
// ———————————————————————–
cout << "--------------- testing basic Queue ----------------------------" << endl;
LQueue
aQueue.enqueue(5);
aQueue.enqueue(7);
aQueue.enqueue(9);
aQueue.enqueue(11);
cout << "
assert(aQueue == expectedQueue1);
cout << endl;
// -----------------------------------------------------------------------
cout << "--------------- testing PriorityQueue
cout << "
cout << "
int seed = 32;
srand(seed);
//sim.runSimulation(jobQueue, “Normal (non-prioirity based) Queueing discipline”);
cout << sim;
srand(seed);
//PriorityQueue
//sim.runSimulation(jobPriorityQueue, “Priority Queueing discipline”);
cout << sim;
// return 0 to indicate successful completion
return 0;
}
Assg
1
1: Priority Queues and Queue Applications
COSC
2
3
3
6
Spring 201
9
March 13, 2019
Dates:
Due: Sunday March 31, by Midnight
Objectives
� Extend queue ADT to add a priority queue type
� Use queue ADT for a job scheduling simulation
� Practice with manipulating linked list data structures
� Practice with inheritance and class abstractions
� Practice with operator overloading
� Practice using queue data types for applications and simulations
� Introduction to some concepts in scienti�c simulations an programming
Description
In this assignment, we will be building a simulation of a job scheduling
and processing system. The purpose of the simulation is to be able to run
simulations in order to compare their performance, when they use di�erent
queuing disciplines in order to schedule and run jobs in the system as they
arrive. We will only be building a simulator that will compare a basic queuing
discipline (�rst-come-�rst-serve) with a priority queuing discipline. In the
system being simulated, jobs will have a priority level assigned to them. It
is more costly to keep high priority jobs waiting. Thus we will de�ne an
execution cost of a job as
1
cost = priority×waitTime (1)
In this simulation, higher numbers will represent higher priority jobs.
Thus in the formula to compute cost, if a high priority job ends up having a
long wait time before it is executed and �nishes, then the cost will be high.
This is not so much of an issue if a low priority task ends up waiting a long
time, or if a high priority task is executed immediately without waiting.
In general, we want to run simulations of jobs arriving, and being man-
aged, dispatched and run, using di�erent queuing disciplines. As already
mentioned, we will only compare a basic �rst-come-�rst-serve queue with
a priority queue, but the basic framework you will create and see in this
assignment is useful for many kinds of simulation system problems.
In this assignment, you are going to be given quite a bit of starting code.
We will be using the basic Queue data type that was developed in the videos
for this weeks content about Queues (“Queue.hpp” and “Queue.cpp”). You
will also be given �les called “JobSimulator.[hpp|cpp]” which contain de�-
nitions already for a Job class, and for a JobSchedulerSimulator class. A
Job class/object represents a single job being managed and run in a sim-
ulation. The basic characteristics of a Job for our assignment is that it is
created or arrives in a system at some startTime. The simulator will simu-
late the creation/arrival of new jobs. New jobs are also randomly assigned
a priority level and a serviceTime upon arrival (again by the simulator).
The serviceTime is the amount of system time that the Job needs in or-
der to complete its work, or in other words it is the amount of resources or
time that the system will need to allocate to and be busy with in order to
complete the work of the Job.
The JobSchedulerSimulator runs a simulation of jobs arriving, being
put on a waiting jobQueue, and being dispatched and run when the system
is ready to run the next Job. Di�erent types of queues will e�ect the perfor-
mance of the system and how well it does in reducing the overall and average
cost of running jobs on the system. The simulator will simulate time using
discrete time steps, starting at time 1, 2, . . . up to the simulationTime
that is speci�ed as one of the simulation parameters. Other parameters of
a simulation, besides the type of queuing discipline to use, is the min and
max priority range to randomly assign when new jobs arrive, and the min
and max amount of serviceTime that newly created jobs will need from the
system.
You basically have to perform two di�erent parts to complete the sim-
ulator you have been given. You have to implement a PriorityQueue
2
class (derived from the given LQueue linked list based queue class), in or-
der to have a PriorityQueue we can use for the simulator. And the main
runSimulation() method has not been implemented in the JobSchedulerSimulator
class, you will need to create it according to the description below.
For this assignment you need to perform the following tasks.
1. Create a PriorityQueue class and implement a new enqueue() method
to implement a priority queuing discipline. For e�ciency, priority
queues are often implemented using a heap, so that both insertion
and removal of items can be done in O(log n) time. However, we are
going to use a simple naive method and simply insert new items into
a link list that we keep sorted by priority. Doing this means that the
insertion (enqueue()) operation becomes O(log n), but since for a pri-
ority queue we always want the next item with the highest priority
for a dequeue(), dequeue() is still O(1) constant time, since we will
keep items order by priority and the highest priority item in the queue
should always be at the front of the list.
This may sound like a lot, but there is really not too much to do to
get a basic priority queue working. You need to perform the following
steps
(a) Create a new class called PriorityQueue that inherits (using pub-
lic inheritance) and derives from the LQueue class. This class still
needs to be a template class, as it needs to be able to handle
queues of di�erent types of objects. I have set the member vari-
ables of the LQueue class to be protected, which means that your
PriorityQueue class methods will be able to access and refer to
the queueFront and queueBack member variables. You should
insert your class de�nition for your PriorityQueue at the end of
the “Queue.hpp” �le.
The only method you need to implement/override is the enqueue()
method. All other methods should work correctly using the LQueue()
implementations you will inherit. But since you are overriding
enqueue() you do need to put a new declaration for this function
in your PriorityQueue class declaration, but this will be the only
function or variable (re)de�ned in the PriorityQueue.
(b) Once you have the declaration working, you will need to create
your implementation of the enqueue() method for the PriorityQueue.
As we already mentioned, instead of always just inserting the new
3
item/node at the back of the queue, you instead need to some
some extra work and insert the new node into the linked list at the
proper position so that the link list is ordered by priority. You can
assume that the objects inserted into a PriorityQueue are over-
loaded so that boolean comparisons (like operator<, operator<=,
operator>, etc.) are de�ned to order object by their priority. The
Job class that you will be managing with your PriorityQueue has
had this operators de�ned to order jobs by their priority level. The
pseudo-code for the algorithm your enqueue() function needs to
perform is as follow:
0. Create a new Node dynamically, and assign the
newItem as its item. You may need to set link
to NULL and don’t forget to update the numitems
variable of the LQueue parent as well.
1. Case 1, if the queue is empty, then the new node
becomes both the queueFront and the queueBack.
You don’t have to do anything else, because a
list of only 1 item is already sorted.
2. Case 2, if the priority of the newItem is bigger
than the priority of the queueFront, then simply
make the newNode the new queueFront (and don’t
forget to link the newNode back to the old front
item).
3. Case 3, if the newNode priority is less than or
equal to the front node, then it is going to end
up somewhere in the middle (or end) of the
linked list. Here you need a loop to search for
the correct position. You need to keep following
links until the current node is greater or equal
in priority to the newNode, and the node it links
to is smaller priority.
a. Once you have found that position, you need
to link the newNode between the two nodes, in
the correct position to keep the list sorted.
4
b. You may or may not need to do something special
to detect if you are linking as the last node,
so it becomes the new queueBack. For the
priority queue, you don’t need the queueBack
pointer anymore, since you aren’t inserting on
the end, so you can safely ignore the queueBack
member variable for your priority queue. But
you do need to make sure if your newNode ends up
being the last node, that its link is properly
NULL terminated.
You should try and implement the cases in order, and uncomment
out the individual tests of the PriorityQueue given one by one
to test them.
(c) Once you have your PriorityQueue working, and it is passing
all of the tests given for it, you should then try and implement
the runSimulation() class method. This is a member of the
JobSchedulerSimulator class. You need to add the function
prototype for this function in the “JobSimulator.hpp” �le, and
add the implementation of the function at the end of the “Job-
Simulator.cpp” �le.
There are 2 examples of how this function should be called in
the tests give to you. The runSimulation() method takes a
Queue
that is parameterized to hold objects of type Job, as its �rst pa-
rameter. The second parameter to the function is a simple string
description of the simulation type/queue that will be run, for
display purposes. You should assign the class member variable
this value of the passed in description as one of the things you
din in the runSimulation() method.
We already brie�y described the runSimulation() method. Here
is the pseudo-code of what you need to implement in this method:
for time in range 1..simulanTime
do
// 1. process new job creation, use jobArrived()
// to check this
if job arrived
do
– generate a random priority
5
(using generateRandomPriority() )
– generate a random serviceTime
(generateRandomServiceTime() )
– create a new instance of a Job
– enqueue the job on the job queue
passed in to this function
done
// 2. dispatch jobs to run on system
if no job is running and job queue is not empty
do
– dequeue the next job from the job queue
– set remaining time for this job to its service time
done
// 3. If job is currently running, update remaining time
if job running
do
– decrement the jobs remaining time
// handle when job has finished here
if job is now finished
do
– update stats on number of jobs completed
– update totalWaitTime
– update totalCost
done
done
done
The order of execution of the 3 steps is important in the simula-
tion. If no job is running at the start of the time step, it should
be possible for a new job to enter at that time step, it be immedi-
ately dispatched, and it executes for 1 simulated time step. Thus
you have to check the arrival, dispatch and update in that order.
After you main loop simulating the system time steps, you may
have to do some more things to calculate your �nal statistics,
which is not shown. For example, when a job completes, you
6
should keep track of the number of jobs that have completed so
far, and keep track of the total wait time and total cost. You
need these sums so you can calculate the average wait time and
the average cost after the simulation ends. These averages should
be calculated only for the jobs that successfully completed be-
fore the simulation ended. There is also a parameter named
numJobsUnfinished in the simulator, which is the number of jobs
still on the job queue when the simulation ends that you should
�ll in as well.
In this assignment you will only be given 5 �les in total. The “assg-
11
.cpp” �le contains tests of the PriorityQueue you are to create, and exam-
ples of creating a JobSchedulerSimulator, and how your runSimulation()
method should be called. In addition, as mentioned, there are the “Queue.[hpp|cpp]”
�les, that you will modify to add the PriorityQueue class implementa-
tion. And the �les “JobSimulator.[hpp|cpp]” contain both the Job class
and the JobSchedulerSimulator class. You need to only add the single
runSimulation() member method to the JobSchedulerSimulator class in
these �les.
Here is an example of the output you should get if your code is passing
all of the tests and is able to run the simulation. You may not get the
exact same statistics for the runSimulation() output, as the simulation is
generating random numbers, but you should see similar values.
————— testing basic Queue —
————————–
Front: 5
7
9 11 :Back
————— testing PriorityQueue
Front: 5 :Back
needs to go on front
Front:
10
5 :Back
7
ends
up on back
Front: 10 5 2 :Back
ends up on back
Front: 10 5 2 1 :Back
Front: 10 5 3 2 1 :Back
(can’t see if correct or not with ints)
Front: 10 5 3 2 2 1 :Back
————— testing PriorityQueue
Front: [id: 1 priority: 5] :Back
needs to go on front
Front: [id: 2 priority: 10] [id: 1 priority: 5] :Back
up on back
Front: [id: 2 priority: 10] [id: 1 priority: 5] [id: 3 priority: 2] :Back
up on back
Front: [id: 2 priority: 10] [id: 1 priority: 5] [id: 3 priority: 2]
[id: 4 priority: 1] :Back
8
Front: [id: 2 priority: 10] [id: 1 priority: 5] [id: 5 priority: 3]
[id: 3 priority: 2] [id: 4 priority: 1] :Back
Front: [id: 2 priority: 10] [id: 1 priority: 5] [id: 5 priority: 3]
[id: 3 priority: 2] [id: 6 priority: 2] [id: 4 priority: 1] :Back
———– testing jobSchedulerSimulator() ——————–
Job Scheduler
Simulation Results
——————————–
Simulation Parameters
————————–
Description : Normal (non-prioirity based) Queueing discipline
Simulation Time : 10000
Job Arrival Probability : 0.1
Priority (min,max) : (1, 10)
Service Time (min,max) : (5, 15)
Simulation Results
————————–
Number of jobs started : 990
Number of jobs completed : 956
Number of jobs unfinished: 33
Total Wait Time : 165051
Total Cost : 906378
Average Wait Time : 172.6475
Average Cost : 948.0941
Job Scheduler Simulation Results
——————————–
Simulation Parameters
————————–
Description : Priority Queueing discipline
Simulation Time : 10000
9
Job Arrival Probability : 0.1
Priority (min,max) : (1, 10)
Service Time (min,max) : (5, 15)
Simulation Results
————————–
Number of jobs started : 990
Number of jobs completed : 956
Number of jobs unfinished: 34
Total Wait Time : 113251
Total Cost : 204155
Average Wait Time : 118.4634
Average Cost : 213.5513
Assignment Submission
A MyLeoOnline submission folder has been created for this assignment. You
should attach and upload your completed “Queue.[hpp|cpp]” and “JobSim-
ulator.[hpp|cpp]” source �les to the submission folder to complete this as-
signment. You do not need to submit your “assg-11.cpp” �le with test. But
please only submit the asked for source code �les, I do not need your build
projects, executables, project �les, etc.
Requirements and Grading Rubrics
Program Execution, Output and Functional Requirements
1. Your program must compile, run and produce some sort of output to
be graded. 0 if not satis�ed.
2. (50 pts.) PriorityQueue is implemented correctly.
� Correctly derived class from LQueue base class.
� Class is still a template class
� Correctly specify prototype to override enqueue() method of base
class.
� enqueue() implementation works for the empty list case
� enqueue() works to insert node at front when it is highest priority
� enqueue() works to insert node in list in correct order by priority
10
� enqueue() works when inserting node with lowest priority at back
of list
3. (50 pts.) runSimulation() function is implemented correctly.
� Correctly creating new jobs and assigning random priority and
service time on Poisson random arrival.
� Correctly dispatching jobs from queue when no job is running
� Correctly simulating job running, keeping track of remaining
� Correctly update statistics when jobs �nish.
� All simulation steps and statistics look correctly calculated.
Program Style
Your programs must conform to the style and formatting guidelines given
for this class. The following is a list of the guidelines that are required for
the assignment to be submitted this week.
1. Most importantly, make sure you �gure out how to set your indentation
settings correctly. All programs must use 2 spaces for all indentation
levels, and all indentation levels must be correctly indented. Also all
tabs must be removed from �les, and only 2 spaces used for indentation.
2. A function header must be present for member functions you de�ne.
You must give a short description of the function, and document all of
the input parameters to the function, as well as the return value and
data type of the function if it returns a value for the member functions,
just like for regular functions. However, setter and getter methods do
not require function headers.
3. You should have a document header for your class. The class header
document should give a description of the class. Also you should doc-
ument all private member variables that the class manages in the class
document header.
4. Do not include any statements (such as system(“pause”) or inputting
a key from the user to continue) that are meant to keep the terminal
from going away. Do not include any code that is speci�c to a single
operating system, such as the system(“pause”) which is Microsoft
Windows speci�c.
11