In this question I want to develop a Priority Based Round Robin algorithm for schedule some tasks.
This is the input tasks
AT = Arrival Time
BT = Burst Time
P = Priority
Process AT BT P
1 0 8 5
2 1 4 1
3 2 9 4
4 3 5 3
And the desired output is
Process Start End
1 0 1
2 1 5
4 5 10
1 10 17
3 17 26
Is there any proper algorithm to schedule this? it is able to use data structures like Queue etc.
I tried using 2 PriorityQueues
and could not be success
This is done in JAVA, but it ends with most of doing nothing.
public static void scheduleRoundRobin(int q, ArrayList<CPUProcess> processes){
processes.sort(new ArrivalTimeSorter());
int t = processes.get(0).getArriveTime();
PriorityQueue<CPUProcess> idleQ = new PriorityQueue<>(new BurstComparator());
PriorityQueue<CPUProcess> readyQ = new PriorityQueue<>(new PriorityComparator());
ArrayList<CPUProcess> results = new ArrayList<>();
CPUProcess currentJob = null;
while (processes.size() > 0 || readyQ.size() > 0 || idleQ.size() > 0){
for (CPUProcess process : processes){
if (!process.isFinished() && process.getArriveTime() <= t){
if (currentJob == null){
currentJob = process;
currentJob.setStartTime(t);
}
else
readyQ.add(process);
}
}
if (currentJob != null){
if (readyQ.peek() != null){
CPUProcess process = readyQ.peek();
if (process.getPriority() < currentJob.getPriority() && process.getBrustTime() < currentJob.getBrustTime()){
currentJob.setEndTime(t);
idleQ.add(currentJob);
results.add(CPUProcess.getClone(currentJob));
currentJob = process;
}
}
else if (idleQ.peek() != null){
if (currentJob.getBrustTime() <= 0){
results.add(CPUProcess.getClone(currentJob));
processes.remove(currentJob);
}
currentJob = idleQ.peek();
idleQ.remove();
}
}
if (currentJob != null){
currentJob.setBrustTime(currentJob.getBrustTime() - t);
}
t += q;
}
System.out.println(results);
}
Here are the interfaces i ve implemented
class PriorityComparator implements Comparator<CPUProcess>{
@Override
public int compare(CPUProcess o1, CPUProcess o2) {
return o1.getPriority() - o2.getPriority();
}
}
class ArrivalTimeSorter implements Comparator<CPUProcess>{
@Override
public int compare(CPUProcess o1, CPUProcess o2) {
return o1.getArriveTime() - o2.getArriveTime();
}
}
class BurstComparator implements Comparator<CPUProcess>{
@Override
public int compare(CPUProcess o1, CPUProcess o2) {
return o1.getBrustTime() - o2.getBrustTime();
}
}
The basic algorithm is a simple simulation. You put your processes in an arrival queue, sorted by arrival time (just as you show). Then you simulate the scheduler, iterating through time. At each time step
Continue this until the arrival queue and execution list are empty.