순환 버퍼

Circular buffer
개념적으로 원형 버퍼를 나타내는 링입니다.이를 통해 버퍼에는 실제 엔드가 없으며 버퍼를 루프할 수 있음을 시각적으로 알 수 있습니다.다만, 메모리는 물리적으로 링으로서 작성되지 않기 때문에, 일반적으로 다음과 같이 선형 표현을 사용합니다.

컴퓨터 과학에서 순환 버퍼, 순환 큐, 순환 버퍼 또는 링 버퍼는 엔드 투 엔드로 연결된 것처럼 단일 고정 크기의 버퍼를 사용하는 데이터 구조입니다.이 구조는 데이터 [1]스트림을 쉽게 버퍼링할 수 있습니다.하드웨어에는 [2][3]초기 순환 버퍼 구현이 있었습니다.

개요

24바이트 키보드 순환 버퍼.마이크로프로세서가 응답하지 않기 때문에 쓰기 포인터가 읽기 포인터에 도달하려고 하면 버퍼는 키 입력을 정지합니다.컴퓨터에 따라서는 비프음이 울립니다.

원형 버퍼는 우선 빈 상태로 시작되며 길이가 설정됩니다.다음 그림은 7 요소 버퍼입니다.

Circular buffer - empty.svg

1이 원형 버퍼의 중앙에 쓰여 있다고 가정합니다(원형 버퍼의 정확한 시작 위치는 중요하지 않습니다).

Circular buffer - XX1XXXX.svg

다음으로 2개의 요소(2 & 3)가 순환 버퍼에 추가되어 1 뒤에 배치된다고 가정합니다.

Circular buffer - XX123XX.svg

2개의 요소가 삭제되면 순환 버퍼 내에서 가장 오래된2개의 값이 삭제됩니다.순환 버퍼는 FIFO(선입선출) 로직을 사용합니다.이 예에서는 1과 2가 순환 버퍼에 가장 먼저 들어가고 가장 먼저 제거되며 버퍼 내부에 3이 남습니다.

Circular buffer - XXXX3XX.svg

버퍼에 7개의 요소가 있는 경우 버퍼는 완전히 꽉 찼습니다.

Circular buffer - 6789345.svg

순환 버퍼의 속성은 버퍼가 가득 차 후속 쓰기가 수행되면 가장 오래된 데이터 덮어쓰기를 시작합니다.이 예에서는 A와 B라는2개의 요소가 추가되어 3과 4가 덮어씁니다.

Circular buffer - 6789AB5.svg

또는 버퍼를 관리하는 루틴으로 인해 데이터 덮어쓰기가 방지되어 오류가 반환되거나 예외가 발생할 수 있습니다.데이터 덮어쓰기 여부는 순환 버퍼를 사용하는 버퍼 루틴 또는 응용 프로그램의 의미에 따라 결정됩니다.

마지막으로, 2개의 요소가 제거되면 반환되는 것은 3&4가 아니라 5&6입니다.이는 A&B가 3&4를 오버프로트하여 버퍼를 생성하기 때문입니다.

Circular buffer - X789ABX.svg

사용하다

순환 버퍼의 유용한 특성은 소모될 때 요소를 이리저리 섞을 필요가 없다는 것입니다.(비원형 버퍼를 사용한 경우, 1개의 버퍼를 사용할 때 모든 요소를 이동시켜야 합니다.)즉, 순환 버퍼는 FIFO(선입선출) 버퍼로서 적합하며, 표준 비순환 버퍼는 LIFO(후입선출) 버퍼로서 적합하다.

순환 버퍼링은 최대 크기가 고정된 큐에 대해 적절한 구현 전략이 됩니다.큐에 최대 사이즈를 채용하고 있는 경우는 순환 버퍼가 이상적인 실장입니다.모든 큐 동작은 일정한 시간입니다.그러나 순환 버퍼를 확장하려면 메모리 이동이 필요하며, 이는 상대적으로 비용이 많이 듭니다.큐를 임의로 확장할 경우 링크드리스트 어프로치가 바람직할 수 있습니다.

상황에 따라서는, 예를 들면 멀티미디어에서, 써넣기 순환 버퍼를 사용할 수 있습니다.버퍼가 생산자-소비자 문제에서 경계 버퍼로 사용되는 경우, 소비자(사운드 카드 등)가 일시적으로 따라갈 수 없는 경우, 생산자(오디오 제너레이터 등)가 오래된 데이터를 덮어쓰는 것이 바람직할 수 있습니다.또한 LZ77 패밀리의 무손실 데이터 압축 알고리즘은 데이터 스트림에서 보다 최근에 발견된 문자열이 스트림에서 곧 발생할 가능성이 높다는 가정 하에 작동합니다.구현은 순환 버퍼에 최신 데이터를 저장합니다.

순환 버퍼 역학

하드웨어 순환 버퍼 구현, 미국 특허 3979733, 그림 4

순환 버퍼는 2개의 포인터와 2개의 정수를 사용하여 구현할 수 있습니다.

  • 메모리 버퍼 시작
  • 버퍼 용량(길이)
  • 버퍼 인덱스에 쓰기(끝)
  • 버퍼 인덱스에서 읽기(시작)

다음 이미지는 길이 = 7인 부분적으로 꽉 찬 버퍼를 보여 줍니다.

Circular buffer - XX123XX with pointers.svg

다음 이미지는 4개의 요소(번호1 ~ 4)가 덮어쓰기된 풀버퍼를 나타내고 있습니다.

Circular buffer - 6789AB5 with pointers.svg

처음에 인덱스가 종료되고 시작됨은 0으로 설정됩니다.순환 버퍼 쓰기 조작은 요소를 엔드 인덱스 위치에 쓰고 엔드 인덱스는 다음 버퍼 위치로 증분합니다.순환 버퍼 읽기 작업은 시작 인덱스 위치에서 요소를 읽고 시작 인덱스가 다음 버퍼 위치로 증가합니다.

그 시작과 끝 인덱스는 모든 버퍼 slots,[4]을 활용한 버퍼 또는 빈 완전한 국가 말할 수 있지만 버퍼만 길이-1.[5]의 이 경우 최대 사용 중 크기, 그 시작과 끝 인덱스 및 전체가 사용 중 크기는 길이-1. 또 다른 해결책 또 다른 정수가 있는 것이 동등한 버퍼가 비어 있을 수 있지 않았습니다.세어보세요이 값은 쓰기 작업에서는 증가하고 읽기 작업에서는 감소합니다.그런 다음 빈칸을 확인하는 것은 카운트가 0과 같음을 의미하며, 가득 찼음을 확인하는 것은 카운트가 [6]길이와 같음을 의미합니다.

다음 소스 코드는 C 구현입니다.function put()은 항목을 버퍼에 저장하고 function get()은 버퍼에서 항목을 가져옵니다.

열거하다 {N = 3}; 인트 부프[N];     // N 요소 순환 버퍼 인트 끝. = 0;    // 인덱스 쓰기 인트 개시하다 = 0;  // 인덱스 읽기  무효 놓다(인트 아이템) {   부프[끝.++] = 아이템;   끝. %= N; }  인트 얻다() {   인트 아이템 = 부프[개시하다++];   개시하다 %= N;   돌아가다 아이템; }

최적화

원형 버퍼 구현은 기본 버퍼를 가상 [7][disputed – discuss]메모리의 두 인접 영역에 매핑함으로써 최적화할 수 있습니다(기본 버퍼의 길이는 시스템 페이지 크기의 몇 배와 같아야 합니다).그 후 직접 메모리액세스를 통해 순환 버퍼에 대한 읽기 및 쓰기를 보다 효율적으로 수행할 수 있습니다.첫 번째 가상 메모리 영역의 끝을 초과하는 액세스는 기본 버퍼의 선두까지 자동으로 랩됩니다.읽기 오프셋이 두 번째 가상 메모리 영역으로 진행되면 읽기 및 쓰기 오프셋이 모두 기본 버퍼 길이만큼 감소합니다.

고정 길이 요소 및 연속 블록 순환 버퍼

순환 버퍼의 가장 일반적인 버전은 8비트 바이트를 요소로 사용합니다.

순환 버퍼의 일부 실장에서는 8비트바이트보다 큰 고정 길이 요소(오디오버퍼용 16비트 정수, 텔레콤버퍼용 53바이트 ATM 셀 등)가 사용됩니다.각 항목은 연속적이며 올바른 데이터 정렬을 가지고 있기 때문에 이러한 값의 읽기 및 쓰기는 비연속 및 비정렬 값을 처리하는 소프트웨어보다 빠를 수 있습니다.

ping-pong 버퍼링은 정확히 2개의 큰 고정 길이 요소를 가진 매우 특수한 원형 버퍼로 간주할 수 있습니다.

Bip 버퍼(Bipartite 버퍼)는 길이가 가변적인 연속 블록을 항상 반환한다는 점을 제외하고는 원형 버퍼와 매우 유사합니다.이를 통해 순환 버퍼의 거의 모든 효율성 이점을 제공하면서도 연속된 [8]블록만 받아들이는 API에서 버퍼를 사용할 수 있습니다.

고정 크기의 압축 원형 버퍼는 전체 데이터 [9]시퀀스의 고정 크기의 압축 표현을 유지하기 위해 기본 수 이론에 기초한 대체 색인 전략을 사용한다.

레퍼런스

  1. ^ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Operating Systems: Three Easy Pieces [Chapter: Condition Variables, figure 30.13] (PDF), Arpaci-Dusseau Books
  2. ^ Hartl, Johann. "Impulswiederholer - Telephone Exchange (video)". Youtube. Retrieved 15 December 2021.
  3. ^ Fraser, Alexander Gibson. "US patent 3979733 Digital data communications system packet switch". US States Patent. Retrieved 15 December 2021.
  4. ^ Chandrasekaran, Siddharth (2014-05-16). "Implementing Circular/Ring Buffer in Embedded C". Embed Journal. EmbedJournal Team. Archived from the original on 11 February 2017. Retrieved 14 August 2017.
  5. ^ https://www.kernel.org/doc/Documentation/circular-buffers.txt#:~:text=A%20circular%20buffer%20is%20a, next%20item%20in%20the%20buffer.
  6. ^ Morin, Pat. "ArrayQueue: An Array-Based Queue". Open Data Structures (in pseudocode). Archived from the original on 31 August 2015. Retrieved 7 November 2015.
  7. ^ Mike Ash (2012-02-17). "mikeash.com: Friday Q&A 2012-02-17: Ring Buffers and Mirrored Memory: Part II". mikeash.com. Archived from the original on 2019-01-11. Retrieved 2019-01-10.
  8. ^ Simon Cooke (2003), "더 Bip Buffer - 트위스트 포함 원형 버퍼" 웨이백 머신에 2012-10-06 아카이브됨
  9. ^ Gunther, John C. (March 2014). "Algorithm 938: Compressing circular buffers". ACM Transactions on Mathematical Software. 40 (2): 1–12. doi:10.1145/2559995. S2CID 14682572.

외부 링크