1

我有一个结构向量,结构看起来像这样:

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

用这些数据填充我的向量后:

1 1 5
2 3 2
3 5 10

其中每一行是一个单独的结构的 ID、到达时间和突发时间,我将如何使用“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 之后,只需对 SJF 算法进行一些修改,RR 就会很容易实现。

我考虑实现 SJF 的方式是首先根据到达时间对向量进行排序,然后如果两个或多个向量索引具有相同的到达时间,则首先根据最短的 burstTime 对其进行排序。之后,使用

int currentTime = 0;

跟踪已经过去了多少时间,以及

int i = 0;

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

我知道,每当 currentTime 小于下一个最快到达时间时,这意味着处理器处于空闲状态,需要将 currentTime 设置为此到达时间。

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

我知道这些是要实现的简单数学运算,但我想不出如何以我想要的方式将它们全部展开。它循环的方式以及有时几个进程具有相同的到达时间的方式让我大吃一惊。我是否需要更多变量来跟踪正在发生的事情?每次进程被突发时间较短的新进程抢占和中断时,我是否应该改变向量中所有项目的到达时间?非常感谢 C++ 代码甚至伪代码方面的任何帮助。我觉得我对 SJF 如何工作的概念非常了解,但我只是在将我理解的内容翻译成代码时遇到了麻烦。

谢谢!

4

1 回答 1

1

我知道 SJF 和 RR 调度非常相似,只是 RR 具有时间量,因此在被另一个进程抢占之前,没有进程可以持续超过任意时间限制。

我不认为这是对的。至少我不是这样学的。与 SJF 相比,RR 更接近 FCFS(先到先得)。

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

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

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

于 2012-10-09T10:02:47.583 回答