Create a priority based round robin algorithm

Question

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();
    }
}

Answer 1

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

• Ingest: any process arriving at this time, move from the arrival queue to the execution list, inserting it according to priority.
• Schedule: choose the process with the highest priority.
• Execute: decrement the remaining execution (burst) time for that process. If the result is 0, remove the process from the execution list.

Continue this until the arrival queue and execution list are empty.