FIFO의 empty, full과 동시 입출력

큐가 저장하는 것은 수락한 순서다

FIFO는 먼저 들어온 거래를 먼저 내보내는 저장 구조입니다. 읽기 포인터 rptr는 가장 오래된 항목, 쓰기 포인터 wptr는 다음 저장 위치를 가리킵니다. 둘의 값만 같아서는 empty와 full을 구분할 수 없으므로 이번 설계는 점유 수 count를 별도로 둡니다. 깊이 D=4이면 포인터는 2비트지만 count는 0~4를 표현해야 해 3비트가 필요합니다. 데이터뿐 아니라 tag도 같은 메모리 항목으로 저장합니다.

이 장의 FIFO는 빈 큐에서 입력을 출력으로 곧바로 통과시키지 않는 등록형 큐입니다. out-valid=count>0이고 pop=out-valid AND out-ready입니다. in-ready는 count<D OR pop으로 정합니다. 따라서 full이어도 기존 머리를 이번 에지에 배출하면 새 입력을 받을 수 있습니다. push=in-valid AND in-ready이며 다음 점유는 count+push-pop입니다. count를 두 개의 if에서 각각 증가·감소시키면 동시 입출력에서 한 대입이 다른 대입을 덮는 오류가 생길 수 있으므로 합친 식이나 네 경우 분기를 사용합니다.

첫 행에서 빈 큐는 out-valid=0이므로 소비자 ready=1이어도 pop이 없습니다. 새 입력의 첫 전달 기회는 다음 에지입니다. 마지막 행에서 큐 [A,B,C,D]는 A를 전달하고 E를 저장하여 [B,C,D,E]가 됩니다. count는 계속 4이며 읽기·쓰기 포인터는 각각 한 칸 이동합니다. 포인터가 같은 메모리 위치를 가리키는 full 상황에서 old A 읽기와 new E 쓰기의 실제 메모리 의미도 확인해야 합니다.

깊이가 2의 거듭제곱이면 포인터 하위 비트의 순환이 modulo D와 같습니다. D=3이면 2비트 포인터가 3까지 갈 수 있으므로 최종 유효 위치 2에서 0으로 돌아가는 명시적 wrap이 필요합니다. 깊이만 바꿔도 같은 코드가 정확하다고 가정하지 않습니다. full/empty의 동시 전이, 여러 바퀴 wrap, 마지막 한 항목의 pop, full에서의 교체를 각각 시험합니다.

버퍼가 평균 처리량을 마법처럼 늘리지는 않습니다. 입력이 매 사이클 1개이고 소비자가 5사이클 멈추면, 원래 비어 있는 D=4 큐는 처음 네 개만 수락하고 다섯째를 멈춰야 합니다. 생산자가 backpressure를 지킬 수 없으면 최소 다섯 칸의 여유 또는 다른 손실 정책이 필요합니다. 소비자가 계속 느리면 어떤 유한 FIFO도 결국 full이 됩니다. 버퍼는 제한된 burst 차이를 흡수하므로 필요한 깊이는 최대 누적 유입에서 누적 배출을 뺀 값으로 추정합니다.

가장 중요한 불변식은 0≤count≤D와 accepted-delivered=count입니다. 합계만으로 순서 바뀜은 잡지 못하므로 tag 큐도 확인합니다. 비어 있는 출력 데이터와 full에서 거절된 입력을 거래로 세지 않는 것이 버퍼 경계 테스트의 기준입니다.