라우터가 기다리는 자원을 연결하면 영구 대기가 보인다
라우터의 대기열은 가득 차 있지만 링크 사용률은 낮다. 입력을 잠시 줄여도 남은 패킷들이 움직이지 않는다. 이런 상태는 부하가 높아서 잠깐 기다리는 정체와 다를 수 있다. channel dependency를 보면 각 패킷이 무엇을 붙잡고 무엇을 기다리는지 연결하여, 단순한 혼잡인지 영구 대기의 구조인지 판단할 수 있다.
네트워크의 선과 대기의 선은 다르다
물리 네트워크 그림의 꼭짓점은 라우터이고 선은 연결이다. channel dependency graph에서는 꼭짓점이 패킷이 점유하는 채널 자원이다. 패킷이 자원 c0을 계속 가진 채 다음 자원 c1을 요구할 수 있으면 c0→c1이라는 의존 관계를 그린다. 여러 대기열을 쓰는 경우 물리 전선 하나를 꼭짓점 하나로 뭉개면 중요한 상태를 잃을 수 있다.
Dally와 Seitz의 원문은 결정적인 wormhole 경로의 가정 아래 이러한 그래프와 순환 조건을 정의한다. 목적지에 도착한 메시지가 결국 소비된다는 가정도 포함한다. 경로 규칙만 확인하고 목적지의 무한 대기를 제외하지 않으면 증명의 대상이 바뀐다. 원문 PDF 2–3쪽, II절
그래프의 선은 특정 순간에 반드시 대기 중이라는 뜻이 아니다. 허용한 경로에서 그러한 자원 전이가 가능하다는 뜻이다. 현재 실행의 대기 관계와, 앞으로 발생할 수 있는 모든 관계를 모은 그래프를 나누어 읽어야 한다.
네 패킷의 대기가 고리를 닫는다
설명용으로 c0, c1, c2, c3의 네 자원을 원형으로 놓고, 각 자원의 수신 대기열은 한 flit으로 제한하자. P0는 c0을 점유하고 c1을, P1은 c1을 점유하고 c2를 요구한다. P2는 c2를 가진 채 c3을, P3은 c3을 가진 채 c0을 기다린다. 각 head는 아직 목적지에 도달하지 않았고, 다른 경로나 패킷 폐기 기능은 없다고 정한다.
대기 관계는 c0→c1→c2→c3→c0이다. 다음 대기열이 모두 차 있어 어느 head도 한 칸 전진할 수 없다. 현재 점유한 자원을 놓으려면 먼저 전진해야 하는데, 그 전진을 위해 필요한 자원도 같은 조건으로 잡혀 있다. 새로운 패킷의 주입을 0으로 내려도 네 패킷의 상태는 바뀌지 않는다.
링크의 비트 전송은 멈췄지만 네트워크가 비었다는 뜻은 아니다. 대기열과 패킷별 경로 상태가 모두 사용 중일 수 있다. 물리 링크의 낮은 활동량과 자원의 낮은 점유를 같은 것으로 해석하면 이런 실패를 놓친다.
고리가 있다고 매번 잠기는 것은 아니다
같은 허용 경로에서도 패킷 하나만 보내면 다음 자원이 비어 있어 통과한다. 따라서 의존 그래프의 순환은 모든 트래픽에서 즉시 실패한다는 뜻이 아니다. 특정 점유 조합이 순환 대기를 실현할 수 있음을 경고한다. 반대로 많은 무작위 패턴이 통과했다고 그 조합이 없다고 증명하지는 못한다.
일반적인 적응형 경로나 탈출 자원, 선점 및 폐기 정책까지 들어가면 논증의 조건이 달라진다. 가능한 전이를 모두 합친 그래프에 순환이 있다는 사실만으로 그런 모든 설계를 같은 방식으로 판정하지 않는다. 이 글의 네 패킷 예제는 점유를 유지하고 정해진 다음 자원을 기다리는 모델로 한정한다.
순서를 정하면 닫힌 대기를 끊을 수 있다
자원에 순위를 주고 패킷이 항상 더 높은 순위로만 이동하도록 정해 보자. 순환이 있다면 출발한 순위로 되돌아와야 하지만 매 단계 증가한다는 규칙과 모순된다. 앞의 예에서는 c3에서 c0으로 넘어가는 경로를 금지하거나 다른 자원 체계로 바꾸어 고리를 끊어야 한다. 금지한 연결을 그대로 필요로 하는 패킷의 목적지 도달 방법도 함께 설계한다.
이 순서는 누군가에게 전송 기회가 실제로 제공되고, 목적지가 데이터를 소비한다는 조건에서 자원 순환에 의한 영구 대기를 막는 근거다. 모든 패킷의 대기시간이 짧거나 공평하다는 보장은 별도로 얻어야 한다.
혼잡은 필요한 출력이 바쁘지만 계속 비워지는 상태일 수 있다. starvation은 진행 가능한 특정 패킷이 중재에서 계속 지는 문제다. livelock은 패킷이 움직여도 목적지에 도달하지 않는 문제다. 이들을 대기 고리와 같은 원인으로 취급하면 입력률 조절이나 우선순위 변경이 엉뚱한 해결책이 된다.
channel dependency를 검토할 때는 패킷이 유지하는 자원, 요구하는 다음 자원, 해제 조건을 먼저 적는다. 그 연결이 닫힐 수 있는지 확인하고, 허용 경로와 복구 규칙의 가정을 명시한다. ‘오래 기다린다’라는 관측을 자원의 고리로 바꾸면, 더 오래 기다려도 풀리지 않을 문제를 설계 단계에서 구별할 수 있다.