Atomic Operation 으로 하는 동시성 제어

Test-And-Set (TAS)

TAS 를 이용해서 간단한 동시성 제어를 할 수 있다. testAndSet 이라는 function 을 가지고 아래의 do...while 문을 쓰레드 A, B 에서 동시에 호출한다고 해 보자. 이 때 lock 은 같은 변수이다.

function TestAndSet(boolean_ref lock) {
    boolean initial = lock
    lock = true
    return initial
}

do {
    while(TestAndSet(&lock))
        ; // do nothing
    // critical section
    lock = false;
    // remainder section
} while(true);

우선 TestAndSet() 은 다음과 같은 일을 한다. 말 그대로 ‘지금 값이 무엇인지 검사하고, 값을 바꾼다’ 는 것이다.

  1. lock의 현재 값을 저장해 둔다.
  2. lock의 값을 true 로 설정한다.
  3. 저장한 lock 의 값을 반환한다.

그럼 이걸로 어떻게 아래 block 의 critical section 에 대한 동시성 제어를 할 수 있을까? Thread A 가 먼저 실행했다고 가정하면, 이런 시나리오가 된다.

  1. A : TestAndSet() 의 반환값이 false 이다. while 문을 빠져나온다.
  2. B : TestAndSet() 의 반환값이 true 이다. (A가 true로 두고 나왔기 때문에) while 문에서 계속 돈다.
  3. A : Critical Section 수행 후, lock 을 false 로 바꾼다.
  4. B : 여러 번의 TestAndSet() 호출 후에, 드디어 반환값이 false 가 되었다
    (A가 false 로 두고 나왔기 때문에) while 문을 빠져나온다.

자, 그런데 뭔가 이상하다. 이렇게 이상적으로 동작하지 않을 것 같다. TestAndSet() 함수를 라인별로 동시에 실행한다고 하면 이런 사단이 날 수 있다.

  1. A : TestAndSet() 에 진입해 lock 값을 저장한다. 이 값은 false 이다.
  2. B : TestAndSet() 에 진입해 lock 값을 저장한다. 이 값은 false 이다.
  3. A : TestAndSet() 에서 lock 값을 true 로 바꾼다.
  4. B : TestAndSet() 에서 lock 값을 true 로 바꾼다.
  5. A : TestAndSet() 에서 저장한 값을 반환한다. 이 값은 false 이다.
  6. B : TestAndSet() 에서 저장한 값을 반환한다. 이 값은 false 이다.
  7. A & B : 모두 동시에 critical section 을 수행한다.

그럼 어떡하나? TestAndSet() 은 그래서 저런 함수만으로는 안 되고 Test-And-Set 의 연산이 일관되도록 조정해야 한다. 함수 안에 spinlock 을 쓰면 되겠네요? 싶겠지만 lock 구현하자고 lock 을 또 만드는 건 아닌 것 같다. 그래서 Test-And-Set 은 CPU에서 지원하는 Atomic Instruction 을 사용한다.

Fetch-And-Add : Ticket Lock

Atomic Operation 으로 구현할 수 있는 Lock 중에 Ticket Lock 이 있는데, Fetch-And-Add 로 구현할 수 있는 방법을 알아보자.

ticketLock_init(int *next_ticket, int *now_serving)
{
    *now_serving = *next_ticket = 0;
}

ticketLock_acquire(int *next_ticket, int *now_serving)
{
    my_ticket = fetch_and_inc(next_ticket);
    while(*now_serving != my_ticket) {}
}

ticketLock_release(int *now_serving)
{
    now_serving++;
}

TAS 의 케이스를 이해하고 본다면 별 다른 설명이 필요 없을 것 같다.

  1. Table Lock 초기화를 한다.
  2. A : Table Lock 을 얻으려 한다. 이미 얻었던 my_ticket (0) 과 now_serving (0) 이 같은 값이므로 곧바로 빠져나온다.
  3. B : Table Lock 을 얻으려 한다. 이미 얻었던 my_ticket (1) 과 now_serving (0) 이 다른 값이므로 while 문에서 대기한다.
  4. C : Table Lock 을 얻으려 한다. 이미 얻었던 my_ticket (2) 과 now_serving (0) 이 다른 값이므로 while 문에서 대기한다.
  5. A : Table Lock 을 해제한다. now_serving (0) 을 증가시켜 now_serving (1) 을 만든다.
  6. B : 비로소 Table Lock 을 얻었다. (C는 여전히 대기 중이다.)

여기서 핵심은 fetch_and_inc 인데, 마찬가지로 얻어오는 루틴과 값을 증가시키는 루틴이 따로 떨어져 있으면 중복된 티켓을 들고 기다리는 쓰레드들이 발생할 수 있다. 따라서 이것도 atomic operation 이 되어야 한다.

Timsort

학부에서 알고리즘 수업을 들으면, 가장 빠른 정렬 알고리즘이 뭐냐는 질문에 쉽게 Quicksort 라고 답할 수 있겠다. 실제로 현업에서도 적용하기 가장 편하기 때문에 많이 차용되는 편이다. 그런데 모든 문제를 쉽게 풀 수 있는 은탄은 세상에 존재하지 않듯, Quicksort 역시 특정 케이스에서는 성능이 낮게 나오는 경우가 있다. 더 심각한(?) 것은, 이 특정 케이스가 현실에서는 꽤나 자주 발생한다는 것이다.

그 케이스란 바로 ‘거의 정렬된 데이터’ 이다. 거의 정렬된 데이터라면 pivoting – partitioning 을 반복할 필요도 없이 Bubble Sort 나, 심지어는 Insertion Sort 를 해도 된다. Bubble Sort 의 경우엔 알고리즘 복잡도가 n이지만 compare 과정에서 조기에 끝날 가능성이 매우 높아 비용이 거의 발생하지 않을 것이고, Insertion Sort 도 비슷한 이유로 빠르게 끝날 것이다. 하지만 모든 정렬 케이스가 거의 정렬된 데이터만 있지 않기 때문에 쓰지 않는 것일 뿐이다.

만약에 데이터 순열이 ‘거의 정렬된 데이터의 N 벌’이라고 하자. 1, 2, 3, …, 10, 2, 3, 4, …, 20 이런 식으로 말이다. (여기서는 2벌) 그림을 그리자면 산이 N 개 생긴 것 처럼 보일 것이다. 이런 경우에는 Bubble Sort 가 큰 힘을 쓰지 못한다. 특정 원소가 산의 제 위치에 찾아가야 하는데, 조기에 끝났던 아까의 경우와는 달리 재수가 없다면 거의 모든 원소 개수와 비교해 봐야 하기 때문이다. 이럴 경우 역시 특효약이 있는데, 산마다 Mergesort 를 하면 쉽다.

오늘 이야기할 Timsort 는 Mergesort 의 변형이라고 보면 된다. 아까 ‘산마다 Mergesort’ 를 한다고 했는데, 어느 지점부터 산으로 봐야할지를 판단하는 알고리즘이 선행된다. 그리고 Mergesort 도 단순히 1개씩 건너뛰는 방법에서 좀 더 나은 방법을 제시한다.

결론부터 말하자면 Timsort 는 무작위 데이터에서 Quicksort 보다 뒤쳐진다. 프로젝트할 때 적용해 본 결과로는 30~50% 정도 느렸다. 하지만 말했다시피, 현실 데이터는 어느 정도 정렬된 데이터의 덩어리를 가지고 있는 경우가 매우 많기 때문에, 그 부분에서는 확실한 성능 차이를 보였다.

자, 이제 한 번 알아보자.

1단계 : Run

데이터 순열에서 이미 정렬이 끝난 부분 데이터들을 Run 이라고 한다. 1, 2, 1, 2, 3, 1, … 같이 주어졌을 때, 1, 2 와 1, 2, 3 을 Run 으로 인식하는 것이다. Timsort 에서는, 데이터 순열을 이런 Run 들로 찾거나 만들어서 확보하는 과정을 거친다. 이게 1단계이다.

Timsort 는 Run 이 너무 짧으면 나중에 의미가 없으므로, 최소 길이를 정해서 Run 을 만들도록 한다. 보통은 길이가 16인 Run 부터 의미있게 쓰길래, 나도 똑같이 16으로 조건을 설정했다.

Run 은 데이터 처음부터 정렬되어 있는 위치까지를 찾는다. 이 길이가 16 미만이라면, 해당 범위는 기억해 두고 다음 Run 을 찾는다. 이렇게 길이가 16 이상의 Run 을 만들 수 있는데, 이 때 쓰는 알고리즘은 사실 아무거나 가져다 써도 된다. 길이가 짧을 때의 정렬 알고리즘은 어느 것을 쓰나 대동소이하기 때문에, 나는 Insertion Sort를 썼다.

2단계 : Merge

1단계 이후로는, 이제 데이터 순열에 Run 여러개가 연속되어 있다. 만약 Run 이 1개뿐이라면? 축하한다. 아주 작은 원소 개수를 정렬하려 했거나, 이미 정렬된 데이터를 넣었단 것이니 이번 단계를 하지 않아도 된다.

앞의 두 Run 을 불러서 Mergesort 하면 되는데, 여기서 Timsort 만의 트릭이 두 개 존재한다.

하나는, Merge 에 참여할 두 Run 의 최소값/최대값을 서로 비교해서, 아예 이긴 구간이나 아예 진 구간을 미리 산정해 두는 것이다. 이 부분은 사실상 Mergesort 과정에서 비교 대상이 될 필요가 없다. 괜한 compare 연산만 낭비하지 말고 처음에 (혹은 나중에) 순순히 들어와주기만 하면 된다. 이 전처리 과정이 끝나면, 남아있는 Run 끼리 Merge 과정을 거친다.

두 번째는, Merge 과정에서 만약 한 쪽이 계속 이기는 상황 (오름차순 정렬이라고 가정했을 때, 한 쪽의 Run 이 계속 작은 원소를 가지고 있을 때) 라면 더 이상의 비교는 무의미하다. 이런 연속 위닝 회수를 정해서, 이후에는 ‘어디까지 이기는지 binary search 로 찾아서 한 번에 그냥 옮기자’ 라는 건너뛰기 모드 (galloping mode) 로 전환된다. 코드를 참조했을 땐, 이 위닝 회수는 3이었다. 스윕승?

건너뛰기 모드 (galloping mode) 에서는, 지고 있던 Run 의 첫 번째 원소가 이기고 있던 Run 의 어느 원소에서 비로소 이기는지를 찾는 것이다. 처음엔 한 칸, 다음엔 두 칸, 그 다음엔 네 칸씩 뛰며 이길 때 까지 찾는다. 그러다가 찾았다면, 직전 구간 사이를 Binary Search 를 통해 최초로 이긴 위치를 찾아내면 된다.

그 다음은? 이기고 있던 Run 의 처음부터 발견된 위치 직전까지를 통째로 memcpy 하면 된다.

마치며

이걸 구현할 때는 급한 나머지 그냥 구현했었는데, (물론 어딘가에선 하고 있겠지만) Mergesort 자체가 병렬 구현이 가능하므로 Timsort 역시 병렬 구현이 가능하리라 본다. Run 을 만드는 작업은 병렬로 할 수 있을까 고민이 되지만, Merge 과정은 작업 큐만으로도 쉽게 그려낼 수 있다.

역시 이것도 만병통치약이 될 수 없다. 상황에 맞춰 적절히 섞어써야 한다. 이런 정렬 알고리즘도 있구나 하며 배웠던 소중한 기회로 여기고 있다.

정리는 비움으로, 그리고 마음부터

마음이 붕.

몸은 여기 있는데, 어디로 가고 있는지조차 모를 정도로 격랑(激浪)에 떠밀려 가는 것처럼.

조각난 지식들은 어딘가에 있겠지만, 약에 쓰려고 하면 개똥도 찾을 수 없는 것 처럼 내 단편의 끄적임을 찾기 힘들 때마다 드는 생각이 있다. 이걸 전부 모아뒀다면. 다짐은 용오름처럼 솟구치지만 이내 잠잠한 바다 속으로 꺼져버린다. 정리할 시간이 없진 않았을 텐데, 하면서.

정리와 분류는 결국 데이터를 다루는 사람, 데이터 소프트웨어를 만드는 개발자 둘 모두에게 있어 경쟁력이자 기본이라고 생각한다. 어떻게 효율적으로 정리를 할 것인지 매번 고민한다. 사무실에서도, 집에서도, 혼자 스탠드등에 앉아 있으면서도. 정리해 두면, 잘 꺼내 쓸 수 있을거란 기대가 있으니까. 이 때 또 물어본다. 정말 꺼내 쓸만한 것들인지는 확인해 보았느냐고. 설마 폐지를 정리하려 드는 것은 아닐까 하고. 그래서 정리에는 비움이 필요하다.

지금 이 생각에도 비움이 필요하다. 마음 속에 부는 바람줄을 하나씩 잠재워야 한다. 초가 타지 않도록, 그나마 따뜻한 이 믿음이 꺼지지 않도록. 이걸 먼저 정리해야겠다. 그래야 지금 앉아있는 곳으로 마음이 돌아올테니까.