我將如何實現循環調度模擬器？

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. I有一種方法只用一個deque來做到這一點，還是更容易創建另一個卡組作爲FIFO隊列來處理這個問題？我知道我需要一個整數來跟蹤已經過了多少時間，但除此之外，這個問題實際上困擾着我。它的空閒時間把我拋棄了。任何C++代碼或甚至psuedocode的幫助都會有幫助。謝謝！

Answer 1

我知道我需要一個整數，以保持多少時間已經過去了

我將開始與三個值的軌道 - 經過的時間，當前進程和下道工序。您的調度循環可能如下所示。我已經把選擇下一個過程的邏輯獨立的功能簡單起見：

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