Concurrent Counters
다음은 가장 간단한 counter 구조체이다.
- A Counter Without Locks
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;
}- A Counter With Locks
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으로 인해 bottleneck 현상이 발생한다.
아래 그림은 한 스레드가 count에 100만 번 접근할 때, 스레드를 1개부터 4개까지 늘려가면서 시간을 측정한 그래프이다.
Scalable Counting
- scalable(확장성): Core가 1개에서 4개로 늘어나면 4배 빨라질 수 있는가?
확장성을 고려해서 approximate하게 count 하는 방법이다.
최종 값은 같지만 실행 중에 값을 확인하면 근사치를 보여준다.
- Sloppy Counter Implementation (Approximate )
typedef struct __counter_t {
int global; // global count
pthread_mutex_t glock; // global lock
int local[NUMCPUS]; // local count (per cpu)
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 by ’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; // assumes amt > 0
if (c->local[cpu] >= c->threshold) { // transfer to global
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 (which may not be perfect)
int get(counter_t *c) {
pthread_mutex_lock(&c->glock);
int val = c->global;
pthread_mutex_unlock(&c->glock);
return val; // only approximate!
}local lock을 만들어서 자신의 값이 S(Sloppy)에 도달하면 global counter를 update 한다.
- Example: Tracing the Sloppy Counters
네 개의 스레드가 있을 때 각자 local lock을 증가시킨다. 그러다가 미리 정한 값 S(sloppy)가 5가 되면 global 카운터에 반영한다.
이후 local lock을 다시 0으로 만든다.
- Performance of Traditional(Perfect) vs. Sloppy Counters
Approximate는 아주 좋은 성능을 보인다. (S=1024인 경우이다.)
Perfect는 bottleneck 현상으로 느리다.
- Scaling Sloppy Counters
S가 작으면 확장성이 사라지고, S가 크면 global 값을 근사하기 힘들어진다.
S=1이면 근사 없이 perfect 한 case이다.
Concurrent Linked Lists
linked list를 이용하는 방법이다.
- concurrent Linked List
// 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
}그런데 여기서 critical section인 insert 하는 부분만을 lock으로 감쌀 수는 없을까?
Scaling Linked Lists (hand-over-hand locking)
노드 전체에 한 lock을 쓰는 것이 아니라 각 node마다 lock을 준다.
- Concurrent Linked List: Rewritten
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
}new->next = L->head; L->haed = new; 두 줄만 lock으로 감싸 주었다. Lookup도 수정함.
리스트 전체를 공유하도록 구현했지만 lock 하나로 연결 리스트를 관리하기 때문에 bottleneck이 걸리면 성능이 저하되고, 확장성에 문제가 생길 수 있다. 따라서 lock을 더 분산해보자.
lock이 여러 개로 늘어나면 성능이 무조건 좋아지나?
→ 오히려 복잡해져서 오류가 더 많이 생길 수도 있음.
또한 lock이 늘어나는 것도 비용이 든다.
Concurrent Queues
- Michael and Scott Concurrent Queue
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의 next)가 tmp를 가리키게함.
q->tail = tmp; // q->tail이 마지막 노드를 가리키게함
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; // queue was empty
}
*value = newHead->value;
q->head = newHead;
pthread_mutex_unlock(&q->headLock);
free(tmp);
return 0;
}2개의 lock을 사용하고 dummy를 추가했다.
head와 tail을 가리키는 lock을 각각 하나씩 주었는데, insert는 tail에서, delete는 head에서 한다.
넣고 빼는 것을 분리시켜서 race condition이 일어나지 않게 했다.(insert끼리 경쟁하고 delete끼리 경쟁) 대신 가득 찼는데 Enqueue 하거나, 비어 있을 때 Dequeue를 하면 기다려야 한다.
Concurrent Hash Table
lock이 너무 많이 만들어서 분산해도 너무 적어도 안 좋다.
- A Concurrent 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) {
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);
}key % BUCKETS으로 나눈다.
만약 우연히 key가 한 lock으로 몰리면 bottleneck 발생.
- Scaling Hash Tables
맨 위는 큐(인큐만 반복), 맨 아래가 hash table이다.
Uploaded by Notion2Tistory v1.1.0