Bei ein m JS Programm, an dem ich gerade Arbeite, hänge ich gerade etwas
fest.
Ich habe Klassen für Jobs, Parallelausführbare Joblisten, und
sequenziell ausführbare Joblisten, und die Joblisten erben von der Job
klasse, sind also verschachtelbar.
An den meisten Stellen meines Programms war das sehr Praktisch, da hatte
ich rekursive Funktionen, die jeweils eine Sequenzielle oder Parallele
Liste oder ein Job zurückgegeben haben, und das dann zusammen setzten.
Aber jetzt habe ich eine Situation, wo ich eine Reihe von Jobs habe, und
ich weiss, welcher Job von welchen andern Abhängig sind, ein gerichteter
azyklischer Graph. Daraus muss ich nun irgendwie diese Sequenziellen und
Parallelen Joblisten machen.
Ich weiss, dass es da vermutlich keine Perfekte Lösung gibt, aber es
gibt mehr oder weniger akzeptable Lösungen. Die Trivialste Lösung wäre
die Jobs einfach zu sortieren, und dann eine Sequenz daraus zu machen.
Aber eigentlich würde ich gerne so viel wie möglich parallel machen, und
möglichst wenig nacheinander.
1
class Job {};
2
class JobList extends Job {};
3
class ParallelJobList extends JobList {
4
constructor(jobs){
5
this.list = new Set(jobs);
6
}
7
add(job){
8
this.list.add(job);
9
}
10
};
11
class SequentialJobList extends JobList {
12
constructor(jobs){
13
this.list = [...(jobs??[])];
14
}
15
add(job){
16
this.list.push(job);
17
}
18
};
19
20
function generate(){
21
const jobs = []; // Array holding jobs
22
const depends = Symbol();
23
const dependants = Symbol();
24
25
// Some code generating the jobs here
26
// job[depends] is a Set containing a reference to all Jobs the Job depends on.
27
// job[dependants] is a Set containing a reference to all Jobs which depend on this Job.
28
29
// TODO: Convert this into JobLists somehow
30
31
return joblist;
32
}
Meine erste Idee war, das in Gruppen einzuteilen und zu Ordnen,
basierend auf den Jobs ohne Vorgängern:
1
const top_nodes = new Set();
2
for(const a of jobs)
3
if(!a[dependants])
4
top_nodes.add(a);
5
const level = Symbol();
6
const groups = Symbol();
7
function walk_tree(group, node, covered=new Set(), i=0){
8
if(covered.has(node))
9
throw new Error("Couldn't resolve cyclic dependency between parallel actions");
10
node[level] = i;
11
(node[groups]??=new Set()).add(group);
12
covered = new Set([...covered, node]);
13
for(const dnode of node[dependants])
14
walk_tree(group, dnode, covered, i+1);
15
}
16
let group = 0;
17
for(const a of top_nodes)
18
walk_tree(group++, a);
Aber irgendwie bringt mich das auch nicht weiter.
Als Beispiel, sowas könnte irgendwie so aussehen ( Mit () Sequenziell,
{} Parallel ):
1
a <- d
2
b <- d
3
d <- e
4
d <- f
5
b <- f
6
g <- e
7
h <- i
8
9
{
10
(i,h),
11
(
12
{
13
(
14
{a,b},
15
d,
16
),
17
g
18
}
19
{e,f}
20
)
21
}
Habt ihr Ideen, wie ich das einigermassen Sinnvoll machen könnte?
Der Begriff den du suchst heißt:
Topologische Sortierung
https://de.wikipedia.org/wiki/Topologische_Sortierung
und was du dazu noch machen kannst: Knoten die von Haus aus nur 1
Eingang und 1 Ausgang haben, logisch dem Vor-/Nachfolgeknoten zuordnen,
da der quasi zwingend zu einer Sequenz gehört.
Ein manueller Ansatz ist, einfach stets alles in deiner sortierten
Sequenz parallel auszuführen, was "bereit" ist, i.e. dessen
Vorbedingungen erfüllt sind. Möglich ist das zum Beispiel mit
threadsicheren queues und thread pools für die es in deiner Umgebung
bestimmt APIs gibt.
https://en.wikipedia.org/wiki/Thread_pool
Wenn das System schlauer werden soll als das, musst du überlegen welche
der jobs zu priorisieren sind. Das kann man eigentlich nur wirklich
sinnvoll, wenn man die erwarteten Laufzeiten kennt oder bei sich
wiederholenden Jobs diese Laufzeiten wenigstens messen und statistisch
auswerten kann.
Das Thema statisches und dynamisches Scheduling ist aber ein Feld für
sich. Um hier etwas empfehlen zu können, bräuchten wir mehr
Informationen.
Der Freundliche Gast X. schrieb:> Topologische Sortierung
Topologische Sortierung geht schon mal in die richtige Richtung, das
tönt fast genau wie das, was ich hier versuche. Nur dass ich nicht nur
eine Liste, sondern verschachtelte Listen habe, aus Parallel und
Sequenziell ausführbarem. Aber es ist ein guter Startpunkt, ich bin noch
am schauen, was es da so alles gibt.
A. S. schrieb:> Ein manueller Ansatz ist, einfach stets alles in deiner sortierten> Sequenz parallel auszuführen, was "bereit" ist
Das kann ich leider nicht machen. Das ist teil eines recht komplexen
Solvers, ich brauch das dort als Teil einer wichtigen Optimierung, an
der Stelle kann ich das nicht anders aufbauen, da kommen auch noch
weitere Optimierungen hinten dran die die Datenstruktur erwarten.
Ausserdem führt das Programm die Jobs auch nicht selbst aus. Das geht in
etwa so:
* User gibt ein, was er gerne hätte.
* Das Programm findet raus, wie das gemacht werden kann.
* Die Klassen ParallelJobList, SequentialJobList und Job, haben eine
Serializierungs- und Deserialisierungs-Methode. Das wird dann erstmal
als JSON in der DB gespeichert.
* Die DB ID und das JSON wird an den Browsergesendet. Der hat die 3
Klassen auch, und davon abgeleitete Klassen, die daraus ein UI aufbauen
können.
* Der Nutzer sieht dann, was in welcher Reihenfolge ausgeführt werden
würde.
* Der Nutzer gibt an, wann er es ausführen will, bestätigt es, und an
den Server wird die Zeit und di ID des Ablaufs gesendet.
* Serverseitig wird dass dann wieder Deserialisiert, und in einem neuen
Format serialisiert und an ein anderes Programm gesendet. Das andere
Programm führt es dann aus.
Das ist eigentlich alles schon fertig, und geht eigentlich auch - Einige
Abläufe sind nur noch etwas suboptimal, da sitze ich momentan dran. Und
das ganze ist noch etwas komplexer als hier beschrieben.
Daniel A. schrieb:> Das kann ich leider nicht machen.
ich verstehe deinen Punkt nicht ganz. Natürlich kannst du den Plan so
wie ich's beschrieben habe auch offline vorberechnen und dann an den
user oder wegen mir auch an den solver geben.
Wenn du einen besseren Plan als das haben willst, dann ist das ein
Zeichen dafür dass du weniger Kerne hast als parallel laufende Jobs.
Dann brauchst du wie gesagt Informationen oder wenigstens Heuristiken
über die Laufzeiten, um eine kluge Entscheidung treffen zu können.
Du kannst zum Beispiel annehmen, dass jeder Job gleich lange dauert.
Aber das sollte eine bewusste Entscheidung sein.
A. S. schrieb:> ich verstehe deinen Punkt nicht ganz. Natürlich kannst du den Plan so> wie ich's beschrieben habe auch offline vorberechnen und dann an den> user oder wegen mir auch an den solver geben.
Sagen wir, wir haben folgendes:
a<-b
b<-c
d<-e
e<-f
Sangen wir nun, ich schaue, was momentan ausgeführt werden kann. Das
wären a und d. Nun kommt der Knackpunkt. Wenn es sofort ausgeführt wird,
weiss ich danach, ok, a ist durch, also kann nun b kommen, weil keine
Vorgänger mehr. Aber da die Jobs nicht sofort ausgeführt werden, kann
ich das nicht machen.
Ich könnte jetzt depth first oder breath first da durch gehen. Depth
first gäbe das a->b->c->d->e->f. Breath first würde es
[a,d]->[b,e]->[c,f]. Das ist am Ende genau das, was die Algorithmen zur
Topologischen Sortierung auch machen, und auch mehr oder weniger das
selbe, was ich oben sowieso schon gemacht habe. Ideal wäre hier nun aber
[a->b->c, d->e->f], die 2 Sequenzen parallel. Mit einem Besseren
Algorithmus kann man das auch heraus bekommen. Und genau nach solchen
Suchte ich ja. Aber hat sich vorerst eh erledigt, der momentane Ansatzt
geht bisher gut genug.
A. S. schrieb:> Wenn du einen besseren Plan als das haben willst, dann ist das ein> Zeichen dafür dass du weniger Kerne hast als parallel laufende Jobs.> Dann brauchst du wie gesagt Informationen oder wenigstens Heuristiken> über die Laufzeiten, um eine kluge Entscheidung treffen zu können.
Die Jobs sind komplett anders, als du dir das vorstellst. Das sind
Sachen wie Server Runterfahren, Starten, Rebooten, checken ob Services
laufen, Ressourcen in VMWare oder der HMC anpassen, Maintenance Mode
setzen / beenden, etc. Das macht allerhand Dinge auf allerhand Servern,
und die Dinge haben Abhängigkeiten zueinander. Wie lange das dauert kann
man auch oft nicht sagen. Es kann auch sein, dass mal etwas nicht geht,
und man es selbst machen muss, und den Job dann bestätigt.
Ich brauche die Datenstruktur einerseits im Solver zur weiteren
Optimierung, und andererseits, zur Visualisierung. Die Einteilung in
parallele und sequenzielle Blöcke macht es übersichtlicher, als nur
einen Graphen anzuzeigen. Die Abläufe betreffen wichtige Produktive
Systeme, da muss genau hingeschaut werden, dass da alles richtig ist,
bevor man die bestätigt. Und im Programm, welches die nachher ausführt,
sieht man auch genau, was läuft in der Jobkette, und kann auch Jobs
Anhalten, überspringen, etc.
Thread beobachten
Seitenaufteilung abschalten