[OS] 29. Lock-based Concurrent Data Structures

급식·2022년 5월 28일
OS
1

OSTEP

목록 보기
21/24
post-thumbnail

지난 포스트에서 Lock은 무엇인지, 어떻게 구현하는지, 어떤 lock이 좋은 lock인지,, 등등 아주 자세히 lock에 대해 이것저것 뜯어 살펴보았다.

배우기만 하고 써먹을 줄 몰라서는 아무짝에도 쓸모가 없다! 이 좋은 lock을 어떻게 써먹을 수 있을까?
우리가 개발하면서 이래저래 많이 사용하는 Linked list, Queue, Hash table에 락을 추가함으로써 각각의 자료구조에 대한 연산을 thread-safe하게, 그러니까 동시에 공통 자원에 접근해도 문제가 없도록 보장하는 방법과 이를 최소한의 성능 저하로 실현하는 방법을 이번 장에서 공부할 것이다. 가보자 가보자!

29.1 Concurrent Counters

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, 말 그대로 정수값을 하나 저장해두고 값을 올리거나 내리는데 사용하는 자료 구조이다.
엥 그냥 ++이나 --하면 되는거 아녀? 싶지만 이 연산 자체가 atomic하지 않으므로 이전에 예제 코드로 살펴봤듯 여러 스레드가 동시에 이 작업을 수행하면 원하는 결과가 제대로 나오지 않는다.

Simple But Not Scalable

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;
}

이때 여기에 Lock을 끼얹어주면?! 비로소 thread-safe하여 동시에 여러 스레드가 접근해도 안전해진다.

여기서는 죄다 lock/unlock으로 원래 하려던 작업들을 critical section으로 만들어주었지만, lock/unlock 자체도 비용이 들어가는 연산이기 때문에 아무데서나 막 남발하면 안된다. 애초에 concurrency로 성능상의 이득을 보려고 탄생한게 multi-thread인데, 이걸 불필요하게 막 쓰면 이 이점을 그냥 걷어차버리는 것이다!

자료구조를 이해한다는 것은 각각의 연산에 들어가는 비용까지 이해하고 있다는 것이라 생각한다.
불필요하게 느려터진 자료구조를 누가 쓰겠는가!

위 그래프의 y축은 특정 횟수만큼 count를 올리는데 소요되는 시간을 의미하고, x축은 스레드의 갯수를 의미한다. 시간이 적게 들어야 좋은 거니까(병렬성의 이득을 보는거니까) y축의 값은 낮을수록 좋은 거겠지?

그러나 우리가 방금 구현한 방식(Precise, 왜 precise인지는 바로 뒤에서 볼 것이다)은 스레드가 늘어날 때마다 오히려 소요 시간이 훅훅 늘어나고 있다. 이런 상황을 scalability가 없다고 표현 하는데, 이는 말 그대로 스레드를 늘려봤자 시간이 그만큼 단축되는게 아니라 변함이 없거나 오히려 더 상황이 나빠지는 상황을 의미한다.

왜 저렇게 성능이 박살이 나있는지도 잠깐 생각해보자. 왜일까?
이는 Bottle neck, 그러니까 병목 현상이 발생하기 때문으로 요약할 수 있을 것 같다. counter의 값을 올리고 내리는 increment/decrement, 그리고 값을 실제로 가져오는 get이 공통의 lock을 갖고 있기 때문에 정직하게 주루룩 한줄로 서있으니 느릴 수 밖에 없는 것이지!

그럼 우리의 최종 목표는 곧 Perfect scaling을 구현하는 것이라 할 수 있겠다. 지금부터 스레드를 늘려도 작업이 병렬적으로 처리 되어서 위의 precise한 구현처럼 오히려 실행 시간이 늘어나지 않도록 개선해보자,,!

Scalable Counting

위의 그래프의 맨 밑바닥에 깔려 있는 점들, 그러니까 approximate한 구현은 대체 무슨 마법을 부렸길래 저렇게 빠르게 실행될 수 있는 것일까?

typedef struct __counter_t {
  int global; // global count
  pthread_mutex_t glock; // global lock
  int local[NUMCPUS]; // per-CPU count
  pthread_mutex_t llock[NUMCPUS]; // ... and locks
  int threshold; // update frequency
} counter_t;

// init: record threshold, init locks, init values
// of all local counts and global count
void init(counter_t *c, int threshold) {
  c->threshold = threshold;
  c->global = 0;
  
  pthread_mutex_init(&c->glock, NULL);
  
  int i;
  for (i = 0; i < NUMCPUS; i++) {
    c->local[i] = 0;
    pthread_mutex_init(&c->llock[i], NULL);
  }
}

// update: usually, just grab local lock and update
// local amount; once local count has risen ’threshold’,
// grab global lock and transfer local values to it
void update(counter_t *c, int threadID, int amt) {
  int cpu = threadID % NUMCPUS;
  
  pthread_mutex_lock(&c->llock[cpu]);
  
  c->local[cpu] += amt;
  if (c->local[cpu] >= c->threshold) {
    // transfer to global (assumes amt>0)
    pthread_mutex_lock(&c->glock);
    c->global += c->local[cpu];
    pthread_mutex_unlock(&c->glock);
    c->local[cpu] = 0;
  }
  
  pthread_mutex_unlock(&c->llock[cpu]);
}

// get: just return global amount (approximate)
int get(counter_t *c) {
  pthread_mutex_lock(&c->glock);
  int val = c->global;
  pthread_mutex_unlock(&c->glock);
  return val; // only approximate!
}

휴! 코드 참 길다. 겁먹지 말고 천천히,, 아주 천천히 뜯어보자.
일단 counter 구조체를 구성하는 각각의 멤버 변수들의 의미부터 파악하는게 좋겠다.
참고로 간결하게 문제의 핵심을 짚어보기 위해 decrement 없이 update를 통해 increment만 한다고 가정해보겠다.

int global
우리가 최종적으로 얻고자 하는 counter의 상태값 그 자체를 의미하며, 여러 스레드들이 으쌰으쌰 힘을 합쳐서 이 global에 값을 보태주는 작업을 한다.

int local[NUMCPUS]
여기서 이전의 Precise counter와 차별화된다. 이 배열의 각각의 요소는 각각의 스레드가 바로 global에다가 값을 갱신해주는게 아니라, 자기가 일단 값을 가지고 있다가 나중에 반영하기 위해 임시로 값을 저장하기 위한 임시 공간의 역할을 한다.

int threshold
그럼 언제 local[i]의 값을 global에 반영해주는가? 아까 decrement 없이 increment만 한다고 가정했는데, 이렇게 값을 나눠서 올리다보면 언젠가는 특정 임계점(threshold)를 지날 것이다.
그때!! 각각의 스레드가 쥐고 있던 값을 global에 반영해주고, 이를 0으로 초기화해서 다시 임시 공간(local[i])을 비워줄 것이다.

pthread_mutex_t glock
Global lock을 의미하며, 말 그대로 모든 스레드가 공통적으로 지켜야 할 lock을 의미한다.
이 lock은 딱 두 지점, global 값을 반영할 때와 읽어올 때 작동해 스레드간의 mutual exclusion을 보장한다.

pthread_mutex_t llock[NUMCPUS]
Local lock을 의미하며, 말 그대로 각각의 스레드가 독립적으로 가지는 lock을 의미한다.
이 lock은 딱 local[i]에 값을 갱신해줄 때 사용되는데, local[i]가 global에 값을 보태는건 local[k]와는 전혀 관심사가 겹치지 않으니까 lock을 분배해준다는게 핵심 아이디어이다!
물론 그 안에서 쥐고 있던 값이 threshold를 넘어 global에 반영해야 할 때는 global lock을 또 걸어야겠지? 이때는 local[i]와 local[k]가 같은 자원에 접근하는 거니까.

이제 슬슬 왜 위에서 approximate라고 이름 붙였는지 알 것 같지 않은가?

이전의 precise 방법에서는 각각의 스레드가 global에 매ㅐㅐㅐ번, 계ㅔㅔㅔㅔ속 값을 더하거나 빼기 때문에 먼저 들어간 스레드가 lock을 걸어버리면 뒤에서 기다리고 있는 스레드는 아무것도 못하고 기다려야 하는 병목이 발생했었는데, 여기서는 일정 주기(대충 threshold와 비슷하게. 모든 global update가 threshold를 딱 맞게 채우리라는 보장이 없으므로.)마다 값을 global에 반영하기 때문에 race condition이 발생할 가능성이 확 낮아졌다.

다만 말 그대로 approximate한 방법이기 때문에, 스레드에게 맡겨진 모든 작업들이 끝나기 전에 get을 통해 값을 읽으려고 하면 실제로 각각의 local[i]에 저장된(저장되어왔던) 값들의 합보다 작을 수 있다. threshold에 도달하기 전에 값을 조회하려고 하면 아직 local value가 global value에 반영되지 않아서 그렇다!

위의 표를 보면, L1이 먼저 threshold인 5에 도달해 global value에 값을 반영해준 다음 local value를 0으로 초기화해주었다. 그 다음으로? L4가 threshold에 도달해 global value에 반영해준 다음 local value를 0으로 초기화해주었는데, 이때 L2와 L3가 아직 global value에 반영되지 않았기 때문에 L1~L4가 가져가서 더한 값(5+2+4+5=16)에 global value(10)가 아직 미치지 못했음을 확인할 수 있다. 물론 각각의 스레드에게 주어진 작업이 모두 끝나면 최종적으로는 원하는 값에 도달할 수 있겠지?

음,, 이건 설명하다가 생각난건데, 만약 threshold에 도달하지 못한 상태에서 주어진 작업이 모두 끝나면 local에 남아 global에 반영되지 않은 threshold 미만의 잔돈(?) 같은게 남을테니까, 주어진 작업이 모두 끝나면 mutual exclusive하게 이걸 반영해줄 수 있는 아래와 비슷한 코드가 필요할 것 같다. 불필요한 작업이라면 댓글로 알려달라!

void hard_global_update(counter_t *c, int threadID) {
  int cpu = threadID % NUMCPUS;
  
  pthread_mutex_lock(&c->llock[cpu]);
  
  pthread_mutex_lock(&c->glock);
  c->global += c->local[cpu];
  pthread_mutex_unlock(&c->glock);
  
  c->local[cpu] = 0; // 깔끔하게 처리해주기 위해
  
  pthread_mutex_unlock(&c->llock[cpu]);
 }

..

함수별로 하나씩 설명하려고 했는데, 주요 개념을 멤버 변수를 설명하면서 줄줄이 다 해버리는 바람에 딱히 할 내용이 없다. 딱하나 추가적으로 눈여겨봐야할만한 점이라면,, init에서 각각의 스레드를 위한 lock을 초기화해주었다는 정도?

이 개념이 이어질 concurrent data structure를 이해하는데 아주 중요한 열쇠가 될 것이다. 병목 없이 일을 나눠서 주려면, 관심사(값을 갱신하는 등)에 대한 mutual exclusion을 분산시켜야 한다는 아이디어를 이해하는 것이 중요하다.

이 Approximate한 접근 방법의 효율성을 보여주는 그래프이다.
가로축인 S값(Sloppiness, 엉성함)이 커지면 커질수록 global에 local value를 반영하는 주기가 길어지므로 작업을 모두 수행하는데 소요되는 시간이 적음을 확인할 수 있다.

물론! 엉성하면 엉성할수록 모든 작업이 끝나기 전에 global에 접근했을 때 실제 값과의 차이는 더 많이 벌어지겠지? 사용하기 전에 반드시 이것저것 따져보자.

29.2 Concurrent Linked Lists

위의 counter 예시를 통해 하나의 값에 대해서 concurrent하게, 나아가 조금 엉성하게 값을 반영함으로써 효율적으로 scalability까지 실현하는 예제를 살펴보았다.

이제! Linked list에서 concurrency를 달성해보자! 삽입이랑 조회 연산만!

아 참고로, 조회 연산(List_Lookup)은 말 그대로 인자로 주어진 key가 해당 list에 있는지 없는지 확인하는 역할만 한다. 뒤의 Concurrent hash table에서 또 써먹으므로 기억해두자.

// basic node structure
typedef struct __node_t {
  int key;
  struct __node_t *next;
} node_t;

// basic list structure (one used per list)
typedef struct __list_t {
  node_t *head;
  pthread_mutex_t lock;
} list_t;

void List_Init(list_t *L) {
  L->head = NULL;
  pthread_mutex_init(&L->lock, NULL);
}

int List_Insert(list_t *L, int key) {
  pthread_mutex_lock(&L->lock);
  node_t *new = malloc(sizeof(node_t));
  
  if (new == NULL) {
    perror("malloc");
    pthread_mutex_unlock(&L->lock);
    return -1; // fail
  }
  
  new->key = key;
  new->next = L->head;
  L->head = new;
  
  pthread_mutex_unlock(&L->lock);
  return 0; // success
}

int List_Lookup(list_t *L, int key) {
  pthread_mutex_lock(&L->lock);
  node_t *curr = L->head;
  
  while (curr) {
      if (curr->key == key) {
        pthread_mutex_unlock(&L->lock);
        return 0; // success
    }
    curr = curr->next;
  }
  pthread_mutex_unlock(&L->lock);
  return -1; // failure
}

Concurrent counter와 마찬가지로 Global lock 하나만 쓰는 구현부터 살펴보자.
Lock을 하나만 쓰는 만큼, 간단하게 그냥 노드를 만들고 head 쪽에 삽입하는 작업과 조회하는 작업이 mutual exclusive하게 작동하도록 구현했다. 노드를 탐색하고 있는데 중간에 갑자기 새 노드가 들어오면 안되니까!

음, 본격적으로 다음 논의를 하기 전에 이 부분을 한 번 짚고 넘어가자.

  if (new == NULL) {
    perror("malloc");
    pthread_mutex_unlock(&L->lock);
    return -1; // fail
  }

일반적으로 잘 발생하지 않을 케이스라고 생각할 수도 있겠지만, 만약 메모리의 동적 할당에 실패했을 때 깜빡하고 global lock을 풀어주지 않으면 이 스레드 때문에 다른 스레드들이 끝없이 기다려야 할 것이다. 최근의 Linux 커널 패치에 관한 연구에 따르면 약 40%에 달하는 버그가 이런 유형이었다고 한다.

Insert는 리스트의 상태가 변하는 것이므로 어쩔 수 없이 코드 블록 전체를 lock/unlock으로 감쌀 수밖에 없을 것 같으니 그렇다 치고(정말 그럴까? 한 번 고민해보자!), 위의 코드의 List_Lookup, 그러니까 조회 연산 부분 구현을 살펴보면 이 코드를 짠 사람이 lock 본연의 기능과 코드의 안정성 두 마리 토끼를 잡기 위해 어떤 고민을 했는지 음미할 수 있다. 킁카킁카.

Lock을 거는 부분 자체는 삽입 연산과 동일하다. lock을 하나만 사용할 것이기 때문에, 이런 식으로 mutual exclusion을 구현하는 것은 어쩔 수 없다.

그러나! 검색에 성공하는 경우와 실패하는 경우 둘 다 값을 반환하기 직전에 global unlock을 수행하므로 위에서 언급한 실수가 발생할 여지가 확 줄어들었다고 볼 수 있다. 읽으면서 그제야 아차 싶었던 나라면 unlock을 하나 빼먹어서 위의 40%에 그대~~로 포함되었을 것 같다 ㅎ.

개선!

위의 코드가 정말 최선인걸까? 어떤 프로그램이든 일단 기본적인 요구사항을 만족했으면 그 다음으로는 성능을 꼭 챙겨 살펴봐야 한다.

void List_Init(list_t *L) {
  L->head = NULL;
  pthread_mutex_init(&L->lock, NULL);
}

void List_Insert(list_t *L, int key) {
  // synchronization not needed
  node_t *new = malloc(sizeof(node_t));
  if (new == NULL) {
    perror("malloc");
    return;
  }
  new->key = key;

  // just lock critical section
  pthread_mutex_lock(&L->lock);
  new->next = L->head;
  L->head = new;
  pthread_mutex_unlock(&L->lock);
}

int List_Lookup(list_t *L, int key) {
  int rv = -1;
  pthread_mutex_lock(&L->lock);
  
  node_t *curr = L->head;
  while (curr) {
    if (curr->key == key) {
      rv = 0;
      break;
    }
    curr = curr->next;
  }
  pthread_mutex_unlock(&L->lock);
  return rv; // now both success and failure
}

두 가지가 바뀌었는데, 첫째로 List_Insert에서 새 node를 만들어주는 부분이 critical section에서 빠졌다! Critical section이 길면 길수록 다른 스레드가 기다려야 하는 시간이 늘어난다는 의미이기 때문에, 굳이~~ 다른 스레드와 동기화되어야 할 필요가 없어 이 부분을 바깥으로 빼줌으로써 조금 더 효율적인 코드가 되었다.

둘째로 List_Lookup에서 일관성을 위해 탐색에 성공했을 경우 바로 return을 해주는게 아니라 break문을 통해 루프에서 빠져 나와 단 하나의 unlock을 통해 lock을 풀어주고 return하도록 구현을 조금 바꿨다.

도찐개찐 아니냐,, 하고 생각할 수도 있겠지만, 일관되게 lock/unlock을 함으로써 혹시 모를 실수를 미연에 방지할 수 있다는 장점이 있다. 명심하자. Concurrent와 관련된 40%의 버그가 우리의 어처구니 없는 실수로 발생해왔다!

Scaling Linked Lists

아까 Precise counter에서 정확성을 포기하는 대신 lock을 각각의 스레드에 분배해주고, 매 갱신 요청마다 race condition이 발생하게 하는 것이 아니라 그보다 큰 일정 주기마다 갱신하게 함으로써 bottle neck을 줄이는 방식(approximate counter)으로 scalibility를 실현했다.

방금 살펴본 single global lock 방식의 concurrent linked list도 마찬가지로 연산/조회 작업이 단 하나의 lock을 사용하기 때문에 bottle neck이 발생할 수 있으므로, 비슷하게 lock을 적절히 분산시켜보면 어떨까?

이러한 아이디어가 반영된 방법론으로 Hand-Over-Hand Locking(= Lock coupling)이라는게 있다. 이름에서 알 수 있듯 일단 lock을 각각의 list node에 분배해주고, list head node부터 목표 노드까지 탐색하는 과정에서 일단 뒤에 있는 node의 lock을 얻어야 현재 node의 lock을 해제할 수 있도록 하는 모습이 node들이 lock을 마치 건네주는(hand-over-hand) 모습과 비슷할 것이다.

다만! 이렇게 lock을 분산시킨다고 해서 무조건 성능이 좋아지는 것은 아니다. (그만큼 복잡해지기도 하고)
리스트의 길이가 N이라면 최악의 경우 N번의 lock/unlock이 발생할텐데, 이게 평균 실행 시간을 생각해보면 결코 무시할 수 없는 크기의 overhead이기 때문이다. 책에서는 차라리 approximate하게 일정 개수의 노드를 처리할 때마다 하나의 새로운 lock을 새로 얻게 하는 Hybrid 방식이 나을 것 같다고 평가하고 있다.

29.3 Concurrent Queues

위에서 얘기했듯 노드 하나 하나에 lock을 분산시키는건 그다지 좋은 선택이 아니다. 무조건 쓰지 말라는게 아니라, 일반적으로 불필요하거나 과도한 overhead가 발생하므로 최대한 적게 사용하는 편이 좋다는게 더 정확한 표현일 것 같다.

이어서 큐(Queue)를 한 번 생각해보자. 큐는 FIFO(First In, First Out) 규칙에 의해 노드의 삽입과 삭제(정확히는 pop)가 발생하는 자료구조로, 이를 linked list로 구현하려면 구조체에 head와 tail을 가리키기 위한 포인터가 있는게 효율적이다.

큐의 기본 연산을 간편히 구현하기 위해 head에서 값을 뺀다 치면(dequeue=pop), 값을 넣어 주는 것(enqueue=push)은 그 반대인 tail 쪽에서 수행되어야 하는데, 매 enque마다 head부터 맨 마지막 node까지 싹 탐색하는건 비효율적이기 때문에 마지막 node를 가리키는 포인터도 함께 저장한다고 생각하면 되겠다. (이게 이해가 안되면 OS가 아니라 자료 구조를 먼저 공부해야 한다 ㅠ)

typedef struct __node_t {
  int value;
  struct __node_t *next;
} node_t;

typedef struct __queue_t {
  node_t *head;
  node_t *tail;
  pthread_mutex_t head_lock, tail_lock;
} queue_t;

void Queue_Init(queue_t *q) {
  node_t *tmp = malloc(sizeof(node_t));
  tmp->next = NULL;
  q->head = q->tail = tmp;
  pthread_mutex_init(&q->head_lock, NULL);
  pthread_mutex_init(&q->tail_lock, NULL);
}

void Queue_Enqueue(queue_t *q, int value) {
  node_t *tmp = malloc(sizeof(node_t));
  assert(tmp != NULL);
  tmp->value = value;
  tmp->next = NULL;

  pthread_mutex_lock(&q->tail_lock);
  q->tail->next = tmp;
  q->tail = tmp;
  pthread_mutex_unlock(&q->tail_lock);
}

int Queue_Dequeue(queue_t *q, int *value) {
  pthread_mutex_lock(&q->head_lock);
  node_t *tmp = q->head;
  node_t *new_head = tmp->next;
  if (new_head == NULL) {
    pthread_mutex_unlock(&q->head_lock);
    return -1; // queue was empty
  }
  *value = new_head->value;
  q->head = new_head;
  pthread_mutex_unlock(&q->head_lock);
  free(tmp);
  return 0;
}

책에 나와 있는 구현체는 위와 같이 생겼다!

Queue_Init 부분을 보면 알겠지만 head와 tail에만 lock을 분산시켰음을 알 수 있다. 실은 이 concurrent queue에서 이 부분을 제외하면 나머지는 일반적인 큐와 거의 비슷하다!

이 head_lock과 tail_lock이 실질적으로 사용되는 함수가 무엇인지 잘 살펴보면 나머지 코드도 쉽게 이해할 수 있다. Enqueue 작업은 tail에서만 발생하니까 그 이외의 노드에 대해서는 동시에 접근할 일이 없으므로 tail_lock만을 사용하고, dequeue 작업은 head에서만 발생하니까 그 이외의 노드에 대해서는 마찬가지로 동시에 접근할 일이 없으므로 head_lock만을 사용했다. (설명을 일부 빼놓았으니까 그냥 끄덕끄덕 하고 넘어가지 말고 잠깐 생각해보고 넘기자!!!)

또,, 내가 봐왔던 일반적인 큐의 구현과 다르게 되어 있는 부분이 있어서 기록을 남겨놓겠다.

void Queue_Init(queue_t *q) {
  node_t *tmp = malloc(sizeof(node_t));
  tmp->next = NULL;
  q->head = q->tail = tmp;
  pthread_mutex_init(&q->head_lock, NULL);
  pthread_mutex_init(&q->tail_lock, NULL);
}

자세히 보면 큐를 초기화 할 때 임의의 node를 하나 넣어 놓고 head와 tail이 이 노드를 가리키도록 하고 있는데, 이 node는 실질적으로 데이터를 가지고 있는 node가 아니라 큐가 비어 있음을 확인하기 위한 dummy node로써 기능한다.

그래서,, Enqueue 작업이야 더 설명할 것도 없이 간단해보이지만 dummy node 때문에 dequeue가 살짝 복잡하게 와닿을 수도 있을 것 같아서 부연 설명을 조금 덧붙인다.

  1. Dequeue는 head node에서 발생하므로 head에 대한 lock을 일단 걸어주고,
  2. 큐의 맨 앞에 있는 dummy node(tmp)와 그 뒤에 있는 node(new_head)까지 읽어 new_head가 NULL이면 큐가 비어 있음을 의미하므로 이에 맞는 처리를 해주면 된다. (바로 lock을 풀고 -1을 반환)
  3. 만약 그렇지 않고 new_head가 NULL이 아니라면? 그 큐는 비어 있는 큐가 아니므로 dequeue가 가능한 것이다.
  4. 이 부분이 살짝 논리가 축약되어 있는데, 일단 맨 앞에 있던 값을 int pointer인 value가 가리키는 곳에 옮겨 써준 다음 dummy node를 한 칸 뒤로 옮겨준 뒤 기존의 dummy node였던 tmp가 차지하던 공간을 해제해주고 있다. (unlock도 잊지 말고!)

4번 단계가 쪼끔 복잡하다고 생각할 수 있는데, 어차피 dequeue 과정에서 큐의 맨 앞 노드를 아예 없는 것처럼 취급(new_head가 실질적인 맨 앞 노드니까!)하므로 그냥 '지금부터 이거 dummy node로 쓸거야~~'하고 표시만 해놔도 상관 없기 때문에 저렇게 구현한 것이라 생각하면 된다. 이해가 잘 안되면 직접 큐에 노드가 0개, 1개, 2개 이상 들어 있는 경우에 어떻게 dequeue 함수가 작동하는지 그려보자!

결론적으로 이 Concurrent queue에서의 시사점은 Global lock을 적절한 수준에서 분산시켰다는 것이다. 어쨌든 이 concurrent queue의 기본 골격은 linked list인데, 어차피 enqueue/dequeue 연산이 각각 큐의 tail/head에서만 발생하며 서로 영향을 주지 않고 독립적으로 작동할 수 있으므로(일부러 enqueue에서 Dummy node의 의의는 따로 안적어두었다 ㅎ) lock도 딱 이 두 부분에만 각각 부여함으로써 global lock만 썼으면 모든 스레드가 한 줄로 기다려야 했던 것을 두 줄로 나눠주었다는 점, 깊이 생각해보고 넘어가자!

29.4 Concurrent Hash Table

마지막으로! Concurrent한 hash table은 어떻게 구현할 수 있을지 고민해볼 차례이다. 대신 핵심 아이디어만 살펴보기 위해 table의 크기를 동적으로 조정할 수 있는 기능은 따로 생각해보지 않고, 딱 고정된 크기의 구현만을 생각해볼 것이다. 이것만 해도 머리 아플걸?

혹시, 호오오옥시라도 Hash table이 무엇인지 잘 모르겠다면 미리 관련 주제들을 공부해보고 오면 좋겠다.

#define BUCKETS (101)

typedef struct __hash_t {
	list_t lists[BUCKETS];
} hash_t;

void Hash_Init(hash_t *H) {
  int i;
  for (i = 0; i < BUCKETS; i++)
 	 List_Init(&H->lists[i]);
}

int Hash_Insert(hash_t *H, int key) {
	return List_Insert(&H->lists[key % BUCKETS], key);
}

int Hash_Lookup(hash_t *H, int key) {
	return List_Lookup(&H->lists[key % BUCKETS], key);
}

일단 concurrent한 부분을 빼고 생각해보자. 이 hash table을 통해 우리가 원하는 결과는 이 자료 구조에 이전에 특정 값을 넣었었는지, 그렇지 않은지를 빠른 시간 안에 알아내는 것이다.

그전에! 기본적으로 hash table에선 자료구조 특성상 충돌이 항상 발생할 수 있는데, 현재 hash table의 크기(BUCKETS)가 101이며 각각의 값이 들어갈 cell의 위치를 정하는데 식 key % BUCKETS를 사용하고 있으므로 예를 들자면 값 10, 111, 212, ... , 10 + (101 * N)은 모두 10번 cell에 저장될 것이다.

근데 같은 cell에 값을 추가해줄 때마다 기존에 저장된 값이 저장되었다는 정보를 잃으면 안되니까, 충돌이 발생하면(선택한 cell에 이미 어떤 값이 들어있다면) 그걸 지우는게 아니라 그 뒤에 이번에 넣을 값을 추가해주는 식으로 꼬리에 꼬리를 물고 정보를 보존해야 한다.

뭔가 떠오르는게 있지 않은가?! 이걸 일반화하면 각각의 cell이 해당 위치에 저장될 데이터들을 linked list로 저장하는 것으로 hash table을 구현할 수 있다. 이젠 하나의 값이 [있거나/없는] 선택지가 아니라 [없거나/1개 이상의 값이 있는] 선택지로 확장되었으므로 지금부터는 cell이 아니라 bucket이라고 부르겠다.

그럼 우리가 원하는 작업, 그러니까 특정 값(key)이 이 hash table에 있는지 없는지 확인하는 Hash_Lookup을 한다는 것은 곧 주어진 key로 bucket을 O(1)의 시간 복잡도로 한 번에 알아낸 다음, linked list로 구현된 bucket의 맨 앞부터 맨 뒤까지 이 값이 있는지 없는지 탐색하는 작업(List_Lookup)일 것이다.

...

오케! 그럼 이제 여기에 concurrency를 얹어보자.
사실 얹고 자시고 할 것 없이 우리가 지금 bucket이라고 부르는 linked list가 위에서 정의한 concurrent linked list라고 하면 끝이다!

이게 무슨 의미를 가지냐면, 어차피 각각의 bucket에 접근하기 위해 식 key % BUCKET을 사용하므로 각각의 bucket 끼리는 서로 간섭할 여지가 없으므로 각각의 bucket들이 같은 lock을 사용할 필요가 없다는 것이다.

좀 더 딱딱하게 말하자면, 이 concurrent hash table은 scalable하다. 왜냐? 여러 CPU가 있고 이 모든 CPU들이 hash table에 접근하려 할 때 CPU에 올라가 있는 실행 흐름이 같은 bucket에 접근하려 하는 것만 아니라면 무조건 병렬적으로 실행할 수 있기 때문이다! 이걸 Simple concurrent list로 구현했다면 같은 상황에서 무조건 병목이 발생했을텐데, 흥미롭지 않은가?

마무리

이렇게까지 뜯어봤는데 흥미롭지 않다면 counter -> linked list -> queue -> hash table 순서대로 concurrency를 구현하기 위해 어떤 노력들을 했는지 다시 곱씹어봤으면 좋겠다.

  1. counter
    관심의 대상이 되는 공통의 자원이 단 하나의 정수값 밖에 없었으므로 관리할 lock도 하나 밖에 없었다. (approximation을 통한 성능 향상은 다른 concurrent data structure에선 다루지 않았다.)

  2. Linked List
    이번엔 관심의 대상이 되는 값이 하나가 아니라 여러 값들(node)인데, 이론상 각각의 node가 서로 간섭하지 않으므로 lock을 node에 하나씩 달아주면 성능이 향상될 것 같았는데 lock/unlock에 발생하는 overhead를 무시할 수 없으므로 global lock 하나를 쓰는게 오히려 낫다고 결론지었다.

  3. Queue
    기본적인 골격은 linked list이지만, enqueue/dequeue가 자료 구조의 상태에 영향을 주는 유이한 연산이며 dummy node의 존재로 두 연산이 서로 영향을 끼치지 않으므로 global lock을 head/tail lock으로 나누어 한 줄로 대기하던 병목을 두 줄로 나누어 성능 향상을 달성했다!

  4. Hash Table
    여기선 자료구조 자체가 각각의 bucket들이 서로 영향을 끼칠 수 없도록 설계되어 있기 때문에, lock을 각각의 bucket에 나누어 줌으로써 동시에 실행되는 연산들이 race condition에 놓일 확률을 대폭 낮추었다. 대략 bucket의 갯수만큼 정도?!

휴! 그래도 복잡한 thread trace보다 더 추상화가 쉬워서 잘 와닿기도 하고, 어디 쓰일지 금방금방 떠올라서 concurrency 관련 주제 중에선 가장 재밌게 공부했던 것 같다.

이어서 하나 더 하고 잔다! 화이팅!

profile
급식
뭐 먹고 살지.
이전 포스트

[OS] 28. Locks

다음 포스트

[OS] 30. Condition Variables

0개의 댓글