Make mit der "-j" -Option: Wie weiß Make, wann im Abhängigkeitsgraphen weiterzugehen ist?

Question

This post beschreibt, wie make Ziele in der richtigen Reihenfolge erstellt. Ich würde gerne mehr über die Parallelität speziell erfahren. Von der Post:

Unter normalen nichtparallelen Betrieb machen Sie einfach wählen Sie eine einzelne Ziel jeder Iteration und bauen Sie es. Wenn es parallel ist, wird es so viele abhängigkeitslose Ziele wie möglich aufnehmen und sie parallel aufbauen, bis zur Anzahl der erlaubten simultanen Jobs.

Was ich Bild:

1. ohne fehlende Abhängigkeiten alle Ziele finden.
2. Erstellen Sie alle diese Ziele.
3. Warten Sie, bis alle parallelen Worker fertig sind (synchronisieren).
4. Zurück zu Schritt (1).

Aber das ist falsch: make -j weiß irgendwie, wenn in der Grafik ohne Schritt (3) voranzukommen. Neue Ziele beginnen erst, wenn alle Abhängigkeiten abgeschlossen sind und ein paralleler Worker verfügbar ist. Wie?

Betrachten wir zum Beispiel die Grafik:

A -> C 
B -> D 

In meine erste Vermutung, make -j2 würde für warten beideA und B zu beenden, bevor entwederC oder D beginnt. Es scheint jedoch zu wissen, dass es weitergehen kann zu C, wenn A endet, aber B ist noch in Bearbeitung.

Answer 1

Intern erstellt make einen gerichteten azyklischen Graphen (DAG), wobei jeder Knoten ein Ziel ist und jede Kante eine vorausgesetzte Beziehung ist.

Make wählt einen Startknoten als (a) ein Ziel, das in der Befehlszeile angefordert wird, oder (b) das erste im Makefile definierte Ziel.

Von dort aus wird das Diagramm Tiefe zuerst, von links nach rechts gehen. Also dieses Make-Datei gegeben:

A: B C 
B: D E 
C: F 
E: G 

machen die DAG wie folgt laufen:

A -> B -> D -> E -> G -> C -> F 

Da make ersten Endknoten baut, die tatsächliche Aufruf von Rezepten (vorausgesetzt, alle Knoten veraltet sind) wird in dieser Reihenfolge:

D, G, E, B, F, C, A 

Sie können dieses triviale mit dieser einfachen Make-Datei, um sie beweisen:

A: B C 
B: D E 
C: F 
E: G 
A B C D E F G: ; @echo $@ 

Also, wie kommt nun Parallelismus dazu?

In einem parallelen Build erstellt make die gleiche DAG und folgt dem gleichen Algorithmus, um es zu gehen. Der große Unterschied ist, was geschieht, wenn sich make entscheidet, ein Ziel zu bauen. In einem nicht-parallelen Build ruft make das Rezept auf und wartet, bis es beendet ist, dann gehe zum nächsten.

In einem parallelen Build (unter Annahme nicht unendlicher Jobs) wird make zuerst ein Jobserver-Token erhalten. Wenn es nicht möglich ist, wird es auf einen warten warten. Wenn es möglich ist, ruft es das Rezept für dieses Ziel auf, aber anstatt zu warten, kehrt es zu seinem Algorithmus zurück und geht zum nächsten Knoten in der DAG, der der Geschwisterknoten ist. Wenn es keine Geschwister gibt, gehen wir zurück zum Elternteil und sehen, ob , dass ein Geschwister hat (make kann das Elternteil nicht bauen, weil das Kind noch nicht fertiggestellt ist). Usw. durch die DAG. Wenn es zum Ende der DAG kommt und nicht alles abgeschlossen ist, beginnt make von vorne.