创建基于优先级的循环算法

Question

在这个问题中，我想开发一个基于优先级的循环算法来安排一些任务。

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

所需的输出是

Process Start End
1       0     1
2       1     5
4       5     10
1       10    17
3       17    26

有什么合适的算法来安排这个吗？它能够使用队列等数据结构

我试过使用 2 PriorityQueues 但没有成功这是在 JAVA 中完成的，但它以大部分无所作为结束。

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

这是我实现的接口

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

基本算法是一个简单的模拟。你把你的流程放在一个到达队列中，按到达时间排序（就像你展示的那样）。然后你模拟调度程序，遍历时间。在每个时间步

Ingest：此时到达的任何进程，从到达队列移动到执行列表，按优先级插入。
调度：选择优先级最高的进程。
执行：减少该进程的剩余执行（突发）时间。如果结果为0，则将该进程从执行列表中移除。

继续此操作，直到到达队列和执行列表为空。

创建基于优先级的循环算法

Create a priority based round robin algorithm

algorithm

round-robin

preemption