Как бы я внедрил симулятор планирования Round Robin?

Question

Как бы я внедрил симулятор планирования Round Robin?

Используя деку структур, которые выглядят так:

struct{
int ID;
int arrivalTime;
int burstTime;
};

Как бы я перешагнул через деку структур, чтобы, если вход, где, как это:

0 0 3
1 5 2
3 8 4

где каждая строка — это идентификатор структуры, прибывающего времени и burstTime соответственно, я мог бы напечатать что-то вроде этого:

Time 0 Process 0 is running
Time 2 Process 0 is running
Time 3 Processor is Idle
Time 5 Process 1 is running
Time 7 Processor is Idle
Time 8 Process 3 is running
Time 10 Process 3 is running

этот вывод предполагает временной квант 2. Есть ли способ сделать это с помощью только одной deque или было бы проще создать другую колоду в виде очереди FIFO для обработки этого? Я знаю, что мне понадобится целое число, чтобы отследить, сколько времени прошло, но кроме этого эта проблема действительно ставит меня в тупик. Это простой, который отталкивает меня. Любая помощь в коде C ++ или даже psuedocode действительно поможет. Спасибо!

1

c++deque scheduling struct

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

Я бы начал с трех значений — прошедшее время, текущий процесс и следующий процесс. Ваш цикл планирования может выглядеть примерно так: Для простоты я поставил логику выбора следующего процесса в отдельную функцию:

time = 0;
currentProcess = deque.end();
while(some processes remaining)
{
nextProcess = getNextProcess(time, currentProcess, deque);

if(nextProcess->arrivalTime > time)
{
// nothing to do now
// advance time by smaller of quota or nextProcess->arrivalTime
} else {
// at least one process has work ready
if(currentProcess != nextProcess)
{
// preemt currentProcess
// start nextProcess
// advance time by the smaller of quota or nextProcess->burstTime
// reduce nextProcess->burstTime by the time advanced
} else {
// continue with current process for quota or its remaining burstTime
// reduce its burstTime
}
}

currentProcess = nextProcess;
}

Внедрение getNextProcess В зависимости от ваших приоритетных критериев, наивный подход может выглядеть так:

Вы проходите deque начиная с позиции currentProcess + 1, Когда вы дойдете до конца, продолжайте с начала.
Обратите внимание на процесс с наименьшим arrivalTime это больше чем time, Давай называть это closestCandidate
Если вы найдете подходящий процесс с arrivalTime <= time а также burstTime > 0верни что
Если вы нажмете currentProcess опять же, решите между currentProcess а также closestCandidate что лучше обработать и вернуть.

Последнее, что нужно сделать, — эффективно реализовать условие зацикливания. Я оставлю это для вас, чтобы выяснить.

ПРИМЕЧАНИЕ: я не уверен, если deque лучший контейнер здесь, я бы использовал forward_list и удалите процессы по мере их завершения. Вы также можете сделать это в deque, но это операция O (n).

0