원형 버퍼
배열로 큐를 만들면 앞에서 꺼낼 때마다 문제가 생깁니다. 맨 앞 원소를 지우면 나머지를 한 칸씩 당겨야 해서 O(n)이 되고, 당기지 않고 앞쪽 칸을 비워 두면 뒤쪽 끝이 차서 앞쪽이 남아 있어도 더 쓸 수 없습니다. 원형 버퍼(circular buffer, ring buffer)는 고정 크기 배열의 끝과 처음을 이어 붙여 원처럼 쓰는 큐입니다. 읽을 위치(head)와 쓸 위치(tail) 두 인덱스만 움직이고 원소는 옮기지 않으므로 쓰기와 읽기가 모두 O(1)입니다.
인덱스가 배열 끝에 닿으면 나머지 연산(% 용량)으로 0으로 돌아가고, 읽혀서 비워진 앞쪽 칸이 다시 쓰입니다. 그래서 메모리가 처음 잡은 크기에서 늘지 않고, 실행 중에 메모리를 새로 할당하지 않아도 됩니다. 이 토픽에서는 head와 tail이 움직이는 모습, 끝에서 처음으로 돌아가는 순간, 그리고 head == tail이 비어 있음과 가득 참을 모두 뜻할 수 있는 문제를 단계별로 봅니다.
핵심 개념
head와 tail
head는 다음에 읽을 칸, tail은 다음에 쓸 칸입니다. 쓰면 tail이, 읽으면 head가 한 칸씩 앞으로 갑니다.
핵심 개념
고정 크기 배열
용량이 처음에 정해지고 늘어나지 않습니다. 크기가 일정해서 메모리를 예측할 수 있고 실행 중 할당이 필요 없습니다.
핵심 개념
나머지 연산으로 되감기
인덱스를 (i + 1) % 용량으로 올리면 마지막 칸 다음이 0번 칸이 됩니다. 이 한 줄이 배열의 끝과 처음을 이어 줍니다.
핵심 개념
비어 있음과 가득 참의 구분
head == tail은 비어 있을 때도, 가득 찼을 때도 성립합니다. 한 칸을 비워 두거나, 개수를 따로 세거나, 인덱스를 되감지 않고 세는 방법으로 구분합니다.
핵심 개념
가득 찼을 때의 정책
새 쓰기를 거부하거나 기다리게 할 수 있고, 가장 오래된 값을 덮어쓸 수도 있습니다. 어느 쪽을 고를지는 데이터를 잃어도 되는지에 달려 있습니다.
핵심 개념
2의 거듭제곱 용량
i가 0 이상이고 용량이 2의 거듭제곱이면 i % 용량을 i & (용량 - 1)이라는 비트 AND로 바꿀 수 있어 계산이 단순해집니다.
원형 버퍼의 배경
원형 버퍼는 생산자가 쓰는 속도와 소비자가 읽는 속도가 다를 때 둘 사이의 완충 지대로 쓰입니다. 크기가 고정이고 원소를 옮기지 않아서 장치 드라이버나 오디오 처리처럼 지연이 일정해야 하는 곳에 일반적으로 쓰입니다. 리눅스 커널 문서는 생산자와 소비자가 각각 하나일 때 양쪽 끝이 공유하는 하나의 락 없이, 메모리 배리어로 순서를 맞춰 쓰는 원형 버퍼 사용법을 따로 설명합니다. 커널의 CIRC_CNT와 CIRC_SPACE 매크로는 크기가 2의 거듭제곱인 버퍼를 전제로 합니다.
숫자로 확인하기
자주 하는 오해
면접에서 이렇게 물어요
면접 질문
원형 버퍼는 왜 쓰나요?
고정 크기 배열로 큐를 만들면서 쓰기와 읽기를 O(1)에 하기 위해서입니다. 원소를 옮기지 않고 인덱스만 움직이며, 읽혀서 빈 앞쪽 칸을 다시 써서 메모리를 낭비하지 않습니다.
면접 질문
가득 참과 빈 상태는 어떻게 구분하나요?
head == tail만으로는 구분할 수 없어서 칸 하나를 비워 두고 (tail + 1) % 용량 == head를 가득으로 보거나, 원소 개수를 따로 세거나, head와 tail을 되감지 않고 계속 증가시켜 tail - head로 개수를 구합니다(인덱스가 정수 한계를 넘어도 맞으려면 용량이 2의 거듭제곱이어야 합니다).
면접 질문
용량을 2의 거듭제곱으로 잡는 이유는?
i가 0 이상이면 i % 용량 대신 i & (용량 - 1)로 칸 번호를 구할 수 있어 나눗셈이 필요 없습니다. 용량 제한이 생기는 대신 계산이 단순합니다.
면접 질문
여러 스레드가 쓰려면 어떻게 하나요?
쓰는 쪽과 읽는 쪽이 하나씩이면 각자 자기 인덱스만 바꾸므로 락 없이 만들 수 있지만, 메모리 순서를 보장하는 장치가 필요합니다. 생산자나 소비자가 여럿이면 락이나 원자적 연산 등 별도의 동기화가 필요합니다.
실제 시스템에서는
함께 보면 좋은 토픽
참고 자료
Python — head와 tail로 만든 원형 버퍼 큐
from queue import Full class RingBuffer: def __init__(self, capacity): self.buf = [None] * capacity self.cap = capacity self.head = 0 # 읽을 위치 self.tail = 0 # 쓸 위치 self.size = 0 # 개수를 따로 센다 def enqueue(self, v): if self.size == self.cap: raise Full('buffer full') self.buf[self.tail] = v self.tail = (self.tail + 1) % self.cap # 끝에 닿으면 0으로 돌아간다 self.size += 1 def dequeue(self): if self.size == 0: raise IndexError('buffer empty') v = self.buf[self.head] self.buf[self.head] = None self.head = (self.head + 1) % self.cap self.size -= 1 return v rb = RingBuffer(4) for v in 'abc': rb.enqueue(v) print(rb.dequeue(), rb.dequeue(), rb.head, rb.tail, rb.size) # a b 2 3 1 rb.enqueue('d'); rb.enqueue('e'); rb.enqueue('f') print(rb.buf, rb.head, rb.tail, rb.size) # ['e', 'f', 'c', 'd'] 2 2 4 try: rb.enqueue('g') except Full as e: print(e) # buffer full print([rb.dequeue() for _ in range(4)]) # ['c', 'd', 'e', 'f']
원소를 옮기지 않고 head와 tail 두 인덱스만 움직입니다. enqueue는 tail 칸에 값을 쓰고 tail을 (tail + 1) % cap으로 한 칸 앞으로 보내고, dequeue는 head 칸의 값을 읽고 head를 같은 식으로 보냅니다. 둘 다 배열을 훑지 않으므로 O(1)입니다. 시각화의 쓰기와 읽기 탭이 보여 주는 동작과 같습니다. 용량 4에서 a, b, c를 넣고 a, b를 꺼내면 head는 2, tail은 3이고 원소는 1개입니다. 이어서 d, e, f를 넣으면 tail이 배열 끝(칸 3)을 지나 0으로 돌아와 e가 칸 0에, f가 칸 1에 쓰이고, 버퍼 배열은 ['e', 'f', 'c', 'd']가 됩니다. 이때 head와 tail이 모두 2로 같지만 원소가 4개인 가득 찬 상태입니다. head == tail만으로는 비어 있음과 가득 참을 구분할 수 없어서, 이 코드는 size를 따로 세어 판단합니다. 가득 찬 상태에서 enqueue하면 예외(여기서는 표준 라이브러리 queue의 Full)를 던지고, dequeue는 쓴 순서대로 c, d, e, f가 나옵니다. 배열 안에서는 순서가 돌아가 있어도 읽는 순서는 먼저 쓴 것이 먼저(FIFO)입니다.
Python — 가득 차면 가장 오래된 값을 덮어쓰는 버퍼
class OverwriteBuffer: def __init__(self, capacity): self.buf = [None] * capacity self.cap = capacity self.count = 0 # 지금까지 쓴 총 개수 def write(self, v): self.buf[self.count % self.cap] = v # 가장 오래된 값을 덮어쓴다 self.count += 1 def items(self): n = min(self.count, self.cap) start = (self.count - n) % self.cap return [self.buf[(start + i) % self.cap] for i in range(n)] ob = OverwriteBuffer(3) for i in range(1, 6): ob.write(i) print(ob.items()) # [3, 4, 5] from collections import deque dq = deque(maxlen=3) for i in range(1, 6): dq.append(i) print(list(dq)) # [3, 4, 5]
로그나 센서 값처럼 최근 n개만 필요한 경우에는 가득 찼을 때 쓰기를 거부하지 않고 가장 오래된 값을 덮어씁니다. 여기서는 읽는 쪽 인덱스를 따로 두지 않고 지금까지 쓴 총 개수 count 하나로 위치를 계산합니다. count % cap이 다음에 쓸 칸이고, 가득 찬 뒤에는 그 칸에 있던 가장 오래된 값을 새 값이 덮어씁니다. 용량 3에 1부터 5까지 쓰면 1과 2가 차례로 덮어써져 최근 값 [3, 4, 5]만 남습니다. items는 가장 오래된 값부터 읽기 위해 (count - n) % cap 칸에서 시작합니다. 파이썬 표준 라이브러리의 deque에 maxlen을 주면 같은 동작을 합니다. maxlen이 있는 deque는 가득 찬 상태에서 한쪽 끝에 항목을 추가할 때 반대쪽 끝의 항목을 버리므로, 위 직접 구현과 같은 [3, 4, 5]가 나옵니다.
Java — 용량을 2의 거듭제곱으로 잡고 나머지 연산을 비트 AND로 대신하기
static class Ring { private final int[] buf; private final int mask; private int head = 0; private int tail = 0; Ring(int capacityPowerOfTwo) { buf = new int[capacityPowerOfTwo]; mask = capacityPowerOfTwo - 1; } boolean offer(int v) { if (tail - head == buf.length) return false; // 가득 참 buf[tail & mask] = v; tail++; return true; } int poll() { if (tail == head) return -1; // 비어 있음 return buf[head++ & mask]; } } Ring r = new Ring(4); for (int i = 1; i <= 5; i++) System.out.print(r.offer(i) + " "); System.out.println(); // true true true true false System.out.println(r.poll() + " " + r.poll()); // 1 2 r.offer(6); r.offer(7); System.out.println(r.poll() + " " + r.poll() + " " + r.poll() + " " + r.poll()); // 3 4 6 7
i가 0 이상이고 용량이 2의 거듭제곱이면 i % cap과 i & (cap - 1)의 결과가 같아서, 나머지 연산 대신 보통 더 빠른 비트 AND 한 번으로 칸 번호를 구할 수 있습니다. 용량 4의 mask는 3(이진수 11)이고 7 & 3은 3입니다. 이 방식은 용량을 2의 거듭제곱으로 제한하는 대신 계산이 단순해집니다. 여기서는 head와 tail을 0으로 되돌리지 않고 계속 증가시킵니다. 인덱스가 int 범위를 넘어 음수가 되어도 용량이 2의 거듭제곱이라서 tail & mask와 tail - head가 계속 맞습니다. 원소 개수는 tail - head로 구하므로 size 변수가 따로 없고, tail - head가 0이면 비어 있고 용량과 같으면 가득 찬 것이라 head == tail의 모호함이 없습니다. 용량 4에 1부터 5를 넣으면 앞의 네 개만 들어가고 다섯 번째는 false입니다. 1, 2를 꺼낸 뒤 6, 7을 넣으면 6과 7이 칸 0과 1에 쓰이고, 남은 값을 꺼내면 쓴 순서대로 3, 4, 6, 7이 나옵니다.
Q1
원형 버퍼에서 head 또는 tail 인덱스를 한 칸 앞으로 옮길 때 쓰는 계산은?
Q2
원형 버퍼에서 head == tail 일 때 비어 있는지 가득 찼는지 구분하는 흔한 방법은?
Q3
원형 버퍼를 큐로 사용할 때의 장점은?