OSTEP 29 - Locked Data Structures

자료 구조에 락을 추가하여 쓰레드가 사용할 수 있도록 만들면, 그 구조는 thread safe하다고 할 수 있다.

핵심 질문: 자료 구조에 락을 추가하는 방법

어떤 방식으로 락을 추가해야 그 자료 구조가 정확하게 동작하게 만들 수 있을까?
더 나아가, 자료 구조에 락을 추가하여 여러 쓰레드가 병행성을 지원하면서 동시에 고성능을 얻기 위해 무엇을 해야 할까?

1. 병행 카운터

간단한 자료구조인 카운터를 어떻게 thread safe하게 할까?

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

간단하지만 확장성 없음

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

간단하고 가장 보편적인 병행 자료구조 디자인 패턴을 따른다. 자료구조를 조작할 때, 락을 획득하고 그 호출문이 리턴할 때 락이 해제되도록 했다.

이 방식은 Monitor를 사용하여 만든 자료 구조와 유사하다. 모니터 기법은 객체에 대한 메소드를 호출하고 리턴할 때 자동적으로 락을 획득하고 해제한다.

제대로 동작하지만, 성능이 문제다. 각 쓰레드가 특정 횟수만큼 공유 카운터를 증가시키는 벤치마크를 실행하자.

9-3bdd-4e38-8ad4-4c3409ae0fbc:image.png)

더 많은 CPU가 동작할수록 단위 시간당 총 수행량이 늘어날 것으로 기대하지만, 단일 쓰레드로 카운터를 백만 번 갱신하는 데 대략 0.03초가 걸렸다. 두 개의 쓰레드로 카운트 값을 백만 번 갱신하는 데 약 5초 이상이 걸렸다.

이상적으로는 하나의 쓰레드가 하나의 CPU에서 작업을 끝내는 것처럼 멀티프로세서에서 실행되는 쓰레드들도 빠르게 작업을 처리하고 싶을 것이다(완벽한 확장성: perfect scaling).

확장성 있는 카운팅

확장 가능한 카운터가 으면 Linux의 몇몇 작은 멀티코어 기기에서 심각한 확장성 문제를 겪을 수 있다고 한다. 이를 위해 개선된 방법인 엉성한 카운터(sloppy counter)가 있다.

엉성한 카운터는 하나의 논리적 카운터로 표현되는데, CPU 코어마다 존재하는 하나의 물리적인 지역 카운터와 하나의 전역 카운터로 구성되어 있다.

엉성한 카운터의 기본 개념은 다음과 같다. 쓰레드는 지역 카운터를 증가시킨다. 이 지역 카운터는 지역 락에 의해 보호된다. CPU들에 분산되어 있는 쓰레드들은 지역 카운터를 경쟁 이 갱신할 수 있다. 확장성이 있다고 볼 수 있다.

지역 카운터의 값은 주기적으로 전역 카운터로 전달되는데, 이때 전역 락을 사용하여 지역 카운터의 값을 전역 카운터의 값에 더하고, 그 지역 카운터의 값은 0으로 초기화한다.

S라는 값을 두어, 지역 카운터가 S가 넘어가면 글로벌 카운터를 업데이트 한다.

S의 값이 낮다면 성능이 낮은 대신 전역 카운터의 값이 매우 정확해진다. S의 값이 매우 크다면 성능은 탁월하겠지만 전역 카운터의 값은 CPU의 개수와 S의 곱만큼 뒤처지게 된다.

typedef struct __counter_t {
	int global;
	pthread_mutex_t glock;
	int local[NUMCPUS];
	pthread_mutex_t llock[NUMCPUS]; 
	int threshold;
} counter_t;

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

void update(counter_t *c, int threadID, int amt) {
	pthread_mutex_lock(&c−>llock[threadID]);
	c−>local[threadID] += amt; 
	if (c−>local[threadID] >= c−>threshold) {
		pthread_mutex_lock(&c−>glock);
		c−>global += c−>local[threadID];
		pthread_mutex_unlock(&c−>glock);
		c−>local[threadID] = 0;
	}
	pthread_mutex_unlock(&c−>llock[threadID]);
}

int get(counter_t *c) {
	pthread_mutex_lock(&c−>glock);
	int val = c−>global;
	pthread_mutex_unlock(&c−>glock);
	return val;
}

2. 병행 연결 리스트

연결 리스트에서 병행 삽입 연산을 thread safe하게 해보자

삽입 연산을 시작하기 전에 락을 획득하고 리턴 직전에 해제한다. 매우 드문 경우지만, malloc()이 실패할 경우에 미묘한 문제가 생길 수 있다. 그런 경우가 발생한다면 실패를 처리하기 전에 락을 해제해야 한다.

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

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;
	}
	new−>key = key;
	new−>next = L−>head;
	L−>head = new;
	pthread_mutex_unlock(&L−>lock);
	return 0;
}

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;
		}
		curr = curr−>next;
	}
	pthread_mutex_unlock(&L−>lock);
	return −1;
}

삽입 연산이 병행하여 진행되는 상황에서 실패를 하더라도 락 해제를 호출하지 않으면서 삽입과 검색이 올바르게 동작하도록 수정할 수 있을까? 삽입 코드에서 임계 영역을 처리하는 부분만 락으로 감싸도록 코드 순서를 변경하고, 검색 코드의 종료는 검색과 삽입 모두 동일한 코드 패스를 사용토록 할 수 있다.

이 방법이 동작하는 이유는 코드 일부는 사실 락이 필요 없기 때문이다.

malloc() 자체가 thread safe하다면, 쓰레드는 언제든지 경쟁 조건과 다른 병행성 관련 버그를 걱정하지 않으면서 검색할 수 있다. 공유 리스트 갱신 때에만 락을 획득하면 된다.

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

void List_Insert(list_t *L, int key) {
	// 동기화를 할 필요 없음
	node_t *new = malloc(sizeof(node_t));
	
	if (new == NULL) {
		perror(“malloc ”);
		return;
	}
	new−>key = key;

	// 임계 영역만 락으로 보호
	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; // 성공 혹은 실패
}

확장성 있는 연결 리스트

병행이 가능한 연결 리스트를 갖게 되지만 확장성이 좋지 않다. 병행성을 개선하는 방법 중 하나로 hand-over-hand locking(또는 lock coupling) 이라는 기법이 있다.

개념은 단순하다. 전체 리스트에 하나의 락이 있는 것이 아니라 개별 노드마다 락을 추가하는 것이다. 리스트를 순회할 때 다음 노드의 락을 먼저 획득하고 지금 노드의 락을 해제하도록 한다.

개념적으로는, 리스트 연산에 병행성이 높아지지만, 노드를 순회할때마다 락 획득과 해제가 필요하니 속도 개선을 기대할 수는 없다.

3. 병행 큐

큰 락을 사용하는 것이 병행 자료 구조를 만들기에 표준이다. 근데, 큐에서는 이 방법을 사용하지 않을 것이다.

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 headLock;
	pthread_mutex_t tailLock;
} 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−>headLock, NULL);
	pthread_mutex_init(&q−>tailLock, 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−>tailLock);
	q−>tail−>next = tmp;
	q−>tail = tmp;
	pthread_mutex_unlock(&q−>tailLock);
}

int Queue_Dequeue(queue_t *q, int *value) {
	pthread_mutex_lock(&q−>headLock);
	node_t *tmp = q−>head;
	node_t *newHead = tmp−>next;
	if (newHead == NULL) {
		pthread_mutex_unlock(&q−>headLock);
		return −1;
	}
	*value = newHead−>value;
	q−>head = newHead;
	pthread_mutex_unlock(&q−>headLock);
	free(tmp);
	return 0;
}

두 개의 락이 있는데, 하나는 큐의 헤드에, 다른 하나는 테일에 사용되는 것을 알 수 있다. 이 두 개 락의 목적은 큐에 삽입과 추출 연산에 병행성을 부여하는 것이다. 일반적인 경우에는 삽입 루틴이 테일 락을 접근하고 추출
연산이 헤드 락만을 다룬다.

큐는 멀티 쓰레드 프로그램에서 자주 사용된다. 멀티 쓰레드 프로그램에서 사용하기 위해서는 큐가 비거나 가득 찬 경우, 쓰레드가 대기하도록 하는 기능이 필요하다. 이를 위해 사용하는 것이 그 유명한 조건 변수(condition variable) 이다.

4. 병행 해시 테이블

이전에 학습한 병행 리스트를 사용하여 구현하였으며 잘 동작한다. 전체 자료 구조에 하나의 락을 사용한 것이 아니라 해시 버켓 (리스트로 구현되어 있음) 마다 락을 사용하여서 성능이 우수하다.

#define BUCKETS ()

typedef struct __hash_t {
	list_t lists[BUCKETS];
} hash_t;
 
void Hash_Init(hash_t *H) {
	int i;
	for (i = ; i < BUCKETS; i++) {
		List_Init(&H−>lists[i]);
	}
}

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

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