c++ - 我将如何实现 SJF 和 Round Robin 调度模拟器？

Question

我有一个结构 vector ，结构看起来像这样:

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

用这些数据填充我的 vector 后:

1 1 5
2 3 2
3 5 10

其中每一行都是一个单独的结构 ID、arrivalTime 和 burstTime，我将如何使用“for”或“while”循环遍历我的 vector 索引并以我可以打印出类似内容的方式计算数据:

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 之后，只需对 SJF 算法进行一些修改，RR 就会很容易实现。

我想实现SJF的方法是先根据到达时间对 vector 进行排序，然后如果两个或多个 vector 索引具有相同的到达时间，则首先根据最短突发时间对其进行排序。之后，使用

int currentTime = 0;

跟踪过去了多少时间，以及

int i = 0;

用作我的 vector 的索引并控制一个“while”循环，我将如何实现一个允许我打印出上面显示的所需输出的算法？我对需要发生的事情有一个大概的了解，但我似乎无法以有效的方式在代码中将其全部列出。

我知道只要 currentTime 小于下一个最快的 arrivalTime，就意味着处理器空闲，需要将 currentTime 设置为这个 arrivalTime。

如果 vector[i+1].arrivalTime < currentTime + vector[i].burstTime，我需要将 vector[i].burstTime 设置为 vector[i+1].arrivalTime - currentTime，然后将 currentTime 设置为vector[i+1].arrivalTime，然后打印出currentTime和进程ID

我知道这些是要实现的简单数学运算，但我想不出如何按照我想要的方式进行布局。它循环的方式以及有时几个进程如何具有相同的到达时间让我失望。我是否需要更多变量来跟踪正在发生的事情？每次进程被突发时间较短的新进程抢占和中断时，我是否应该改变 vector 中所有项目的到达时间？ C++ 代码甚至伪代码的任何帮助将不胜感激。我觉得我对 SJF 的工作原理的概念相当扎实，但我只是在将我理解的内容转化为代码时遇到了麻烦。

谢谢!

Answer 1

I know that SJF and RR scheduling are pretty similar with the exception that RR has the time quantum so that no process can last longer than a arbitrary time limit before being pre-empted by another process.

我觉得不对。至少那不是我学到的。 RR 比 SJF 更接近 FCFS(先到先得)。

实现 SJF 的一种方法是根据运行时间将传入的作业插入到待处理列表中。如果新作业的运行时间比末尾作业的运行时间长，则插入位置在末尾；否则它在运行时间比传入作业长的第一个作业之前。调度很简单:删除挂起列表头部的作业并运行该作业直至完成。如果短作业不断进入并在运行时间长的作业之前得到处理，则运行时间长的作业可能永远不会运行。

实现循环法的一种方法是使用 FIFO，就像使用 FCFS 一样。新作业被添加到队列的末尾。调度再次变得简单:删除队列头部的作业并处理它。到目前为止，这正是 FCFS 所做的。两者的不同之处在于 RR 对作业可以运行多长时间有限制。如果作业完成的时间超过了某个时间量程，则作业仅运行该时间量，然后将其添加回队列的末尾。请注意，使用此公式，如果时间片长于最长运行作业的运行时间，则 RR 等同于 FCFS。

我想您可以像 SJF 那样将那些未完成的作业重新插入到进程列表的中间，但对我来说这似乎不是很循环，而且调度会更麻烦。您不能使用“始终在头部运行作业”调度规则，因为那样的话您将拥有的只是 SJF，只是变得更复杂了。