web-gelistirme-sc.com

Round robin planlamasının ortalama bekleme süresi nasıl hesaplanır?

Bu tablo göz önüne alındığında: enter image description here

Bunlar zaman çizgileridir (zaman dilimi = 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

Ortalama bekleme süresini hesaplamanın basit bir yolu var mı?

Teşekkürler

Not: Her işlem için birkaç bitiş zamanı vardır!

Not2 : Bu soru aynı zamanda bir yan alıştırma olarak öncelikli algoritmayı da içeriyordu, lütfen Round robin algoritması için öncelikli sütunu dikkate almayın

7
ron

Öncelikle, tüm işlemlerin 0 zamanında geldiği bu sorunun basit versiyonunu çözmeye çalışalım. Varsayım, her biri n olarak çalıştırma süresi olan ei işlemlerimiz olduğunu varsayalım. Zaman dilimi s. Olsun. Her işlem için gereken zaman dilimi sayısının NSPi. Olmasını sağlayın. Şimdi NSPi = ceiling(ei/s) işlevimiz var. Bir işlem için gereken süre i = NSPi * s. Programın uzunluğu = sum over i from 1 to n (NSPi). İ = finish time of i - execution time of i işlemi için bekleme süresi. Ancak, her işlemin farklı bir yürütme süresine sahip olması nedeniyle, her işlemin hesaplama bitiş zamanı karmaşıktır. Ancak, belirli bir örnek için RR algoritmasının ortalama bekleme zamanına ihtiyaç duyduğunuzdan, şunu hesaplayabilirsiniz: (Length of the schedule - sum of execution time of all processes)/num of processes.

Sanırım şimdi bu formülün nasıl geliştiği hakkında bir fikriniz olacaktı. İdeal olarak, bir programın uzunluğunun tüm işlemlerin yürütme süresinin toplamına eşit olmasını ister. Ancak tüm yürütme süreleri, zaman dilimlerinin bir faktörü değildir. Bu nedenle, bazı zaman dilimlerinde, hiçbir işlem programlanmadığı yerlerde delikler alırız. Bu yüzden pratikte, programın uzunluğu yürütme sürelerinin toplamından daha büyüktür. Şimdi toplam bekleme süresi olarak farklılıklarımız var.

0
arunmoezhi

Bekleme süresini Gantt chart çizerek hesaplayabilirsiniz, böylece işlemin bekleme süresi Completion time - (Arrival time + Burst time )'a eşittir.

7
user3919801

RR için Bekleme süresi = Son başlangıç ​​saati - varış saati - (preemption * quantum)

P1'in son başlangıç ​​zamanı 24'tür (P1 Gannt tablosunda 3. kez çalışıyorsa) P1 kullanım ömründe 2 kez bekletilir Quantum = 4, Arrival = 0.

P1 Bekleme Süresi = 24 - 0 - (2 * 4) = 16 :)

2
Ashis Kr. Das

| H | I | J | K | L | H | J | K | L | J | K | L | J | L | L | Çok uzun, cevabınız kısaca şöyle: 0 4 8 12 16 20 20 28 28 36 36 40 44 48 52 56 60 Ortalama bekleme süresi = ((H - varış zamanı) + ( I - varış zamanı) + (J - varış zamanı) + (K - varış zamanı) + (L - varış zamanı))/5 = (24 - 0) + (8-5) + (52 - 8) + (44 -11) + (60 - 15)/5 = 29.8 m sn Çok uzun, cevabınız kısaca şöyle: İşte RR zamanlama algoritmasının Gantt çizelgesi İşlem [patlama zamanı, zaman kuantum, varış zamanı] H [8, 4, 0] I [4, 4, 5] J [16, 4, 8] k [12, 4, 11] L [20, sabit = 4, 15] 

1
user2242139

Java ile uygulamayı denedim:

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;
}
0
Mike-wei