이 문서의 저작권은 GPL 라이센스를 따릅니다(This document is released under the GPL license).
=========
원형 버퍼
=========
작성: David Howells <dhowells@redhat.com>
Paul E. McKenney <paulmck@linux.vnet.ibm.com>
번역: 양정석 <dasomoli@gmailREMOVETHIS.com>
리눅스는 원형 버퍼를 구현하는데 사용할 수 있는 많은 기능을 제공합니다.
다음의 두가지 셋이 있습니다:
(1) 2의 거듭제곱 크기의 버퍼에 대한 정보를 결정하기 위한 편리한 함수들
(2) 버퍼 안의 객체의 생산자와 소비자가 하나의 락(lock)을 공유하지 않기를
원할 때를 위한 메모리 장벽
이들 기능을 사용하기 위해서, 아래에서 논의되는 것처럼, 적어도 하나의 생산자와
하나의 소비자가 있어야 합니다. 여러 생산자를 처리하는 것도 그들을 연속적으로
일렬로 늘어놓는 것으로, 여러 소비자를 처리하는 것도 그들을 연속적으로 일렬로
늘어놓는 것으로써 처리 가능합니다.
내용:
(*) 원형 버퍼가 뭔가요?
(*) 2의 거듭제곱 버퍼 측정.
(*) 원형 버퍼와 함께 메모리 장벽 사용하기
– 생산자.
– 소비자.
===================
원형 버퍼가 뭔가요?
===================
가장 먼저, 원형 버퍼가 뭘까요? 원형 버퍼는 그 안에 두가지 인덱스가 있는 유한한
크기의 고정된 버퍼입니다:
(1) ‘헤드(head)’ 인덱스 – 생산자가 항목을 버퍼로 집어넣는 곳
(2) ‘테일(tail)’ 인덱스 – 소비자가 다음 항목을 버퍼에서 찾는 곳
일반적으로 테일 포인터가 헤드 포인터와 같을 때, 그 버퍼는 빈 것입니다; 그리고 그
버퍼는 헤드 포인터가 테일 포인터보다 하나 작을 때, 가득 찬 것입니다.
헤드 인덱스는 아이템들이 추가될 때, 테일 인덱스는 아이템들이 제거될 때 증가합니다.
테일 인덱스는 헤드 인덱스를 절대로 넘어설 수 없고, 두 인덱스 모두 그들이 버퍼의
끝에 다다랐을 때, 0으로 다시 돌아와야 합니다. 그래서 무한한 양의 데이터가
그 버퍼를 통해 흐를 수 있습니다.
일반적으로 항목들은 모두 같은 단위 크기이지만, 아래 테크닉을 사용하는 것이
엄격하게 요구되지는 않습니다. 인덱스들은 여러 항목이나 가변 크기의 항목들이
두 인덱스 모두 다른 것을 추월하지 않도록 제공되는 그 버퍼 안으로 포함된다면,
1보다 더 많이 증가할 수 있습니다. 그러나 그 구현자는 한 단위 크기 이상의
한 부분은 버퍼의 끝을 돌 수 있고, 두 세그먼트로 쪼개질 수 있기 때문에 조심해야
합니다.
=======================
2의 거듭제곱 버퍼 측정
=======================
제멋대로인 크기의 원형 버퍼의 사용하거나 남아있는 양의 계산은 보통 나머지
(나누기) 명령의 사용을 필요로 하는 느린 동작이 됩니다. 그러나 버퍼가 2의
거듭제곱 크기라면, 훨씬 빠른 비트-앤드(bitwise-AND) 명령을 대신 사용할 수
있습니다.
리눅스는 2의 거듭 제곱 원형 버퍼를 처리하기 위한 매크로 셋을 제공합니다. 이들은
다음을 통해 사용할 수 있습니다:
#include <linux/circ_buf.h>
그 매크로들은:
(*) 버퍼의 남은 양 측정:
CIRC_SPACE(head_index, tail_index, buffer_size);
이것은 항목들이 넣어질 수 있는 그 버퍼[1] 안에 남은 공간의 양을 반환합니다.
(*) 버퍼 안에 최대로 연이어 붙어있는 공간 측정:
CIRC_SPACE_TO_END(head_index, tail_index, buffer_size);
이것은 항목들이 다시 그 버퍼의 처음으로 돌아가는 것 없이 즉시 삽입되어질
수 있는 그 버퍼[1] 안에 남은 연이은 공간의 양을 반환합니다.
(*) 버퍼의 사용량 측정:
CIRC_CNT(head_index, tail_index, buffer_size);
이것은 현재 버퍼[2]를 사용하는 항목 수를 반환합니다
(*) 처음으로 돌아가는 것이 없을 때(non-wrapping)의 버퍼 사용량 측정:
CIRC_CNT_TO_END(head_index, tail_index, buffer_size);
이것은 다시 그 버퍼의 처음으로 돌아가는 것 없이 뽑아 낼 수 있는 연이은
항목들[2]의 수를 반환합니다.
이들 매크로 각각은 명목상으로 0 에서 buffer_size-1 사이의 값을 반환할 것입니다.
그러나:
[1] CIRC_SPACE*() 들은 생산자 안에서 사용되도록 의도되었습니다. 생산자에게
그들은 생산자가 헤드 인덱스를 제어하기 때문에 하한값을 반환할 것입니다.
그러나 소비자는 여전히 다른 CPU 상에서 그 버퍼를 감소시키고, 테일 인덱스를
옮기고 있을 수 있습니다.
생산자가 그 공간을 바쁘게 감소시킬 수 있기 때문에, 소비자에게 그것은
상한값을 보여줄 것입니다.
[2] CIRC_CNT*() 들은 소비자 안에서 사용되도록 의도되었습니다. 소비자에게
그들은 소비자가 테일 인덱스를 제어하기 때문에 하한값을 반환할 것입니다.
그러나 생산자는 여전히 다른 CPU 상에서 그 버퍼를 채우고, 헤드 인덱스를
옮기고 있을 수 있습니다.
소비자가 그 버퍼를 바쁘게 비울 수 있기 때문에, 생산자에게 그것은 상한값을
보여줄 것입니다.
[3] 서드 파티에게는, 생산자와 소비자가 보여질 수 있게 되어감에 의해, 그
인덱스들에 쓰는 순서는 그들이 독립적이고, 다른 CPU 상에서 생성될 있기 때문에
보장될 수 없습니다. 그래서 이런 상황에서의 결과는 그저 추정이 될 것이고, 아예
틀릴 수도 있습니다.
=======================================
원형 버퍼와 함께 메모리 장벽 사용하기
=======================================
원형 버퍼와 함께 메모리 장벽을 사용함으로써, 여러분은 다음을 위한 욕구를
피할 수 있습니다.
(1) 그 버퍼의 양 끝으로의 접근을 다스리기 위한 단일 락(lock) 사용, 그래서
그 버퍼가 동시에 채우고 비울 수 있는; 그리고
(2) 어토믹(atomic) 카운터 연산 사용
이를 위한 두 편이 있습니다: 그 버퍼를 채우는 생산자, 그를 비우는 소비자.
어느 한번에 하나만 버퍼를 채워야 하고, 어느 한번에 하나만 버퍼를 비워야 합니다만,
두 편은 동시에 수행할 수 있습니다.
생산자
——
생산자는 이처럼 보일 것입니다:
spin_lock(&producer_lock);
unsigned long head = buffer->head;
unsigned long tail = ACCESS_ONCE(buffer->tail);
if (CIRC_SPACE(head, tail, buffer->size) >= 1) {
/* 버퍼로 아이템 하나를 넣어라 */
struct item *item = buffer[head];
produce_item(item);
smp_wmb(); /* 헤드를 증가시키기 전에 항목을 넣어라 */
buffer->head = (head + 1) & (buffer->size – 1);
/* wake_up() 은 어느 하나가 깨기 전에 헤드가 제출됐음을 확인할
* 것이다 */
wake_up(consumer);
}
spin_unlock(&producer_lock);
이는 CPU가 새로운 항목의 내용을 헤드 인덱스가 소비자에게 사용가능하게 만들기
전에 반드시 쓰여져야 한다는 것을 지시할 것이고, 그 후 그 CPU가 소비자가 깨기
전에 바뀐 헤드 인덱스가 쓰여져야만 함을 지시합니다.
wake_up() 이 꼭 사용하는 그 메카니즘일 필요는 없지만, 만약 상태 변경이 일어난다면,
사용되는 아무 것이나 헤드 인덱스의 갱신과 소비자의 상태 변경 사이에 반드시 한번의
(쓰기) 메모리 장벽을 보장해야 함을 명심하세요.
소비자
——
소비자는 이처럼 보일 것입니다:
spin_lock(&consumer_lock);
unsigned long head = ACCESS_ONCE(buffer->head);
unsigned long tail = buffer->tail;
if (CIRC_CNT(head, tail, buffer->size) >= 1) {
/* 그 인덱스에 있는 내용을 읽기 전에 인덱스를 읽어라 */
smp_read_barrier_depends();
/* 버퍼로부터 하나의 항목을 꺼내라 */
struct item *item = buffer[tail];
consume_item(item);
smp_mb(); /* 테일을 증가시키기 전에 서술자 읽기를 끝내라 */
buffer->tail = (tail + 1) & (buffer->size – 1);
}
spin_unlock(&consumer_lock);
이는 CPU가 새로운 항목을 읽기 전에 그 인덱스가 올라갔음을 확인할 것을 지시할
것이고, 그 후 CPU가 그 항목을 지울 새로운 테일 포인터를 쓰기 전에 그 항목
읽기를 끝냈음을 확인하도록 합니다.
반대 인덱스를 읽기 위한 두 알고리듬 안에 ACCESS_ONCE() 의 사용에 주의하세요.
이것은 컴파일러가 그들의 캐시된 값-어떤 컴파일러는 smp_read_barrier_depends()를
가로질러 수행하는-을 버리고 재로딩하는 것을 막습니다. 여러분이 반대 인덱스가
한 번만 사용될 거라고 알 수 있다면, 이것이 엄격히 필요하지는 않습니다.
=============
더 읽을 거리
=============
리눅스의 메모리 장벽 기능에 대한 설명을 위해 Documentation/memory-barriers.txt도
보세요.