[ OS ] Lock-based Concurrent Data Structures

1. Counters

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; // 리컨은 밖에서
}

성능은 별로다. Sloppy counter 사용하면 병렬성 높힐 수 있다.

 

1.1 Sloppy counter

 

대충하는 counter 이다. 이는 global counter를 매번 증가시키지 않고 각 local counter를 각각 만들어 이를 증가 시키다가 일정 수준에 달하면 그 때 global counter를 증가시키는 것이다. 이 때 local counter은 다시 0으로 재성정해준다. 

 

typedef struct __counter_t {
	int global; 
	pthread_mutex_t glock; // global를 위한 mutex lock
	int local[NUMCPUS];  //cpu 개수 
	pthread_mutex_t llock[NUMCPUS]; // local 위한 mutex lock 배열
	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) {
	int cpu = threadID % NUMCPUS;
	pthread_mutex_lock(&c->llock[cpu]); // local lock
	c->local[cpu] += amt; // assumes amt > 0
	if (c->local[cpu] >= c->threshold) { //한계에 도달하면
		pthread_mutex_lock(&c->glock);
		c->global += c->local[cpu];   // global 에 증가
		pthread_mutex_unlock(&c->glock);
		c->local[cpu] = 0;  // 다시 0으로 세팅
	}
	pthread_mutex_unlock(&c->llock[cpu]);
}

int get(counter_t *c) {
	pthread_mutex_lock(&c->glock);
	int val = c->global;
	pthread_mutex_unlock(&c->glock);
	return val; // 반영 덜 됏을 것~!
}

 

2. Linked lists

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; // fail
	}   
	new->key = key;
    // 리스트 건드는건 이 두 줄 뿐
    pthread_mutex_lock(&L->lock);
	new->next = L->head;
	L->head = new;
	pthread_mutex_unlock(&L->lock);
	return 0; // success
}

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) {
			//pthread_mutex_unlock(&L->lock); return;  // 여기서 하지말고 밖에서
			rv 0; // success
            break;
		}
		curr = curr->next;
	}
	pthread_mutex_unlock(&L->lock);
	return rv; 
}

3. Queues

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; // 디큐를 위한 lock
	pthread_mutex_t tailLock;
} queue_t;

void Queue_Init(queue_t *q) {
	node_t *tmp = malloc(sizeof(node_t)); // dummy node, 인튜 디큐가 같은것을 가르키는거 방지
	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;
}

4. Hash tables

// 리스트 활용

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