Nirmal4ru
September 24th, 2009, 03:55 AM
Job scheduling system
(Using Priority Queues and hash table)
Consider a scheduling system in an operating system – the jobs form a queue and the one
with maximum priority will scheduled next. It is required to change job priority after
entering the queue.
Implement this using Priority queues which can be implemented with a binary heap. It
has two basic operations: insert and findMin. The job priority can be changed at any
time using additional operations like decreaseKey and increaseKey. The difficulty
raised by these two operations is that they require locating a particular entry in the heap,
and the basic heap operations provide no efficient way to accomplish that task. The
solution is to store an auxiliary data structure that keeps track of the location of each
object in the heap array. Usually, a hash table is used to store the location information. In
this assignment, you will implement this dual data structure and the extra
operations decreaseKey and increaseKey.
You should decide how to structure your code to maintain a properly synchronized hash
table and heap. If you are careful with your design, you should be able to use most of the
Weiss hash and heap code with minor changes and a few additions. You can assume that
each entry consists of a string identifier (like the job identifier), and an integer priority.
There will also be a string instance variable called owner, containing the name of the
owner of the job.
Method 1:
Here's one possibility for organizing the code: have a class called JobEntry that
implements both the Hashable and Comparable interfaces:
public class JobEntry implements Hashable, Comparable {
private String identifier; // used as hash key
private int location; // stores location of entry in heap
private int priority; // used for heap order
private String owner; // extra information -- owner of job
...
public int hash(int tableSize) { ... } // uses hash key
public int compareTo(Object obj) { ... } // uses priority
public boolean equals(Object obj) { ... } // uses hash key
}
Thus, the same JobEntry object can be inserted in both the hash table and the heap (i.e.
both hash table and heap store a reference to the same object).
Method 2:
Another possibility is to store all the information about the job (identifier, priority,
owner) into a class representing an entry in the heap, e.g.:
public class JobHeapEntry implements Comparable {
private String identifier;
private int priority; // used for heap order
private String owner;
...
}
and wrap this class in another class, representing the hash table entry and containing the
location of a JobHeapEntry object in the heap, e.g.:
public class JobHashEntry implements Hashable {
private JobHeapEntry job;
private int location;
...
}
Just choose one method out of the two and indicate in your algorithm. You must make
sure that whenever a change is made to the heap, the hash table is also updated.
The main driver class for your program -- let's call it JobPriorityQueueDemo -- should
read an initial set of job entries from a file specified as a command line argument and
build a heap (with hash table indexing) from these entries. Here, each line describes one
process being scheduled: the first token is the process identifier (which should be treated
as a string), the second token is the process owner, and the third token is the (integer)
priority.
Once the initial heap is built, the program should provide a command-line user interface
(or optionally a menu) to a binary heap. It allows the user to specify any of the following
commands:
insert <identifier> <owner> <int priority>
deleteMin
decreaseKey <identifier> <int decrement>
increaseKey <identifier> <int increment>
printHeap
quit
The insert command puts a string object into the heap, with an associated integer
priority (lower values have higher priority) and owner. The deleteMin command prints
to standard output the string with the lowest priority and removes the job from the heap.
The two operations, decreaseKey and increaseKey, allow the user to change the
priority of a string that has already been added to the heap -- the increment and decrement
values should be positive integers. The printHeap command prints all of the jobs in the
heap in order of location -- from index 1 to index currentSize -- without altering the
heap; you should use this command for debugging purposes and to demonstrate in your
results.txt file that your heap is working properly. The quit command ends the program.
Here are some additional suggestions of what you'll need to do to get the data structure
working:
· Modify the BinaryHeap class to store a hash table in addition to the heap array.
· Modify the BinaryHeap operations so that the entries in the hash table are updated
whenever an object is placed into or moved around in the heap array.
· Add a private method called percolateUp, which will be one of the steps for the
decreaseKey method (look at the insert method for help with writing percolateUp)
· Add the additional operations decreaseKey and increaseKey to the BinaryHeap
class.
· Add a method that allows you to build a heap from file.
THANKS IN ADVANCE
(Using Priority Queues and hash table)
Consider a scheduling system in an operating system – the jobs form a queue and the one
with maximum priority will scheduled next. It is required to change job priority after
entering the queue.
Implement this using Priority queues which can be implemented with a binary heap. It
has two basic operations: insert and findMin. The job priority can be changed at any
time using additional operations like decreaseKey and increaseKey. The difficulty
raised by these two operations is that they require locating a particular entry in the heap,
and the basic heap operations provide no efficient way to accomplish that task. The
solution is to store an auxiliary data structure that keeps track of the location of each
object in the heap array. Usually, a hash table is used to store the location information. In
this assignment, you will implement this dual data structure and the extra
operations decreaseKey and increaseKey.
You should decide how to structure your code to maintain a properly synchronized hash
table and heap. If you are careful with your design, you should be able to use most of the
Weiss hash and heap code with minor changes and a few additions. You can assume that
each entry consists of a string identifier (like the job identifier), and an integer priority.
There will also be a string instance variable called owner, containing the name of the
owner of the job.
Method 1:
Here's one possibility for organizing the code: have a class called JobEntry that
implements both the Hashable and Comparable interfaces:
public class JobEntry implements Hashable, Comparable {
private String identifier; // used as hash key
private int location; // stores location of entry in heap
private int priority; // used for heap order
private String owner; // extra information -- owner of job
...
public int hash(int tableSize) { ... } // uses hash key
public int compareTo(Object obj) { ... } // uses priority
public boolean equals(Object obj) { ... } // uses hash key
}
Thus, the same JobEntry object can be inserted in both the hash table and the heap (i.e.
both hash table and heap store a reference to the same object).
Method 2:
Another possibility is to store all the information about the job (identifier, priority,
owner) into a class representing an entry in the heap, e.g.:
public class JobHeapEntry implements Comparable {
private String identifier;
private int priority; // used for heap order
private String owner;
...
}
and wrap this class in another class, representing the hash table entry and containing the
location of a JobHeapEntry object in the heap, e.g.:
public class JobHashEntry implements Hashable {
private JobHeapEntry job;
private int location;
...
}
Just choose one method out of the two and indicate in your algorithm. You must make
sure that whenever a change is made to the heap, the hash table is also updated.
The main driver class for your program -- let's call it JobPriorityQueueDemo -- should
read an initial set of job entries from a file specified as a command line argument and
build a heap (with hash table indexing) from these entries. Here, each line describes one
process being scheduled: the first token is the process identifier (which should be treated
as a string), the second token is the process owner, and the third token is the (integer)
priority.
Once the initial heap is built, the program should provide a command-line user interface
(or optionally a menu) to a binary heap. It allows the user to specify any of the following
commands:
insert <identifier> <owner> <int priority>
deleteMin
decreaseKey <identifier> <int decrement>
increaseKey <identifier> <int increment>
printHeap
quit
The insert command puts a string object into the heap, with an associated integer
priority (lower values have higher priority) and owner. The deleteMin command prints
to standard output the string with the lowest priority and removes the job from the heap.
The two operations, decreaseKey and increaseKey, allow the user to change the
priority of a string that has already been added to the heap -- the increment and decrement
values should be positive integers. The printHeap command prints all of the jobs in the
heap in order of location -- from index 1 to index currentSize -- without altering the
heap; you should use this command for debugging purposes and to demonstrate in your
results.txt file that your heap is working properly. The quit command ends the program.
Here are some additional suggestions of what you'll need to do to get the data structure
working:
· Modify the BinaryHeap class to store a hash table in addition to the heap array.
· Modify the BinaryHeap operations so that the entries in the hash table are updated
whenever an object is placed into or moved around in the heap array.
· Add a private method called percolateUp, which will be one of the steps for the
decreaseKey method (look at the insert method for help with writing percolateUp)
· Add the additional operations decreaseKey and increaseKey to the BinaryHeap
class.
· Add a method that allows you to build a heap from file.
THANKS IN ADVANCE