8

鉴于此表： 在此处输入图像描述

这些是时间线（时间片 = 4）：

|p1|p1|p2|p3|p4|p5|p1|p2|p3|p4|p5|p2|p3|p4|p5|p2|p3|p4|p5|p2|p3|p3|
0  4  8 12 16  20 24 28 32 36 40 44 48 52 56 60 64 68 69 72 75 79 80

有没有简单的方法来计算平均等待时间？

谢谢

注意：每个过程有几个完成时间！

注2：本题还涉及优先级算法作为辅助练习，请忽略轮询算法的优先级列

4

6 回答 6

10

You can calculate Waiting time by drawing Gantt chart so waiting time of ith process is equal to Completion time - (Arrival time + Burst time ) .

于 2014-09-08T08:05:09.197 回答
2

对于RR，等待时间=上次开始时间-到达时间-（抢占*量子）

P1的最后开始时间是24（当P1在甘特图中第三次运行时）P1在其生命周期内抢占了2次Quantum = 4，Arrival = 0。

P1 的等待时间 = 24 - 0 - (2 * 4) = 16 :)

于 2014-10-28T17:56:50.710 回答
1

|H |I |J |K |L | H| J| K|L |J |K|L |J |L |L | 它太长了，简而言之，您的答案是：0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 平均等待时间 = ((H - 到达时间) + (I - 到达时间) + (J - 到达时间）+（K-到达时间）+（L-到达时间））/5=（24-0）+（8-5）+（52-8）+（44-11）+（60-15）/ 5= 29.8 m sec 太长了，简而言之，你的答案是这样的：这里是 RR 调度算法的甘特图 Process[burst time, timequantum,arrival time] H[8, 4, 0] I[4, 4, 5] J[16, 4, 8] k[12, 4, 11] L[20, 常数 = 4, 15]

于 2013-04-09T18:17:40.250 回答
1

让我们首先尝试解决这个问题的简单版本，其中所有进程都在时间 0 到达。假设我们有n每个进程的执行时间为ei。让时间片成为s。设每个进程所需的时间片数为NSPi。现在我们有了NSPi = ceiling(ei/s). 一个过程所需的时间 i = NSPi * s. 时间表的长度 = sum over i from 1 to n (NSPi)。进程 i = 的等待时间finish time of i - execution time of i。但是计算每个进程的完成时间很复杂，因为每个进程都有不同的执行时间。但是由于您只需要特定实例的 RR 算法的平均等待时间，您可以将其计算为(Length of the schedule - sum of execution time of all processes)/num of processes：

我想现在你应该已经知道这个公式是如何演变的了。理想情况下，希望调度的长度等于所有进程的执行时间的总和。但并非所有执行时间都是时间片的一个因素。因此，在某个时间片中，我们会发现没有安排任何进程的漏洞。所以在实践中，调度的长度大于执行时间的总和。现在我们将它们的差异作为总等待时间。

于 2012-07-25T20:34:10.543 回答
0

我尝试在java中实现它：

public static float waitingTimieRobin(int[] arrival, int[] run, int q) {
    Queue<Integer> orderQueue = new LinkedList<>();
    orderQueue.add(0);
    Set<Integer> orderSet = new HashSet<>();
    orderSet.add(0);

    float sumTime = 0.0f;

    int curTime = 0;
    while (!isOver(run)) {

        int order = orderQueue.poll();
        orderSet.remove(order);
        int arrTime = arrival[order];
        int runtime = run[order];
        sumTime += (curTime - arrTime);
        if (runtime <= q) {
            curTime += runtime;
            run[order] = 0;
        } else {
            curTime += q;
            arrival[order] = curTime;
            run[order] = runtime - q;
        }

        for (int i = 0; i < run.length; i++) {
            if (arrival[i] > curTime) {
                break;
            } else if (i != order && run[i] != 0 && !orderSet.contains(i)) {
                orderQueue.add(i);
                orderSet.add(i);
            }
        }

        if(arrival[order] == curTime && run[order] != 0 && !orderSet.contains(order)) {
            orderQueue.add(order);
            orderSet.add(order);
        }
    }

    return sumTime / arrival.length;
}

public static boolean isOver(int[] run) {
    for (int runtime : run) {
        if (runtime > 0) {
            return false;
        }
    }
    return true;
}
于 2016-09-29T13:40:41.970 回答
-1

我的回答是等待时间和周转时间是

等待时间：(16+51+51+45+42)/5=41 周转时间：(28+70+72+58+57)/5=57

于 2014-05-12T15:19:29.133 回答