이번 달 초에 Dr. Dobb’s Journal (DDJ)을 보다가 multi-thread 용으로 구현된 흥미로운 링버퍼(ring buffer; circular buffer)에 관한 글을 발견(http://www.ddj.com/dept/architect/199902669)
간략히 설명하자면 기존의 링버퍼는 1개의 1차원 배열을 사용하고 여기의 양 끝에 각각 접근하는 consumer-producer modle을 사용했습니다. 각각은 이 1차원 배열에 접근해서 데이터를 추가하거나(producer part), 데이터를 꺼내가는(consumer part) 작업을 수행하는데 이 동작에 대해 1차원 배열을 접근하는 것을 동기화해서 (lock을 걸던 mutex를 쓰던), 1차원 배열이나 내부적인 book-keeping을 위한 포인터들이 오염되는 것을 막는다.
이 새로운 자료구조는 다음과 같은 방식을 사용해서 문제를 해결한다.
- 1개의 1차원 배열이 아니라 3개의 1차원 배열을 사용한다.
- 3개의 배열을 각각 W, R, F (write, read, free) 라고 명명하고,이 것들을 순서대로 순회하면서 상태를 변경하고 읽거나, 쓰거나 한다.
- Consumer 혹은 producer는 각각 서로 다른 1차원 배열만을 본다 (0, 1, 2번 배열 중 1개 씩;즉총 3개의 배열중 어느 한 순간에 사용되는 것은 최대 2개임)
- Synchronization primitive를 사용하지 않고 구현한다.
일단 이런 기본적인 가정을 가지고 각각의 배열은 추가적으로 사용 중 flag와 현재 들어있는 원소 수를 유지한다.
실제로 동작하는 방식은 각 개체 별로 나눠서 생각하면,
Producer (writer)
- 현재 사용 중인 버퍼 배열에 빈 공간이 있으면 쓴고, 현재 버퍼의 원소수 카운터 + 1
- 다음 버퍼 배열 ( 현재 버퍼 배열 번호 + 1 mod 3 )이 `Free’로 표시 되어 있으면(사용 중 flag가 false), 다음 버퍼 배열로 이동하고(사용 중 flag를 true로) 현재 버퍼 배열을 `Free’로 표시(사용 중 flag를 true로)
Consumer (reader)
- 현재 사용 중인 버퍼 배열에 읽을 원소가 있으면 읽고, 버퍼의 원소 수 카운터 – 1
- 현재 버퍼 배열의 원소 수 카운터가 0이고, 다음 버퍼 배열( 현재 버퍼 배열 번호 + 1 mod 3 )을 사용 중으로 체크하고 현재 버퍼 배열을 `Free’로 표시 (위에서도 그렇지만 동기화 방식을 쓰는 것이 없기 때문에 이 순서가 매우 중요하다)
이 알고리즘이 잘 도는 이유는,
- Reader/writer 는 한 순간에 하나의 버퍼 배열만을 사용하는데 이 것들이 서로 다른 것이 보장이되고,
- Writer가 하나의 배열에 계속 쓰는게 아니라 다음 배열이 Free가 되면 그쪽으로 바로 옮겨가서 현재 배열을 Reader가 쓰기 시작한다는 것 ( Reader가 직전 배열을 다 읽었는데 현재 배열로 넘어오는걸 기다리는 일이 생기지 않음)
- 알고리즘만 잘 살펴보면 메모리에 실제로 쓰이는 write순서는 약간 중요하지만 별도의 동기화 연산이 포함되지 않는 점
대충 이 정도인듯하다. 사실 배열말고 singly linked list같은걸 쓰면(예를 들어 Win32 api의 slist; interlocked-function 만으로 구현) 되긴하지만,이 쪽은 cache에 안 좋은 관계로 -_-;
다이어그램은 서울 올라가면 생길(?) 예정 (현재 휴가쓰고 고향집에 내려온 참)