Spin buffer explained…

이번 달 초에 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
  2. 다음 버퍼 배열 ( 현재 버퍼 배열 번호 + 1 mod 3 )이 `Free’로 표시 되어 있으면(사용 중 flag가 false), 다음 버퍼 배열로 이동하고(사용 중 flag를 true로) 현재 버퍼 배열을 `Free’로 표시(사용 중 flag를 true로)

Consumer (reader)

  1. 현재 사용 중인 버퍼 배열에 읽을 원소가 있으면 읽고, 버퍼의 원소 수 카운터 – 1
  2. 현재 버퍼 배열의 원소 수 카운터가 0이고, 다음 버퍼 배열( 현재 버퍼 배열 번호 + 1 mod 3 )을 사용 중으로 체크하고 현재 버퍼 배열을 `Free’로 표시 (위에서도 그렇지만 동기화 방식을 쓰는 것이 없기 때문에 이 순서가 매우 중요하다)

이 알고리즘이 잘 도는 이유는,

  • Reader/writer 는 한 순간에 하나의 버퍼 배열만을 사용하는데 이 것들이 서로 다른 것이 보장이되고,
  • Writer가 하나의 배열에 계속 쓰는게 아니라 다음 배열이 Free가 되면 그쪽으로 바로 옮겨가서 현재 배열을 Reader가 쓰기 시작한다는 것 ( Reader가 직전 배열을 다 읽었는데 현재 배열로 넘어오는걸 기다리는 일이 생기지 않음)
  • 알고리즘만 잘 살펴보면 메모리에 실제로 쓰이는 write순서는 약간 중요하지만 별도의 동기화 연산이 포함되지 않는 점

대충 이 정도인듯하다. 사실 배열말고 singly linked list같은걸 쓰면(예를 들어 Win32 api의 slist; interlocked-function 만으로 구현) 되긴하지만,이 쪽은 cache에 안 좋은 관계로 -_-;

…다이어그램은 서울 올라가면 생길(?) 예정
(현재 휴가쓰고 고향집에 내려온 참)

ps. 다이어그램 그려야하는데 참 귀찮지 말입니다. (7/2)

Published by

rein

나는 ...

5 thoughts on “Spin buffer explained…”

  1. 졸업을 위해서 철학과 수업만 듣고, 군대 다녀왔더니 머리가 그냥 돌이 되었나 보다.

    저게 왜 동기화 기초가 필요 없는지 한참 생각 중…

    근본 전제를 잘못 이해 하고 있는건가 -0-

  2. Pingback: rein's world
  3. 처음 읽을 땐 뭐가 뭔지 아햏햏 하다가 오늘 다시 들어와서 보니 이해가 간다는(뭐냐)
    저렇게 RingBuffer 클래스 하나 만들어 두고 멀티스레드 프로그램에서 사용하면 참 좋을 듯?

  4. 괜찮긴 한데 단점도 없는 구조는 아니라서, 컨슈머 1; 프로듀서 1일 때만 락프리다.
    사실 저건 큐가 바틀넥일 때만이고 -_-;
    락 프리 프로그래밍의 세계는 복잡오묘 -,-

Leave a Reply