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

knivil

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.

hustbaer

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".

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.

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.

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)
}

scrontch

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.

Jester

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.

scrontch

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.

otze

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

hustbaer

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).