c++ - 我将如何实现循环调度模拟器？

Question

使用如下结构的双端队列:

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++ 代码甚至伪代码的任何帮助都会真正有帮助。谢谢!

Answer 1

I know I'll need an integer to keep track of how much time has elapsed

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

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) 操作。