Ответ 1
График зависимости основывается, как и следовало ожидать, на предпосылках, перечисленных для каждой цели Makefile. make построит график, где цели и предпосылки - это вершины, и есть ориентир от пререков к их целям. Таким образом, количество входящих ребер подскажет вам, сколько пререквизитов имеет цель. Если он не имеет входящих ребер, то он не имеет необходимых условий.
Вершины для файлов .c и .h, например, не будут иметь входящих краев. Эти файлы являются вашими исходными файлами и не нуждаются в создании.
Затем он выполняет топологическую сортировку на графике, чтобы определить порядок выполнения. Материал из Википедии:
Каноническое применение топологической сортировки (топологический порядок) заключается в планировании последовательности заданий или задач; алгоритмы топологической сортировки были впервые изучены в начале 1960-х годов в контексте метода PERT для планирования в управлении проектами (Jarnagin 1960). Работы представлены вершинами, и есть край от x до y, если задание x должно быть завершено до начала работы y (например, при стирке одежды стиральная машина должна закончить, прежде чем мы высушим одежду). Затем топологическая сортировка дает порядок выполнения заданий.
Суть топологической сортировки состоит в том, чтобы найти вершины без входящих ребер (без зависимостей) и поместить их в первую очередь. Затем удалите их из графика. Теперь у вас будет новый набор вершин без входящих ребер (без зависимостей). Это следующее. И так до конца. (Если вы когда-либо достигнете точки, когда таких вершин нет, тогда граф зависимостей содержит цикл, который является условием ошибки.)
В типичном Makefile это означает, что вы сначала создадите исходные файлы (ничего не нужно делать). Затем файлы объектов, которые зависят от этих исходных файлов. Затем библиотеки и исполняемые файлы, созданные из этих объектных файлов.
При нормальной непараллельной операции make будет просто выбирать одну цель для каждой итерации и строить ее. Когда он параллелен, он будет захватывать как можно больше целей без зависимостей, а также строить их параллельно, вплоть до количества разрешенных одновременных заданий.
Поэтому, когда make получает, скажем, шаг объектного файла, у него будет большое количество вершин в графе, у всех нет входящих ребер. Он знает, что он может создавать объектные файлы параллельно, и поэтому он выделяет n копий gcc для создания объектных файлов.