Блог

Я пытаюсь реализовать алгоритм циклического планирования. Но код, который я сделал до сих пор, учитывает только время пакета. Мне также нужно учитывать время прибытия процесса. У меня есть массив time_chart, который я использую для хранения номера процесса, который выполняется в данный момент. Но если ни один процесс в данный момент не выполняется (то есть, если выбранный процесс завершил выполнение, а следующий процесс не прибыл.), значение 0 должно быть вставлено в массив time_chart.

Я сохранил время пакета и время прибытия в 2D-массив как:

 //proc[][0] is the AT array
//proc[][1] is the BT array
  

и квант времени в переменной q . Ниже приведен мой код:

 int time_chart[] = new int[total_time];
int sel_proc = 1;
int current_q = 0;

for (int k = 0; k < total_time; k  ) {

    //Assign selected process to current time in the Chart
    time_chart[k] = sel_proc;

    //Decrement Remaining Time of selected process by 1 since it has been assigned the CPU for 1 unit of time
    proc[sel_proc - 1][1]--;

    //Updating value of sel_proc for next iteration
    current_q  ;

    if (current_q == q || proc[sel_proc - 1][1] == 0)//If Time slice has expired or the current process has completed execution
    {
        current_q = 0;
        //This will select the next valid value for sel_proc
        for (int j = 1; j <= n; j  ) {
            sel_proc  ;
            if (sel_proc == (n   1)) {
                sel_proc = 1;
            }
            if (proc[sel_proc - 1][1] != 0) {
                break;
            }
        }
    }
}

// print timeline for testing
for (i = 0; i < total_time; i  ) {
System.out.println("Time "   i   ": "   time_chart[i]);
}
  

в настоящее время он выберет следующий процесс, даже если он еще не прибыл. Следовательно, мне нужно проверить, прибыл ли следующий процесс или нет. Я пытался использовать proc[sel_proc][0] <= k , чтобы проверить это, но, похоже, это не сработало. Под этим я подразумеваю, что я не получил никаких выходных данных. Я не могу придумать другого способа проверить, прибыл ли следующий процесс или нет. Как я могу проверить это и поместить значение 0 в массив, если следующий процесс не прибыл?

Хотя вы можете выполнить это, используя только массивы, логика может оказаться проще, если вы создадите структуру классов для хранения информации о процессе и будете использовать два Queues . Первый Queue представляет собой список процессов, упорядоченных по времени прибытия, а второй Queue — процессы, которые выполняются в данный момент.

Вы можете смоделировать свой процесс следующим образом

 private static class Process {
    public final int id;
    public final int burstTime;
    public final int arrivalTime;
    public int executionTime;

    public Process(int id, int burstTime, int arrivalTime) {
        super();
        this.id = id;
        this.burstTime = burstTime;
        this.arrivalTime = arrivalTime;
    }
}
  

Затем создайте незапланированные процессы вызова очереди (или то, что когда-либо кажется подходящим) и добавьте процессы в эту очередь, упорядоченную по времени прибытия. Queue<Process> = new LinkedList<>()

Теперь во время вашего цикла вы каждый раз просто проверяете начало очереди и смотрите, равно ли время прибытия процесса текущему времени или больше. Если это так, удалите его из очереди и добавьте в начало очереди планировщика. LinkedList<Process> = new LinkedList<>()

Вы всегда удаляете головной процесс из очереди планировщика и обновляете время выполнения процесса. Убедитесь, что не выходите за рамки пакетного времени, т. Е. время выполнения всегда увеличивается на quantum ИЛИ burstTime — ExecutionTime , в зависимости от того, что меньше. После обновления, если время выполнения меньше, чем время выполнения пакета, добавьте процесс обратно в очередь планировщика.

Помните, что текущее время не будет увеличено на квант, если оставшееся время для процесса было меньше кванта.

Эта проблема намного проще, если вместо одного int отслеживания текущего процесса вы используете список всех. Хорошим выбором является сохранение упорядоченного списка, в котором запущенный процесс находится во главе, а остальные следуют в том порядке, в котором они должны выполняться в будущем. Затем вы всегда можете запустить следующий процесс, повернув список. Просто обновить список для каждого кванта. Коллекция Java, которая упрощает все эти опции, называется Deque .

Что-то вроде этого:

 Deque<Integer> running = new ArrayDeque<>();
for (int quantum = 0; quantum < totalDuration;   quantum) {
  // Add new arrivals to the list of running processes.
  // Note that if the processes are pre-sorted by arrival time,
  // this loop can be made more efficient. This assumes no sorting.
  for (int process = 1; process <= processCount;   process) {
    if (arrivalTime[process] == quantum)
      running.addLast(process); // Use addFirst if new procs should run immediately.
  }
  if (running.isEmpty())
    timeChart[quantum] = 0; // Nothing to run
  else {
    // Select the process now at the head.
    int selectedProcess = running.getFirst();

    // Decrement the running process's burst time. If it's done, remove
    // it from the running list.
    if (--burstTime[selectedProcess] == 0) 
      running.removeFirst();

    // Record the run for this quantum.        
    timeChart[quantum] = selectedProcess;

    // Rotate the previous head to the tail of the list for next quantum.
    if (running.size() > 1)
      running.addLast(running.removeFirst());
  }
}
  

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

На самом деле, вы должны посмотреть, будет ли время прибытия процесса меньше или равно следующему наступающему времени. Итак, вы должны проверить proc[sel_proc][0] <= k 1 . В частности, единственное изменение, которое вам следует внести, — это ваше if, которое вместо

 if (proc[sel_proc - 1][1] != 0) {
    break;
}
  

должно стать: (если оставшееся время пакета не равно нулю и время его прибытия предшествует или равно следующему времени, т. е. k 1)

 if (proc[sel_proc - 1][1] != 0 amp;amp; proc[sel_proc][0] <= k   1) {
        break;
}
  

Что еще более важно, убедитесь, что вашей последней допустимой единицей измерения времени является total_time — 1, а не само total_time. Кроме того, зависит ли ваше время прибытия от 0 или от 1, это угловые случаи, с которыми вы должны быть осторожны.

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

Разделение времени работает на уровне ОС, потому что ОС может выбирать, какие (из допустимых) процессов / потоков она хочет запустить на процессоре, и потому что ОС может в принципе остановить поток по любой инструкции и сбросить реестры процессора в кэш. Этот принцип будет работать только в коде, если каждую задачу можно разбить на очень маленькие единицы работы (инструкции ‘CPU’). Таким образом, если у вас есть 100 задач, состоящих из 100 блоков каждая, и 4 процессорных ядра, вы можете реализовать свой собственный алгоритм разделения времени (но я бы не рекомендовал его).

Традиционно, если у вас есть несколько одновременных задач, вы бы использовали threadpool с количеством потоков, равным количеству ядер процессора (или больше, если задачи имеют IO), и вы бы просто ставили задачи в очередь по мере их поступления, и позволяли ОС беспокоиться о сокращении времени.