c++ - 我将如何实现Round Robin调度模拟器？

使用如下所示的双端队列结构：

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

我将如何遍历结构的双端队列，以便在输入如下所示的情况下：

0 0 3
1 5 2
3 8 4

其中每一行分别是一个结构的ID，arrivalTime和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。是否有一种方法可以仅使用一个双端队列来完成此操作，还是可以创建另一个平台作为FIFO队列来处理此操作？我知道我需要一个整数来跟踪已逝去的时间，但除此之外，这个问题确实使我感到困扰。它的空闲时间让我失望。 C ++代码甚至psuedocode的任何帮助都会真正提供帮助。谢谢！

最佳答案

我知道我需要一个整数来跟踪已经过去了多少时间


我将从三个值开始-经过时间，当前过程和下一个过程。您的调度循环可能如下所示。为了简单起见，我将选择下一个进程的逻辑放在一个独立函数中：

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并在完成后删除进程。您也可以在双端队列中执行此操作，但这就是O（n）操作。