need help understanding what to do

[andrewthecoder]

i have a program for my 350 class i need to do but me and my classmates dont understand how to go about it. we have asked the teacher and he just say the same thing that we don't understand if you can shed some light on this and give us some tips how to do it that would be amazing this is the problem


The program will simulate a processor using a binary heap priority queue.
The jobs to be processed will be arriving into the system on a random basis based on the following arrival times with specific processing time units.

“Regular” jobs:
Arrival Time....Processing Time
5 +/- 1..........3 +/- 2

10 +/- 1.........8 +/- 2

25 +/- 1.........13 +/- 2

“Highest Priority” jobs:
Arrival Time Processing Time
30 +/- 5 ............10 +/- 2

To start there is one processor with a priority queue to hold all jobs that have not started. Upon arrival a job will begin processing if no current job is executing or, if a job is currently in process, be placed on the priority queue based on processing time. Once a job starts it runs to completion unless a “Highest Priority” interrupts a running job. The interrupted job is removed from the processor and the remaining time is calculated and job placed back into the priority queue based on the new processing time.

You are to determine and capture a set of metrics to determine how well the system is performing (e.g. number of jobs on the queue, wait time on the queue, etc.).

You are to evaluate the metrics you collect and determine how many processors should be employed to process jobs most effectively. High number of jobs in the queue (i.e. long wait times to process) and a continually empty queue are an ineffective processing environment.

The simulation should run for 500 time units to “pre-fill” system with jobs, report metrics of queue size then continue to run for an additional 9500 time units and then report final metrics.

[dhayden]

Go through the assignment and start thinking about what you need:

The program will simulate a processor using a binary heap priority queue.

You mentioned your classmates. Is this a team programming exercise? If so then assign someone the job of creating a priority heap class (or see if one exists in the standard library).

The jobs to be processed will be arriving into the system on a random basis based on the following arrival times with specific processing time units.

So you need a class Job, and something to inject jobs into the system.

“Regular” jobs:
Arrival Time....Processing Time
5 +/- 1..........3 +/- 2
10 +/- 1.........8 +/- 2
25 +/- 1.........13 +/- 2

“Highest Priority” jobs:
Arrival Time Processing Time
30 +/- 5 ............10 +/- 2

I'd ask the prof for clarification here. It sounds like it means some jobs arrive every 4-6 seconds and take 1-5 seconds to process. Other jobs arrive every 9-11 seconds and take 6-10 seconds to process etc. So does that mean that you're supposed to create these? Or will he/she give you a file with them in it? Better find out.

In any case, it sounds like each job has an arrival time and a processing time.

To start there is one processor with a priority queue to hold all jobs that have not started.

So a Processor class. It has a priority queue of unstarted jobs.

Upon arrival a job will begin processing if no current job is executing or, if a job is currently in process, be placed on the priority queue based on processing time.

Ah! That answers one question: the ordering of the queue is based on processing time. Also class Processor has a currently running job.

Also, you need a way to assign a job to a processor. Something like:

Processor::assignJob(Job &newJob)
{
    if (runningJob == NULL) {
        runningJob = &newJob;
    } else {
        waitingJobs.insert(newJob);
    }
}

Once a job starts it runs to completion unless a “Highest Priority” interrupts a running job.

We can do this. Now assignJob is like:

Processor::assignJob(Job &newJob)
{
    if (runningJob == NULL) {
        runningJob = &newJob;
    } else if (runningJob->priority < newJob.priority) {
        waitJobs.insert(runningJob);   // put low priority job back on queue
        runningJob = &newJob;
    } else {
        waitingJobs.insert(newJob);
    }
}

The interrupted job is removed from the processor and the remaining time is calculated and job placed back into the priority queue based on the new processing time.

Okay, not a problem. You have the running time for the job, so you can deal with that.

Ah! What about time? You need a clock for your simulator. So
double simTime; // simulation time.

You are to determine and capture a set of metrics to determine how well the system is performing (e.g. number of jobs on the queue,

The priority queue needs an int size() method.
wait time on the queue
A job needs a field that holds the time when it went on the queue. Then the wait time is just simTime - job.onQueueTime

You are to evaluate the metrics you collect and determine how many processors should be employed to process jobs most effectively. High number of jobs in the queue (i.e. long wait times to process) and a continually empty queue are an ineffective processing environment.

So you need a way to dump out the number of items on the queue during the simulation.

The simulation should run for 500 time units to “pre-fill” system with jobs, report metrics of queue size then continue to run for an additional 9500 time units and then report final metrics.

So the thing above gets called twice.

But how the heck do you tie all this together?? I wrote a simulator at work that's pretty lightweight and fast. Here's how it works:

The simulation is based an an Event class. An event has the time when it occurs and a virtual process() method that runs the event:

class Event {
public:
    double time;
    virtual void process();
};

The simulator has a priority heap (hey! how convenient!) of Events sorted by time. The simulation simply does something like:

while (eventQueue.size()) {
   Event *e= eventQueue.pop();
   simTime = e->time;
   e->process();
}

Your events are
- the job generators. Each time they run they create a Job and an event to start it.
- The start job event. When it runs it puts an item on a processor
- And end job event. When this runs it removes the running process from a processor and starts the next one.

There are lots of ways to do this so don't take anything I've written as gospel. It's from memory off the top of my head! But it should be more than enough to get you going.

One bit of caution: design as much of the system as possible BEFORE you start coding. Write your header files. Think about how things should work, discover that you need more data or methods. Add those. Keep going until you're pretty sure everything will work. Only then should you start to write the code.

[andrewthecoder]

@dhayden
wow man thanks so much. its starting to make some more sense i was talking it over with a group we were thinking we would use a random number generator 0-3 and use the numbers to represent the different cases we were going to have so 0 would represent 5+/-1 and so on... then have another random generator from 0-2 to determine which of the number ex. 4, 5, 6 would be chosen and i would do this for each case to determine it. then we were going to use again another random number generator 0-4 to determine the processing time for each case. it would for the first one represent like 1,2,3,4,5 and thats how we were going to determine the jobs. the professor is not giving us any input we have to have randomly generated cases. from what i can tell i think the arrival time does matter for anything other than the processsing time since he wants it ordered throught the process time. do you think that would be a good way to generate our cases?

[dhayden]

The requirements aren't clear, but I wouldn't interpret them the way you say. If I understand you right, you would basically inject jobs like this:
- pick a job type at random (from the 3 "regular jobs" and 1 "high priority" job).
- pick the random start time and processing time based on the job type.
- put it in the system.
- repeat.

The problem is that I think these 4 generating functions are supposed to all run in parallel, not serially as you're suggesting.

[andrewthecoder]

@dhayden
so what would i have to do to make them run parallel? and i know nobody understands what he wants and when he asks he doesnt make it any more clear. i was just gonna do the first original one to choose which job then make cases for the number it choose

[dhayden]

You should do it as a simulator like I described in my first post :). If you do it that way then injecting the jobs is just a question of adding the events. You can add them all before you even start the simulator:

addJobs(int arrivalBase, int arrivalDelta, int processingBase, int processingDelta, enum Priority prio, double endTime)
{
    for (double t=0; t < endTime) {
       Job j = new Job;
       j.time = t + arrivalBase + (double) rand()/RAND_MAX * 2 * arrivalDelta - arrivalDelta;
       j.processingTime = processingBase + (double)rand()/RAND_MAX*2*processingDelta - processingDelta;
       j.priority = prio;
       t += j.time;
       if (j.time < endTime) {
           sim.addEvent(j);
       } else {
           delete j;
       }
    }
}

and in main():

addJobs(5,1,3,2,Regular,10000);
addJobs(10,1,8,2,Regular, 10000);
addJobs((25,1,13,2,Regular,10000);
addJobs(30,5,10,2,High,10000);

[andrewthecoder]

@dhayden
ohhhh ok now man your a life saver. i get what your saying im going to attempt to try and do this myself now. one more question tho he asks us what number of processors would make this most efficient how do i find that out?

[dhayden]

Write the code so you can set the number of processors. Run it with several different values and record the statistics that the Sim prints out. Then use your judgment to decide.

[andrewthecoder]

@dhayden
ok he just told us that each type of the jobs are independant of another and every intervals of 5 +-1 seconds job tpye 1 injected at every interbal of 10 +- 1 job type 2 inserted and job type 3 every 25 +-1 injected. so we dont need to choose a random job they are just inputed based on those times