Программа планирования циклического перебора не дает правильного результата

Question

Я изо всех сил пытаюсь визуализировать простую программу планирования Round Robin, которая находит среднее время ожидания для фиксированного числа процессов, которые прибывают на сервер. Предполагается, что мне дан массив времен прихода, пакетов и квантового времени (фиксированное время для обслуживания каждого процесса), который сортируется в порядке возрастания времени прихода.

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

У вас правильная идея. Самый простой подход - это симуляция процесса, но вам не хватает нескольких ключевых частей, которые не позволят вам найти правильное решение.

• Ваша программа не смотрит на время прибытия, чтобы определить, когда добавить процессы в очередь.
• Ваша программа не использует оставшееся количество времени для выполнения другого процесса
• Ваша программа неправильно рассчитывает время ожидания. Необходимо учитывать время ожидания каждого процесса в очереди, кроме запущенного.
• Ваша программа зацикливается на очереди. Вероятно, было бы проще, если бы ваша программа проходила по времени. Каждый раз вы можете смоделировать, какие процессы запущены.

Я создал аналогичную программу циклического перебора, которая должна делать то, что вы ищете.

//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[] - это отдельный объект, поэтому вы не можете преобразовать его в список с помощью Arrays.asList(), потому что он возвращает List<int[]>, но для этого нужно создать функцию

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