[OS] Lock-based Concurrent Data Structure

자료구조에 lock을 더하면, 여러 스레드가 concurrent하게 해당 자료구조 관련 operation을 할 수 있게 된다

그럼 어떻게 lock을 걸 것인가 ?

concurrent counter

여러 스레드가 counter에 접근해서 1을 증가시키거나 감소시킨다고 해보자

제일 먼저 생각할 수 있는 건, 모든 operation 전, 후에 lock을 거는 것이다. 하지만 당연하게도 모든 operation마다 lock을 걸면 시간이 어마무시해지겠죵?!
그니깐 우리 다른 방법을 생각해 봅시다

Sloppy Counter

우리가 지금 하려는 건 멀티 스레드 counter increment 자나용?!
그니깐 cpu 별로 logical counter를 둡시다. 그리고 각 스레드는 자기의 logical cpu counter 값을 increment 시키는 거!! 그리고, 전체 counter값인 global counter가 있는데 global counter가 주기적으로 logical counters를 가져와서 자기의 global counter 값에 더해주면, 가끔씩 오차가 발생해도 꽤 정확한 카운터가 되겠쮸?

그럼 얼마나 자주 global counter를 업데이트 해줄것인가!
그건 slopiness 값인 s에 의해 결정되는데,

• s가 작을 수록 - 정확하지만, lock operation을 자주 해야하므로 성능 저하
• s가 클수록 - counter 값은 차이가 날 수 있지만 보다 scalable함

Concurrent Linked List

linked list도 counter처럼, insert 앞 뒤, find 앞, 뒤에 lock을 걸어주고 해제하는 방법을 제일 먼저 생각할 수 있음

근데 실험적으로 이렇게 하면 에러가 꽤 생긴다는 게 밝혀져서 이렇게 하지 말고, "진짜 critical section" 앞 뒤로만 lock을 걸기로 함

list insert

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

list find

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

scailing Linked List

Linked List를 scaling하는 방법으로는 hand-over-hand locking(lock coupling)이 있다. list의 node마다 lock을 줘서 list를 순회할 때 다음 노드의 lock을 잡은 다음 현재 노드의 lock을 해제해주는 방법이다. 다음 노드의 lock을 잡고 현재 노드의 lock을 해제하는 게 손 위에 손을 잡는 것 같나보다..........이런 개 시발..........

이렇게 하면 list operation의 concurrency를 높일 수 있긴 한데, 모든 노드의 lock을 해제하고 잡는다고 생각해봐라.... 진짜 cost 개 쩔어서 실제로는 잘 안 쓰인다.

Concurrent Queue

queue는 맨 뒤에 element를 추가하고, 맨 앞의 element를 pop 시키는 자료구조이다.

따라서 insert할 때 tail에 lock걸고, pop할 때 head에 lock거는 게 직관적으로 와 닿을 것이다.

void Queue_Enqueue(queue_t *q, int value){
  node_t *tmp = malloc(sizeof(ndoe_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->head_lock);
  
  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;
}

concurrent hash table

hash table은 hash bucket을 list로 maintain하고 list에 대한 lock은 위에서 이미 정의해줬기에 hash table에선 따로 lock 안 걸어줘도 됨