Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
The moose likes Beginning Java and the fly likes Help with priority queues in simulations. H/W Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Help with priority queues in simulations. H/W" Watch "Help with priority queues in simulations. H/W" New topic

Help with priority queues in simulations. H/W

Andrey Petrov

Joined: Sep 25, 2010
Posts: 3
I am stuck. Help. It's late, I'm tired. My mind refuses to think.
One thing: Doesn't increment globalTime;
Two thing: Heap misbehaves.
Three thing: Wrong output.

The purpose of this programming project is to learn to use priority queues (a.k.a. heaps).
One common use of priority queues is in simulation. A software simulator attempts to mimic
some real-life problem based on a set of parameters and assumptions. You are to build a
simple simulator to demonstrate a how a computer’s job scheduling algorithm works. Your
simulator will use two priority queues to accomplish that, one that prioritizes events by
time, and one that prioritizes jobs based on their specified priorities.
Your simulator will read a text file containing job information, such as the job’s submission
time, execution time, and priority. Your simulator will write a text file of information about
each job’s execution, including its start time and end time.
For this project, time will be represented by integers, starting at time 0 and ending when
the last job finishes execution.
Your input file will be a text file named “Jobs.txt” that will contain information about the
sequence of jobs whose execution you will simulate. Each line of the input file will
represent one job. The information about each job will consist of its job ID (a character
string without spaces), its arrival time (an integer greater than or equal to zero), its priority
(an integer between zero and 255 where a larger number indicates higher priority), and its
run time (an integer greater than zero). For example, the following is a possible input file:

Sample Jobs.txt Input File
JobID Arrival Time Priority Run Time
Job1 0 5 12
Job2 0 10 10
Job3 8 15 6
Job4 9 0 25
Job5 15 99 9
I suggest creating a Job class that to contain the information about each job. The class will
need to implement the Comparable interface, which means it will need to have a method
named compareTo() that will compare two jobs by priority.

Your output will be a text file named “Schedule.txt” that will describe how the jobs got
scheduled and run according to time and priority. Each line of the output file will contain
information about one job, and the file will be ordered in the jobs’ run sequence. The
information to be output for each job will be its job ID, its start time, its end time, its
arrival time, its priority, and its run time. The following table shows what the output for
the above input would be:

Sample Schedule.txt Output File
JobID Start Time End Time Arrival Time Priority Run Time
Job2 0 10 0 10 10
Job3 10 16 8 15 6
Job5 16 25 15 99 9
Job1 25 37 0 5 12
Job4 37 62 9 0 25
A ZIP file containing your project.
For this project use the class MyPriorityQueue from Chapter 25 for your priority queue
objects. You will need two priority queues.
The first will contain scheduler events. It will be prioritized by event time, with an earlier
time being a higher priority. An event may be either a job arrival or a job completion.
I suggest creating a JobEvent class to represent events. The class should contain an event
type, an event time, and a Job object. This class will need to implement the Comparable
interface, including a compareTo() method that will compare two events and prioritize them
by time, with earlier times having higher priority.
You second priority queue will contain all the jobs that have arrived and are waiting to run.
It will be prioritized by job priority.
Your program will need to read the input file, build a Job object for each job, then an
arrival JobEvent for the Job, and put the arrival into the first priority queue.
Next, your program will need to process each event in the first priority queue. If the highes-
priority event is a job arrival, the job will need to be extracted from the JobEvent and
added to your second priority queue.
If the highest-priority event is a job completion, its information will be written to the outut
file. Then the next job will need to be extracted from the second priority queue, and a job
completion JobEvent constructed for its completion time, and that JobEvent added to the
first priority queue.
Processing will continue as long as there are JobEvents in the first priority queue.

My output is the following:

Sample Schedule.txt Output File
JobID Start EndTime Arrival Priority RunTime
Job1 0 12 0 5 12
Job5 0 9 15 99 9
Job4 0 25 9 0 25
Job3 0 6 8 15 6
Job2 0 10 0 10 10
fred rosenberger
lowercase baba

Joined: Oct 02, 2003
Posts: 10908

"heap misbehaves" and "wrong output" doesn't really tell a reader ANYTHING about what the problem is. The best way to get help is to ask specific, focused questions, giving as much information as possible. HOW does the heap misbehave? What does it do that you don't expect? For that matter, what DO you expect it to do?

A general tip is to not write so much code before trying to fix it. You should only write 2-3 (or even one single) lines of code before you compile, test, and debug it. Make sure each new piece you write is ROCK SOLID before you try doing anything else.

If we were going to focus on globalTime, I'd put in some println statements around lines 39 and 54. Make sure you are entering the if-blocks, check and see what job.getRunTime() returns (if it's zero, then that's why globalTime isn't changing).

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Campbell Ritchie

Joined: Oct 13, 2005
Posts: 36464
Line 34: Never, never use == false or == true. It should read
if (!event.getCompleted()) . . .

And the name of the method is poor; it would be better as "hasCompletd" or "isCompleted".
Steve Luke

Joined: Jan 28, 2003
Posts: 3935

A few more tid-bits for you:

1) On time tracking with globalTime. When you first create the JobEvents, you do this:

So every one of your JobEvents you make when the file gets read are created with a time of zero. I think the intention is to have the 'arrival' event's time be the Job's arrival time (while the 'completed' event's time would be the time the event had finished).

2) On the 'arrival' versus 'completed' JobEvents: when you create a JobEvent you do this:

Since you hard-code completed to be true every JobeEvent is going to be treated as a completed JobEvent, regardless of what you use as a parameter when you create the JobEvent. This means the code you expect to execute for 'arrival' events will never happen, no Jobs will be added to the JobHeap, and the code you expect to happen when a Job is pulled out of the JobHeap will not be executed either (I don't think).

I agree. Here's the link:
subject: Help with priority queues in simulations. H/W
Similar Threads
Priority Queue and iterator
Discete Event Simulation Question (Code) ?
variable scope question/confusion
Threads and Synchronization examples