1

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

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

我将如何逐步完成结构的双端队列，以便输入如下所示：

0 0 3
1 5 2
3 8 4

其中每一行分别是结构的 ID、到达时间和突发时间，我将能够打印出如下内容：

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

4

1 回答 1

0

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

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

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从 position 开始currentProcess + 1。当你到达终点时，从头开始。
  • 注意最小arrivalTime大于的过程time。让我们称之为closestCandidate
  • 如果您使用 and 找到合适的流程arrivalTime <= time，请burstTime > 0返回该流程
  • 如果您currentProcess再次点击，请决定哪个更好处理currentProcess并closestCandidate返回。

最后要做的一件事是有效地实现循环条件。我会把它留给你弄清楚。

注意：我不确定deque这里是否是最好的容器，我可能会forward_list在它们完成时使用和删除进程。您也可以在双端队列中执行此操作，但那是 O(n) 操作。

于 2012-10-10T14:11:23.873 回答