"-j"옵션으로 만들기 : 의존성 그래프에서 앞으로 나아갈 때 어떻게 알 수 있습니까?

Question

This post은 make이 올바른 순서로 대상을 작성하는 방법을 설명합니다. 병렬에 대해 더 자세히 이해하고 싶습니다. 게시물에서 :

정상적인 비 병렬 작업에서 make는 각 반복을 대상으로 하나를 선택하여 빌드합니다. 병렬 일 때 최대 동시 작업 수인 까지 가능한 한 많은 종속성이없는 대상을 으로 잡고 병렬로 빌드합니다.

나는 사진 무엇 :

1. 없이 누락 된 종속성이있는 모든 대상을 찾습니다.
2. 모든 대상을 빌드하십시오.
3. 모든 병렬 작업자가 완료 (동기화) 할 때까지 기다리십시오.
4. (1) 단계로 돌아갑니다.

그러나 이것은 잘못된 것입니다. make -j은 단계 (3)없이 그래프에서 앞으로 이동해야하는시기를 어떻게 든 알고 있습니다. 새 대상은 모든 종속성이 완료되고 병렬 작업자가 사용 가능할 때만 시작됩니다. 방법?

내 첫번째 추측에

A -> C 
B -> D 

, make -j2이 중 하나C 또는 D이 시작되기 전에 완료 모두A 및 B 기다릴 것 :

예를 들어, 그래프를 고려한다. 그러나 A이 완료되었지만 B이 아직 진행 중이면이 메시지는 C으로 이동할 수 있음을 알 것입니다.

Answer 1

내부적으로 각 노드가 대상이고 각 가장자리가 전제 조건 관계인 방향성 비순환 그래프 (DAG)를 만듭니다.

Make는 시작 노드를 (a) 명령 행에서 요청한 대상 또는 (b) makefile에 정의 된 첫 번째 대상으로 선택합니다.

거기에서 make는 그래프 깊이 - 왼쪽에서 오른쪽으로 이동합니다.

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

메이크업이 같은 DAG를 안내합니다 : 그래서 메이크 주어진

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

메이크업 먼저 리프 노드를 구축하기 때문에, (모든 노드가 최신입니다 가정) 조리법의 실제 호출 될 것입니다

01 :

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

당신은이 간단한 메이크으로 하찮게 자신이 증명할 수 : 순서로

그럼 이제 어떻게 병렬 처리가 이루어 집니까?

병렬 빌드에서 make는 동일한 DAG를 만들고 같은 알고리즘을 따라 걸어갑니다. 큰 차이점은 make가 타겟을 빌드하기로 결정할 때 일어나는 일입니다. 병렬이 아닌 빌드에서는 make가 레시피를 호출하고 종료 될 때까지 기다린 후 다음 레서피로 이동합니다.

병렬 빌드 (무한 작업이 아닌 것으로 가정)에서는 make가 먼저 jobserver 토큰을 얻습니다. 잠을 못 자면 잠을 잘 것이다. 가능한 경우 해당 대상에 대한 레시피를 호출하지만 기다리는 대신 해당 알고리즘으로 돌아가서 형제 노드가 될 DAG의 다음 노드로 이동합니다. 형제가없는 경우 부모에게 다시 돌아가서 에에 형제가 있는지 확인합니다 (자식이 아직 완성되지 않았기 때문에 부모를 만들지 못함). DAG를 통해 기타. DAG가 끝나고 모든 것이 완료되지 않은 경우 make는 처음부터 다시 시작합니다.