원형 버퍼(环形缓冲区)는 전형적인 생산자-소비자(Producer-Consumer) 모델을 구현하는 자료구조입니다. 비유하자면, 생산자가 계속 물을 채우고 소비자가 물을 빼는 웅덩이와 같습니다.

여기서 의문이 생길 수 있습니다. "생산자와 소비자 사이에 왜 굳이 버퍼 메모리 공간을 두는가? 생산자의 파이프 끝을 소비자의 파이프 시작 부분에 직접 연결하면 공간을 절약할 수 있지 않은가?"

이 방식은 작동하지 않습니다. 생산자가 물을 생산하는 속도와 소비자가 물을 소비하는 속도를 알 수 없기 때문입니다. 두 속도가 강제로 맞춰지면 속도 차이로 인해 파이프가 터질 위험이 있습니다.

오디오 시스템 프레임워크(예: ALSA)는 원형 큐를 사용하며, 생산자와 소비자 속도가 맞지 않을 때 xrun 문제가 발생합니다.

원형 큐의 특징

1. 배열 기반 원형 버퍼

배열로 원형 버퍼를 구성하려면 다음 세 가지 요소가 필요합니다:

• 읽기 위치(R)
• 쓰기 위치(W)
• 버퍼 길이(Len)

초기 상태에서 R과 W는 배열의 시작 주소(인덱스 0)를 가리킵니다.

• 버퍼가 비었는지 확인: R == W 이면 비어 있음
• 버퍼가 가득 찼는지 확인: (W - R) == Len 이면 가득 참

2. 데이터 3개 쓰기

데이터 3개를 쓰면 W = 3, R = 0 이 됩니다.

3. 데이터 2개 읽기

데이터 2개를 읽으면 R = 2, W = 3 (변화 없음) 입니다.

4. 데이터 3개 추가 쓰기

W가 Len을 초과하면, 실제 데이터를 넣을 위치는 W % Len 연산으로 구합니다. 예를 들어, Len=5일 때 W=6이면 6 % 5 = 1 인덱스에 데이터를 저장합니다.

5. 데이터 1개 더 쓰기 (버퍼 가득 참)

이 시점에서 (W - R) == Len 이므로 버퍼가 가득 차서 더 이상 쓸 수 없습니다.

C 언어 코드 구현

다음은 가장 기본적인 원형 큐 구현 예제입니다.

#include <stdio.h>
#include <stdlib.h>

#define BUFFER_SIZE 10

/* 원형 큐 구조체 */
typedef struct {
    int data[BUFFER_SIZE];
    int write_pos;
    int read_pos;
} CircularQueue;

/* 큐 초기화 */
CircularQueue* queue_init(void) {
    CircularQueue *q = (CircularQueue*)malloc(sizeof(CircularQueue));
    if (q == NULL) {
        printf("메모리 할당 실패\n");
        return NULL;
    }
    q->write_pos = 0;
    q->read_pos = 0;
    return q;
}

/* 큐가 가득 찼는지 확인 */
int is_full(CircularQueue *q) {
    return ((q->write_pos - q->read_pos) == BUFFER_SIZE);
}

/* 큐가 비었는지 확인 */
int is_empty(CircularQueue *q) {
    return (q->write_pos == q->read_pos);
}

/* 데이터 추가 (enqueue) */
int enqueue(CircularQueue *q, int value) {
    if (q == NULL) return -1;
    if (is_full(q)) {
        printf("큐가 가득 참\n");
        return -2;
    }
    q->data[q->write_pos % BUFFER_SIZE] = value;
    q->write_pos++;
    return 0;
}

/* 데이터 추출 (dequeue) */
int dequeue(CircularQueue *q) {
    if (q == NULL) return -1;
    if (is_empty(q)) {
        printf("큐가 비어 있음\n");
        return -2;
    }
    int value = q->data[q->read_pos % BUFFER_SIZE];
    q->read_pos++;
    return value;
}

/* 큐 메모리 해제 */
void queue_destroy(CircularQueue *q) {
    if (q == NULL) return;
    free(q);
}

int main() {
    CircularQueue *q = queue_init();
    
    /* 데이터 10개 쓰기 */
    for (int i = 0; i < 10; i++) {
        enqueue(q, i);
    }
    
    /* 데이터 10개 읽기 */
    for (int i = 0; i < 10; i++) {
        printf("%d ", dequeue(q));
    }
    printf("\n");
    
    queue_destroy(q);
    return 0;
}

최적화된 버전 (비트 연산 활용)

버퍼 크기가 2의 거듭제곱일 때, 모듈로 연산(%) 대신 비트 AND(&) 연산을 사용할 수 있습니다. 이는 연산 속도를 높입니다.

#include <stdio.h>
#include <stdlib.h>

#define BUFFER_SIZE 64  /* 2의 거듭제곱 */
#define INDEX_MASK (BUFFER_SIZE - 1)

typedef struct {
    int data[BUFFER_SIZE];
    int write_pos;
    int read_pos;
} FastQueue;

FastQueue* fast_queue_init(void) {
    FastQueue *q = (FastQueue*)malloc(sizeof(FastQueue));
    if (q == NULL) {
        printf("메모리 할당 실패\n");
        return NULL;
    }
    q->write_pos = 0;
    q->read_pos = 0;
    return q;
}

int fast_is_full(FastQueue *q) {
    return ((q->write_pos - q->read_pos) == BUFFER_SIZE);
}

int fast_is_empty(FastQueue *q) {
    return (q->write_pos == q->read_pos);
}

int fast_enqueue(FastQueue *q, int value) {
    if (q == NULL) return -1;
    if (fast_is_full(q)) {
        printf("큐가 가득 참\n");
        return -2;
    }
    q->data[q->write_pos & INDEX_MASK] = value;
    q->write_pos++;
    return 0;
}

int fast_dequeue(FastQueue *q) {
    if (q == NULL) return -1;
    if (fast_is_empty(q)) {
        printf("큐가 비어 있음\n");
        return -2;
    }
    int value = q->data[q->read_pos & INDEX_MASK];
    q->read_pos++;
    return value;
}

void fast_queue_destroy(FastQueue *q) {
    if (q == NULL) return;
    free(q);
}

요약

원형 큐는 오디오 데이터 처리, 네트워크 패킷 버퍼링, 임베디드 시스템 등 다양한 분야에서 널리 사용됩니다. 위 예제는 기본적인 동작 원리를 설명하며, 실제 프로젝트에서는 더 복잡한 조건(멀티스레드 안전성, 동적 크기 조정 등)을 고려해야 합니다. 이 기본 구조를 이해하면 실제 개발에 응용할 수 있습니다.