---
title: "돌아가는 포인터도 불공평할 수 있다: 라운드로빈 중재"
author: "브레이브브라우저쓰자"
published_at: "2026-10-08T04:01:02.207Z"
updated_at: "2026-10-05T14:08:54.945Z"
tags: ["라운드로빈 중재"]
canonical_url: "https://ariser.io/@writer_a9817d5a8de0/%EB%8F%8C%EC%95%84%EA%B0%80%EB%8A%94-%ED%8F%AC%EC%9D%B8%ED%84%B0%EB%8F%84-%EB%B6%88%EA%B3%B5%ED%8F%89%ED%95%A0-%EC%88%98-%EC%9E%88%EB%8B%A4-%EB%9D%BC%EC%9A%B4%EB%93%9C%EB%A1%9C%EB%B9%88-%EC%A4%91%EC%9E%AC"
ai_assisted: true
---

# 돌아가는 포인터도 불공평할 수 있다: 라운드로빈 중재

이 글은 AI가 활용됐습니다.

[원문](https://ariser.io/@writer_a9817d5a8de0/%EB%8F%8C%EC%95%84%EA%B0%80%EB%8A%94-%ED%8F%AC%EC%9D%B8%ED%84%B0%EB%8F%84-%EB%B6%88%EA%B3%B5%ED%8F%89%ED%95%A0-%EC%88%98-%EC%9E%88%EB%8B%A4-%EB%9D%BC%EC%9A%B4%EB%93%9C%EB%A1%9C%EB%B9%88-%EC%A4%91%EC%9E%AC)

우선순위 포인터가 매 사이클 돌아가니 요청도 공평하게 처리될 것 같다. 그런데 하류가 두 사이클에 한 번만 받자 한 요청자가 영원히 기다린다. **라운드로빈 중재의 공정성은 포인터가 돌아가는 모습이 아니라, 실제 수락된 거래 뒤에 다음 기회를 누구에게 주는가로 결정된다.**

라운드로빈은 요청자들을 순환 순서로 살펴보는 중재 방식이다. 여기서는 요청자가 0, 1, 2이고 각 거래가 한 항목이라고 정한다. 요청을 제시한 쪽은 수락 전까지 요청과 데이터를 유지한다. 출력은 valid와 ready가 함께 높은 에지에 하나의 항목을 받는다. 아래는 이 규칙을 분석하기 위한 가상의 알고리즘과 추적이다.

## 선택한 것과 처리한 것은 다르다

현재 시작 인덱스가 p라면 p, p+1, p+2의 순환 순서에서 첫 번째 활성 요청을 winner로 선택하자. winner가 실제로 수락되었을 때만 시작점을 그 다음 요청자로 옮긴다.

```systemverilog
always_ff @(posedge clk or negedge rst_n) begin
  if (!rst_n)
    start_index <= 2'd0;
  else if (fire) begin
    if (winner == 2'd2)
      start_index <= 2'd0;
    else
      start_index <= winner + 2'd1;
  end
end
```

여기서 fire는 선택한 요청이 존재하고 하류가 수락한 사건이다. winner를 계산하는 선택 회로는 생략했다. 모두 계속 요청하고 매 에지 수락된다면 0→1→2→0의 순서가 반복된다. 하류가 막히면 아직 아무도 처리하지 않았으므로 start_index도 그 자리에서 기다린다.

그 대신 매 클록에 포인터를 움직이는 두 요청자 버전을 생각하자. p는 에지 0에 0, 에지 1에 1, 에지 2에 0으로 번갈아 바뀐다. 하류가 짝수 에지에만 ready=1이라면 실제로 수락되는 것은 계속 요청자 0이다. 요청자 1은 선택되는 에지가 있지만 항상 ready=0이어서 수락되지 않는다.

포인터의 회전 횟수는 같아도 서비스 횟수는 같지 않다. 올바른 두 요청자 버전은 에지 0에 0을 수락한 뒤 p=1로 옮기고, 에지 1이 막히면 그대로 유지한다. 에지 2에는 1을 수락한다. **기회의 갱신을 클록과 연결할지 수락과 연결할지가 공정성의 차이를 만든다.**

## 대기 시간의 상한은 어떤 단위인가

세 요청자가 모두 계속 요청하고, 위 순환 탐색과 수락 뒤 갱신을 지킨다면 어떤 요청자는 자기 수락 전에 다른 요청자의 성공한 거래를 최대 두 번 기다린다. 요청이 계속 유지되는 동안 세 번째 다른 거래가 먼저 지나갈 수는 없다. 순환 순서가 그 요청을 만나기 때문이다.

이 상한은 클록 사이클 수가 아니다. 하류가 100사이클 멈추면 해당 요청도 100사이클 더 기다린다. 하류가 영원히 멈추면 누구도 완료되지 않는다. 중재기의 공정성과 환경의 진행 보장을 합쳐야 시간의 상한을 말할 수 있다.

요청이 수락 전에 사라지는 경우도 다르다. 계속 기다린다는 전제가 깨졌으므로 “언젠가 반드시 수락된다”는 결론을 그대로 적용할 수 없다. 짧은 펄스 요청을 쓰는 인터페이스라면 중재기 앞에 저장이 필요하거나, 놓쳤을 때 재시도한다는 계약이 있어야 한다.

## 비어 있는 요청자를 넘기는 방식도 영향을 준다

일부 요청자만 활성인 경우에는 시작 인덱스를 무조건 하나씩 증가시키는 방식과, 다음 활성 요청으로 이동하는 방식의 처리 비율이 달라질 수 있다. 같은 라운드로빈이라는 이름 아래에서도 빈 요청자를 어떻게 넘기는지와 선택 구조가 구현마다 다르다.

[PULP의 라운드로빈 중재기](https://github.com/pulp-platform/common_cells/blob/master/src/cc_rr_arb_tree.sv)는 활성 요청이 일부일 때 처리 비율을 고르게 하는 FairArb 옵션과, 수락이 지연될 때 선택을 유지하는 LockIn 옵션을 따로 둔다. 실제 코드에서 내부 우선순위 갱신도 출력의 요청과 수락 조건을 사용한다. 이름만 보고 기본 설정의 모든 공정성·안정성 규칙을 추측해서는 안 되는 이유다.

이 글의 순환 탐색 알고리즘은 원문의 트리 회로를 그대로 복사한 것이 아니다. 공정성을 설명하기 위해 시작점 다음의 첫 활성 요청을 선택하도록 명시한 모델이다. 다른 선택 규칙을 쓰는 중재기에는 그 규칙에 맞는 상한과 비율 분석이 필요하다.

## 거래가 같아도 사용한 자원은 다를 수 있다

0과 1이 번갈아 한 거래씩 처리된다고 하자. 0의 거래는 64바이트이고 1은 8바이트라면 거래 횟수는 같아도 byte 단위 사용량은 8배 다르다. 라운드로빈의 공정성 단위가 “거래 한 번”이었기 때문이다. 같은 원리로 하나의 요청이 긴 burst를 독점하면 다른 요청자의 시간 대기가 길어질 수 있다.

원하는 기준이 byte 수, 점유 시간 또는 서비스 비율이라면 단순 거래 순환만으로 충분하지 않을 수 있다. 우선 어떤 사건이 한 번의 서비스를 끝내는지 정해야 한다. 여러 beat로 구성된 거래 전체를 하나로 세는 중재와, beat마다 다시 선택하는 중재는 다른 인터페이스다.

출력의 데이터 유지도 공정성과 따로 확인해야 한다. 아직 수락되지 않은 winner를 새 요청 때문에 바꾸면, 지속 제시를 기대하는 소비자에게 payload가 바뀔 수 있다. 그런 계약에서는 winner를 잠가 수락까지 유지해야 한다. 포인터만 유지하는 것이 선택 데이터의 안정성을 항상 보장하지는 않는다.

## 증명할 때 환경을 편하게 만들면 놓치는 것

형식 검증으로 starvation 부재를 확인한다면 요청이 지속되는 조건과 하류가 언젠가 수락한다는 조건을 분리해야 한다. 하류 ready를 항상 1로 가정하면 앞의 짝수 에지 반례를 볼 수 없다. 너무 강한 가정은 검사하려는 현상을 없앤다.

[SymbiYosys의 빠른 시작 문서](https://symbiyosys.readthedocs.io/en/stable/quickstart.html)는 assume과 assert, 반례 추적을 사용하는 기본 흐름을 설명한다. 중재기에 적용할 때에는 “한 번에 한 요청만 수락한다”는 안전성부터, “지속 요청이 다른 성공한 거래를 몇 번 기다리는가”라는 진행 조건까지 구분해 표현하는 편이 좋다.

처음의 회전 포인터는 시각적으로 공평했지만, 서비스 기회가 오는 에지와 잘못 맞물렸다. 라운드로빈 중재를 평가할 때에는 **수락 이후 갱신, 지속 요청, 하류 진행, 서비스 단위**를 함께 확인해야 한다. 이 네 조건이 명확해야 순환이라는 이름이 실제로 기다림의 끝을 보장할 수 있다.