使用如下结构的双端队列:
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++ 代码甚至伪代码的任何帮助都会真正有帮助。谢谢!
最佳答案
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) 操作。
关于c++ - 我将如何实现循环调度模拟器?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12820202/