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