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

Question

我有結構的載體，具有結構看起來像這樣：

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

填充我的矢量與此數據後：

1 1 5 
2 3 2 
3 5 10 

其中每行是一個單獨的結構的ID，arrivalTime和burstTime，我將如何使用「for」或「while」循環來遍歷向量的索引，並以某種方式計算數據，以便我可以打印如下內容：

Time 0 Processor is Idle 
Time 1 Process 1 is running 
Time 3 Process 2 is running 
Time 5 Process 1 is running 
Time 8 Process 3 is running 

我知道SJF和RR調度非常相似，不同之處在於RR具有時間段，因此在被另一個進程搶佔之前，任何進程都不會超過任意時間限制。考慮到這一點，我認爲在我實現SJF之後，RR將會輕鬆完成SJF算法的一些修改。

我認爲實現SJF的方法是先根據到達時間對矢量進行排序，然後如果兩個或多個矢量指數具有相同的到達時間，則首先根據最短的burstTime對其進行排序。在此之後，使用

int currentTime = 0; 

跟蹤多少時間已經過去了，

int i = 0; 

我的向量的索引的使用和控制「而」循環，我將如何實現一種算法，允許我打印出上面顯示的所需輸出？我對需要發生的事情有一個大致的瞭解，但我似乎無法用一種有效的方式將它全部放在代碼中。

我知道，只要當前時間小於下一個最早的到達時間，那麼這意味着處理器處於空閒狀態，currentTime需要設置爲這個到達時間。

如果向量[I + 1] .arrivalTime < currentTime的+載體[I] .burstTime，我需要設置向量[I] .burstTime爲矢量[I + 1] .arrivalTime - currentTime的，則設置currentTime的以矢量[i + 1] .arrivalTime，然後打印出當前時間和進程ID

我知道這些是簡單的數學運算來實現，但我不能想到如何以一種可行的方式我想要它。它循環的方式以及有時幾個進程有相同的到達時間會讓我失望。我是否需要更多變量來跟蹤發生的事情？每次進程被預先佔用並被更短的突發時間的較新進程中斷時，是否應該將向量中所有項目的到達時間移動？任何C++代碼或甚至僞代碼的幫助將不勝感激。我覺得我對SJF的工作原理非常堅定，但我只是無法將我理解的內容翻譯成代碼。

謝謝！

Answer 1

我知道SJF和RR調度與RR具有時間段的例外非常相似，因此在被另一個進程搶佔之前，任何進程都不能超過任意時間限制。

我認爲這是不對的。至少這不是我學習的方式。 RR更接近FCFS（先到先得），而不是SJF。

實現SJF的一種方法是根據運行時間將傳入作業插入待處理列表。如果新作業的運行時間比最後作業的運行時間長，則插入位置結束;否則它在第一項工作之前的運行時間比傳入工作時間長。調度很簡單：刪除待處理列表頭部的作業並運行該作業完成。長時間工作的工作可能永遠不會運行，如果短時間的工作不斷進行，並在長時間的工作之前處理該工作。

實現循環的一種方法是使用FIFO，就像使用FCFS一樣。新作業被添加到隊列的末尾。調度再次簡單：刪除隊列頭部的作業並對其進行處理。到目前爲止，這正是FCFS所做的。這兩者的不同之處在於，「無線電規則」對可以運行的工作時間有限制。如果作業花費的時間比完成時間要長，則作業僅運行該時間量，然後將其添加回隊列末尾。請注意，使用此公式，如果時間量大於最長運行作業的運行時間，則RR等同於FCFS。

我想你可以將這些不完整的工作作爲SJF插入到進程列表的中間，但對我來說這似乎不是很徹底，而且調度會更加順利。你不能使用「總是在頭腦中工作」的調度規則，因爲你所擁有的只是SJF，只是變得更加複雜。