답변.

질문의 역사

링 버퍼(링크 버퍼, 순환 버퍼)는 제한된 메모리의 시스템, 장치 드라이버, 네트워크 및 다중 작업 시스템에서 자주 사용됩니다. 이 개념은 운영 체제 개발 초기 단계에서도 사용되었으며, 메모리를 최적화하여 추출 후 요소를 이동하는 데 리소스를 쓰지 않는 것이 중요했습니다.

문제

전형적인 복잡성은 "버퍼가 가득 참" 및 "버퍼가 비어 있음" 조건을 올바르게 처리하는 것과 데이터 덮어쓸 수 없도록 보호가 없는 것, 다중 스레드에서의 동기화가 복잡해지는 것입니다. 경계 혼동과 인덱스 검사의 잘못된 확인으로 오류가 발생할 수 있습니다.

해결책

링 버퍼 객체는 배열, 두 개의 인덱스(head 및 tail) 및 필요한 경우 상태를 구분하기 위한 카운터 변수 또는 추가 로직으로 구현됩니다. 읽기 및 쓰기는 버퍼 크기 모듈을 따라 수행됩니다.

#define BUF_SIZE 8
char buffer[BUF_SIZE];
int head = 0, tail = 0; // head - 쓰기, tail - 읽기

// 쓰기
if (((head + 1) % BUF_SIZE) != tail) {
    buffer[head] = data;
    head = (head + 1) % BUF_SIZE;
} else {
    // 버퍼가 가득 찼습니다.
}

// 읽기
if (head != tail) {
    char d = buffer[tail];
    tail = (tail + 1) % BUF_SIZE;
}

주요 특징:

모듈 작업을 사용하여 경계를 확인합니다.
빈 버퍼와 가득 찬 버퍼를 구분하기 위한 특별한 처리나 요소 수를 저장해야 합니다.
동적 메모리 할당 없이 쉽게 구현할 수 있습니다.

질문의 함정.

완전히 채워진 버퍼와 완전히 비어 있는 버퍼를 어떻게 구분할 수 있습니까?

head == tail을 사용하여 빈 버퍼를 자주 구별합니다. 가득 찼음을 확인하기 위해서는 빈 공간 하나를 남기거나 요소 수를 별도로 세는 방법을 사용합니다.

잠금 없이 다중 스레드 환경에서 버퍼를 사용할 수 있습니까?

아니요. 동시에 읽기 및 쓰기를 할 때 경쟁 상태가 발생할 수 있습니다. 원자적 작업이나 잠금을 사용해야 합니다.

head 또는 tail의 오버플로우를 제어하지 않으면 어떻게 됩니까?

오버플로우가 발생하면 배열의 경계를 초과하여 정의되지 않은 동작이 발생하고 메모리 손상이 발생할 수 있습니다.

전형적인 오류 및 안티 패턴

"가득 차 있음"과 "비어 있음"을 구분하지 않아서 작업의 의미가 깨짐 (head == tail)
모듈러 산술을 포기하여 인덱스 계산 오류 발생
다중 스레드 작업 시 동기화 위반

실제 사례

부정적인 사례

개발자는 head == tail을 "비어 있음"과 "가득 참"으로 동시에 해석하는 링 버퍼를 구현하여 오버플로우 신호를 잃어버렸습니다.

장점:

코드 간단함

단점:

가득 찬 상태와 비어 있는 상태를 명확히 구분할 수 없으며, 데이터가 손실되거나 덮여졌습니다.

긍정적인 사례

대신 요소 수를 셀 카운터 변수를 추가하거나 하나의 슬롯을 예약하여 head가 절대 tail과 완전히 일치하지 않도록 했습니다.