3. Suche Algorithmus zur gleichmäßigen Ausführung von gewichteten Prozessen

Suche Algorithmus zur gleichmäßigen Ausführung von gewichteten Prozessen


  • Hallo,

    gegeben folgendes Problem:
    Ich habe ein liste von Prozessen (a, b, c, ...), die jeweils ein Gewicht haben. (a.w, b.w, c.w, ...)
    Nun sollen die Prozesse gemäß ihrem Gewicht unterschiedlich oft ausgeführt werden, und zwar deterministisch und so dass die einzelnen Ausführungen möglichst homogen verteilt sind.

    Beispiel:
    Sei a.w=40, b.w=20, c.w=10.
    Dann sollen die Prozesse in dieser Reihenfolge ausgeführt werden:
    a,a,b,a,a,b,c,a,a,b,a,a,b,c,...

    aber *nicht*
    a,a,a,a,b,b,c,a,a,a,a,b,b,c,...
    das wär zu einfach. 😉

    Dazu hab ich mal das hier gefunden
    http://en.wikipedia.org/wiki/Weighted_Round_Robin
    welches dem letzteren entspricht. (angewandt auf Netzwerktechnonolgie aber egal)
    Ich suche aber "Homogeneous Weighted Round Robin" 🙂
    Gibt's das schon fertig irgendwo?
    Oder will sich mal jemand in Pseudo-Code versuchen?
    (Wird in Python implementiert)

    0

  • Ok, hab's fast.
    Der folgende Python-Code reproduziert die gewünschte Ausgabe, mit einer kleinen Unstimmigkeit am Anfang, aber damit kann ich leben:

    a,b,c,a,b,a,a,b,c,a,a,b,a,a,b,c,...

    (d.h. es wird jeder Prozess einmal ausgeführt am Anfang, aber dann konvergiert es schnell)

    process_orders_p.sort(key=lambda x: -x.w)  ## sort by descending weight
    w_sum = reduce(lambda x, y: x+y.w, process_orders_p, 0)  ## sum of all weights

    total_runs = 0
    for process_order in process_orders_p:
        process_order.runs = 0

    for i in range(0,49):
        for process_order in process_orders_p:
            if process_order.runs <= total_runs * process_order.w/w_sum :
                ## run the process
                print(process_order)
                total_runs = total_runs + 1
                process_order.runs = process_order.runs + 1
    0
  • K

    Welche Reichenfolge fuer a, b, c, d und e soll sich denn ergeben, wenn die Gewichte 40, 30, 25, 15 und 10 sind?

    0

  • Öhm. Müsste das nicht einfach so gehen...
    Pseudocode:

    foreach t in tasks
    t.inverse_weight = 1 / t.weight
    t.penalty = t.inverse_weight

forever
    t = select task with lowest penalty
    execute(t)
    t.penalty += t.inverse_weight
    0
  • K

    Bloed nur, dass die Strafe quadratisch waechst.

    0

  • knivil schrieb:

    Welche Reichenfolge fuer a, b, c, d und e soll sich denn ergeben, wenn die Gewichte 40, 30, 25, 15 und 10 sind?

    Naja, sagen wir so:
    Es soll immer derjenige Prozess als nächstes an die Reihe kommen, der in der bisherigen Verteilung der bereits ausgeführten Prozesse am deutlichsten "unterrepräsentiert" ist.

    Hintergrund ist folgendes:
    Die Prozesse brauchen Ressourcen auf.
    Die Prozessreihe wird also irgendwann aus Ressourcenmangel abgebrochen werden.

    Es soll nun eben so sein, dass auch bei relativ frühzeitigem Abbruch der Reihe die Verteilung der gelaufenen Prozesse möglichst Nahe an der gewünschten Verteilung (definiert durch die Gewichte) liegt.
    "möglichst Nahe" muss wohl noch genauer über ein geeignete Metrik definiert werden. Da bin ich mir selbst noch nicht im klaren.
    Was würde man denn da so nehmen?

    0

  • Naja, im Prinzip tut meine Lösung ja.
    Nur die anfängliche Konvergenz könnte noch besser sein.
    Mir reicht das aber. Muss noch etwas testen.

    Also nur um die Sache noch etwas theoretisch weiterzuführen:
    Ich denke man könnte folgende Metrik zwischen gewünschter und aktueller Verteilung definieren:

    M = sqrt( Sum_over_p( (p.w/w_sum - p.runs/total_runs)^2) )

    (Also Summe über die Abstandsquadrate zwischen relativer gewollter und tatsächlicher Verteilung).
    Nun führt man immer denjenigen Prozess als nächstes aus, für den das neue M minimal ist.

    Ist aber recht rechenaufwendig.

    0

  • knivil schrieb:

    Bloed nur, dass die Strafe quadratisch waechst.

    Da wächst gar nix quadratisch. 😕

    0
  • K

    Definiere gewuenschte Verteilung! Das was du suchst, ist prioritaetenbasiertes Scheduling. Ich wuerde es aehnlich wie hustbaer machen. Nur wuerde ich jedem Prozess ein Zeitkonto geben, das bei Gelegenheit aufgefuellt wird. Der ganze Kram mit Verteilung und so ist unnoetig.

    Da wächst gar nix quadratisch.

    Ja, hast recht. Es waechst linear.

    0

  • scrontch schrieb:

    (...)

    M = sqrt( Sum_over_p( (p.w/w_sum - p.runs/total_runs)^2) )

    (...)

    Ist aber recht rechenaufwendig.

    * die Wurzel ist unnötig
    * das Quadrieren kannst du mit abs() ersetzen

    Mein Vorschlag sollte aber exakt den selben Output liefern (vorausgesetzt man passt die Startparameter entsprechend an), und ist viel einfacher.

    ps: ich persönlich würde "weight" gar nicht definieren sondern direkt "inverse_weight". Dann würde ich "inverse_weight" in "cost" umbenennen und "penalty" in "consumed".
    Und natürlich gehört ein Overflow-Check rein - wenn "consumed" zu gross wird muss man über alle Tasks drüberlaufen und den Wert wieder verringern (um den kleinsten aktuellen "consumed" aller Tasks). Bzw. wenn man mit float/double rechnet gibt's nicht so schnell nen Overflow, aber die Genauigkeit schrumpft, d.h. da muss man auch irgendwann "rebasen".

    0
  • ?

    Ich kenne mich nicht so aus in diesem Thema, aber meine spontane Idee ist:

    Idee:
    Berechne für jeden Thread sowas wie den Wert das er drankommen muß.(Dringlichkeitswert)
    Dieser Wert steigt mit jeder Zeiteinheit an, in dem dieser Thread nicht drankommt. Nimm immer den Thread der den höchsten dringlichkeitswert hat und setze den Dringlichkeitswert dann für den Thread der gerade bearbeitet wird auf Null. (Jeder Thread wird gleich lange ausgeführt und dann abgebrochen)

    In deinem Fall.
    Verwende Gewichtungen größer eins. Um so größe das Gewicht ist desto wichtiger ist der jeweilige Thread. Multipliziere in jedem Schritt das Gewicht mit der vergangenen Zeit um den Dringlichkeitswert des Threads zu bestimmen.

    So werden wichtigere Threads häufiger ausgeführt. Unwichtige Threads verhungen aber nicht.

    0
  • ?

    Also:

    Initialisierung
 for (i=0; i < threadAnzahl; i++)
    {
       Wichtigkeitswert.thread[i] = 0; 
        Gewicht[i] festlegen als Wert größer Null.   
    }

Algorithmus:
while(true)
{
    for (i=0; i < threadAnzahl; i++)
    {
         Wichtigkeitswert.thrad[i] = Wichtigkeitswert.thread[i] + Gewicht[i]*  
         vergangene Zeit;
    }

Berechne Thread j mit hochstem Wichtigkeitswert;
Führe Thread j für die Zeit X aus. X ist für alle Threads konstant)
}

    Mit dem Ansatz sollten die Gewichte sogar zur Laufzeit dynamisch veränderbar sein.

    0
  • ?

    Initialisierung
    for (i=0; i < threadAnzahl; i++)
    {
    Wichtigkeitswert.thread[i] = 0;
    Gewicht[i] festlegen als Wert größer Null.
    }

    hab das Zurücksetzen vergessen:

    Algorithmus:
    while(true)
    {
    for (i=0; i < threadAnzahl; i++)
    {
    Wichtigkeitswert.thrad[i] = Wichtigkeitswert.thread[i] + Gewicht[i]*
    vergangene Zeit;
    }

    Berechne Thread j mit hochstem Wichtigkeitswert;
    Wichtigkeitswert.thrad[j] = 0;
    Führe Thread j für die Zeit X aus. X ist für alle Threads konstant)
    }

    0

  • Ich hab's jetzt mit der "linearen" Lösung von hustbaer gemacht.
    Ich hatte noch meine "quadratische" Lösung probiert, die etwas (gefühlt) schönere Reihen ausgibt. (Es fängt z.b mit a,b,a,c,a,b,a, an). Aber den Rechen-Mehraufwand rechtfertigt das nicht.

    Die Lösung von hustbaer ist der beste Kompromiss.
    Hier der Python Code der Vollständigkeit halber

    for process_order in process_orders_p:
    process_order.consumed = 1 / float(process_order.w)

for i in range(0,49):
    process_orders_p.sort(key=lambda x: x.consumed)  ## sort by ascending consumed
    ## run the top process
    run_process(process_orders_p[0])
    process_orders_p[0].consumed = process_orders_p[0].consumed + 1 / float(process_orders_p[0].w)

    Ausgabe (a.w=40, b.w=20, c.w=10):

    a
a
b
a
a
b
c
a
a
b
a
a
b
c
a
a
b
a
a
b
c
a
b
a
a
b
c
a
a
b
a
a
b
c
...

    Danke für Eure Beiträge.

    0
  • J

    hustbaer schrieb:

    scrontch schrieb:

    (...)

    M = sqrt( Sum_over_p( (p.w/w_sum - p.runs/total_runs)^2) )

    (...)

    Ist aber recht rechenaufwendig.

    * die Wurzel ist unnötig
    * das Quadrieren kannst du mit abs() ersetzen

    [/quote]

    dann erhältst du aber ein anderes maß. das was scrontch benutzt ist die L_2-Norm, du machst eine L_1-Norm draus. die wurzel kann man aber wirklich ohne unterschied wegsparen.

    0

  • Ja, genau.
    Äquivalent sind die beiden nicht.
    Wie gesagt sieht man es auch im Ergebnis.
    Klar auch dass ich die Wurzel nicht im Programmcode gezogen habe. Das diente nur der Vollständigkeit halber zur besseren Erläuterung.

    0
  • O

    ansonsten kannste auch immer simpel ne gleichverteilte Zufallsvariable ziehen. Geht auch gut

    0

  • Ich mag mich da zwar täuschen, aber ich glaube schon dass man auf die selbe Reihenfolge kommen kann, wenn man die Startwerte passend wählt (z.b. process_order.consumed = 0 oder process_order.consumed = 0.5 / float(process_order.w) oder sowas).

    0
Anmelden zum Antworten