循环调度程序没有产生正确的结果

Question

我正在努力想象一个简单的循环调度程序，它可以找到到达服务器的固定数量进程的平均等待时间。假设我得到了一个到达时间、突发时间和量子时间（为每个进程服务的固定时间）的数组，按到达时间的升序排序。

public float roundRobin (int n, int[] arrivalTimes, int[] runTimes, int quantumTime) {

    Queue<Integer> queue = new LinkedList<>(Arrays.asList(runTimes));
    int waitingTime = 0;

    while (!queue.isEmpty()) {
        int currentProcess = queue.poll();
        if (currentProcess > quantumTime) {
            int remaining = currentProcess - quantumTime;
            waitingTime += remaining;
            queue.add(remaining );
        }
    }

    return (float)waitingTime/n;
}

当我尝试使用我在互联网上找到的示例输入运行时，上面的代码没有产生正确的平均等待时间。有人能告诉我我做错了什么，以及我如何正确执行我的结果吗？任何帮助都将不胜感激！

Answer 1

你有正确的想法。最简单的方法是模拟过程，但您缺少一些关键部分，这些部分将阻止您获得正确的解决方案。

< li >您的程序不查看到达时间来确定何时将进程添加到队列中。 < li >您的程序没有使用剩余的量程时间来执行另一个进程 < li >您的程序没有正确计算等待时间。它需要考虑队列中除正在运行的进程之外的每个进程的等待时间。 < li >您的程序正在队列中循环。如果你的程序能穿越时间，可能会更容易。每次，您都可以模拟正在运行的进程。

我创建了一个类似的循环程序，可以满足您的需求。

//Use a class to keep track of the current processes status.
public class Process{
    public int burstTime;
    public int arrivalTime;
    public int completionTime;
    public int remainingRunTime;

    //Initialize processes with an arrival time and burst time
    public Process( int arrivalTimeValue , int burstTimeValue){
        burstTime = burstTimeValue;
        arrivalTime = arrivalTimeValue;
        completionTime = -1;
        remainingRunTime = burstTime;
    }
}

static public float roundRobin ( int[] arrivalTimes, int[] burstTimes, int quantumTime) {
    //Avoid divide by zero
    if(arrivalTimes.length == 0)
        return 0;

    //processes can be either arriving, running or finished
    List<Process> arrivingProcesses = new ArrayList<Process>();
    Queue<Process> runningProcesses = new LinkedList<Process>();
    List<Process> finishedProcesses = new ArrayList<Process>();

    //Create all processes in arriving
    for(int i = 0; i < arrivalTimes.length; i++){
        arrivingProcesses.add(new Process(arrivalTimes[i], burstTimes[i]));
    }
    //I assume the arrays already list the processes based on priority.
    // If there is another way you want to choose priority then you should sort arrivingProcesses


    int currentTime = 0;

    //Simulate time until the processes are all finished
    while(!(arrivingProcesses.isEmpty() && runningProcesses.isEmpty())){

        //First add any arriving processes to the queue
        for(int i = arrivingProcesses.size()-1; i>= 0; i--){
            if(arrivingProcesses.get(i).arrivalTime <= currentTime){
                runningProcesses.add(arrivingProcesses.get(i));
                arrivingProcesses.remove(i);
            }
        }

        //Run the first item in the queue
        if(!runningProcesses.isEmpty())
            runningProcesses.peek().remainingRunTime --;

        currentTime++;

        //finish process if run time is 0
        if(runningProcesses.peek().remainingRunTime == 0){
            runningProcesses.peek().completionTime = currentTime;
            finishedProcesses.add(runningProcesses.remove());
        }

        //if the quantum time is reached, put the process in the back
        if(currentTime%quantumTime == 0 && !runningProcesses.isEmpty()){
            runningProcesses.add(runningProcesses.remove());
        }

    }

    //Calculate total waiting time
    float totalWaitTime = 0;

    for(Process checkProcess : finishedProcesses){
        totalWaitTime += (checkProcess.completionTime - (checkProcess.arrivalTime + checkProcess.burstTime));
    }

    //return the average
    return totalWaitTime / arrivalTimes.length;

}

如果这些都不合理，请告诉我。

Answer 2

int[]是单个对象，因此您无法通过Array. asList（）将其转换为列表，因为它返回List

public static List<Integer> asList(int[] array) {
    List<Integer> result = new ArrayList<>(array.length);
    for (int i : array)
        result.add(i);
    return result;
}