[OS] Lock을 사용하여 Concurrency를 지원하는 자료구조 만들기 - OS 공부 20

안녕하세요 Pingu입니다.

 

지난 글에서는 Concurrency(동시성)을 구현할 때 필요한 mutual exclusion(상호 배제)을 구현하기 위한 lock이라는 개념에 대해 알아봤습니다. 이번 글에서는 지난번에 알아본 lock을 사용하여 queue, linked list, hash table 등의 자료구조에서 여러 개의 스레드가 동시에 접근하더라도 문제가 없도록 하는 방법에 대해 알아볼 예정입니다. 제가 공부할 때 참고하고 있는 OSTEP 책에서는 Chapter 29 - Locked Data Structure 입니다!

Lock-based Concurrent Data Structures

자료구조에 여러개의여러 개의 스레드가 동시에 접근한다면 어떻게 될까요? 예를 들어 배열의 경우 특정 인덱스에 여러 개의 스레드가 동시에 접근해서 값을 바꿔버린다면 원하는 값을 저장할 수 없을거에요. 따라서 여러개의 스레드를 사용한다면 자료구조에 스레드로 부터 안전하도록 해줘야하는데요, 이를 lock을 사용해서 해보려고합니다. 자료구조는 값이 하나만 있는게 아닌 여러개 있기 때문에 적절한 위치에 lock을 사용해야 성능과 정확도를 모두 만족시킬 수 있습니다. 그럼 어떻게 자료구조를 thread safety 하게 만들 수 있는지 알아보도록 하겠습니다!

Concurrent Counters

우선 간단한 자료구조로 lock을 사용하여 thread safety 하게 만들어 보겠습니다.

typedef struct counter_t {
    int value;
} counter_t;

void init(counter_t *c) {
    c->value = 0;
}

void increment(counter_t *c) {
    c->value++;
}

void decrement(counter_t *c) {
    c->value--;
}

int get(counter_t *c) {
    return c->value;
}

위와 같은 코드를 살펴보겠습니다. 위의 코드는 counter라는 구조체를 하나 만들고 구조체 안에 변수를 정수형으로 하나 만들어 그 값을 더하거나 빼는 함수들 만들어둔 코드입니다. 이 코드의 함수들과 구조체를 그대로 사용하면 어떻게 될까요? 원하는 값으로 value값이 변화할까요?

counter_t counter;

// counter 값을 1씩 10000번 더합니다
void *plusCounter(void *arg) {
    printf("plus begin\n");
    for (int i=0; i < 10000; i++) {
        increment(&counter);
    }
    return NULL;
}

// counter 값을 1씩 10000번 뺍니다
void *minusCounter(void *arg) {
    printf("minus begin\n");
    for (int i=0; i < 10000; i++) {
        decrement(&counter);
    }
    return NULL;
}
int main() {
    pthread_t p1,p2;
    init(&counter);
    printf("main : begin (counter = %d)\n",counter.value);
    pthread_create(&p1, NULL, plusCounter, "A");
    pthread_create(&p2, NULL, minusCounter, "B");

    pthread_join(p1,NULL);
    pthread_join(p2,NULL);

    printf("counter's value : %d\n", get(&counter));
}

위와 같이 스레드 1개는 1을 10000번 더하는 작업을 다른 스레드 1개는 1을 10000번 빼는 작업을 수행합니다. 각각 만 번씩 수행하니까 결과는 0이 나와야 하지만 실제로 수행하면 값이 할 때마다 변하는 것을 볼 수 있습니다.

이와 같은 값이 나오는 이유는 우선 임계 영역에 대한 mutual exclusion을 고려하지 않았기 때문에 어떤 스레드가 임계 영역에 접근하고 있더라도 다른 스레드가 접근할 수 있기 때문에 정확한 값이 보장이 되지 않는 것입니다. 따라서 이를 원하는 값이 나오도록 하기 위해선 lock, unlock을 사용하여 아래와 같이 수정하여 원자성을 보장해줘야 합니다.

typedef struct counter_t {
    int value;
    pthread_mutex_t lock;
} counter_t;

void init(counter_t *c) {
    c->value = 0;
    pthread_mutex_init(&c-> lock, NULL);
}

void increment(counter_t *c) {
    pthread_mutex_lock(&c->lock);
    c->value++;
    pthread_mutex_unlock(&c->lock);
}

void decrement(counter_t *c) {
    pthread_mutex_lock(&c->lock);
    c->value--;
    pthread_mutex_unlock(&c->lock);
}

int get(counter_t *c) {
    pthread_mutex_lock(&c->lock);
    int rc = c->value;
    pthread_mutex_unlock(&c->lock);
    return rc;
}

위와 같이 value 값에 접근할 때마다 lock, unlock 함수를 사용하여 상호 배제를 구현해줘야 임계 영역인 value 값에 하나의 스레드만 접근이 보장되며 원하는 값을 얻을 수 있습니다. 위와 같이 수정한 뒤 코드를 실행한 결과는 아래와 같습니다.

원하는 값인 0이 잘 나오는 것을 알 수 있습니다. 이렇게 lock, unlock을 활용하여 자료구조들을 thread safety 하게 만들 수 있습니다.

 

lock, unlock을 사용하는 데에도 자원이 드는데, 이 때문에 스레드를 1개만 사용할 때가 2개를 사용할 때보다 더 빠른 현상이 발생합니다. 이는 하나의 스레드일 때는 lock, unlock을 처리하는 게 더 쉽기 때문인데, 이러한 점 때문에 스레드가 증가할수록 성능이 나빠집니다. 하지만 성능이 좋아지기 위해 스레드를 사용하는데, 오히려 나빠진다면 다른 방법을 찾아야 할 것 같습니다. 스레드가 여러 개가 되더라도 성능 저하가 발생하지 않도록 해줘야 하는데, 이를 달성하는 것을 perfect scaling이라고 합니다.

 

lock을 사용할 때 스레드가 증가하면 성능이 나빠지는 문제를 해결하기 위해 approximate counter(근사 카운터)라는 아이디어가 도입되었습니다. 근사 카운터는 CPU 코어 당 하나의 local 카운터가 있고 전체적으로 공유하는 하나의 global 카운터를 갖도록 하는 아이디어입니다. 각 코어마다 존재하는 하나의 local 카운터에 값을 증가시키다가 일정 값에 가까워지면 이를 global 카운터에 더하는 아이디어입니다.

위의 그래프가 근사 카운터를 수행하는 과정인데, 우선 위의 예에서는 local 카운터가 5가 될 때마다 global 카운터에 더해줍니다. 여기서 global값에 더해질 때의 local 카운터의 값을 임계 값이라고 하며 임계값이 작을수록 아까 발생한 문제와 비슷한 상황이 됩니다. 이는 당연하겠지만 lock, unlock을 호출하는 빈도수가 증가하기 때문이죠. 그렇다고 임계값을 너무 크게 만들면 global 값에 원하는 값과 거리가 먼 값이 저장될 수 있습니다.

근사 카운터를 사용하는걸 C언어 코드로 나타내면 위와 같습니다. 그럼 이렇게 하여 카운트를 한다면 성능은 얼마나 향상될까요?

위의 그래프는 임계값을 1024로 한 근사 카운터를 사용했을 때의 성능과 아무것도 없이 lock을 적용한 예에서의 성능 차이를 그린 그래프입니다. 근사 카운터를 사용한 시스템은 스레드가 늘어나더라도 성능 차이가 없는데 비해 사용하지 않은 시스템은 스레드가 증가할수록 성능이 나빠지는 것을 볼 수 있습니다.

위의 그래프는 임계값과 성능의 차이를 보기 위한 그래프로 임계값이 커질수록 성능이 좋아지는 것을 볼 수 있습니다.

Concurrent Linked Lists

간단한 자료구조에 대해 멀티 스레드 시스템에서 lock의 필요성과 lock에 의한 성능 저하를 해결하는 방법을 알아봤으니 이젠 좀 더 복잡한 자료구조인 linked list에 대해 살펴보도록 하겠습니다.

위와 코드는 lock을 적용한 linked list 코드입니다. Insert, Lookup, 즉 삽입 함수와 탐색 함수가 존재하는 것도 알 수 있어요. 위 코드에서 삽입이 나타나는 과정을 그림으로 그려보겠습니다.

위와 같이 삽입 함수가 호출되면 head 포인터를 새로 삽입되는 노드를 가리키도록 만들어줘야 하고 삽입되는 노드의 next 포인터를 원래 존재하던 노드 중 마지막 노드를 가리키게 해줘야 합니다.

 

위의 코드에서 lock을 획득하고 해제하는 위치를 잘 보면 lock을 획득하는 곳은 하나인데 lock을 해제하는 곳은 두 군데입니다. 또한 lock을 획득하려는 곳이 함수의 시작인데 이렇게 되면 malloc()이 실패하는 경우 삽입에 실패하기 전에 잠금을 해제해야 하는데 이렇게 코드를 작성하면 오류가 발생하기 쉽습니다. 따라서 임계 영역에 접근할 때만 lock을 획득하는 게 좋은데 이를 수정한 코드가 아래와 같습니다.

이러한 linked list 역시 스레드 수가 늘어날 때 성능이 저하되는 것을 방지해야 하는데, 이를 방지하는 방법 중 하나는 hand over locking입니다. Hand over locking은 전체 리스트에 대한 lock을 사용하는 것이 아닌 리스트의 노드들에게 lock을 추가하는 방법입니다. 리스트를 순회할 때를 예를 들어보면 다음 노드의 lock을 획득한 뒤 현재 노드의 lock을 해제합니다.

 

이러한 hand over locking을 사용하면 list 작업 시 높은 수준의 동시성을 가능하게 합니다. 하지만 노드마다 lock이 존재하므로 이는 엄청난 오버헤드가 발생하는 게 당연한 결과겠죠?

Concurrent Queues

이번에는 유명한 자료구조인 큐에 lock을 사용하여 thread safety 하게 만들어보겠습니다.

큐에서 주의 깊게 볼 점은 lock이 2개라는 점입니다. 큐는 FIFO 구조를 갖는 자료구조로 앞, 뒤로 모두 데이터가 이동합니다. 즉 삽입을 위한 lock, 삭제를 위한 lock을 각각 사용하여 상호 배제를 구현하는 것이죠. 그런데 위와 같이 간단하게 만들어진 큐는 문제가 있습니다. 예를 들어 큐가 비어있거나, 데이터가 너무 많은 경우 스레드가 대기할 수 있도록 하는 bounded 큐는 다음 글에서 자세히 알아보도록 하겠습니다.

Concurrent Hash Tables

마지막으로 살펴볼 자료구조는 hash table입니다. 해시 테이블에 대한 lock을 구현한 코드는 아래와 같습니다.

해시 테이블은 아까 알아본 linked list에서 사용한 함수들을 사용하면 구현할 수 있는데요, 이는 동작하는 과정을 보면 이해하실 수 있습니다.

위의 그림이 해시 테이블이 동작하는 과정을 간단히 그려본 건데요, 일단 key값이 있고 이를 적절히 변환해주는 규칙에 따라 배열의 Index 값으로 바꿔줍니다. 이 배열을 bucket이라고 이름을 지었고 bucket에는 각각의 데이터를 가진 리스트를 가리키는 포인터가 있습니다. key 값들을 적절히 변환한다고 해도 위와 같이 같은 index가 나오는 경우가 있을 수 있는데 이러한 경우를 대비해 각 entries마다 또 링크드 리스트로 연결할 수 있게 포인터가 존재합니다. 즉 링크드 리스트가 여러 개 존재하는 자료구조가 해시 테이블이기 때문에 아까 알아본 함수들로 구현할 수 있는 것이죠.

이렇게 해시 테이블을 thread safety 하게 구현한 뒤 여러 스레드가 동시에 업데이트를 진행하는 작업을 수행하면 위와 같이 한 개의 lock을 사용하는 해시 테이블보다 성능이 훨씬 좋아지는 것을 볼 수 있습니다.

Summary

이번 글에서는 구조체, linked list, 큐, 해시 테이블에서 동시성 프로그래밍을 위해 lock을 도입하고 그 결과로 thread safety 하게 만드는 방법들에 대해 알아봤습니다. 여기서 알 수 있었던 것은 조건문과 같은 제어 흐름을 변경하는 곳에서는 lock의 사용을 주의해야 한다는 것과 동시성을 막무가내로 하는 것은 오히려 성능이 나빠진다는 것을 알게 되었습니다. 따라서 성능 향상을 위해 CPU 별로 다른 메모리를 활용한다거나 하는 방법들을 알아봤습니다. 다음 글에서는 동시성을 구현할 때 필요한 항목 중 synchronization(동기화)를 구현하기 위한 condition variables(조건 변수)에 대해 알아보도록 하겠습니다!

 

감사합니다.