원형 버퍼
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
원형 버퍼는 포인터와 정수를 사용하여 구현되는 자료 구조로, 고정된 크기의 배열을 순환적으로 사용하여 데이터를 저장하고 관리한다. 데이터의 입출력을 효율적으로 처리하며, FIFO(선입선출) 버퍼, 큐, 덮어쓰기 등 다양한 방식으로 활용된다. 멀티미디어, 생산자-소비자 문제, 데이터 압축, 통신, 임베디드 시스템, 운영체제 등 여러 분야에서 사용되며, 특히 대한민국에서는 온라인 게임, 디지털 방송, 스마트폰 등에서 데이터 처리 효율을 높이는 데 기여한다. 핑퐁 버퍼 및 바이파티트 버퍼와 유사한 개념이다.
더 읽어볼만한 페이지
- 배열 - 할바흐 배열
할바흐 배열은 특정 면에 자기장을 집중시키고 다른 면에서는 상쇄시키는 배열로, 자장 격리에 유용하며 다양한 산업 및 첨단 기술 분야에 응용된다. - 배열 - 경계 검사
경계 검사는 변수나 배열 인덱스가 특정 범위 내에 있는지 확인하여 산술 오버플로 방지 및 배열 경계 초과 접근을 막는 과정으로, 소프트웨어 및 하드웨어적으로 지원되며 그 중요성이 강조되었다. - 컴퓨터 메모리 - 플래시 메모리
플래시 메모리는 전기적으로 데이터의 쓰기 및 삭제가 가능한 비휘발성 메모리 기술로, 마스오카 후지오 박사가 발명하여 카메라 플래시와 유사한 소거 방식으로 인해 명명되었으며, NOR형과 NAND형으로 나뉘어 각기 다른 분야에 적용된다. - 컴퓨터 메모리 - 메모리 계층 구조
메모리 계층 구조는 CPU 데이터 접근 속도 향상을 위해 레지스터, 캐시, RAM, 보조 기억 장치 등으로 구성되며, 속도, 용량, 비용이 다른 계층들을 통해 효율적인 메모리 관리를 가능하게 한다.
| 원형 버퍼 | |
|---|---|
| 개요 | |
| 자료 구조 | 자료 구조 |
| 종류 | 큐 |
| 다른 이름 | 환형 큐, 순환 버퍼 |
| 작동 방식 | |
| 정의 | 고정 크기의 버퍼처럼 작동하며, 끝에 도달하면 시작 부분으로 돌아가 데이터를 덮어쓰는 방식 |
| 사용 | 데이터 스트림 처리에 유용하며, 버퍼가 가득 찰 때까지 데이터가 기록되고, 버퍼가 가득 차면 가장 오래된 데이터를 새 데이터로 덮어씀. |
| 장점 | 고정 크기이므로 메모리 관리가 용이함 데이터를 읽고 쓰는 데 일정한 시간 복잡도를 가짐 |
| 단점 | 버퍼 오버플로가 발생할 수 있으므로, 버퍼 크기를 신중하게 결정해야 함 |
| 활용 분야 | |
| 스트리밍 미디어 | 오디오 및 비디오 데이터를 효율적으로 처리 |
| 통신 시스템 | 데이터 패킷을 안정적으로 전송 |
| 실시간 시스템 | 센서 데이터를 빠르게 처리 |
| 구현 | |
| 방식 | 배열 또는 연결 리스트로 구현 가능 |
| 주의 사항 | 읽기 및 쓰기 포인터를 관리하고, 버퍼 오버플로 및 언더플로를 방지해야 함 |
2. 동작 원리
원형 버퍼는 선입선출(FIFO) 방식으로 동작하며, 데이터 입력(쓰기) 및 출력(읽기) 시 포인터가 이동하는 방식으로 작동한다.
원형 버퍼는 배열을 기반으로 하지만, 물리적인 링 형태가 아닌 논리적인 링 형태로 동작한다. 이를 위해 인덱스(첨자)를 버퍼 크기로 나누어 나머지를 구하는 정규화를 수행하여, 인덱스가 범위를 벗어나지 않도록 한다. 정규화 덕분에 인덱스가 버퍼의 마지막을 넘어서면 처음으로 돌아가고, 버퍼의 처음보다 앞으로 가면 마지막으로 이동한다.
대부분의 프로세서 명령어 집합 아키텍처에서 정수 나머지 연산은 느리기 때문에, 실제로는 버퍼 크기를 2의 멱으로 설정하고, `N-1`과의 비트별 논리곱을 통해 정규화를 수행하는 경우가 많다. 이는 컴파일러에 의해 자동으로 수행되기도 한다. 하지만 메모리 제약이 있는 경우에는 버퍼 크기를 조절하거나, 조건 분기를 통해 정규화를 수행하기도 한다.
링 버퍼의 인덱스는 잉여류의 개념으로 설명할 수 있다.
원형 버퍼의 동작 예시는 다음과 같다.
- 빈 버퍼에 1을 입력한다. (시작 위치는 중요하지 않다.)
- 2와 3을 추가로 입력한다.
- 1과 2를 출력하면 3만 남는다.
- 버퍼 크기가 7이므로, 7개의 원소를 입력하면 꽉 찬다.
- 가득 찬 상태에서 A와 B를 추가 입력하면, 가장 오래된 3과 4를 덮어쓴다.
- 데이터 덮어쓰기를 방지하려면 오류를 반환하거나 예외를 발생시킬 수 있다.
- 5와 6을 제거하면, A와 B가 남는다.
2. 1. 기본 구조
원형 버퍼는 다음과 같은 4가지 요소로 구성된다.[4]- 고정된 크기의 배열
- 배열의 크기
- 제일 처음 입력된 데이터의 위치 (읽기 포인터)
- 마지막으로 입력된 데이터의 위치 (쓰기 포인터)
마지막으로 입력된 데이터의 위치 대신, 입력된 데이터의 개수를 저장하기도 한다.
원형 버퍼는 처음에 비어 있으며 설정된 길이를 갖는다.
원형 버퍼 중앙에 1이 기록되었다고 가정하면 다음과 같다. (원형 버퍼에서 정확한 시작 위치는 중요하지 않다.)
그 후, 원형 버퍼에 2와 3이 추가되어 1 다음에 배치되면 다음과 같다.
두 개의 요소가 제거되면, 원형 버퍼 내에서 가장 오래된 두 값인 1과 2가 제거된다. 원형 버퍼는 선입선출(FIFO) 논리를 사용하므로, 버퍼에는 3만 남는다.
버퍼에 7개의 요소가 있으면 가득 찬 상태이다.
원형 버퍼의 속성은 가득 찼을 때 후속 쓰기가 수행되면 가장 오래된 데이터를 덮어쓰기 시작한다는 것이다. 현재 예에서 A와 B가 추가되면 3과 4를 덮어쓴다.
데이터 덮어쓰기 여부는 버퍼 루틴 또는 원형 버퍼를 사용하는 응용 프로그램의 의미 체계에 따라 달라진다. 덮어쓰기를 방지하고 오류를 반환하거나 예외를 발생시킬 수도 있다.
마지막으로, 두 개의 요소를 제거하면 3과 4 (또는 현재 A와 B)가 아니라, 5와 6이 제거된다. 5와 6이 이제 가장 오래된 요소이기 때문이다.
원형 버퍼는 포인터와 세 개의 정수를 사용하여 구현할 수 있다.[4]
- 메모리 내 버퍼 시작 주소
- 버퍼 용량 (길이)
- 버퍼 쓰기 인덱스 (끝)
- 버퍼 읽기 인덱스 (시작)
처음에는 인덱스 끝과 시작이 0으로 설정된다. 원형 버퍼 쓰기 연산은 끝 인덱스 위치에 요소를 쓰고, 끝 인덱스는 다음 버퍼 위치로 증가한다. 원형 버퍼 읽기 연산은 시작 인덱스 위치에서 요소를 읽고, 시작 인덱스는 다음 버퍼 위치로 증가한다.
시작 및 끝 인덱스만으로는 버퍼가 꽉 찼는지 또는 비어 있는지 구별하기에 충분하지 않다.[5] 하지만 버퍼의 최대 사용 크기가 길이 − 1인 경우 가능하다.[6] 이 경우 시작 및 끝 인덱스가 같으면 버퍼가 비어 있고, 사용 중인 크기가 길이 − 1이면 꽉 찬 것이다. 또 다른 해결책은 쓰기 연산에서 증가하고 읽기 연산에서 감소하는 다른 정수 카운트를 갖는 것이다. 그러면 비어 있는지 확인하는 것은 카운트가 0인지 테스트하는 것을 의미하고, 꽉 찼는지 확인하는 것은 카운트가 길이와 같은지 테스트하는 것을 의미한다.[7]
다음은 C로 구현된 원형 버퍼의 예시이다.
#include
enum { N = 10 }; // 원형 버퍼의 크기
int buffer [N]; // 참고: 주어진 시간에 (N - 1)개의 요소만 저장할 수 있습니다.
int writeIndx = 0;
int readIndx = 0;
int put (int item)
{
if ((writeIndx + 1) % N == readIndx)
{
// 버퍼가 가득 찼으므로 오버플로를 방지합니다.
return 0;
}
buffer[writeIndx] = item;
writeIndx = (writeIndx + 1) % N;
return 1;
}
int get (int * value)
{
if (readIndx == writeIndx)
{
// 버퍼가 비어 있습니다.
return 0;
}
- value = buffer[readIndx];
readIndx = (readIndx + 1) % N;
return 1;
}
int main ()
{
// 원형 버퍼 테스트
int value = 1001;
while (put (value ++));
while (get (& value))
printf ("read %d\n", value);
return 0;
}
버퍼는 메모리 공간 효율이 높은 배열을 사용하여 구현되지만, 배열을 물리적으로 링 형태로 배치할 수는 없다. 따라서 인덱스(첨자)를 버퍼 크기로 나누어 나머지를 구하는 정규화를 수행하여 일정한 범위로 제한함으로써, 직선 형태의 버퍼 양 끝을 논리적으로 연결한다. 정규화를 통해 인덱스가 버퍼의 마지막을 넘어서면 처음으로 돌아가고, 음수가 적절하게 처리되어 있다면 버퍼의 처음보다 앞으로 가면 마지막으로 진행된다.
정규화는 나머지 연산을 사용하지만, 대부분의 프로세서 명령어 집합 아키텍처에서는 정수 나머지 연산이 나눗셈과 마찬가지로 느리다. 실제로는 버퍼 크기 `N`을 2의 멱으로 올리고, `N-1`과의 비트별 논리곱을 구하는 경우가 많다. 소스 코드상에서는 나머지로 되어 있어도, 현재의 컴파일러는 2의 멱에서의 나머지를 자동으로 비트별 논리곱으로 최적화한다. 단, 버퍼 크기를 늘리면 여분의 메모리가 필요하므로, 메모리 사용량 제약이 강할 때는 버퍼 크기를 어중간한 상태로 유지하고, 일반적인 방법으로 나머지를 구하거나, 버퍼의 끝에 도달했는지 여부로 조건 분기를 사용한다. 하지만 매우 많은 양의 인덱스 계산을 반복하는 경우가 아니라면 오버헤드는 미미하다.
배열의 인덱스가 "0 오리진"(배열의 첫 번째 요소의 인덱스가 0)인 경우, "1 오리진" 등 배열의 첫 번째 요소의 인덱스가 0이 아닌 경우에는 0 오리진의 인덱스로 환산하여 정규화해야 한다.
링 버퍼의 인덱스는 수론적으로 잉여류를 이룬다.
2. 2. 동작 예시
빈 원형 버퍼에 1이 입력되었다고 가정한다. (정확한 시작 위치는 원형 버퍼에서 중요하지 않다.)
추가로 2와 3이 입력되면 3개의 원소를 갖는 원형 버퍼가 된다.
여기서 두 개의 원소가 출력되면, 1과 2가 제거되고 3만 남는다.
이 버퍼의 크기는 7이므로, 7개의 원소가 입력되면 꽉 차게 된다.
원형 버퍼의 속성상 가득 찬 상태에서 추가 입력이 발생하면, 가장 오래된 데이터를 덮어쓰기 시작한다. 현재 예시에서 A와 B 두 개의 원소가 추가되면 3과 4를 덮어쓰게 된다.
데이터 덮어쓰기를 방지하기 위해 오류를 반환하거나 예외를 발생시킬 수도 있다. 데이터 덮어쓰기 여부는 버퍼 루틴이나 원형 버퍼를 사용하는 응용 프로그램의 설정에 따라 달라진다.
마지막으로, 두 개의 원소를 제거하면 3과 4 (또는 A와 B)가 아닌, 5와 6이 제거된다. 5와 6이 가장 오래된 원소이기 때문이다.
3. 구현
원형 버퍼는 고정된 크기의 배열과 함께, 다음 요소들을 사용하여 구현된다.[4]
- 배열의 크기
- 제일 처음 입력된 데이터의 위치 (시작 인덱스)
- 마지막으로 입력된 데이터의 위치 (끝 인덱스)
마지막으로 입력된 데이터의 위치 대신, 입력된 데이터의 개수를 저장하기도 한다.
시작 및 끝 인덱스만으로는 버퍼가 꽉 찼는지 또는 비어 있는지 구별하기 어렵다.[5] 단, 버퍼의 최대 사용 크기를 '길이 - 1'로 설정하면 시작 및 끝 인덱스가 같을 때 버퍼가 비어 있고, 사용 중인 크기가 '길이 - 1'이면 꽉 찬 것으로 판단할 수 있다.[6]
다른 방법으로는 쓰기 연산에서 증가하고 읽기 연산에서 감소하는 별도의 정수 카운트를 사용할 수 있다.[7] 이 경우 카운트가 0이면 버퍼가 비어 있고, 카운트가 길이와 같으면 꽉 찬 것으로 판단한다.
원형 버퍼는 메모리 공간 효율이 높은 배열을 사용하지만, 물리적으로 링 형태로 배치할 수는 없다. 대신, 인덱스를 버퍼 크기로 나눈 나머지를 구하는 정규화를 통해 인덱스를 일정 범위로 제한하여 버퍼의 양 끝을 논리적으로 연결한다.
정규화는 주로 나머지 연산을 사용하지만, 일부 프로세서에서는 정수 나머지 연산이 느릴 수 있어, 버퍼 크기를 2의 멱으로 설정하고 비트 연산을 통해 최적화를 수행하기도 한다. 하지만 이 경우 추가적인 메모리가 필요할 수 있다.
3. 1. 구현 방식
원형 버퍼는 포인터와 세 개의 정수를 사용하여 구현할 수 있다.[4]- 메모리 내 버퍼 시작 주소
- 버퍼 용량 (길이)
- 버퍼 쓰기 인덱스 (끝)
- 버퍼 읽기 인덱스 (시작)
처음에는 끝과 시작 인덱스가 모두 0으로 설정된다. 원형 버퍼 쓰기 연산은 끝 인덱스 위치에 요소를 쓰고, 끝 인덱스는 다음 버퍼 위치로 증가한다. 원형 버퍼 읽기 연산은 시작 인덱스 위치에서 요소를 읽고, 시작 인덱스는 다음 버퍼 위치로 증가한다.
시작 및 끝 인덱스만으로는 버퍼가 꽉 찼는지 또는 비어 있는지 구별하기에 충분하지 않다.[5] 버퍼의 최대 사용 크기가 길이 - 1인 경우는 예외이다.[6] 이 경우 시작 및 끝 인덱스가 같으면 버퍼가 비어 있고, 사용 중인 크기가 길이 - 1이면 꽉 찬 것이다. 다른 해결책으로는 쓰기 연산에서 증가하고 읽기 연산에서 감소하는 별도의 정수 카운트를 사용하는 방법이 있다. 이 경우 카운트가 0이면 버퍼가 비어 있는 것이고, 카운트가 길이와 같으면 꽉 찬 것이다.[7]
다음은 C로 구현된 원형 버퍼의 예시이다. `put()` 함수는 버퍼에 항목을 추가하고, `get()` 함수는 버퍼에서 항목을 가져온다. 두 함수 모두 버퍼의 용량을 고려한다.
#include
enum { N = 10 }; // 원형 버퍼의 크기
int buffer [N]; // 참고: 주어진 시간에 (N - 1)개의 요소만 저장할 수 있습니다.
int writeIndx = 0;
int readIndx = 0;
int put (int item)
{
if ((writeIndx + 1) % N == readIndx)
{
// 버퍼가 가득 찼으므로 오버플로를 방지합니다.
return 0;
}
buffer[writeIndx] = item;
writeIndx = (writeIndx + 1) % N;
return 1;
}
int get (int * value)
{
if (readIndx == writeIndx)
{
// 버퍼가 비어 있습니다.
return 0;
}
- value = buffer[readIndx];
readIndx = (readIndx + 1) % N;
return 1;
}
int main ()
{
// 원형 버퍼 테스트
int value = 1001;
while (put (value ++));
while (get (& value))
printf ("read %d\n", value);
return 0;
}
원형 버퍼 구현은 기본 버퍼를 두 개의 연속된 가상 메모리 영역에 매핑하여 최적화할 수 있다.[8] 이 경우 기본 버퍼의 길이는 시스템의 페이지 크기의 배수여야 한다. 원형 버퍼에서 읽고 쓰는 작업은 직접 메모리 접근을 통해 더 효율적으로 수행될 수 있으며, 첫 번째 가상 메모리 영역의 끝을 넘어가는 접근은 자동으로 기본 버퍼의 시작 부분으로 래핑된다. 읽기 오프셋이 두 번째 가상 메모리 영역으로 이동하면, 읽기 및 쓰기 오프셋은 기본 버퍼의 길이만큼 감소한다.
원형 버퍼의 일부 구현에서는 8비트 바이트보다 큰 고정 길이 요소를 사용한다. 예를 들어 오디오 버퍼의 경우 16비트 정수, 통신 버퍼의 경우 53바이트 ATM 셀 등을 사용한다. 각 항목은 연속적이며 올바른 데이터 정렬을 가지므로, 이러한 값을 읽고 쓰는 소프트웨어는 연속적이지 않고 정렬되지 않은 값을 처리하는 소프트웨어보다 빠를 수 있다.
핑퐁 버퍼는 정확히 두 개의 큰 고정 길이 요소를 가진 매우 특수한 원형 버퍼로 간주할 수 있다.
''바이파티트 버퍼''(bip buffer, 이분 버퍼)는 원형 버퍼와 매우 유사하지만, 항상 가변 길이의 연속 블록을 반환한다는 차이점이 있다. 이는 원형 버퍼의 효율성 이점을 대부분 제공하면서도, 연속 블록만 허용하는 API에서 버퍼를 사용할 수 있게 해준다.[9]
고정 크기 압축 원형 버퍼는 전체 데이터 시퀀스의 고정 크기 압축 표현을 유지하기 위해 초등 정수론을 기반으로 하는 대체 인덱싱 전략을 사용한다.[10]
버퍼는 일반적으로 메모리 공간 효율이 높은 배열을 사용하여 구현되지만, 배열을 물리적으로 링 형태로 배치할 수는 없다. 따라서 인덱스(첨자)를 버퍼 크기로 나누어 나머지를 구하는 정규화를 수행하여, 인덱스를 일정한 범위로 제한한다. 이를 통해 직선 형태의 버퍼 양 끝을 논리적으로 연결한다. 정규화를 통해 인덱스가 버퍼의 마지막을 넘어서면 처음으로 돌아가고, 음수가 적절하게 처리된다면 버퍼의 처음보다 앞으로 가면 마지막으로 진행된다.
정규화는 나머지 연산을 통해 이루어지지만, 대부분의 프로세서 명령어 집합 아키텍처에서는 정수 나머지 연산이 나눗셈과 마찬가지로 느리다. 따라서 실제로는 버퍼 크기 `N`을 2의 멱으로 설정하고, `N-1`과의 비트별 논리곱을 구하는 경우가 많다. 소스 코드 상에서는 나머지 연산으로 표현되어 있더라도, 최신 컴파일러는 2의 멱수에 대한 나머지 연산을 자동으로 비트별 논리곱으로 최적화한다. 단, 버퍼 크기를 2의 멱수로 설정하면 여분의 메모리가 필요하다. 따라서 메모리 사용량 제약이 강한 경우에는 버퍼 크기를 적절한 값으로 유지하고, 일반적인 방법으로 나머지 연산을 수행하거나, 버퍼의 끝에 도달했는지 여부를 조건 분기를 통해 확인한다. 하지만 매우 많은 양의 인덱스 계산을 반복하는 경우가 아니라면, 이러한 오버헤드는 미미하다.
위의 설명은 배열의 인덱스가 "0 오리진"(배열의 첫 번째 요소의 인덱스가 0)인 경우를 가정한 것이다. "1 오리진"과 같이 배열의 첫 번째 요소의 인덱스가 0이 아닌 경우에는, 0 오리진 인덱스로 환산하여 정규화해야 한다.
링 버퍼의 인덱스는 수론적으로 잉여류를 이룬다.
3. 2. 구현 시 고려 사항
원형 버퍼는 포인터와 세 개의 정수를 사용하여 구현할 수 있다.[4]- 메모리 내 버퍼 시작 주소
- 버퍼 용량 (길이)
- 버퍼 쓰기 인덱스 (끝)
- 버퍼 읽기 인덱스 (시작)
처음에는 쓰기 인덱스와 읽기 인덱스가 0으로 설정된다. 원형 버퍼 쓰기 연산은 쓰기 인덱스 위치에 요소를 쓰고, 쓰기 인덱스는 다음 버퍼 위치로 증가한다. 원형 버퍼 읽기 연산은 읽기 인덱스 위치에서 요소를 읽고, 읽기 인덱스는 다음 버퍼 위치로 증가한다.
시작 및 끝 인덱스만으로는 버퍼가 꽉 찼는지 또는 비어 있는지 구별하기에 충분하지 않다.[5] 하지만 버퍼의 최대 사용 크기가 길이 - 1인 경우 가능하다.[6] 이 경우 시작 및 끝 인덱스가 같으면 버퍼가 비어 있고, 사용 중인 크기가 길이 - 1이면 꽉 찬 것이다.
또 다른 해결책은 쓰기 연산에서 증가하고 읽기 연산에서 감소하는 정수 카운트를 사용하는 것이다. 이 경우 카운트가 0이면 버퍼가 비어있는 것이고, 카운트가 길이와 같으면 꽉 찬 것이다.[7]
버퍼는 일반적으로 메모리 공간 효율이 높은 배열을 사용하여 구현되지만, 배열을 물리적으로 링 형태로 배치할 수는 없다. 따라서 인덱스를 버퍼 크기로 나누어 나머지를 구하는 정규화를 수행하여 일정한 범위로 제한함으로써, 직선 형태의 버퍼 양 끝을 논리적으로 연결한다. 정규화를 통해 인덱스가 버퍼의 마지막을 넘어서면 처음으로 돌아가고, 음수가 적절하게 처리되어 있다면 버퍼의 처음보다 앞으로 가면 마지막으로 진행된다.
정규화는 나머지 연산을 통해 이루어지지만, 대부분의 프로세서 명령어 집합 아키텍처에서는 정수 나머지 연산이 나눗셈과 마찬가지로 느리다. 따라서 실제로는 버퍼 크기 `N`을 2의 멱으로 설정하고, `N-1`과의 비트별 논리곱을 구하는 경우가 많다. 단, 버퍼 크기를 2의 멱으로 설정하면 여분의 메모리가 필요하므로, 메모리 사용량 제약이 강할 때는 버퍼 크기를 2의 멱이 아닌 값으로 유지하고 일반적인 방법으로 나머지를 구하거나, 버퍼의 끝에 도달했는지 여부로 조건 분기를 사용한다. 하지만 매우 많은 양의 인덱스 계산을 반복하는 경우가 아니라면, 이러한 오버헤드는 미미하다.
링 버퍼의 인덱스는 수론적으로 잉여류를 이룬다.
4. 활용
원형 버퍼는 요소가 소모될 때 요소를 섞을 필요가 없어 FIFO(선입선출) 버퍼로 적합하며, 표준 비원형 버퍼는 LIFO(후입선출) 버퍼로 적합하다는 유용한 속성을 가진다.
원형 버퍼링은 고정된 최대 크기를 갖는 큐에 대한 훌륭한 구현 전략이다. 모든 큐 연산이 상수 시간이므로 최대 크기가 정해진 큐에는 원형 버퍼가 이상적이다. 그러나 원형 버퍼를 확장하려면 메모리 이동이 필요하며, 이는 상대적으로 비용이 많이 든다. 임의로 확장되는 큐의 경우, 연결 리스트 접근 방식이 선호될 수 있다.
멀티미디어와 같은 일부 상황에서는 원형 버퍼를 덮어쓰는 것이 사용될 수 있다.
4. 1. 주요 활용 분야
생산자-소비자 문제에서 경계 버퍼로 원형 버퍼가 사용될 수 있다. 생산자(예: 오디오 생성기)가 소비자(예: 사운드 카드)보다 빨라 오래된 데이터를 덮어쓰는 경우가 발생할 수 있다. 무손실 데이터 압축 알고리즘인 LZ77은 데이터 스트림에서 최근에 관찰된 문자열이 다시 나타날 가능성이 높다는 가정하에, 최신 데이터를 원형 버퍼에 저장한다.2024년 1월 현재, 동영상이나 음악 재생 시 버퍼링을 위해 원형 버퍼가 자주 사용된다. 쓰기와 읽기 위치가 충돌할 수 있으며, 스트리밍에서 버퍼 축적이 재생보다 늦어지면 버퍼 대기가 발생한다.
5. 대한민국 내 구체적 활용 사례
대한민국에서는 온라인 게임, 디지털 방송, 스마트폰 등 다양한 분야에서 원형 버퍼가 활용되고 있다.
6. 유사 개념
- '''큐''': FIFO (선입선출) 방식으로 동작하는 자료 구조이다. 원형 버퍼는 큐의 특수한 형태이며, 모든 큐 연산이 상수 시간으로 이루어지므로 고정된 최대 크기를 갖는 큐 구현에 매우 적합하다.[9]
- '''이중 버퍼 (Double Buffering)''': 직접적인 언급은 없지만, 핑퐁 버퍼가 이중 버퍼의 일종으로 언급된다.
- '''핑퐁 버퍼''': 두 개의 큰 고정 길이 요소를 가진 매우 특수한 원형 버퍼이다.[9]
- '''바이파티트 버퍼 (Bipartite buffer)''': 원형 버퍼와 매우 유사하지만, 항상 가변 길이의 연속 블록을 반환한다. 원형 버퍼의 효율성 이점을 대부분 제공하면서도, 연속 블록만 허용하는 API에서 버퍼를 사용할 수 있게 해준다.[9]
참조
[1]
간행물
Operating Systems: Three Easy Pieces [Chapter: Condition Variables, figure 30.13]
http://pages.cs.wisc[...]
Arpaci-Dusseau Books
2014
[2]
웹사이트
Impulswiederholer - Telephone Exchange (video)
https://www.youtube.[...]
Youtube
2021-12-15
[3]
웹사이트
US patent 3979733 Digital data communications system packet switch
https://patents.goog[...]
US States Patent
2021-12-15
[4]
서적
Wireless Algorithms, Systems, and Applications: 16th International Conference, WASA 2021, Nanjing, China, June 25–27, 2021, Proceedings, Part II
https://books.google[...]
Springer International Publishing
2023-09-04
[5]
웹사이트
Implementing Circular/Ring Buffer in Embedded C
https://embedjournal[...]
EmbedJournal Team
2014-05-16
[6]
문서
Circular buffers
https://www.kernel.o[...]
kernel.org
[7]
웹사이트
ArrayQueue: An Array-Based Queue
http://opendatastruc[...]
2015-11-07
[8]
웹사이트
mikeash.com: Friday Q&A 2012-02-17: Ring Buffers and Mirrored Memory: Part II
https://www.mikeash.[...]
2019-01-10
[9]
문서
The Bip Buffer - The Circular Buffer with a Twist
http://www.codeproje[...]
2003
[10]
논문
Algorithm 938: Compressing circular buffers
2014-03
[11]
웹사이트
リングバッファ（循環バッファ / 環状バッファ）とは - 意味をわかりやすく - IT用語辞典 e-Words
https://e-words.jp/w[...]
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com